Lisp: A Language for Stratified Design

From ActiveArchives
Jump to: navigation, search

Research Paper (AI Memo 986, August 1987) by Hal Abelson and Gerald Sussman.

Abelson and Sussman, writing about design principles behind Scheme, their particular dialect of the LISP programming language, begin by speaking of language.

Just as everyday thoughts are expressed in natural language, and formal deductions are expressed in mathematical language, methodological thoughts are expressed in programming languages. A programming language is a medium for communicating methods, not just a means for getting a computer to perform operations — programs are written for people to read as much as they are written for machines to execute.[1]
Three common restrictions are: (1) requiring that a procedure be named and then referred to by name, rather than stating its definition at the point of reference; (2) forbidding procedures to be returned as the values of other procedures; (3) forbidding procedures to be components of such data structures as records or arrays.[2]

They position themselves against prevailing "structured programming" principles.

The well-publicized programming methodology of top-down, structured design produces systems that are organized as trees. Following this methodology, a system is designed as a predetermined combination of parts that have been carefully specified to be combined as determined. Each of the parts is itself designed separately by this same process. The methodology is flawed: if a system is to be robust it must have more generality than is needed for the particular application. The means for combining the parts must allow for after-the-fact changes in the design plan as bugs are discovered and as requirements change. It must be easy to substitute parts for one another and to vary the arrangement by which the parts are combined. This is necessary so that small changes in the problem to solved can be effected by making small changes in the design.[3]

After a specific example of code, they turn to what they call the importance of "metalinguistic abstractions".

Procedural abstractions are a source of power in creating stratified designs — we build structures by composing procedures, we abstract common patterns of usage, and we build upon this framework. But for some problems the appropriate means of combination may be awkward to express as compositions of procedures; towers of abstractions may not suffice.[4]

They list a variety of programming styles from Lisps functional, to C's imperative, through to the more exotic logical relations of a language like Prolog.

Each of these programming paradigms is legitimate, but no single paradigm is sufficient — large systems typically have some parts that are naturally described using one style and other parts that are more naturally expressed in other ways.

Part of the wonder of computation is that we have the freedom to change the framework by which the descriptions of processes are combined. If we can precisely describe a system in *any* well-defined notation, then we can build an interpreter to execute programs expressed in the new notation, or we can build a compiler to translated programs expressed in the new notation into and other programming language.

Beyond simply promoting all forms of abstraction in program design, Abelson and Sussman reveal the limits to procedural abstraction alone, noting how the means of composing these abstractions is important and may well result in "towers" if one's not careful, the vertical metaphor emphasizing both the isolation and fragility of such systems.

... [W]e must consider not only how to describe a process, but also how to describe the language in which the process is to be described. We must view our programs from two perspectives: From the perspective of the interpreter or compiler, an application program is merely data, and the interpreter or compiler operates on that data without reference to what the program is intended to express. When we write programs in the application language, we view that same data as a program with meaning in the application domain... Interpreters and compilers are just programs, but they are special programs. An application program to be interpreted or compiled is not a composition of abstraction of the language in which the interpreter is implemented or to which the compiler translates. This linguistic shift transcends the limits of abstraction.[5]
  1. Lisp: A language for stratified design, Abelson & Sussman, 1987, p.1
  2. Ibid, pp. 1-2
  3. Ibid, p. 2
  4. Ibid, p. 6
  5. Ibid, pp. 6-7
Personal tools