Reflective procedural programming (phd thesis)

We show how a computational system can be constructed to "reason", effectively and consequentially, about its own inferential processes. The analysis proceeds in two parts. First, we consider the general question of computational semantics, rejecting traditional approaches, and arguing that the declarative and procedural aspects of computational symbols (what they stand for, and what behavior they engender) should be analyzed independently, in order that they may be coherently related. Second, we investigate self-referential behavior in computational processes, and show how to embed an effective procedural model of a computational calculus within that calculus (a model not unlike meta-circular interpreter, but connected to the fundamental operations of the machine in such a way as to provide, at any point in a computation, fully articulated descriptions of the state of that computation, for inspection and possible modification). In terms of the theories that result from these investigations, we present a general architecture for procedurally reflective processes, able to shift smoothly between dealing with a given subject domain, and dealing with their own reasoning processes over that domain. An instance of the general solution is worked out in the context of an applicative language. Specifically, we present three successive dialects of LISP: 1-LISP, a distillation of current practice, for comparison purposes; 2-LISP, a dialect constructed in terms of our rationalized semantics, in which the concept of evaluation is rejected in favor of independent notions of simplification and reference, and in which the respective categories of notation, structure, semantics, and behavior are strictly aligned; and 3-LISP, an extension of 2-LISP endowed with reflective powers.