diff options
Diffstat (limited to 'src/_posts/2021-03-01-conditionals-in-ginger.md')
| -rw-r--r-- | src/_posts/2021-03-01-conditionals-in-ginger.md | 195 |
1 files changed, 195 insertions, 0 deletions
diff --git a/src/_posts/2021-03-01-conditionals-in-ginger.md b/src/_posts/2021-03-01-conditionals-in-ginger.md new file mode 100644 index 0000000..a8c6e44 --- /dev/null +++ b/src/_posts/2021-03-01-conditionals-in-ginger.md @@ -0,0 +1,195 @@ +--- +title: >- + Conditionals in Ginger +description: >- + Some different options for how "if" statements could work. +series: ginger +tags: tech +--- + +In the [last ginger post][last] I covered a broad overview of how I envisioned +ginger would work as a language, but there were two areas where I felt there was +some uncertainty: conditionals and loops. In this post I will be focusing on +conditionals, and going over a couple of options for how they could work. + +[last]: {% post_url 2021-01-09-ginger %} + +## Preface + +By "conditional" I'm referring to what programmers generally know as the "if" +statement; some mechanism by which code can do one thing or another based on +circumstances at runtime. Without some form of a conditional a programming +language is not Turing-complete and can't be used for anything interesting. + +Given that it's uncommon to have a loop without some kind of a conditional +inside of it (usually to exit the loop), but it's quite common to have a +conditional with no loop in sight, it makes more sense to cover conditionals +before loops. Whatever decision is reached regarding conditionals will impact +how loops work, but not necessarily the other way around. + +For the duration of this post I will be attempting to construct a simple +operation which takes two integers as arguments. If the first is less than +the second then the operation returns the addition of the two, otherwise the +operation returns the second subtracted from the first. In `go` this operation +would look like: + +```go +func op(a, b int) int { + if a < b { + return a + b + } + return b - a +} +``` + +## Pattern 1: Branches As Inputs + +The pattern I'll lay out here is simultaneously the first pattern which came to +me when trying to figure this problem out, the pattern which is most like +existing mainstream programming languages, and (in my opinion) the worst pattern +of the bunch. Here is what it looks like: + +``` + in -lt-> } -if-> out + } + in -add-> } + } +in -1-> } } +in -0-> } -sub-> } + +``` + +The idea here is that the operation `if` could take a 3-tuple whose elements +are, respectively: a boolean, and two other edges which won't be evaluated until +`if` is evaluated. If the boolean is true then `if` outputs the output of the +first edge (the second element in the tuple), and otherwise it will output the +value of the second edge. + +This idea doesn't work for a couple reasons. The biggest is that, if there were +multiple levels of `if` statements, the structure of the graph grows out +_leftward_, whereas the flow of data is rightwards. For someone reading the code +to know what `if` will produce in either case they must first backtrack through +the graph, find the origin of that branch, then track that leftward once again +to the `if`. + +The other reason this doesn't work is because it doesn't jive with any pattern +for loops I've come up with. This isn't evident from this particular example, +but consider what this would look like if either branch of the `if` needed to +loop back to a previous point in the codepath. If that's a difficult or +confusing task for you, you're not alone. + +## Pattern 2: Pattern Matching + +There's quite a few languages with pattern matching, and even one which I know +of (erlang) where pattern matching is the primary form of conditionals, and the +more common `if` statement is just some syntactic sugar on top of the pattern +matching. + +I've considered pattern matching for ginger. It might look something like: + +{% raw %} +``` + in -> } -switch-> } -> {{{A, B}, _}, ({A,B}-lt->out)} -0-> } -add-> out +in -1-> } -> } } -1-> } -sub-> out +in -0-> } +``` +{% endraw %} + +The `switch` operation posits that a node can have multiple output edges. In a +graph this is fine, but it's worth noting. Graphs tend to be implemented such +that edges to and from a node are unordered, but in ginger it seems unlikely +that that will be the case. + +The last output edge from the switch is the easiest to explain: it outputs the +input value to `switch` when no other branches are able to be taken. But the +input to `switch` is a bit complex in this example: It's a 2-tuple whose first +element is `in`, and whose second element is `in` but with reversed elements. +In the last output edge we immediately pipe into a `1` operation to retrieve +that second element and call `sub` on that, since that's the required behavior +of the example. + +All other branches (in this switch there is only one, the first branch) output +to a value. The form of this value is a tuple (denoted by enclosed curly braces +here) of two values. The first value is the pattern itself, and the second is an +optional predicate. The pattern in this example will match a 2-tuple, ignoring +the second element in that tuple. The first element will itself be matched +against a 2-tuple, and assign each element to the variables `A` and `B`, +respectively. The second element in the tuple, the predicate, is a sub-graph +which returns a boolean, and can be used for further specificity which can't be +covered by the pattern matching (in this case, comparing the two values to each +other). + +The output from any of `switch`'s branches is the same as its input value, the +only question is which branch is taken. This means that there's no backtracking +when reading a program using this pattern; no matter where you're looking you +will only have to keep reading rightward to come to an `out`. + +There's a few drawbacks with this approach. The first is that it's not actually +very easy to read. While pattern matching can be a really nice feature in +languages that design around it, I've never seen it used in a LISP-style +language where the syntax denotes actual datastructures, and I feel that in such +a context it's a bit unwieldy. I could be wrong. + +The second drawback is that pattern matching is not simple to implement, and I'm +not even sure what it would look like in a language where graphs are the primary +datastructure. In the above example we're only matching into a tuple, but how +would you format the pattern for a multi-node, multi-edge graph? Perhaps it's +possible. But given that any such system could be implemented as a macro on top +of normal `if` statements, rather than doing it the other way around, it seems +better to start with the simpler option. + +(I haven't talked about it yet, but I'd like for ginger to be portable to +multiple backends (i.e. different processor architectures, vms, etc). If the +builtins of the language are complex, then doing this will be a difficult task, +whereas if I'm conscious of that goal during design I think it can be made to be +very simple. In that light I'd prefer to not require pattern matching to be a +builtin.) + +The third drawback is that the input to the `switch` requires careful ordering, +especially in cases like this one where a different value is needed depending on +which branch is taken. I don't consider this to be a huge drawback, as +encourages good data design and is a common consideration in other functional +languages. + +## Pattern 3: Branches As Outputs + +Taking a cue from the pattern matching example, we can go back to `if` and take +advantage of multiple output edges being a possibility: + +``` + in -> } -> } -if-> } -0-> } -add-> out +in -1-> } -> } } } -1-> } -sub-> out +in -0-> } } + } + in -lt-> } +``` + +It's not perfect, but I'd say this is the nicest of the three options so far. +`if` is an operation which takes a 2-tuple. The second element of the tuple is a +boolean, if the boolean is true then `if` passes the first element of its tuple +to the first branch, otherwise it passes it to the second. In this way `if` +becomes kind of like a fork in a train track: it accepts some payload (the first +element of its input tuple) and depending on conditions (the second element) it +directs the payload one way or the other. + +This pattern retains the benefits of the pattern matching example, where one +never needs to backtrack in order to understand what is about to happen next, +while also being much more readable and simpler to implement. It also retains +one of the drawbacks of the pattern matching example, in that the inputs to `if` +must be carefully organized based on the needs of the output branches. As +before, I don't consider this to be a huge drawback. + +There's other modifications which might be made to this `if` to make it even +cleaner, e.g. one could make it accept a 3-tuple, rather than a 2-tuple, in +order to supply differing values to be used depending on which branch is taken. +To me these sorts of small niceties are better left to be implemented as macros, +built on top of a simpler but less pleasant builtin. + +## Fin + +If you have other ideas around how conditionals might be done in a graph-based +language please [email me][email]; any and all contributions are welcome! One +day I'll get around to actually implementing some of ginger, but today is not +that day. + +[email]: mailto:mediocregopher@gmail.com |