Bytecodes: vm & compiler for guile3

[Johannes Abt <jsabt@cip.informatik.uni-erlangen.de>]

Hi.

Some time ago, Laurent Peron and others talked about bytecode
compilation for GuileIII. In 1996 I did a bytecode language, a bytecode
interpreter and a compiler, too. I have written a little summary of
the design, the implementation and the results. If you are only
interested in the results: skip to the end. The description may have
some "missing links": I have done the project a long time ago.


The Bytecode Interpreter

The bytecode interpreter is written as a replacement for scm_apply and
and parts of scm_ceval. I had to keep the old functions to evaluate
"normal" expressions. 
The bytecode interpreter was written to demand as few changes to guile as
possible. About 30 lines had to be inserted in "eval.c" in order to
make sure that the C stack does not grow when you make 
SCM -> bytecode -> SCM calls.

The bytecode interpreter is a stack machine with the ability to access
each entry of the stack directly: Im most cases, you just have to push
some values to create a binding.

I do not use continuations, because it includes a copy of the C stack:
A non-terminal function call is just a function call in C.

To pass parameters, I use a pointer into the stack of the stack
machine (which is of course an array in C). My own "scm_apply", that I
use for every function call, transforms the array into an SCM list, if
necessary ("list" and "append", for example). For "+" and other
tc7_asubr/rpsubr, this time and memory consuming task is not
necessary.

I have completely avoided to use global C variables because call/cc does
not capture them. 
RScheme uses global variables to pass parameters. The C compiler assigns
the most important global variables to registers of the CPU. The
drawbacks of using this strategy would have been:
- I would have had to completely rewrite Guile.
- I do not have a clue of register optimization.

For the environment, the bytecode interpreter uses linked SCM lists. 
Later on, I have added the another possibility: You can push values on
the stack and later access them directly, regardless of the depth of
the stack. This reduced the consumption of SCM cells to much less than
that of the Guile interpreter, but it hasn't yielded much speedup.

Using SCM's technique of substituting global variables by "gloc"s is
essential: The "normal" lookup in the global environment is way too slow. 

Evaluating a compiled lambda function returns a "bytecode closures", a
new type that consists of a literal state (an array of code
constants and compiler information) and an environment.
Evaluating a bytecode closures means executing it, of course.
You can save the closures to disk (just like Emacs .elc-Files).



The Compiler

Thanks a lot to Paul Wilson. His lecture notes on scheme compilers
have helped a lot.

It has three parts: The front end, the back end (which generates some
sort of assembler code) and the assembler.

The compiler knows all mandatory special forms and almost all the
other ones, but it cannot do macros.

The result of a compilation is a literal state, which can be execute
via a new function call.

If an environment frame is neither captured nor modified (via set!),
the compiler generates code that creates the environment frame on the
stack of the bytecode interpreter, consequently less cells are used.

The compiler does not do any loop conversions, alpha / beta
conversions, evaluation at compile time, ...



The Result

Both compiler and bytecode interpreter work correctly, as far as I
have tested them: The compiler compiles itself etc. It is pretty complete.

Speed: This subject is really sad. Even though compiled code uses
about 20% less cells, it needs about 10% more CPU time.

I think that loop conversion and many other costly optimizations 
would have been necessary so that compiled code runs faster than
the Guile interpreter. However, does the cost of a big compiler pay if
it speeds execution up just by few percents?


I have to pay respect to the implementors of SCM/Guile:
It is not a trivial task to overtake their interpreter.


If you are interested in further information or the code, just email me.
The code is under GPL, (C) LaBri Bordeaux.


Bye,
Johannes Abt 
 


-- 
PGP Public Key availabe by finger
<URL:http://wwwcip.informatik.uni-erlangen.de/user/jsabt>
"I am returning this otherwise good typing paper to you because someone
has printed gibberish all over it and put your name at the top."
                -- English Professor, Ohio University