Governance by those who do the work.

Tuesday, December 15, 2009

Schlep Toolchains

Schlep Toolchains documents and distributes the hyper-cross-platform technology used to create the WB B-tree database libraries and new implementation of Water for C, C#, and Java from source written in a subset of Scheme.

One might assume that in order for Schlep-dialect code to map to these three languages [C, C#, and Java], the Schlep-dialect must manifest the worst limitations of each language; but translation can actually rectify some of these limitations.

If I had to pick one practical feature of Scheme which elevates it above other languages, it would be internal definitions. The Algorithmic Language Scheme allows procedure definitions (using define, letrec, and named-let) inside of other procedures, which none of C, C#, or Java does. Internal definitions allow calls of internal procedures with a small number of arguments to replace the common alternatives:

  • duplication of code, or
  • top-level definitions and calls passing large numbers of arguments.
C and C# have a `goto' statement, enabling Schlep to emulate calling of internal-procedures in the tail position using some variable assignments (sometimes including temporary variable binding to emulate simultaneous assignment) followed by a goto statement. The restriction to the tail-position does not allow internal recursion other than tail-recursion; but this facilitates use of internal procedures in many situations which would otherwise force less desirable practices.

Java lacks a `goto' statement. Tail-called internal procedures are instead implemented using while (true), continue, and break with labels. The resulting Java code is not as readable as the original Scheme-dialect; but that loss in clarity is balanced by greater expressive power.

Schlep-example gives an example of a procedure with an internal procedure and how Schlep translates this procedure into C, C#, and Java.


glathoud said...

Well done.

Schlep for Javascript would be wonderful (slightly related note: Javascript is stepping on the server side as well).

Aubrey Jaffer said...

Can you supply the JavaScript equivalent of Schlep-example?

glathoud said...
This comment has been removed by the author.
glathoud said...

Here it is, along with a speed performance check (building on Lazutkin's).

scm2js would be a bounty, since it would solve the javascript recursion issue while providing best speed performance.

glathoud said...

One can also do the tail optimization in Javascript directly. Comments and suggestions welcome.