Compiling Scheme to Javascript

Recently I’ve been continuing my experiments with compilers by writing a Scheme to Javascript compiler. This is fairly simple as the languages are very similar, both have garbage collection and first class functions so it’s largely a case of reusing these features directly. There are some caveats though – here is an example of the canonical factorial example in Scheme:

(define factorial
  (lambda (n)
    (if (= n 0) 1
        (* n (factorial (- n 1))))))

The Javascript code generated by the compiler:

var factorial = function (n)
{
    if ((n == 0)) {
        return 1
    } else {
        return (n * factorial((n - 1)))
    }
}

Scheme has tail call optimisation, meaning that recursive calls are as fast as iterative ones – in Javascript however, a function that calls itself will gradually use up the stack. The factorial example above breaks with larger numbers so we need to do some work to make things easier for Javascript interpreters. When considering list processing, fold can be considered a core form that abstracts all other list processing. If we make that fast, we can reuse it to define higher order list processing such as filter, which takes a function and a list and returns another list. The function is called on each element, if it returns false it’s filtered out of the resulting list.

(define filter
  (lambda (fn l)
    (foldl
     (lambda (i r)
       (if (fn i) (append r (list i)) r))
     ()
     l)))

Compiling this with an iterative version of fold – which uses a for loop in Javascript, we generate this code:

var filter = function (fn,l)
{
    return (function() {
        var _foldl_fn=function (i,r) {
            if (fn(i)) {
                return r.concat([i])
            } else {
                return r
            }
        };

        var _foldl_val=[];
        var _foldl_src=l;
        for (var _foldl_i=0; _foldl_i<_foldl_src.length; _foldl_i++) {
            _foldl_val = _foldl_fn(_foldl_src[_foldl_i], _foldl_val); 
        }
        return _foldl_val; })()
    }
}

We have to be a little bit careful that variables created by the compiler don’t clash with those of the user’s code, so we have to make really ugly variable names. You also need to be careful to wrap code in closures as much as possible to control the scope. The problem with this is that there is probably a limit to the amount of nesting possible, especially comparing different implementations of Javascript. A interesting project that has got much further than this is Spock. More context to this work and some actual source code soon…

This work by dave is licensed under a Creative Commons Attribution-ShareAlike 4.0 International