diff options
Diffstat (limited to 'static/src/_posts')
| -rw-r--r-- | static/src/_posts/2021-08-26-the-syntax-of-ginger.md | 480 |
1 files changed, 480 insertions, 0 deletions
diff --git a/static/src/_posts/2021-08-26-the-syntax-of-ginger.md b/static/src/_posts/2021-08-26-the-syntax-of-ginger.md new file mode 100644 index 0000000..4ff64d8 --- /dev/null +++ b/static/src/_posts/2021-08-26-the-syntax-of-ginger.md @@ -0,0 +1,480 @@ +--- +title: >- + The Syntax of Ginger +description: >- + Oh man, this got real fun real quick. +series: ginger +tags: tech +--- + +Finally I have a syntax for ginger that I'm happy with. This has actually been a +huge roadblock for me up till this point. There's a bit of a chicken-and-the-egg +problem with the syntax: without pinning down the structures underlying the +syntax it's difficult to develop one, but without an idea of syntax it's +difficult to know what structures will be ergonomic to use. + +I've been focusing on the structures so far, and have only now pinned down the +syntax. Let's see what it looks like. + +## Preface: Conditionals + +I've so far written [two][cond1] [posts][cond2] regarding conditionals in +ginger. After more reflection, I think I'm going to stick with my _original_ +gut, which was to only have value and tuple vertices (no forks), and to use a +function which accepts both a boolean and two input edges: the first being the +one to take if the boolean is true, and the second being the one to take if it's +false. + +Aka, the very first proposal in the [first post][cond1]. It's hard to justify +up-front, but I think once you see it in action with a clean syntax you'll agree +it just kind of works. + +[cond1]: {% post_url 2021-03-01-conditionals-in-ginger %} +[cond2]: {% post_url 2021-03-04-conditionals-in-ginger-errata %} + +## Designing a Syntax + +Ginger is a bit of a strange language. It uses strange datastructures in strange +ways. But approaching the building of a syntax for any language is actually +straightforward: you're designing a serialization protocol. + +To pull back a bit, consider a list of words. How would you encode this list in +order to write it to a file? To answer this, let's flip the question: how would +you design a sequence of characters (ie the contents of the file) such that the +reader could reconstruct the list? + +Well, constructing the list from a sequence of characters requires being able to +construct it _at all_, so in what ways is the list constructed? For this list, +let's say there's only an append operation, which accepts a list and a value to +append to it, and returns the result. + +If we say that append is encoded via wrapping parenthesis around its two +arguments, and that `()` encodes the empty list, then we get a syntax like... + +``` +(((() foo) bar) baz) +``` + +...which, in this instance, decodes to a list containing the words, "foo", "bar", +and "baz", in that order. + +It's not a pretty syntax, but it demonstrates the method. If you know how the +datastructure is constructed via code, you know what capabilities the syntax must +have and how it needs to fit together. + +## gg + +All of this amounted to me needing to implement the ginger graph in some other +language, in order to see what features the syntax must have. + +A few years ago I had begun an implementation of a graph datastructure in go, to +use as the base (or at least a reference) for ginger. I had called this +implementation `gg` (ginger graph), with the intention that this would also be +the file extension used to hold ginger code (how clever). + +The basic qualities I wanted in a graph datastructure for ginger were, and still +are: + +* Immutability, ie all operations which modify the structure should return a + copy, leaving the original intact. + +* Support for tuples. + +* The property that it should be impossible to construct an invalid graph. An + invalid graph might be, for example, one where there is a single node with no + edges. + +* Well tested, and reasonably performant. + +Coming back to all this after a few years I had expected to have a graph +datastructure implemented, possibly with immutability, but lacking in tuples and +tests. As it turns out I completely underestimated my past self, because as far +as I can tell I had already finished the damn thing, tuples, tests and all. + +It looks like that's the point where I stopped, probably for being unsure about +some other aspect of the language, and my motivation fell off. The fact that +I've come back to ginger, after all these years, and essentially rederived the +same language all over again, gives me a lot of confidence that I'm on the right +track (and a lot of respect for my past self for having done all this work!) + +The basic API I came up with for building ginger graphs (ggs) looks like this: + +```go +package gg + +// OpenEdge represents an edge with a source value but no destination value, +// with an optional value on it. On its own an OpenEdge has no meaning, but is +// used as a building block for making Graphs. +type OpenEdge struct{ ... } + +// TupleOut constructs an OpenEdge leading from a tuple, which is comprised of +// the given OpenEdges leading into it, with an optional edge value. +func TupleOut(ins []OpenEdge, edgeVal Value) OpenEdge + +// ValueOut constructs an OpenEdge leading from a non-tuple value, with an +// optional edge value. +func ValueOut(val, edgeVal Value) OpenEdge + +// ZeroGraph is an empty Graph, from which all Graphs are constructed via calls +// to AddValueIn. +var ZeroGraph = &Graph{ ... } + +// Graph is an immutable graph structure, formed from a collection of edges +// between values and tuples. +type Graph struct{ ... } + +// AddValueIn returns a new Graph which is a copy of the original, with the +// addition of a new edge. The new edge's source and edge value come from the +// given OpenEdge, and the edge's destination value is the given value. +func (g *Graph) AddValueIn(oe OpenEdge, val Value) *Graph +``` + +The actual API is larger than this, and includes methods to remove edges, +iterate over edges and values, and perform unions and disjoins of ggs. But the +above are the elements which are required only for _making_ ggs, which is all +that a syntax is concerned with. + +As a demonstration, here is how one would construct the `min` operation, which +takes two numbers and returns the smaller, using the `gg` package: + +```go +// a, b, in, out, if, etc.. are Values which represent the respective symbol. + +// a is the result of passing in to the 0 operation, ie a is the 0th element of +// the in tuple. +min := gg.ZeroGraph.AddValueIn(gg.ValueOut(in, 0), a) + +// b is the 1st element of the in tuple +min = min.AddValueIn(gg.ValueOut(in, 1), b) + +// out is the result of an if which compares a and b together, and which returns +// the lesser. +min = min.AddValueIn(out, gg.TupleOut([]gg.OpenEdge{ + gg.TupleOut([]gg.OpenEdge{a, b}, lt), + a, + b, +}, if) +``` + +And here's a demonstration of how this `min` would be used: + +```go +// out is the result of passing 1 and 5 to the min operation. +gg.ZeroGraph.AddValueIn(gg.TupleOut([]gg.OpenEdge{1, 5}, min), out) +``` + +## Make it Nice + +_Technically_ we're done. We have an implementation of the language's underlying +structure, and a syntax which encodes it (ie the ugly ass go syntax above). But +obviously I'm not proposing anyone actually use that. + +Another thing I found when digging around in the old ginger repo was a text +file, tucked away in a directory called "sandbox", which had a primitive syntax +which _almost_ worked. I won't copy it here, but you can find it if you care to. +But with that as a foundation I came up with a crude, rough draft spec, which +maps the go syntax to the new syntax. + +``` +ValueOut(val, edgeVal) : -edgeVal-val +ValueOut(val, null) : -val +TupleOut([]val, edgeVal) : -edgeVal-(val, ...) +TupleOut([]val, null) : -(val, ...) +Graph(openEdge->val, ...) : { val openEdge, ... } +``` + +A couple things to note about this spec: + +* `null` is used to indicate absence of value on an edge. The details of `null` + are yet to be worked out, but we can use this placeholder for now. + +* `Graph` is cheating a bit. In the original `gg` implementation a Graph gains + its OpenEdge/Value pairs via successive calls to `AddValueIn`. However, such a + pattern doesn't translate well to text, and since we're dealing purely with + constructing an entire Graph at once we can instead have our Graph syntax + declare all OpenEdge/Value pairs at once. + +* It's backwards! Eg where the go syntax does `ValueOut(val, edgeVal)`, the + proposed spec puts the values in the opposite order: `-edgeVal-val`. The + former results in code which is read from input to output, while the latter + results in the opposite: output to input. + + This was a tip I picked up from the old text file I found, and the result is + code which is more familiar to an existing programmer. I _think_ (but am + not sure) that it's also more in line with how programming is done mentally, + ie we start with a result and work backwards to figure out what it takes to + get there. + + It's possible, though, that I'm wrong, so at this end of this post I'm going + to put some examples of the same code both "forwards" and "backwards" and see + how I feel about it. + +With all that said, let's see it in action! Here's `min` implemented in our shiny new syntax: + +``` +min -{ + a -0-in, + b -1-in, + out -if-( + -lt-(-a,-b), + -a, + -b + ) +} +``` + +and then here's it being used: + +``` +out -min-(-1,-5) +``` + +## Make it _Nicer_ + +The most striking feature of this rough draft spec is all the prefix dashes, +such as in the `-min-(-1,-5)` statement. These dashes were included as they make +sense in the context of what the intended human interpretation of the structure +is: two values, `1`, and `5`, are being _piped into_ the two slots of a 2-tuple, +and that 2-tuple is being _piped into_ the `min` operation, the output of which +is being _piped into_ something `out`. + +The "piping into" is what the dash represents, which is why the top level values +in the graph, `a`, `b`, and `out`, don't have a preceding dash; they are the +ultimate destinations of the pipes leading to them. But these pipes are +ultimately ugly, and also introduce odd questions like "how do we represent +-1?", so they need to go. + +So I've made a second draft, which is only a few changes away from the rough, +but oh man do those changes make a world of difference. Here's the cleaned up +spec: + +``` +ValueOut(val, edgeVal) : edgeVal(val) +ValueOut(val, null) : val +TupleOut([]val, edgeVal) : edgeVal(val, ...) +TupleOut([]val, null) : (val, ...) +Graph(openEdge->val, ...) : { val = openEdge, ... } +``` + +The dashes were simply removed, and the `edgeVal` and `val` concatted together. +For `ValueOut(val, edgeVal)` wrapping parenthesis were put around `val`, to +delineate it and `edgeVal`. This conflicts with the syntax for `TupleOut([]val, +edgeVal)`, but that conflict is easy to remedy: when parenthesis wrap only a +single `val` then that is a `ValueOut`, otherwise it's a `TupleOut`. + +Another change is to add an `=` between the `val` and `openEdge` in the `Graph` +constructor. This is a purely aesthetic change, but as you'll see it works well. + +So let's see it! `min` implemented with this cleaned up syntax: + +``` +min = { + a = 0(in), + b = 1(in), + out = if( + lt(a,b), + a, + b + ) +} +``` + +And then its use: + +``` +min(1,5) +``` + +Well well well, look what we have here: a conventional programming language +syntax! `{`/`}` wrap a scope, and `(`/`)` wrap function arguments and +(optionally) single values. It's a lot clearer now that `0` and `1` are being +used as operations themselves when instantiating `a` and `b`, and `if` is much +more readable. + +I was extremely surprised at how well this actually worked out. Despite having +drastically different underpinnings than most languages it ends up looking both +familiar and obvious. How cool! + +## Examples Examples Examples + +Here's a collection of example programs written in this new syntax. The base +structure of these are borrowed from previous posts, I'm merely translating that +structure into a new form: + +``` +// decr outputs one less than the input. +decr = { out = add(in, -1) } + +// fib accepts a number i, and outputs the ith fibonacci number. +fib = { + + inner = { + n = 0(in), + a = 1(in), + b = 2(in), + + out = if(zero?(n), + a, + inner(decr(n), b, add(a,b)) + ) + + }, + + out = inner(in, 0, 1) +} + +// map accepts a sequence and a function, and returns a sequence consisting of +// the result of applying the function to each of the elements in the given +// sequence. +map = { + inner = { + mapped-seq = 0(in), + orig-seq = 1(in), + op = 2(in), + + i = len(mapped-seq), + + // graphs provide an inherent laziness to the language. Just because + // next-el is _defined_ here doesn't mean it's evaluated here at runtime. + // In reality it will only be evaluated if/when evaluating out requires + // evaluating next-el. + next-el = op(i(orig-seq)), + next-mapped-seq = append(mapped-seq, next-el), + + out = if( + eq(len(mapped-seq), len(orig-seq)), + mapped-seq, + inner(next-mapped-seq, orig-seq, op) + ) + } + + // zero-seq returns an empty sequence + out = inner(zero-seq(), 0(in), 1(in)) +} +``` + +## Selpmexa Selpmexa Selpmexa + +Our syntax encodes a graph, and a graph doesn't really care if the syntax was +encoded in an input-to-output vs an output-to-input direction. So, as promised, +here's all the above examples, but "backwards": + +``` +// min returns the lesser of the two numbers it is given +{ + (in)0 = a, + (in)1 = b, + + ( + (a,b)lt, + a, + b + )if = out + +} = min + +// decr outputs one less than the input. +{ (in, -1)add = out } = decr + +// fib accepts a number i, and outputs the ith fibonacci number. +{ + { + (in)0 = n, + (in)1 = a, + (in)2 = b, + + ( + (n)zero? + a, + ((n)decr, b, (a,b)add)inner + )if = out + + } = inner, + + (in, 0, 1)inner = out + +} = fib + +// map accepts a sequence and a function, and returns a sequence consisting of +// the result of applying the function to each of the elements in the given +// sequence. +{ + { + (in)0 = mapped-seq, + (in)1 = orig-seq, + (in)2 = op, + + (mapped-seq)len = i, + + ((orig-seq)i)op = next-el, + (mapped-seq, next-el)append = next-mapped-seq, + + ( + ((mapped-seq)len, (orig-seq)len)eq, + mapped-seq, + (next-mapped-seq, orig-seq, op)inner + )if = out + + } = inner, + + (()zero-seq, (in)0, (in)1)inner = out +} = map +``` + +Do these make you itchy? They kind of make me itchy. But... parts of them also +appeal to me. + +The obvious reason why these feel wrong to me is the placement of `if`: + +``` +( + (a,b)lt, + a, + b +)if = out +``` + +The tuple which is being passed to `if` here is confusing unless you already +know that it's going to be passed to `if`. But on your first readthrough you +won't know that till you get to the end, so you'll be in the dark until then. +For more complex programs I'm sure this problem will compound. + +On the other hand, pretty much everything else looks _better_, imo. For example: + +``` +// copied and slightly modified from the original to make it even more complex + +(mapped-seq, ((orig-seq)i)op)append = next-mapped-seq +``` + +Something like this reads very clearly to me, and requires a lot less mental +backtracking to comprehend. The main difficulty I have is tracking the +parenthesis, but the overall "flow" of data and the order of events is plain to +read. + +## Next Steps + +The syntax here is not done yet, not by a long shot. If my record with past +posts about ginger (wherein I've "decided" on something and then completely +backtracked in later posts every single time) is any indication then this syntax +won't even look remotely familiar in a very short while. But it's a great +starting point, I think, and raises a lot of good questions. + +* Can I make parenthesis chains, a la the last example, more palatable in some + way? + +* Should I go with the "backwards" syntax afterall? In a functional style of + programming `if` statements _should_ be in the minority, and so the syntax + which better represents the flow of data in that style might be the way. + +* Destructuring of tuples seems to be wanted, as evidenced by all the `a = + 0(in)` lines. Should this be reflected in the structure or solely be + syntactical sugar? + +* Should the commas be replaced with any whitespace (and make commas count as + whitespace, as clojure has done)? If this is possible then I think they should + be, but I won't know for sure until I begin implementing the parser. + +And, surely, many more! I've felt a bit lost with ginger for a _long_ time, but +seeing a real, usable syntax emerge has really invigorated me, and I'll be +tackling it again in earnest soon (fingers crossed). |