Re: dynamic compilation for scheme, with inlining, etc?

[mcvax!ukc!cam-cl!adg@uunet.uu.net (Andy Gordon)]

In article <8809142159.AA28551@uicbert.eecs.uic.edu> wilson@uicbert.eecs.uic.EDU (Paul Wilson) writes:
>I've been thinking about using dynamic compilation for Scheme,
>and wondering if anybody else is.  Have people abandoned the idea
>of dynamic compilation, and if so, was it premature?

Firstly, by "dynamic compilation" I understand a system that
represents a programme to start with as a syntax tree or some other form
suitable for interpretation, but compiles parts of it into native code
as execution proceeds.  Interpreted code is generally smaller than compiled
code so less space is needed than compiling the whole thing.

I worked on a related problem for my honours thesis---how to interface
compiled and interpreted code in the Edinburgh Standard ML compiler.  In the
system I built the programmer indicated by annotations for each function
whether it was to be compiled or interpreted, but I did have in mind a scheme
that would do the annotations automatically, based on data from previous runs,
or even dynamically converting interpreted functions into native code if they
were frequently executed.  I found on small benchmarks that native code
was between four and six times bigger than interpreted byte codes, and
ran between one and seven times faster.

Let's call a system that mixes compiled and interpreted code a "hybrid"
system, and then distinguish between "static" and "dynamic" hybrids, i.e.,
between those in which the mode of each function declaration is determined at
compile time and those in which it can change at run time.  So I built a
static hybrid system, and I think you plan to build a dynamic hybrid system.

There appear to be two reasons for hybrid systems: (1) to give a variable
time/space tradeoff, i.e., between fast/bulky native code and slow/lean
interpreted code; (2) to allow fancy interpretive debuggers and tracers
in the presence of native code.

I don't think reason (1) is very compelling these days, because the size of
compiled code is not an issue with today's computers---certainly, big ML
programmes that are compiled to native code by one of the production compilers
don't take up inordinate space.  However, reason (2) is still attractive,
because interpreted code will always be easier to debug than compiled code.  A
dynamic hybrid system is all the work of a static one, and more, so for it to
be worthwhile it must make debugging much easier.  One can imagine a debugger
threading through a programme, seeking to use interpreted versions of compiled
functions as it finds them---maybe you could keep a pointer in each compiled
function to an interpreted version or the source.  I'd be interested to hear
how you get on.

Here are some references you might find useful when implementing your scheme.
I published a technical report [1] that has a comprehensive literature survey
on hybrid compilation/interpretation, and presents a taxonomy of ways to
switch between compiled and interpreted modes.  I have a few copies of it that
I could post to anyone who is interested (email me).  Other papers that might
be of interest: Brown on "throw away compiling" [2], Low on automatically
selecting an appropriate representation of an abstract data type depending on
usage statistics [3] and Dakin and Dawson on a text editor that mixes
compilation and interpretation, together with performance graphs [4].

[1] A. D. Gordon, "How to Breed Hybrid Compiler/Interpreters",
    Technical report ECS--LFCS--88--50, Laboratory for the Foundations of
    Computer Science, Computer Science Dept., University of Edinburgh,
    Edinburgh, EH9 3JZ, Scotland. April, 1988.

[2] P. J. Brown, "Throw-away compiling", SWPE, 6, pages 423--434, 1976.

[3] J.R. Low, "Automatic data structure selection: an example and overview",
    CACM, 21(5), pages 376--385, May 1978.

[4] R. J. Dakin and P. C. Poole, "A mixed code approach", The Computer Journal,
    16(3), pages 219--222, 1973.