Awelon Progress Report II

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.

My third accomplishment is an experimental development of inflection with adverbs (also discussed here).

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!

AO: [dup bind] swap compose dup bind (pre-compose)
ABC: [r^zlw'l[l]wrzwowrzol]wrzo^zlw'l[l]wrzwowrzol

AO: [%^'wol] %rwrzo %^'wol (specialize dup-bind)
ABC: [^'wol]wrzo^'wol

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.

Advertisements
This entry was posted in Language Design. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s