In the last month, I’ve had only three significant accomplishments.
I feel my biggest accomplishment was implementing the fixpoint function, a Z combinator, which becomes the basis for expressing recursive loops. The code for the Z combinator is not difficult – just `
[swap dup bind swap compose] bind dup apply` in AO(1). But I found it plenty intimidating! It paralyzed me for days. I’m very glad to be past it. In any case, using the fixpoint function is relatively easy: `
[foo] fixpoint` evaluates to `
[[foo] fixpoint foo]`.
Shortly after implementing fixpoint, I implemented a few loops.
I quickly ran into rather pitiful performance problems of my REPL/interpreter. A simple loop such as `
0 [3 +] 10000 repeat` – i.e. a loop that adds 3 a total of 10k times to an initial value of 0 – was taking 6 seconds. Further, a larger loop – around 150k steps – would bust the default Haskell stack.
So my second accomplishment was performance related.
The same loop will now run in 1.3 seconds if I leave stack-frame debugging on, or 0.3 seconds if I disable stack frames. This is still slow, but 20x less slow than before. I’m a little upset with this – I was aiming for a 100x improvement. But it should be enough for bootstrapping. I also implemented a relatively trivial tail-call optimization, i.e. such that blocks ending in `$c]` will not consume a stack frame. (This usually corresponds to ending a block action with `inline`, whose ABC definition is `rvr$c`.) I’ve run loops of 10 million steps in about five minutes.
This idea, in a simple example, is that I can map a word `foo` to every element in a list by writing something like `foo\*`. Or to every element in a list-of-lists (e.g. a matrix) using `foo\**`. This is as opposed to explicitly quoting the word – e.g. `[[foo] map] map` – which tends to hinder refactoring. Developers can define `\*` or any other inflection as words in the AO dictionary.
I don’t know whether I’ll keep inflection. I would like to see how they fare across a few significant projects. My intuition is that a small handful of inflections can greatly reduce noise in AO code.
(1) the Z combinator (fixpoint function) in ABC (weakly simplified):
[rwrwzwlw^zlw'l[l]wrzwowrzowrzol] wrwzwlw'l[l]wrzwowrzo^w vrwvvrrvrrz$wlcllccwlcl
Addendum 6 February: I’ve been searching for simpler, faster fixpoint implementations. I’ve found a few!
[dup bind] swap compose dup bind (pre-compose)
[%^'wol] %rwrzo %^'wol (specialize dup-bind)
These respectively offer ~10% and ~17% performance benefit in the test loops I’ve been running in the interpreter, suggesting the bottleneck is now the loop body. That’s a good thing. 🙂 The simpler fixpoint operation should also be easier to recognize for dedicated optimizations, later on.