“Procedural Reflection in Programming Languages”, 1982-02 ():
[implementation of Brian Cantwell Smith’s original Maclisp; see also reflection/reification, Common Lisp Object System (CLOS), lazy evaluation, meta-circular evaluator/interpreters] We show how a computational system can be constructed to “reason” effectively and consequentially about its own inference processes.
Our approach is to analyse self-referential behavior in computational systems, and to propose a theory of procedural reflection that enables any programming language to be extended in such a way as to support programs able to access and manipulate structural descriptions of their own operations and structures. In particular, one must encode an explicit theory of such a system within the structures of the system, and then connect that theory to the fundamental operations of the system in such a way as to support 3 primitive behaviors:
First, at any point in the course of a computation fully articulated descriptions of the state of the reasoning process must be available for inspection and modification. Second, it must be possible at any point to resume an arbitrary computation in accord with such (possibly modified) theory-relative descriptions. Third, procedures that reason with descriptions of the processor state must themselves be subject to description and review, to arbitrary depth. Such reflective abilities allow a process to shift smoothly between dealing with a given subject domain, and dealing with its own reasoning processes over that domain.
Crucial in the development of this theory is a comparison of the respective semantics of programming languages (such as Lisp and ALGOL) and declarative languages (such as logic and the lambda calculus); we argue that unifying these traditionally separate disciplines clarifies both, and suggests a simple and natural approach to the question of procedural reflection. More specifically, the semantical analysis of computational systems should comprise independent formulations of declarative import (what symbols stand for) and procedural consequence (what effects and results are engendered by processing them), although the two semantical treatments may, because of side-effect interactions, have to be formulated in conjunction.
When this approach is applied to a functional language it is shown that the traditional notion of evaluation is confusing and confused, and must be rejected in favour of independent notions of reference and simplification. In addition, we defend a standard of category alignment: there should be a systematic correspondence between the respective categories of notation, abstract structure, declarative semantics, and procedural consequence (a mandate satisfied by no extant procedural formalism). It is shown how a Clarification of these prior semantical and esthetic issues enables a procedurally reflective dialect to be clearly defined and readily constructed.
An instance of the general solution is worked out in the context of an applicative language, where the question reduces to one of defining an interpreted calculus able to inspect and affect its own interpretation. In particular, we consider 3 successive dialects of LISP: 1-LISP, a distillation of current practice for comparison purposes, 2-LISP, a dialect categorically and semantically rationalized with respect to an explicit theory of declarative semantics for s-expressions, and 3-LISP, a derivative of 2-LISP endowed with full reflective powers.
1-LISP, like all the dialects in current use, is at heart a first-order language, employing meta-syntactic facilities and dynamic variable scoping protocols to partially mimic higher-order functionality.
2-LISP, like Scheme and the lambda calculus, is higher-order: it supports arbitrary function designators in argument position, is lexically scoped, and treats the function position of an application in a standard extensional manner. Unlike SCHEME, however, the 2-LISP processor is based on a regimen of normalization, taking each expression into a normal-form co-designator of its referent, where the notion of normal-form is in part defined with respect to that referent’s semantic type, not (as in the case of the A-calculus) solely in terms of the further non-applicability of a set of syntactic reduction rules. 2-LISP normal-form designators are environment-independent and side-effect free; thus the concept of a closure can be reconstructed as a normal-form function designator. In addition, since normalization is a form of simplification, and is therefore designation-preserving, meta-structural expressions are not de-referenced upon normalization, as they are when evaluated. Thus we say that the 2-LISP processor is semantically flat, since it stays at a semantically fixed level (although explicit referencing and de-referencing primitives are also provided, to facilitate explicit level shifts). Finally, because of its category alignment, argument objectification (the ability to apply functions to a sequence of arguments designated collectively by a single term) can be treated in the 2-LISP base-level language, without requiring resort to meta-structural machinery.
3-LISP is straightforwardly defined as an extension of 2-LISP, with respect to an explicitly articulated procedural theory of 3-LISP embedded in 3-LISP structures. This embedded theory, called the reflective model, though superficially resembling a meta-circular interpreter, is causally connected to the workings of the underlying calculus in crucial and primitive ways. Specifically, reflective procedures are supported that bind as arguments (designators of) the continuation and environment structure of the processor that would have been in effect at the moment the reflective procedure was called, had the machine been running all along in virtue of the explicit processing of that reflective model. Because reflection may recurse arbitrarily, 3-LISP is most simply defined as an infinite tower of 3-LISP processes, each engendering the process immediately below it. Under such an account, the use of reflective procedures amounts to running programs at arbitrary levels in this reflective hierarchy. Both a straightforward implementation and a conceptual analysis are provided to demonstrate that such a machine is nevertheless finite.
The 3-LISP reflective model unifies 3 programming language concepts that have formerly been viewed as independent: meta-circular interpreters, explicit names for the primitive interpretive procedures (
EVALandAPPLYin standard Lisp dialects), and procedures that access the state of the implementation (typically provided, as part of a programming environment, for debugging purposes).We show how all such behaviors can be defined within a pure version of 3-LISP (ie. independent of implementation), since all aspects of the state of any 3-LISP process are available, with sufficient reflection, as objectified entities within the 3-LISP structural field.