Compiling a circuit using Java

Question

I wrote the Scheme interpreter (trying to be fully compatible with R5RS), and it just seemed to me that compiling into VM operation codes would make it faster. (Correct me if I am wrong.) I can interpret the Scheme source code in memory, but I am stuck in understanding code generation.

My question is: what patterns are needed to generate opcodes from the parsing tree, for example, for the JVM or any other virtual machine (or even for a real machine)? And what, if any, will be complications, advantages or disadvantages of this?

Answer 1

There will be two main difficulties associated with the JVM for the circuit.

First, the JVM does not support explicit tail call annotations, so you cannot guarantee proper tail recursion, as required by R5RS (3.5), without resorting to the expensive mini-interpreter trick.

The second problem is related to continuation support. The JVM does not provide anything useful for implementing continuations, so again you have to use a mini-interpreter. I., each trivial CPS function should return the next closure, which will then be called by the infinite loop of the mini-interpreter.

But there are still many interesting optimization possibilities. I would recommend taking a look at Bigloo (there is a relatively fast JVM server) and Kawa. For general compilation methods, see Scheme in 90 minutes .

Still, interpretation is a viable alternative to compilation (at least on the JVM due to its serious limitations and general inefficiency). See how SISC is implemented, this is a rather interesting and innovative approach.