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 n 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 n grows, \\sigma loses importance. But when n 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.