diff options
Diffstat (limited to 'src/_posts/2021-04-27-loops-in-ginger.md')
| -rw-r--r-- | src/_posts/2021-04-27-loops-in-ginger.md | 223 |
1 files changed, 0 insertions, 223 deletions
diff --git a/src/_posts/2021-04-27-loops-in-ginger.md b/src/_posts/2021-04-27-loops-in-ginger.md deleted file mode 100644 index 2b0433c..0000000 --- a/src/_posts/2021-04-27-loops-in-ginger.md +++ /dev/null @@ -1,223 +0,0 @@ ---- -title: >- - Loops in Ginger -description: >- - Bringing it back around. -series: ginger -tags: tech ---- - -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. - -## Loops - -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: - -```go -func printRange(n int) int { - for i := 0; i < n; i++ { - fmt.Println(i) - } -} -``` - -With that established, let's start looking at different patterns. - -## Goto - -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. - -## While - -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. - -## Recur - -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. - -## Map/Reduce - -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. - -## Conclusion - -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! |