Menu
I was writing a Scheme interpreter (trying to be fully R5RS compatible) and it just struck me that compiling into VM opcodes would make it faster. (Correct me if I am wrong.) I can interpret the Scheme source code in the memory, but I am stuck at understanding code generation.
My question is: What patterns will be required to generate opcodes from a parse tree, for, say, the JVM or any other VM (or even a real machine)? And what, if any, will be the complications, advantages, or disadvantage of doing so?
861
Running a Java program Scheme provides a “read-evaluate-print” loop that lets the programmer run a program or parts of a program interactively. To evaluate (+ 3 4) in Scheme, the pro- grammer types the expression to the interpreter, which computes and prints 7.
The job of the Scheme compiler is to expand all macros and all of Scheme to its most primitive expressions. The definition of “primitive expression” is given by the inventory of constructs provided by Tree-IL, the target language of the Scheme compiler: procedure calls, conditionals, lexical references, and so on.
Open a command prompt window and go to the directory where you saved the java program. Assume it's C:\. Type 'javac MyFirstJavaProgram. java' and press enter to compile your code.
Scheme is easily compiled. The central part of its syntax is defined in a scheme code – most languages provide definitions of subroutines. Still, Scheme allows the definition of a new syntax while retaining its compiled language portfolio. There a host of scheme compilers and interpreters, all of them work differently.
For Scheme there will be two major complications related to JVM.
First, JVM does not support explicit tail calls annotations, therefore you won't be able to guarantee a proper tail recursion as required by R5RS (3.5) without resorting to an expensive mini-interpreter trick.
The second issue is with continuations support. JVM does not provide anything useful for implementing continuations, so again you're bound to use a mini-interpreter. I.e., each CPS trivial function should return a next closure, which will be then called by an infinite mini-interpreter loop.
But still there are many interesting optimisation possibilities. I'd recommend to take a look at Bigloo (there is a relatively fast JVM backend) and Kawa. For the general compilation techniques take a look at Scheme in 90 minutes.
And still, interpretation is a viable alternative to compilation (at least on JVM, due to its severe limitations and general inefficiency). See how SISC is implemented, it is quite an interesting and innovative approach.
177
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
