partial evaluation

this section introduces self-applicable partial evaluation, the semantics-based program transformation i use.

The most recent attempts to `automate backquote' are the self-applicable partial evaluation systems exemplified by Similix. The heart of these systems is cogen. cogen transforms interpreter source code into compiler source code. it does two things for the programmer: a binding time analysis (BTA) divides the program into static and dynamic `binding times', and a generation phase handles the bookkeeping necessary to produce loops, avoid infinite loops and assemble code fragments.

Applying Similix to the power example, the programmer builds a generating extension comp by feeding power's source text and a binding time pattern to cogen:

(cogen 'power '(static dynamic) "power.sim")
(comp (list 10 '***))

(power-0 2) --> 1024

Since Similix wasn't built for RTCG and because Scheme's programming model is so undefined, the interface has several glaring weaknesses: files, generated symbols, top-level state, etc. but these are cosmetic ills (solved by fabius, see below).

the real drawback of PE is that cogen requires more than just an interpreter with binding time pattern. to avoid pathalogical behavior (non-termination, excessive specialization, bad separation, etc) the interpreter must be annotated and tweeked to stay within the confines of cogen's analytical powers. perhaps this brittleness outweighs the benefits of automation.


Mark Leone is building a compiler called Fabius that uses BTA to support Lightweight RTCG. It works like cogen, but its compilers produce machine code directly in one pass, rather than producing Scheme (like Similix) or an intermediate language (like `C). So compilers run fast (aka are Lightweight), but produce weak code. It solves Similix's cosmetic problems, but portability is reduced.