Sponge - a Scheme to Befunge compiler


This page holds a quick and dirty compiler for a tiny subset of Scheme into Befunge 98. The compiler is written in (hopefully ANSI) Common Lisp.

Supported dialect

The supported dialect of Scheme compiles the following special forms: The primitive operations start with an underscore and are not first class procedures (which can be easily solved with an eta expansion, e.g. (lambda (x y) (_+ x y))). The following datatypes are supported: The following are misfeatures:

Compiling strategy

The compilation is done in lots of phases:
  1. Desugar let and letrec into lambda abstractions.
  2. Convert to CPS, so it isn't necessary to keep a stack of return addresses (the code always calls its continuation, jumping forward and never returning).
  3. Extract lambdas recursively, transforming them into toplevel definitions.
  4. Produce a matrix of Befunge code from Scheme code. (This is the "real" compilation).
  5. Print the matrix into a text file.
Tricks used:

The code

Here it is the compiler. The Scheme code to be compiled is hardcoded in the source code, and so is the output file. You might want to modify it to do something fancier such as reading the code from a file, like normal people do.

The Befunge object code is reeeally big, but it seems to work in at least some examples. Please be patient when you run the result!

Now writing an Unlambda to Befunge compiler should be almost a trivial task :)

Happy hacking!
Free Web Hosting