summaryrefslogtreecommitdiff
path: root/src/_posts/2021-04-27-loops-in-ginger.md
diff options
context:
space:
mode:
Diffstat (limited to 'src/_posts/2021-04-27-loops-in-ginger.md')
-rw-r--r--src/_posts/2021-04-27-loops-in-ginger.md223
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!