« Languages and Multithreading | Main | Message-passing and Entanglement »

Term-Rewriting Combinators

Progress on the Links interpreter.

Jeremy checked in his completely-overhauled optimizer combinators. We now have ways of defining term-rewriters by combining rewriters; and we can compose a structurally-recursive function just by giving one case and specifying a strategy, such as "bottom-up" or "top-down." This approach is pretty clearly laid out in the papers of Limsoon Wong, but it took us a while to rewrite out existing optimizer functinos this way and to find just the right combinators. Hopefully we'll have a chance to publish the specific techniques that we're finding useful and the pitfalls.

Now, we've cut our optimizer code from ~1200 lines to about 400, a rather good improvement. It's far more readable and approximately as correct! We also spent some time pairing to create unit tests, which was fruitful and makes me feel much more confident that these things will keep working in the future.

Post a comment