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].
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
shade is more general than
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
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 where is the number of times we call
power, is the time
for the specialized version, is the time to generate the
specialized procedure, and is the time for the interpreted
code to execute (given the same exponent value). As grows, loses importance. But when is small, compilation works
only if is also small.
power procedure is viewed as an interpreter, then
power_gen is its compiler and is the compile time. In
this case can be very small compared to a traditional
compiler, but if you call out to
gcc or use an existing Lisp
compiler, may be quite large.