RTCG and Compilation

The two terms `run time code generation' and `compilation' have different connotations though their meaning is really the same. RTCG is fast, low overhead compilation, sometimes for a simple language. The continuity between these terms is explained below and further demonstrated in the three subsections.

A prototypical interpreter is so general it can be used to compute any function; it is Turing complete. But this isn't a hard requirement, witness regular-expression languages. A prototypical language supports inductively structured programs, but since any structure can be encoded into a string (or even an integer, à la Gödel), this isn't a hard rule either. If we stretch the usage of these words, then every program implements an interpreter for a language [Abelson92].

a power procedure: base raised to exponent, programs are integers.
a shading procedure: phong shading, checkerboard.
a shading language: general purpose surface modeler.

The three above examples illustrates this continuity. The generating extension from the power example (power_gen) is a compiler for a very simple language: programs are just integer exponents. The shading procedure shade is more general than power; it computes many related functions things depending on the geometric model [note shade-power]. Gradually, as graphics systems grew, the surface properties included simple expression trees [Cook84]. Finally control flow was added and the shading procedure became a shading language.

Another example comes from user interfaces (UIs). A simple UI allows the user to give a sequence of unparameterized commands. This is like a language without any control flow (a flat event stream). A UI with simple record-and-play macros allows procedure call, but without passing parameters. Finally, sophisticated UIs embed a full programming language [Visual-Basic][elisp][SchemePaint][HyperNeWS].

It's interesting that as a program changes over time it typically moves up a chain of generalizations. Eventually it splits and intermediate languages appear.

Any number of advanced programming systems [SML/NJ][Chez][CMUCL] (we refer to these and their ilk as `lisp systems') support RTCG via compile or an equivalent system procedure. The speed of these compilers (and traditional compilers in general) varies tremendously. Mostly it's a function of optimization, but it's also increased by multiple passes, un/parsing, and even file i/o.

Of course, the total run time will increase if we spend more time doing code generation itself than we save by the execution of this new and faster code: RTCG wins if $\\delta n + \\sigma < \\iota n$ where is the number of times we call power, $\\delta$ is the time for the specialized version, $\\sigma$ is the time to generate the specialized procedure, and $\\iota$ is the time for the interpreted code to execute (given the same exponent value). As grows, $\\sigma$ loses importance. But when is small, compilation works only if $\\sigma$ is also small.

If the power procedure is viewed as an interpreter, then power_gen is its compiler and $\\sigma$ is the compile time. In this case $\\sigma$ can be very small compared to a traditional compiler, but if you call out to gcc or use an existing Lisp compiler, $\\sigma$ may be quite large.