r5rs scheme as a virtual machine – I

Some time ago I advocated that the programming language Scheme is a new portable assembler. We can code something in Scheme and then compile it to PHP or Python. Now I want to try this idea. First, an explanation why Scheme:

I used to convert data in different languages. Similar approaches, similar code, repeating myself. I wanted to code once and get something universal, and even started to think about it. Fortunately, somehow I found that I was re-inventing Lisp. It was a big surprise, to find that my former approach was wrong, namely: “lots of idiotic stupid parentheses” or “academical exercise”.

List vs Scheme. Lisp is big with a few implementations. Scheme: small core, a lot of experimental implementations. The final switch happened after I found XML research on top of Scheme (SXML libraries).

Back to the topic. I’ve made a small research (part 1) to get a general idea what is already done (current answer: nothing). I searched for “scheme virtual machine” in the newsgroup “comp.lang.scheme”, in Google, in Scholar.

Actually, implementing Scheme is not so easy. One has to consider at least:

* the garbage collector
* the full numerical tower
* call/cc
* tail-call
* macros
* compiling tricks: lambda lifting, cps transformation

It is hard to implement everything from the beginning. Let’s use an existing tool.

Every Scheme is implemented through an intermediate VM. We’d like to try those which compile to a languages like C or Java or PHP or Python etc. If there is no such feature, the VM is probably of no use for us because even the author failed to do it.

Instead of the buzzwords “virtual machine” I should search by the word “backend”.

The step 2 (TODO) of the research: check all the implementations listed at http://community.schemewiki.org/?scheme-faq-standards#implementations and find which allow to create backends.

Meanwhile, here are some references which I written out into the notebook.

I’ve read and enjoyed these 3 papers:

* The 90 minute Scheme to C compiler.
* CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A. (A super trick of using the stack as the newest generation of GC. Chicken Scheme is based on it.)
* A parallel virtual machine for efficient Scheme compilation

There are more papers at http://library.readscheme.org/page8.html.

Books:

Christian Queinnec, Lisp in Small Pieces

Samual N. Kamin, “Programming Languages, An Interpreter-Based Approach”, Addison-Wesley, Reading, Mass., 1990.

“The Anatomy of Lisp” by John Allen. (McGraw-Hill ISBN 0-07-001115-X)

Further ports

* Part 2
* Part 3

Leave a Reply