[phylum]<3-LISP>DESRIVIERES>IMPL-PAPER>impl-paper-old-intro.bravo!1

Reflection, in the philosophical sense, is defined as ‘‘the mode, operation, or faculty by which the mind has knowledge of itself and its operations, or by which it deals with the ideas received from sensation and perception.’’ [OED]. A procedurally reflective programming language [Smith 82a, 84a] allows a running program to deal not only with a given subject domain but also with how that program is being run. This ability to introspect necessitates the existence of some account of how programs in the language are run. A procedural account of how a procedural programming language is processed is called a processor (or more commonly, an interpreter). The processor program is expressed in some meta language that traffics in data structures representing fragments of the object language program being processed and other structures encoding the implicit state of the processing such as environments and continuations.

It is possible to formulate accounts (processors) that are user-extensible so that not only can a program gain access to data structures that encode its normally implicit state but also use these structures to change the course of the program’s computation in ways not necessarily even expressible at the object level.

[What use is a m.l. account and hooking into it? Places on firm foundations several aspects of real language systems: extensible w.r.t. control structures, debugging systems, explicit EVAL and environments.]

The ideas of procedural reflection are quite simple. One way to see it is to take as the goal the design of a programming languages that can access, in a clean and principled way, all those implementation-level structures — e.g., the code, the symbol tables, and the execution stacks — that would be required to implement a debugger for the language within that language. The approach taken is that the user’s program is always being run indirectly by this other program, called the processor program. Information implicit at the user’s level is made explicit in this program.

The question that immediately arises is what should the meta language look like? Although it is conceivable to use a meta language different from the object level one, this is arguably uninteresting because it would not be possible to reflect on the processing of the meta level programs (unless, of course, there was a meta meta language, ...). When the object language and the meta language are one and the same, the processor program is termed a meta-circular processor program for the language. If the identity of the object and meta language is taken completely seriously {Note 0}, it follows that above each processor level there must be another processor that is ‘‘meta’’ to it. Although at each meta level the same program is being run (the code for the processor), each level has its own local state. In a procedurally reflective language, the meta-circular processor program that is build in to the language is called the reflective processor program.

Two problems are addressed in this paper. First, how is it possible to implement a procedurally reflective language, given the need for an infinite tower of processing levels? Much like the perceived threat of infinite regress posed by recursion, the infinite tower of processors can be discharged. Second, under what circumstances might efficient implementations be feasible? Different accounts (processors) will admit different implementations. One class of processors, the ‘‘tail-recursive’’ ones, have a particularly efficient implementation strategy.

The goal in the initial portion of the paper will be to expose those key ideas that underly all procedurally reflective architectures. It will be shown in the latter portion how these notions can be applied to 3-LISP, a procedurally reflective dialect of LISP [Smith 82a, Smith 84a, Smith and des Rivieres 84].

The following section looks at the infinite tower of processing, shows how it can be tamed, and outlines the properties that a processor should have if there is to be an efficient implementation. Section 3 contains a brief description of 3-LISP and introduces its form of procedural reflection. In sections 4 and 5 an efficient implementation of 3-LISP will be presented.