Reference implementations

It is time to move the development of the reference implementation of Babel-17 v0.21 forward. At lot of work has already been done: a complete parser is available that spits out a validated syntax tree (including linear scope checks), and a continuation passing interpreter that runs deBruijn-index functional code. What is missing are a few details concerning the interpreter, a reference implementation for the Babel-17 library, connecting the interpreter with the library, and a translation from the syntaxtree to the functional code.

Still work enough to rethink the approach. Was it the right decision to choose deBruijn-indexed environments for a reference implementation? Was it necessary to use continuation-passing, which complicates the code for a feature that only a few serious users will notice positively because it allows to run programs only bound by memory, not by stack size, and allows for proper tail-recursion, and a lot of others might notice in a negative way, because it slows down execution?

The temptation is big to scrape the continuation passing deBruijn stuff, also to switch from Java to Scala, and proceed like it worked out so well for the Mini Babel-17 interpreter.  Write a small and simple interpreter in Scala, then bootstrap and write a proper and efficient compiler in Babel-17. Write most of the library also in Babel-17.

Is this just the usual “I am close to the finishing line, lets start fresh from the beginning” anxiety? Hard to tell. But it really seems to me that the second approach is the much better one. But why did I choose the first one in the first place?

Apart from the usual “lets build some cool tech and try out some cool techniques” reason the most important reason, as far as I remember, was to have a reference implementation that would be also a reference with respect to performance. Of course the hope is that later implementations are a magnitude faster, but they should differ in behavior from the original implementation only by a linear factor. I think there is a much better chance of later quality implementations to properly handle tail-recursion and memory management if the reference implementation does. And deBruijn environments exhibit the same behavior as environments in compiled code would.


Difficult decision ahead.

Leave a Reply

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

You are commenting using your 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

%d bloggers like this: