.%*. .-.
.%@@@+. .--=%@@@-
=@@@@@@- :--+@@@@@@@@@*
*@%@@@@@%: :--=#@@@@@@@@@@@@#@@+
@@::%@@@@@@-: :::-=%@@@@@@@@@@@@@@%#*- :@*
.@@ =@@@@@@@@@+-:::::::-=*@@@@@@@@@@@@@@@@@@@%##- @@:
#@# +%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%#*: -@@
#@- *%@@@@@@@@@@@@@@@@@%%%#= %@=
@@: -=+++== .. @@:
@@ . -@@@ +@@
#@% =@@@@- +@@@@# *+ %@#
#@- -@@@@@@@. +@@@@@% .%@@@@= @@:
@@: +@@@@@@@@@ +@+ +@@@ %@@@@@@@@@ -@@
@@ *@%@* :@@@ *@+ -@@@ %@@@@@@@@@@@# @@@
#@% %@ @% %@@ *@* .@@@ =@@@*@@ :@@@@ @@:
%@:## *@+ :@@ :@@ @@@ %@@: @# .@@@ .@@
@@:. @@: .@@ @@ @@@ %@: @@ @@% @@%
@@ -@@. =@@ @@. @@@ %@. #@- @@# @@.
%@% +@@. @@. %@- @@@ #@ @@. :@@ -@@
%@: +@@+ .@% #@= @@@.@ *@@ +@+ @@*
@@: +@@%. .%% *@+ @@@ %@@ -@# @@
@@ :@@@@@@% :@@ @@% %@@ @# *@@
%@@ #@@@@* @@ @@% %@@. %@. @@:
@@: ===: @@. @@% %@@: =@%. .@@
@@. #@= @@% %@@%+%@#. @@%
@@ +@* @@# -@@@@@* .@@
%@@ :@@ @@# %@@#: =@@
@@: .@@ @@# : @@=
@@. @@. @@# :@@
@@ #@= @@% %@%
#@@ +@+ #@% .@@
@@: =@# +@% =@%
@@ :@% -@@ @@+
@@ .@@ -@: -@@
-@@ @% .: *@#
@@* # @@.
@@ =@@
.@@ @@*
.@@ .@@
*@@ =@#
@@* @@*
@@ -@@
.@@ +@*
.@@ @@-
-@@ =@@
%@% #@*
@@ @@:
@@ +@@
.@@ %@+
:@% @@.
:@% *@%
-@. %@=
%@ @@.
@@ *@%
@@ %@=
@% @@:
:@% +@@
:@* =+- #@+
:@: .%@@@. @@-
-@ =@@@@@# :@@
=@ *@#.=@@% #@%
*@ #@- -@@% %@-
@@ #@: :@@% @@:
@@ #% .@@% .#@@* -@@
@% #% .@@% +@@@@@- %@%
@# %@ :@@% .@@@@@@@@ %@:
@# %@ :@@% +@@% .@@@@ @@:
@# %@ :@@% #@@: :@@@ -@@
@# @@. .@@@ .@@% .@@@= %@%
@# @@. .@@@: %@@- @@@% %@:
@# @@ @@@@ %@@@ *@@@ @@:
@# .@@ @@@@@@@@@@= :@@@ @@
* @@@ :@@@@@@@@. :@@@ *@@
.@@@@@% -@@@@@. .@@@ @@=
@@@@@: .. @@@ @@.
-@%: @@@ @@.
@@@ @@
-@@ =@@
.@@ @@+
.@@:@@.
@@#@-
@@@.
+@-
-
mediocregopher's lil web corner
- It works gooder now.
During some recent traveling I had to be pulled away from cryptic-net work for a while. Instead I managed to spend a few free hours, and the odd international plane ride, to fix the ginger vm.
The problem, as it stood, was that it only functioned "correctly" in a very accidental sense. I knew from the moment that I published it that it would get mostly rewritten immediately.
And so here we are, with a rewritten vm and some new realizations.
The Operation type was previously defined like so:
type Operation interface {
Perform([]Thunk, Operation) (Thunk, error)
}
I'm not going to explain it, because it's both confusing and wrong.
One thing that is helpful in a refactor, especially in a strongly typed language, is to tag certain interfaces as being axiomatic, and conforming the rest of your changes around those. If those interfaces are simple enough to apply broadly and accurately describe desired behavior, they will help pre-decide many difficult decisions you'd otherwise have to make.
So with that mind, I tagged Operation as being an axiomatic interface, given
that ginger is aiming to be a functional language (and I'm wondering if I should
just rename Operation to Function, while I'm at it). The new definition of
the interface is:
type Operation interface {
Perform(Value) Value
}
Operation takes and argument and returns a result, it could not possibly be
boiled down any further. By holding Operation to this definition and making
decisions from there, it was pretty clear what the next point of attack was.
The reason that Operation had previously been defined in such a fucked up way
was to support the if and recur Operations, as if they weren't different
than any other Operations. But truthfully they are different, as they are
actually control flow constructs, and so require capabilities that no other
Operation would be allowed to use anyway.
The new implementation reflects this. if and recur are now both handled
directly by the compiler, while global Operations like tupEl are
implementations of the Operation interface.
The previous iteration of the vm hadn't distinguished between a compile step and
a run step. In a way it did both at the same time, by abusing the Thunk type.
Separating the two steps, and ditching the Thunk type in the process, was the
next major change in the refactoring.
The compile step can be modeled as a function which takes a Graph and returns
an Operation, where the Graph's in and out names correspond to the
Operation's argument and return, respectively. The run step then reads an
input from the user, calls the compiled Operation with that input, and outputs
the result back to the user.
As an example, given the following program:
* six-or-more.gg
max = {
a = tupEl < (in, 0)
b = tupEl < (in, 1)
out = if < (gt < (a, b), a, b)
}
out = max < (in, 6)
we want to compile an Operation which accepts a number and returns the greater
of that number and 6. I'm going to use anonymous go functions to demonstrate the
anatomy of the compiled Operation, as that's what's happening in the current
compiler anyway.
// After compilation, this function will be in-memory and usable as an
// Operation.
sixOrMore := func(in Value) Value {
max := func(in Value) Value {
a := tupEl(in, 0)
b := tupEl(in, 1)
if a > b {
return a
}
return b
}
return max(in, 6)
}
Or at least, this is what I tried for initially. What I found was that it was
easier, in the context of how graph.MapReduce works, to make even the leaf
values, e.g. in, 0, 1, and 6, map to Operations as well. in is
replaced with an anonymous function which returns its argument, and the numbers
are replaced with anonymous functions which ignore their argument and always
return their respective number.
So the compiled Operation looks more like this:
// After compilation, this function will be in-memory and usable as an
// Operation.
sixOrMore := func(in Value) Value {
max := func(in Value) Value {
a := tupEl(
func(in Value) Value { return in }(in),
func(_ Value) Value { return 0}(in),
)
b := tupEl(
func(in Value) Value { return in }(in),
func(_ Value) Value { return 1}(in),
)
if a > b {
return a
}
return b
}
return max(
func(in Value) Value { return in }(in),
func(_ Value) Value { return 6}(in),
)
}
This added layer of indirection for all leaf values is not great for performance, and there's probably further refactoring which could be done to make the result look more like the original ideal.
To make things a bit messier, even that representation isn't quite accurate to
the current result. The compiler doesn't properly de-duplicate work when
following name values. In other words, everytime a is referenced within max,
the Operation which the compiler produces will recompute a via tupEl.
So the actual compiled Operation looks more like this:
// After compilation, this function will be in-memory and usable as an
// Operation.
sixOrMore := func(in Value) Value {
return func(in Value) Value {
if tupEl(func(in Value) Value { return in }(in), func(_ Value) Value { return 0}(in)) >
tupEl(func(in Value) Value { return in }(in), func(_ Value) Value { return 1}(in)) {
return tupEl(func(in Value) Value { return in }(in), func(_ Value) Value { return 0}(in))
}
return tupEl(func(in Value) Value { return in }(in), func(_ Value) Value { return 1}(in))
}(
func(in Value) Value { return in }(in),
func(_ Value) Value { return 6}(in),
)
}
Clearly, there's some optimization to be done still.
While it's still not perfect, the new implementation is far and away better than the old. This can be seen just in the performance for the fibonacci program:
# Previous VM
$ time ./eval "$(cat examples/fib.gg)" 10
55
real 0m8.737s
user 0m9.871s
sys 0m0.309s
# New VM
$ time ./eval "$(cat examples/fib.gg)" 50
12586269025
real 0m0.003s
user 0m0.003s
sys 0m0.000s
They're not even comparable.
Published 2022-04-03
This post is part of a series.
Previously: Ginger Names
Next: How to Errors Good
This site can also be accessed via the gemini protocol: gemini://mediocregopher.com/