Lightweight Languages for Interactive Graphics

Abstract

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.

Contents

  1. top
    1. abstract
    2. contents
    3. road-map
    4. preface
    5. feedback
    6. cute quote
  2. summary
  3. RTCG and compilation
    1. a power procedure
    2. a shading procedure
    3. a shading language
  4. compiler generation
  5. alternatives
    1. precompilation
    2. buffering and APL
    3. self application and cogen
    4. lisp and macros
  6. composing languages
    1. emacs
    2. reflection
    3. layers
  7. related work
  8. system design
    1. root language
      1. eg zip
      2. eg compose
    2. interface to cogen
    3. binding time analysis
      1. simple
      2. pairs
      3. first-order jumps and constants
      4. higher order jumps
      5. spines
    4. generation pass
      1. simple
      2. pairs
      3. constants
      4. general control flow
    5. variable splitting
    6. lift compiler
    7. eg environments
  9. methodology
    1. questions
    2. plan
    3. schedule
  10. preliminary results
    1. loop language
    2. protocol kit
    3. 2D graphics
      1. bcopy and the trick
      2. partially static bit-fields
  11. the future
  12. bibliography
  13. end notes

Map

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.

Preface

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.

Feedback

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

Cute Quote

Copyright 1995 Scott Draves