.%*. .-. .%@@@+. .--=%@@@- =@@@@@@- :--+@@@@@@@@@* *@%@@@@@%: :--=#@@@@@@@@@@@@#@@+ @@::%@@@@@@-: :::-=%@@@@@@@@@@@@@@%#*- :@* .@@ =@@@@@@@@@+-:::::::-=*@@@@@@@@@@@@@@@@@@@%##- @@: #@# +%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%#*: -@@ #@- *%@@@@@@@@@@@@@@@@@%%%#= %@= @@: -=+++== .. @@: @@ . -@@@ +@@ #@% =@@@@- +@@@@# *+ %@# #@- -@@@@@@@. +@@@@@% .%@@@@= @@: @@: +@@@@@@@@@ +@+ +@@@ %@@@@@@@@@ -@@ @@ *@%@* :@@@ *@+ -@@@ %@@@@@@@@@@@# @@@ #@% %@ @% %@@ *@* .@@@ =@@@*@@ :@@@@ @@: %@:## *@+ :@@ :@@ @@@ %@@: @# .@@@ .@@ @@:. @@: .@@ @@ @@@ %@: @@ @@% @@% @@ -@@. =@@ @@. @@@ %@. #@- @@# @@. %@% +@@. @@. %@- @@@ #@ @@. :@@ -@@ %@: +@@+ .@% #@= @@@.@ *@@ +@+ @@* @@: +@@%. .%% *@+ @@@ %@@ -@# @@ @@ :@@@@@@% :@@ @@% %@@ @# *@@ %@@ #@@@@* @@ @@% %@@. %@. @@: @@: ===: @@. @@% %@@: =@%. .@@ @@. #@= @@% %@@%+%@#. @@% @@ +@* @@# -@@@@@* .@@ %@@ :@@ @@# %@@#: =@@ @@: .@@ @@# : @@= @@. @@. @@# :@@ @@ #@= @@% %@% #@@ +@+ #@% .@@ @@: =@# +@% =@% @@ :@% -@@ @@+ @@ .@@ -@: -@@ -@@ @% .: *@# @@* # @@. @@ =@@ .@@ @@* .@@ .@@ *@@ =@# @@* @@* @@ -@@ .@@ +@* .@@ @@- -@@ =@@ %@% #@* @@ @@: @@ +@@ .@@ %@+ :@% @@. :@% *@% -@. %@= %@ @@. @@ *@% @@ %@= @% @@: :@% +@@ :@* =+- #@+ :@: .%@@@. @@- -@ =@@@@@# :@@ =@ *@#.=@@% #@% *@ #@- -@@% %@- @@ #@: :@@% @@: @@ #% .@@% .#@@* -@@ @% #% .@@% +@@@@@- %@% @# %@ :@@% .@@@@@@@@ %@: @# %@ :@@% +@@% .@@@@ @@: @# %@ :@@% #@@: :@@@ -@@ @# @@. .@@@ .@@% .@@@= %@% @# @@. .@@@: %@@- @@@% %@: @# @@ @@@@ %@@@ *@@@ @@: @# .@@ @@@@@@@@@@= :@@@ @@ * @@@ :@@@@@@@@. :@@@ *@@ .@@@@@% -@@@@@. .@@@ @@= @@@@@: .. @@@ @@. -@%: @@@ @@. @@@ @@ -@@ =@@ .@@ @@+ .@@:@@. @@#@- @@@. +@- -mediocregopher's lil web corner
- Bringing it back around.
In previous posts in this series I went over the general idea of the ginger programming language, and some of its properties. To recap:
Ginger is a programming language whose syntax defines a directed graph, in the same way that a LISP language's syntax defines nested lists.
Graph edges indicate an operation, while nodes indicate a value.
The special values in
and out
are used when interpreting a graph as a
function.
A special node type, the tuple, is defined as being a node whose value is an ordered set of input edges.
Another special node type, the fork, is the complement to the tuple. A fork is defined as being a node whose value is an ordered set of output edges.
The special if
operation accepts a 2-tuple, the first value being some state
value and the second being a tuple. The if
operation expects to be directed
towards a 2-fork. If the boolean is true then the top output edge of the fork
is taken, otherwise the bottom is taken. The state value is what's passed to
the taken edge.
There were some other detail rules but I don't remember them off the top of my head.
Today I'd like to go over my ideas for how loops would work in ginger. With loops established ginger would officially be a Turing complete language and, given time and energy, real work could actually begin on it.
As with conditionals I'll start by establishing a base example. Let's say we'd
like to define an operation which prints out numbers from 0 up to n
, where n
is given as an argument. In go this would look like:
func printRange(n int) int {
for i := 0; i < n; i++ {
fmt.Println(i)
}
}
With that established, let's start looking at different patterns.
In the olden days the primary looping construct was goto
, which essentially
teleports the program counter (aka instruction pointer) to another place in the
execution stack. Pretty much any other looping construct can be derived from
goto
and some kind of conditional, so it's a good starting place when
considering loops in ginger.
(in -println-> } -incr-> out) -> println-incr
0 -> } -> } -if-> { -> out
in -> } -eq-> } { -> } -upd-> } -+
^ 0 -> } |
| println-incr -> } |
| |
+--------------------------------+
(Note: the upd
operation is used here for convenience. It takes in three
arguments: A tuple, an index, and an operation. It applies the operation to the
tuple element at the given index, and returns a new tuple with that index set to
the value returned.)
Here goto
is performed using a literal arrow going from the right to left.
it's ugly and hard to write, and would only be moreso the more possible gotos an
operation has.
It also complicates our graphs in a significant way: up till now ginger graphs have have always been directed acyclic graphs (DAGs), but by introducing this construct we allow that graphs might be cyclic. It's not immediately clear to me what the consequences of this will be, but I'm sure they will be great. If nothign else it will make the compiler much more complex, as each value can no longer be defined in terms of its input edge, as that edge might resolve back to the value itself.
While conceptually sound, I think this strategy fails the practability test. We can do better.
The while
construct is the basic looping primitive of iterative languages
(some call it for
, but they're just lying to themselves).
Try as I might, I can't come up with a way to make while
work with ginger.
while
ultimately relies on scoped variables being updated in place to
function, while ginger is based on the concept of pipelining a set of values
through a series of operations. From the point of view of the programmer these
operations are essentially immutable, so the requirement of a variable which can
be updated in place cannot be met.
This pattern is based on how many functional languages, for example erlang, handle looping. Rather than introducing new primitives around looping, these language instead ensure that tail calls are properly optimized and uses those instead. So loops are implemented as recursive function calls.
For ginger to do this it would make sense to introduce a new special value,
recur
, which could be used alongside in
and out
within operations. When
the execution path hits a recur
then it gets teleported back to the in
value, with the input to recur
now being the output from in
. Usage of it
would look like:
(
(in -println-> } -incr-> out) -> println-incr
in -> } -if-> { -> out
in -eq-> } { -> } -upd-> } -> recur
0 -> }
println-incr -> }
) -> inner-op
0 -> } -inner-op-> out
in -> }
This looks pretty similar to the goto
example overall, but with the major
difference that the looping body had to be wrapped into an inner operation. The
reason for this is that the outer operation only takes in one argument, n
, but
the loop actually needs two pieces of state to function: n
and the current
value. So the inner operation loops over these two pieces of state, and the
outer operation supplies n
and an initial iteration value (0
) to that inner
operation.
This seems cumbersome on the surface, but what other languages do (such as
erlang, which is the one I'm most familiar with) is to provide built-in macros
on top of this primitive which make it more pleasant to use. These include
function polymorphism and a more familiar for
construct. With a decent macro
capability ginger could do the same.
The benefits here are that the graphs remain acyclic, and the syntax has not been made more cumbersome. It follows conventions established by other languages, and ensures the language will be capable of tail-recursion.
Another functional strategy which is useful is that of the map/reduce power
couple. The map
operation takes a sequence of values and an operation, and
returns a sequence of the same length where the operation has been applied to
each value in the original sequence individually. The reduce
operation is more
complicated (and not necessary for out example), but it's essentially a
mechanism to turn a sequence of values into a single value.
For our example we only need map
, plus one more helper operation: range
.
range
takes a number n
and returns a sequence of numbers starting at 0
and
ending at n-1
. Our print example now looks like:
in -range-> } -map-> out
println -> }
Very simple! Map/reduce is a well established pattern and is probably the
best way to construct functional programs. However, the question remains whether
these are the best primitives for looping, and I don't believe they are. Both
map
and reduce
can be derived from conditional and looping primitives like
if
and recur
, and they can't do some things that those primitives can. While
I expect one of the first things which will be done in ginger is to define map
and reduce
in terms of if
and a looping primitive, and use them generously
throughout the code, I think the fact that they can be defined in terms of
lower-level primitives indicates that they aren't the right looping primitives
for ginger.
Unlike with the conditionals posts, where I started out not really knowing what
I wanted to do with conditionals, I more or less knew where this post was going
from the beginning. recur
is, in my mind, the best primitive for looping in
ginger. It provides the flexibility to be extended to any use-case, while not
complicating the structure of the language. While possibly cumbersome to
implement directly, recur
can be used as a primitive to construct more
convenient looping operations like map
and reduce
.
As a final treat (lucky you!), here's map
defined using if
and recur
:
(
in -0-> mapped-seq
in -1-> orig-seq
in -2-> op
mapped-seq -len-> i
mapped-seq -> } -if-> { -> out
orig-seq -len-> } -eq-> } { -> } -append-> } -> recur
i -> } } }
} }
orig-seq -i-> } -op-> } }
}
orig-seq -> }
op -> }
) -> inner-map
() -> } -inner-map-> out
in -0-> }
in -1-> }
The next step for ginger is going to be writing an actual implementation of the graph structure in some other language (let's be honest, it'll be in go). After that we'll need a syntax definition which can be used to encode/decode that structure, and from there we can start actually implementing the language!
Published 2021-04-27
This post is part of a series.
Previously: Conditionals in Ginger, Errata
Next: The Syntax of Ginger
This site can also be accessed via the gemini protocol: gemini://mediocregopher.com/