One of the seminal events in computing history was GuySteele's and GeraldSussman's attempt to understand CarlHewitt's ActorsModel. They did this by writing interpreters for a Lispy language that supported message passing. One result was the SchemeLanguage, but the other was the classic paper "The Art of the Interpreter"
We examine the effects of various language design decisions on the programming styles available to a user of the language, with particular emphasis on the ability to incrementally construct modular systems. At each step we exhibit an interactive MetaCircularInterpreter for the language under consideration. Each new interpreter is the result of an incremental change to a previous interpreter.
We explore the consequences of various variable binding disciplines and the introduction of side effects. We find that DynamicScoping is unsuitable for constructing procedural abstractions, but has another role as an agent of modularity, being a structured form of side effect. More general side effects are also found to be necessary to promote modular style. We find that the notion of side effect and the notion of equality (object identity) are mutually constraining; to define one is to define the other.
The interpreters we exhibit are all written in a simple dialect of LISP, and all implement LISP-like languages. A subset of these interpreters constitute a partial historical reconstruction of the actual evolution of LISP.
The paper has 3 parts (excluding the introductory material, notes, bibliography), labelled parts 0, 1, and 2. References is made to parts 3 and 4 in a separate paper. What paper would that be? Was it ever written? Is it online?Nope. From TheEvolutionOfLisp:
Part Three was to have covered order of evaluation (call-by-value versus call-by-name), and Part Four was intended to cover metalanguage, macro processors, and compilers. That these last two parts were never written is no great loss, since these topics were soon treated adequately by other researchers. While The Art of the Interpreter achieved some notoriety in the Scheme underground, it was rejected by an ACM journal.
One decomposition strategy is the packaging of common patterns of the use
of the language. For example, in Algol a for loop captures a common
pattern of if and goto statements. Packages of common patterns
are not necessarily merely abbreviations to save typing. While a simple
abbrevation has little abstraction power because a user must know what the
appreviation expands into, a good package encapsulates a higher level concept
which has meaning indepenent of its implemenatation. Once a package is
constructed the programmer can use it directly, without regard for the details
it contains, precisely because it corresponds to a single notion he uses in
dealing with the programming problem.