.%*. .-. .%@@@+. .--=%@@@- =@@@@@@- :--+@@@@@@@@@* *@%@@@@@%: :--=#@@@@@@@@@@@@#@@+ @@::%@@@@@@-: :::-=%@@@@@@@@@@@@@@%#*- :@* .@@ =@@@@@@@@@+-:::::::-=*@@@@@@@@@@@@@@@@@@@%##- @@: #@# +%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%#*: -@@ #@- *%@@@@@@@@@@@@@@@@@%%%#= %@= @@: -=+++== .. @@: @@ . -@@@ +@@ #@% =@@@@- +@@@@# *+ %@# #@- -@@@@@@@. +@@@@@% .%@@@@= @@: @@: +@@@@@@@@@ +@+ +@@@ %@@@@@@@@@ -@@ @@ *@%@* :@@@ *@+ -@@@ %@@@@@@@@@@@# @@@ #@% %@ @% %@@ *@* .@@@ =@@@*@@ :@@@@ @@: %@:## *@+ :@@ :@@ @@@ %@@: @# .@@@ .@@ @@:. @@: .@@ @@ @@@ %@: @@ @@% @@% @@ -@@. =@@ @@. @@@ %@. #@- @@# @@. %@% +@@. @@. %@- @@@ #@ @@. :@@ -@@ %@: +@@+ .@% #@= @@@.@ *@@ +@+ @@* @@: +@@%. .%% *@+ @@@ %@@ -@# @@ @@ :@@@@@@% :@@ @@% %@@ @# *@@ %@@ #@@@@* @@ @@% %@@. %@. @@: @@: ===: @@. @@% %@@: =@%. .@@ @@. #@= @@% %@@%+%@#. @@% @@ +@* @@# -@@@@@* .@@ %@@ :@@ @@# %@@#: =@@ @@: .@@ @@# : @@= @@. @@. @@# :@@ @@ #@= @@% %@% #@@ +@+ #@% .@@ @@: =@# +@% =@% @@ :@% -@@ @@+ @@ .@@ -@: -@@ -@@ @% .: *@# @@* # @@. @@ =@@ .@@ @@* .@@ .@@ *@@ =@# @@* @@* @@ -@@ .@@ +@* .@@ @@- -@@ =@@ %@% #@* @@ @@: @@ +@@ .@@ %@+ :@% @@. :@% *@% -@. %@= %@ @@. @@ *@% @@ %@= @% @@: :@% +@@ :@* =+- #@+ :@: .%@@@. @@- -@ =@@@@@# :@@ =@ *@#.=@@% #@% *@ #@- -@@% %@- @@ #@: :@@% @@: @@ #% .@@% .#@@* -@@ @% #% .@@% +@@@@@- %@% @# %@ :@@% .@@@@@@@@ %@: @# %@ :@@% +@@% .@@@@ @@: @# %@ :@@% #@@: :@@@ -@@ @# @@. .@@@ .@@% .@@@= %@% @# @@. .@@@: %@@- @@@% %@: @# @@ @@@@ %@@@ *@@@ @@: @# .@@ @@@@@@@@@@= :@@@ @@ * @@@ :@@@@@@@@. :@@@ *@@ .@@@@@% -@@@@@. .@@@ @@= @@@@@: .. @@@ @@. -@%: @@@ @@. @@@ @@ -@@ =@@ .@@ @@+ .@@:@@. @@#@- @@@. +@- -mediocregopher's lil web corner
- Some different options for how "if" statements could work.
In the last ginger post 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.
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:
func op(a, b int) int {
if a < b {
return a + b
}
return b - a
}
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.
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:
in -> } -switch-> } -> { { {A, B}, _}, ({A,B}-lt->out)} -0-> } -add-> out
in -1-> } -> } } -1-> } -sub-> out
in -0-> }
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.
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.
If you have other ideas around how conditionals might be done in a graph-based language please email me; any and all contributions are welcome! One day I'll get around to actually implementing some of ginger, but today is not that day.
Published 2021-03-01
This post is part of a series.
Previously: Ginger
Next: Conditionals in Ginger, Errata
This site can also be accessed via the gemini protocol: gemini://mediocregopher.com/