summaryrefslogtreecommitdiff
path: root/static/src/_posts/2021-12-31-ginger-its-alive.md
blob: efd6bd0778387d498b9109d85a5a444726f00361 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
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!