💾 Archived View for mediocregopher.com › posts › the-syntax-of-ginger.gmi captured on 2024-08-25 at 00:03:00. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-08-18)
-=-=-=-=-=-=-
Oh man, this got real fun real quick.
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.
I've so far written two posts 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. 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.
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.
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:
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:
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:
// 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:
// out is the result of passing 1 and 5 to the min operation.
gg.ZeroGraph.AddValueIn(gg.TupleOut([]gg.OpenEdge{1, 5}, min), out)
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:
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)
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!
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))
}
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.
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.
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).
-----
Published 2021-08-26