This section summarizes the hoped-for contributions and my plan for achieving them. Subsections present the open questions, experiments, preliminary results, and research schedule in greater detail.
There are a number of questions that I hope to answer. I divide them into two categories: what are the analytical properties of the transformed code and its execution, and how practical are the transformations. The former resemble typical compiler performance evaluation questions, the latter are fuzzy software engineering issues (the 2nd Futamura projection has a human factor).
My plan to answer these questions is to
I will start with the following experiments (listed with keywords)
As this is a inter-disciplinary thesis roughly between partial evaluation (PE) and interactive graphics, we can make three categories of the contributions:
Is the final code good enough? DCG assembles its somewhat higher level IR into code locally comparable to gcc's [GCC], using only about 350 instructions per instruction produced. Using a lower level representation allows more optimizations to be handled by generated compilers, but the lack of high level constructs complicates cogen since it can not use these same constructs. I don't plan on generating machine code so I will simply examine the generated abstract code and assess how much optimization will be required to produce fast code, and how quickly naive code could be produced. The root language may have to be extended to make efficient code generation easier, eg loops may require direct support.
Does the speedup justify the time spent compiling? Of course it depends on the application. I will measure abstract instruction counts to compare interpretation to compilation and execution, and determine the break-even point. This ignores scheduling, cache, and memory effects. I hope to show that my generated compilers can be significantly faster than typical lisp compilers and still produce good code.
Is the root language too low level? Some language features may not be easily handled once they are compiled into the IR, since information is lost by translation into a lower level language (eg short-circuit con/disjunctions, types, pattern matching, loops, letrec, varargs, higher-orderness, procedure call/return, etc). I will find ways to handle as many of these as possible. Some of them may require special features, new hints, or some generalization. Some may have to be included directly in the IR. This is a familiar drawback to an IR: it can handle many different languages, but none of them perfectly.
It may turn out to be helpful to impose a type system on the IR. This
would at least obviate the closure-cons hint, any kind of
side-effect purity hint, and probably clean up some dark corners in
the soundness of the system.
Can the compilers that one wants be generated from interpreters? In a trivial sense this is always true, since we can always cook up an interpreter that arbitrarily transforms its program argument, but it's not necessarily usefully true: is cogen saving programmer time? The experiments provide a context for what `one wants'.
Successful compiler generation depends on the exact results of complex
analyses. An innocuous code change may result in a critical value
being lifted, ruining the dynamic code. This is brittleness.
Typical examples are currying a procedure and inserting a let
binding. Working with code while maintaining good binding time
division may simply be too difficult.
How do the generated compilers compare to hand-written ones?
Hand-coded compilers are impossible to beat as there will always be
global invariants undiscovered by automatic means. But cogen
should be able to produce compilers that are globally not stupid and
are locally tight. I will hand-write compilers for some of the
languages, and compare them to the generated compilers.
Will cogen be just as complicated as advanced macro hacking in
Lisp? Binding times attempt to alleviate `@,' ridden code, but
introduce their own complications. I will make a cursory comparison
to C's macro languages: cpp, bison, make, and the
occasional gawk script...
These are contradictory goals. Current techniques do not completely automate compiler generation (and it's hard to imagine how they could). As one approaches full automation, predictability goes down as more and sophisticated analyses and inferences are required. Finding good trade-offs between competing goals is the hallmark of engineering.
Estimated tasks and weeks, roughly in order:
splitting 3 inlining 3 lifting 3 loops 2 meta-writing 4 bta 3 writing i 4 protocols 3 graphics 4 cleaning 2 tower 1 scheme 2 analysis 4 writing ii 8 polishing 4 slack 4 writing iii 4 ------- --- total 58
resulting in graduation in mid 1996.