A Lisp through the Looking Glass

(as PDF)

submitted by John Sturdy for the degree of Ph.D. of the University of Bath 1991

Copyright

`Attention is drawn to the fact that the copyright of this thesis rests with its author. This copy of the thesis has been supplied on condition that anyone who consults it is understood to recognize that its copyright rests with its author and that no quotation from the thesis and no information derived from it may be published without the prior written consent of the author.'

`This thesis may be made available for consultation within the University Library and may be photocopied or lent to other libraries for the purposes of consultation.'

Summary

This thesis presents a new architecture for programming language interpreters, in which interpreters are not only first-class values, but are also arranged in a tower of meta-circular interpretation which is accessible reflectively---so that a program may modify elements of the meta-circular tower under which it runs, and thus cause changes in the manner of its own interpretation.

To facilitate such modification, we develop a representation for interpreters that splits each interpreter into a language (a collection of independently implemented constructs) and an evaluator (connecting the constructs together).

To implement such a mutable infinite meta-circular interpreter, we need another interpreter outside the tower, the meta-evaluator. We present this, along with a systematic way of linking it to the meta-circular tower. We show that a further form of meta-circularity may be introduced by bringing the meta-evaluator into the reflectively accessible part of the system; and that this may be repeated without limit, using the same techniques.

These techniques for meta-interpretation are then shown to be similar to the ``language and evaluator'' model for interpretation, and a concise version of the system is presented that uses common code for many of these functions.

Provision for reflective and mixed language facilities pervade the infrastructure of the system. We show that despite all this power, it is possible to implement such a system efficiently---well within an order of magnitude of the performance of a single-language non-reflective system---and we show how a wide range of languages may be implemented on this infrastructure, which also allows transparent mixed-language programming.

Acknowledgements

Acknowledgements are due to many:

God
for making the universe so very reflective
Julian Padget
for supervising and encouraging me
James Davenport and John ffitch
for assorted ideas and advice
Phil Yelland
for discussions of the more mathematical parts of reflection
Jim des Rivières, Olivier Danvy and Karoline Malmkjær
for comments
My family and friends, particularly Nicky Sanders
for encouragement
Harlequin Ltd
for providing facilities while I was working part-time on this thesis, and for writing the Lisp system I used
My colleagues
at Harlequin, especially Mark Tillotson, Colin Meldrum, and Pekka Pirinen, for assorted discussions on Lisp-related topics and advice on getting the fastest code from the compiler
The friars
for putting up with me at their guest-house, and particularly Brother Edmund for discussions on the metaphysics of reflection
Other research students
whose work overlapped with mine in time, particularly John, Russell, Val, Phil, Mary, Andrew, Daniel, and Isobel
And, of course, SERC
for funding the project---ever present, but usually only visible as a series of forms shadowing what was actually going on.

Table of contents

Chapters

  1. Survey
    1. The background to this thesis
    2. Reflection into context
    3. Related areas of programming language research
    4. Why do we want reflection?
    5. Approaches to reflection
    6. Why mixed languages?
    7. Summary of survey
  2. Introduction
    1. Languages, interpreters and programs
    2. Forms of reflection
    3. Program interpretation
    4. Some related concerns not addressed by this thesis
    5. Formal and informal reflection
    6. Kinds of reflection
    7. Introducing the tower
    8. Central points of this thesis
    9. Summary of introduction
  3. The closure---a building block for computation
    1. Representing computation as data
    2. Including the language in the closure
    3. The relationships between levels
    4. Procedure calling using closures
    5. Summary of closures
  4. How the tower levels are linked together
    1. Levels, strings of levels, and towers
    2. Links in each direction
    3. The umbrella of the tower.
    4. Tower computability; propagation; integrity
    5. Reifying the meta-evaluator
    6. Multidimensional ideas in single-dimensional towers
    7. What does this architecture allow us to do?
    8. Summary of links between levels
  5. Mixing languages
    1. Introducing mixed languages
    2. The requirements of mixed-language working
    3. An abstraction for programming language interpreters
    4. Writing interpreter components
    5. The overall structure of the tower
    6. What can we do using this model?
    7. Summary of mixing languages
  6. Types, abstraction, and representation
    1. Representing the abstract: concretion and abstract-types.html:extension
    2. Requirements for the type system
    3. The structure and content of our type system
    4. Types and evaluation
    5. Types and level shifts
    6. Summary of types, abstraction and representation
  7. The standard evaluator
    1. A general evaluator
    2. The structure of each level
    3. The standard evaluator code
    4. The essence of interpretation
    5. Evaluation strategies
    6. The evaluator as a link between levels
    7. How lisp-like operators evaluate their arguments
    8. Summary of the standard evaluator
  8. Mapping linguistic and semantic features onto the reflective system
    1. Procedure application
    2. Reflective and non-reflective calls
    3. Flow control
    4. Variables, bindings and assignments
    5. Types
    6. Objects and messages, and actors
    7. Parallelism
    8. Declarative languages
    9. Changing the implementation of features dynamically
    10. Evaluation order---strict or lazy
    11. Special substrate features for specific languages
    12. Summary of building languages with reflection
  9. A suitable language for the standard interpreter
    1. Requirements
    2. The implementation of the base language
    3. The real set of primitive operators
    4. Operators for reification and reflection
    5. Summary of the base language
  10. A model meta-evaluator
    1. Requirements for the meta-evaluator
    2. An introduction to platypus
    3. The pull of efficiency
    4. Representation strategies
    5. Mapping
    6. How the meta-evaluator works
    7. Summary of the model meta-evaluator
  11. The meta-evaluator
    1. Platypus89 - a tower evaluator in lisp
    2. The essence of reflective tower evaluation
    3. Summary of the meta-evaluator code.
    4. Other parts of the meta-evaluator
    5. Operators and their shadows
    6. Definition of operators
    7. The c implementation of platypus
    8. Summary of the meta-evaluator
  12. Results
    1. Overview of results
    2. The design ideas
    3. The implementations
    4. Time and space used
    5. Changes needed to support non lisp-like languages
    6. General results
    7. Summary of results
  13. History and future; related work; observations
    1. Other recent developments in interpretation
    2. Possible further work
    3. Higher-level tools
    4. Further applications
    5. Summary of history and future
  14. Reflections
    1. What did I find?
    2. Human reflection
    3. Reflective changes through other artifices
    4. Tower reflective interpretation and other models of computation
    5. Summary of reflections
  15. Summaries
    1. Survey
    2. Introduction
    3. Closures
    4. Links between levels
    5. Languages in closures
    6. The standard evaluator
    7. Types, abstraction, and representation
    8. Building languages with reflection
    9. The base language
    10. Reflective operators
    11. A model for the meta-evaluator
    12. An implementation of the meta-evaluator
    13. Results
    14. History and future
    15. Reflections
    16. Summary

Appendices

  1. Bibliography

Tailpiece

As a tailpiece, the Escher picture used for the PostScript timing tests is presented here:

Escher's ``Circle Limit''
Submitted, Examined And Accepted: 1991
Contact me