Run time code generation (RTCG) and traditional compilation are two ends of the same underlying optimization: factoring computations out of repeated procedure calls. Self-applicable partial evaluation (PE) is a semantics-based program transformation traditionally used for automatic compiler generation (cogen). Recently, PE has also been applied to RTCG. My approach to RTCG is to implement a composable cogen for a compiler intermediate representation. My thesis is that this approach to optimizing programs can be particularly useful for interactive graphics toolkits. I intend to demonstrate this by implementing a compiler generator tuned for RTCG, and showing how it can be used to build software that is highly abstract and yet still as fast as less general programs.
This document is organized as follows: after the summary, the first section demonstrates the connection between simple procedures and interpreted languages. The subsequent sections discuss aspects of system design in light of this. Section design presents the design of the prototype, and how it can be extended to satisfy the goals. In particular, Section 8.1 defines the IR and explains its graphical notation. Section methodology describes on what basis the implementation and examples (including a loop language and 2D graphics) are to be analysed. I conclude with a discussion of the future.
This proposal contains more material than most (including many examples and technical details), but hopefully the hierarchical organization makes it easy to skip the uninteresting material. For example, a reader who already understands the connection between interpreters, procedures, and RTCG may skip subsections 3.1 to 3.3. On the other hand, sections 8.3 to 8.7 present technical details probably only of interest to a partial evaluation specialist.
Please, do not be put-off by the page count.
This document is my thesis proposal. My advisor is Peter Lee; the committee also consists of Olivier Danvy, William Scherlis, and Andrew Witkin.
This document was preduced with jar's markup system. It reads its own format and produces HTML and Latex versions. I have concentrated mostly on the HTML end; basically I am writing and organizing assuming a hypertext browser. I apologize for the awkwardness of the paper version.
The HTML version is available at http://hopeless.mess.cs.cmu.edu:8001/nitrous/top.html. Postscript
from Latex at http://www.cs.cmu.edu/~spot/proposal.ps. It has
been published as CMU-CS-95-148, and should appear in the SCS TR archive soon.
The text of the
slides used in the public presentation is also available.
If you have corrections, suggestions, criticisms, extensions, pointers, additions, substractions, rejections, opinions, references, or any comment at all, please feel free to visit the HyperNews response form
Controlling duration of constancy is the trick.
Alan Perlis, epigram #66
Copyright 1995 Scott Draves