diff options
| -rw-r--r-- | static/src/_posts/2021-12-31-ginger-its-alive.md | 422 |
1 files changed, 422 insertions, 0 deletions
diff --git a/static/src/_posts/2021-12-31-ginger-its-alive.md b/static/src/_posts/2021-12-31-ginger-its-alive.md new file mode 100644 index 0000000..efd6bd0 --- /dev/null +++ b/static/src/_posts/2021-12-31-ginger-its-alive.md @@ -0,0 +1,422 @@ +--- +title: >- + Ginger: It's Alive! +description: >- + The new best language for computing fibonacci numbers. +series: ginger +tags: tech +--- + +As a kind of Christmas present to myself I took a whole week off of work +specifically to dedicate myself to working on ginger. + +My concrete goal was to be able to run a ginger program to compute any Nth +fibonacci number, a goal I chose because it would require the implementation of +conditionals, some kind of looping or recursion, and basic addition/subtraction. +In other words, it would require all the elements which comprise a Turing +complete language. + +And you know what? I actually succeeded! + +The implementation can be found [here][impl]. At this point ginger is an +interpreted language running in a golang-based VM. The dream is for it to be +self-hosted on LLVM (and other platforms after), but as an intermediate step to +that I decided on sticking to what I know (golang) rather than having to learn +two things at once. + +In this post I'm going to describe the components of this VM at a high level, +show a quick demo of it working, and finally talk about the roadmap going +forward. + +[impl]: https://github.com/mediocregopher/ginger/tree/ebf57591a8ac08da8a312855fc3a6d9c1ee6dcb2 + +## Graph + +The core package of the whole project is the [`graph`][graph] package. This +package implements a generic directed graph datastructure. + +The generic part is worth noting; I was able to take advantage of go's new +generics which are currently [in beta][go118]. I'd read quite a bit on how the +generic system would work even before the beta was announced, so I was able to +hit the ground running and start using them without much issue. + +Ginger's unique graph datastructure has been discussed in previous posts in this +series quite a bit, and this latest implementation doesn't deviate much at a +high level. Below are the most up-to-date core datatypes and functions which are +used to construct ginger graphs: + +```go + +// Value is any value which can be stored within a Graph. Values should be +// considered immutable, ie once used with the graph package their internal +// value does not change. +type Value interface { + Equal(Value) bool + String() string +} + +// OpenEdge consists of the edge value (E) and source vertex value (V) of an +// edge in a Graph. When passed into the AddValueIn method a full edge is +// created. An OpenEdge can also be sourced from a tuple vertex, whose value is +// an ordered set of OpenEdges of this same type. +type OpenEdge[E, V Value] struct { ... } + +// ValueOut creates a OpenEdge which, when used to construct a Graph, represents +// an edge (with edgeVal attached to it) coming from the vertex containing val. +func ValueOut[E, V Value](edgeVal E, val V) *OpenEdge[E, V] + +// TupleOut creates an OpenEdge which, when used to construct a Graph, +// represents an edge (with edgeVal attached to it) coming from the vertex +// comprised of the given ordered-set of input edges. +func TupleOut[E, V Value](edgeVal E, ins ...*OpenEdge[E, V]) *OpenEdge[E, V] + +// Graph is an immutable container of a set of vertices. The Graph keeps track +// of all Values which terminate an OpenEdge. E indicates the type of edge +// values, while V indicates the type of vertex values. +type Graph[E, V Value] struct { ... } + +// AddValueIn takes a OpenEdge and connects it to the Value vertex containing +// val, returning the new Graph which reflects that connection. +func (*Graph[E, V]) AddValueIn(val V, oe *OpenEdge[E, V]) *Graph[E, V] + +// ValueIns returns, if any, all OpenEdges which lead to the given Value in the +// Graph (ie, all those added via AddValueIn). +func (*Graph[E, V]) ValueIns(val Value) []*OpenEdge[E, V] + +``` + +The current `Graph` implementation is _incredibly_ inefficient, it does a lot of +copying, looping, and equality checks which could be optimized out one day. +That's going to be a recurring theme of this post, as I had to perform a +balancing act between actually reaching my goal for the week while not incurring +too much tech debt for myself. + +[graph]: https://github.com/mediocregopher/ginger/blob/ebf57591a8ac08da8a312855fc3a6d9c1ee6dcb2/graph/graph.go +[go118]: https://go.dev/blog/go1.18beta1 + +### MapReduce + +There's a final operation I implemented as part of the `graph` package: +[MapReduce][mapreduce]. It's a difficult operation to describe, but I'm going to +do my best in this section for those who are interested. If you don't understand +it, or don't care, just know that `MapReduce` is a generic tool for transforming +graphs. + +For a description of `MapReduce` we need to present an example graph: + +``` + +<--b--- + + \ +X <--a--+<--c----+<--f-- A + + / + + +<---g--- + +<--d--+ + +<---h--- + \ +Y <---------e----------- B +``` + +Plus signs indicate tuples, and lowercase letters are edge values while upper +case letters are vertex values. The pseudo-code to construct this graph in go +might look like: + +```go + g := new(Graph) + + fA := ValueOut("f", "A") + + g = g.AddValueIn( + "X", + TupleOut( + "a", + TupleOut("b", fA), + TupleOut("c", fA), + TupleOut( + "d", + ValueOut("g", "A"), + ValueOut("h", "B"), + ), + ), + ) + + g = g.AddValueIn("e", "B") +``` + +As can be seen in the [code][mapreduce], `MapReduce`'s first argument is an +`OpenEdge`, _not_ a `Graph`. Fundamentally `MapReduce` is a reduction of the +_dependencies_ of a particular value into a new value; to reduce the +dependencies of multiple values at the same time would be equivalent to looping +over those values and calling `MapReduce` on each individually. Having +`MapReduce` only deal with one edge at a time is more flexible. + +So let's focus on a particular `OpenEdge`, the one leading into `X` (returned by +`TupleOut("a", etc...)`. `MapReduce` is going to descend into this `OpenEdge` +recursively, in order to first find all value vertices (ie the leaf vertices, +those without any children of their own). + +At this point `MapReduce` will use its second argument, the `mapVal` function, +which accepts a value of one type and returns a value of another type. This +function is called on each value from every value vertex encountered. In this +case both `A` and `B` are connectable from `X`, so `mapVal` will be called on +each _only once_. This is the case even though `A` is connected to multiple +times (once with an edge value of `f`, another with an edge value of `b`). +`mapVal` only gets called once per vertex, not per connection. + +With all values mapped, `MapReduce` will begin reducing. For each edge leaving +each value vertex, the `reduceEdge` function is called. `reduceEdge` accepts as +arguments the edge value of the edge and the _mapped value_ (not the original +value) of the vertex, and returns a new value of the same type that `mapVal` +returned. Like `mapVal`, `reduceEdge` will only be called once per edge. In our +example, `<--f--A` is used twice (`b` and `c`), but `reduceEdge` will only be +called on it once. + +With each value vertex edge having been reduced, `reduceEdge` is called again on +each edge leaving _those_ edges, which must be tuple edges. An array of the +values returned from the previous `reduceEdge` calls for each of the tuples' +input edges is used as the value argument in the next call. This is done until +the `OpenEdge` is fully reduced into a single value. + +To flesh out our example, let's imagine a `mapVal` which returns the input +string repeated twice, and a `reduceEdge` which returns the input values joined +with the edge value, and then wrapped with the edge value (eg `reduceEdge(a, [B, +C]) -> aBaCa`). + +Calling `MapReduce` on the edge leading into `X` will then give us the following +calls: + +``` +# Map the value vertices + +mapVal(A) -> AA +mapVal(B) -> BB + +# Reduce the value vertex edges + +reduceEdge(f, [AA]) -> fAAf +reduceEdge(g, [AA]) -> gAAg +reduceEdge(h, [BB]) -> hBBh + +# Reduce tuple vertex edges + +reduceEdge(b, [fAAf]) -> bfAAfb +reduceEdge(c, [fAAf]) -> cfAAfc +reduceEdge(d, [gAAg, hBBh]) -> dgAAgdhBBhd + +reduceEdge(a, [bfAAfb, cfAAfc, dgAAgdhBBhd]) -> abfAAfbacfAAfcadgAAgdhBBhda +``` + +Beautiful, exactly what we wanted. + +`MapReduce` will prove extremely useful when it comes time for the VM to execute +the graph. It enables the VM to evaluate only the values which are needed to +produce an output, and to only evaluate each value once no matter how many times +it's used. `MapReduce` also takes care of the recursive traversal of the +`Graph`, which simplifies the VM code significantly. + +[mapreduce]: https://github.com/mediocregopher/ginger/blob/ebf57591a8ac08da8a312855fc3a6d9c1ee6dcb2/graph/graph.go#L338 + +## gg + +With a generic graph implementation out of the way, it was then required to +define a specific implementation which could be parsed from a file and later +used for execution in the VM. + +The file extension used for ginger code is `.gg`, as in "ginger graph" (of +course). The package name for decoding this file format is, therefore, also +called `gg`. + +The core datatype for the `gg` package is the [`Value`][ggvalue], since the +`graph` package takes care of essentially everything else in the realm of graph +construction and manipulation. The type definition is: + +```go +// Value represents a value which can be serialized by the gg text format. +type Value struct { + + // Only one of these fields may be set + Name *string + Number *int64 + Graph *Graph + + // Optional fields indicating the token which was used to construct this + // Value, if any. + LexerToken *LexerToken +} + +type Graph = graph.Graph[Value, Value] // type alias for convenience +``` + +Note that it's currently only possible to describe three different types in a +`gg` file, and one of them is the `Graph`! These are the only ones needed to +implement a fibonacci function, so they're all I implemented. + +The lexing/parsing of `gg` files is not super interesting, you can check out the +package code for more details. The only other thing worth noting is that, for +now, all statements are required to end with a `;`. I had originally wanted to +be less strict with this, and allow newlines and other tokens to indicate the +end of statements, but it was complicating the code and I wanted to move on. + +Another small thing worth noting is that I decided to make each entire `.gg` +file implicitly define a graph. So you can imagine each file's contents wrapped +in curly braces. + +With the `gg` package out of the way I was able to finally parse ginger +programs! The following is the actual, real-life implementation of the fibonacci +function (though at this point it didn't actually work, because the VM was still +not implemented: + +``` +out = { + + decr = { out = add < (in; -1;); }; + + n = tupEl < (in; 0;); + a = tupEl < (in; 1;); + b = tupEl < (in; 2;); + + out = if < ( + isZero < n; + a; + recur < ( + decr < n; + b; + add < (a;b;); + ); + ); + +} < (in; 0; 1;); +``` + +[ggvalue]: https://github.com/mediocregopher/ginger/blob/ebf57591a8ac08da8a312855fc3a6d9c1ee6dcb2/gg/gg.go#L14 + +## VM + +Finally, the meat of all this. If the `graph` and `gg` packages are the sturdy, +well constructed foundations of a tall building, then the `vm` package is the +extremely long, flimsy stick someone propped up vertically so they could say +they built a structure of impressive height. + +In other words, it's very likely that the current iteration of the VM will not +be long for this world, and so I won't waste time describing it in super detail. + +What I will say about it is that within the `vm` package I've defined a [new +`Value` type][vmvalue], which extends the one defined in `gg`. The necessity of +this was that there are types which cannot be represented syntactically in a +`.gg` file, but which _can_ be used as values within a program being run. + +The first of these is the `Operation`, which is essentially a first-class +function. The VM will automatically interpret a graph as an `Operation` when it +is used as an edge value, as has been discussed in previous posts, but there are +also built-in operations (like `if` and `recur`) which cannot be represented as +datastructures, and so it was necessary to introduce a new in-memory type to +properly represent operations. + +The second is the `Tuple` type. This may seem strange, as ginger graphs already +have a concept of a tuple. But the ginger graph tuple is a _vertex type_, not a +value type. The distinction is small, but important. Essentially the graph tuple +is a structural element which describes how to create a tuple value, but it is +not yet that value. So we need a new Value type to hold the tuple once it _has_ +been created during runtime. + +Another thing worth describing about the `vm` package, even though I think they +might change drastically, are [`Thunk`s][thunk]: + +```go +// Thunk is returned from the performance of an Operation. When called it will +// return the result of that Operation having been called with the particular +// arguments which were passed in. +type Thunk func() (Value, error) +``` + +The term "thunk" is borrowed from Haskell, which I don't actually know so I'm +probably using it wrong, but anyway... + +A thunk is essentially a value which has yet to be evaluated; the VM knows +exactly _how_ to evaluate it, but it hasn't done so yet. The primary reason for +their existence within ginger is to account for conditionals, ie the `if` +operation. The VM can't evaluate each of an `if`'s arguments all at once, it +must only evaluate the first argument (to obtain a boolean), and then based on +that evaluate the second or third argument. + +This is where `graph.MapReduce` comes in. The VM uses `graph.MapReduce` to +reduce each edge in a graph to a `Thunk`, where the `Thunk`'s value is based on +the operation (the edge's value) and the inputs to the edge (which will +themselves be `Thunk`s). Because each `Thunk` represents a potential value, not +an actual one, the VM is able to completely parse the program to be executed +(using `graph.MapReduce`) while allowing conditionals to still work correctly. + +[EvaluateEdge][evaledge] is where all that happens, if you're interested, but be +warned that the code is a hot mess right now and it's probably not worth +spending a ton of time understanding it as it will change a lot. + +A final thing I'll mention is that the `recur` operation is, I think, broken. Or +probably more accurately, the entire VM is broken in a way which prevents +`recur` from working correctly. It _does_ produce the correct output, so I +haven't prioritized debugging it, but for any large number of iterations it +takes a very long time to run. + +[vmvalue]: https://github.com/mediocregopher/ginger/blob/ebf57591a8ac08da8a312855fc3a6d9c1ee6dcb2/vm/vm.go#L18 +[thunk]: https://github.com/mediocregopher/ginger/blob/ebf57591a8ac08da8a312855fc3a6d9c1ee6dcb2/vm/op.go#L11 +[evaledge]: https://github.com/mediocregopher/ginger/blob/ebf57591a8ac08da8a312855fc3a6d9c1ee6dcb2/vm/scope.go#L29 + +## Demo + +Finally, to show it off! I put together a super stupid `eval` binary which takes +two arguments: a graph to be used as an operation, and a value to be used as an +argument to that operation. It doesn't even read the code from a file, you have +to `cat` it in. + +The [README][readme] documents how to run the demo, so if you'd like to do so +then please clone the repo and give it a shot! It should look like this when you +do: + +``` +# go run ./cmd/eval/main.go "$(cat examples/fib.gg)" 8 +21 +``` + +You can put any number you like instead of `8`, but as mentioned, `recur` is +broken so it can take a while for larger numbers. + +[readme]: https://github.com/mediocregopher/ginger/blob/ebf57591a8ac08da8a312855fc3a6d9c1ee6dcb2/README.md + +## Next Steps + +The following are all the things I'd like to address the next time I work on +ginger: + +* `gg` + + * Allow for newlines (and `)` and `}`) to terminate statements, not just + `;`. + + * Allow names to have punctuation characters in them (maybe?). + + * Don't read all tokens into memory prior to parsing. + +* `vm` + + * Fix `recur`. + + * Implement tail call optimization. + +* General + + * A bit of polish on the `eval` tool. + + * Expose graph creation, traversal, and transformation functions as + builtins. + + * Create plan (if not actually implement it yet) for how code will be + imported from one file to another. Namespacing in general will fall into + this bucket. + + * Create plan (if not actually implement it yet) for how users can + extend/replace the lexer/parser. + +I don't know _when_ I'll get to work on these next, ginger will come back up in +my rotation of projects eventually. It could be a few months. In the meantime I +hope you're as excited about this progress as I am, and if you have any feedback +I'd love to hear it. + +Thanks for reading! |