Structure and Interpretation of Computer Programs

            2.3.2  Example: Symbolic Differentiation

            2.3.3  Example: Representing Sets

            2.3.4  Example: Huffman Encoding Trees

        2.4  Multiple Representations for Abstract Data

            2.4.1  Representations for Complex Numbers

            2.4.2  Tagged data

            2.4.3  Data-Directed Programming and Additivity

        2.5  Systems with Generic Operations

            2.5.1  Generic Arithmetic Operations

            2.5.2  Combining Data of Different Types

            2.5.3  Example: Symbolic Algebra

    3  Modularity, Objects, and State

        3.1  Assignment and Local State

            3.1.1  Local State Variables

            3.1.2  The Benefits of Introducing Assignment

            3.1.3  The Costs of Introducing Assignment

        3.2  The Environment Model of Evaluation

            3.2.1  The Rules for Evaluation

            3.2.2  Applying Simple Procedures

            3.2.3  Frames as the Repository of Local State

            3.2.4  Internal Definitions

        3.3  Modeling with Mutable Data

            3.3.1  Mutable List Structure

            3.3.2  Representing Queues

            3.3.3  Representing Tables

            3.3.4  A Simulator for Digital Circuits

            3.3.5  Propagation of Constraints

        3.4  Concurrency: Time Is of the Essence

            3.4.1  The Nature of Time in Concurrent Systems

            3.4.2  Mechanisms for Controlling Concurrency

        3.5  Streams

            3.5.1  Streams Are Delayed Lists

            3.5.2  Infinite Streams

            3.5.3  Exploiting the Stream Paradigm

            3.5.4  Streams and Delayed Evaluation

            3.5.5  Modularity of Functional Programs and Modularity of Objects

    4  Metalinguistic Abstraction

        4.1  The Metacircular Evaluator

            4.1.1  The Core of the Evaluator

            4.1.2  Representing Expressions

            4.1.3  Evaluator Data Structures

            4.1.4  Running the Evaluator as a Program

            4.1.5  Data as Programs

            4.1.6  Internal Definitions

            4.1.7  Separating Syntactic Analysis from Execution

        4.2  Variations on a Scheme -- Lazy Evaluation

            4.2.1  Normal Order and Applicative Order

            4.2.2  An Interpreter with Lazy Evaluation

            4.2.3  Streams as Lazy Lists

---

        4.3  Variations on a Scheme -- Nondeterministic Computing

            4.3.1  Amb and Search

            4.3.2  Examples of Nondeterministic Programs

            4.3.3  Implementing the 

Amb

 Evaluator

        4.4  Logic Programming

            4.4.1  Deductive Information Retrieval

            4.4.2  How the Query System Works

            4.4.3  Is Logic Programming Mathematical Logic?

            4.4.4  Implementing the Query System

    5  Computing with Register Machines

        5.1  Designing Register Machines

            5.1.1  A Language for Describing Register Machines

            5.1.2  Abstraction in Machine Design

            5.1.3  Subroutines

            5.1.4  Using a Stack to Implement Recursion

            5.1.5  Instruction Summary

        5.2  A Register-Machine Simulator

            5.2.1  The Machine Model

            5.2.2  The Assembler

            5.2.3  Generating Execution Procedures for Instructions

            5.2.4  Monitoring Machine Performance

        5.3  Storage Allocation and Garbage Collection

            5.3.1  Memory as Vectors

            5.3.2  Maintaining the Illusion of Infinite Memory

        5.4  The Explicit-Control Evaluator

            5.4.1  The Core of the Explicit-Control Evaluator

            5.4.2  Sequence Evaluation and Tail Recursion

            5.4.3  Conditionals, Assignments, and Definitions

            5.4.4  Running the Evaluator

        5.5  Compilation

            5.5.1  Structure of the Compiler

            5.5.2  Compiling Expressions

            5.5.3  Compiling Combinations

            5.5.4  Combining Instruction Sequences

            5.5.5  An Example of Compiled Code

            5.5.6  Lexical Addressing

            5.5.7  Interfacing Compiled Code to the Evaluator

    References

    List of Exercises

    Index

[Go to first, previous, next page;   contents;   index]

---

[Go to first, previous, next page;   contents;   index]

 

Foreword

Educators, generals, dieticians, psychologists, and parents program. Armies, students, and some

societies are programmed. An assault on large problems employs a succession of programs, most of

which spring into existence en route. These programs are rife with issues that appear to be particular to

the problem at hand. To appreciate programming as an intellectual activity in its own right you must

turn to computer programming; you must read and write computer programs -- many of them. It

doesn’t matter much what the programs are about or what applications they serve. What does matter is

how well they perform and how smoothly they fit with other programs in the creation of still greater

programs. The programmer must seek both perfection of part and adequacy of collection. In this book

the use of ‘‘program’’ is focused on the creation, execution, and study of programs written in a dialect

of Lisp for execution on a digital computer. Using Lisp we restrict or limit not what we may program,

but only the notation for our program descriptions.

Our traffic with the subject matter of this book involves us with three foci of phenomena: the human

mind, collections of computer programs, and the computer. Every computer program is a model,

hatched in the mind, of a real or mental process. These processes, arising from human experience and

thought, are huge in number, intricate in detail, and at any time only partially understood. They are

modeled to our permanent satisfaction rarely by our computer programs. Thus even though our

programs are carefully handcrafted discrete collections of symbols, mosaics of interlocking functions,

they continually evolve: we change them as our perception of the model deepens, enlarges, generalizes

until the model ultimately attains a metastable place within still another model with which we struggle.

The source of the exhilaration associated with computer programming is the continual unfolding

within the mind and on the computer of mechanisms expressed as programs and the explosion of

perception they generate. If art interprets our dreams, the computer executes them in the guise of 

programs!

For all its power, the computer is a harsh taskmaster. Its programs must be correct, and what we wish

to say must be said accurately in every detail. As in every other symbolic activity, we become

convinced of program truth through argument. Lisp itself can be assigned a semantics (another model,

by the way), and if a program’s function can be specified, say, in the predicate calculus, the proof

methods of logic can be used to make an acceptable correctness argument. Unfortunately, as programs

get large and complicated, as they almost always do, the adequacy, consistency, and correctness of the

specifications themselves become open to doubt, so that complete formal arguments of correctness

seldom accompany large programs. Since large programs grow from small ones, it is crucial that we

develop an arsenal of standard program structures of whose correctness we have become sure -- we

call them idioms -- and learn to combine them into larger structures using organizational techniques of

proven value. These techniques are treated at length in this book, and understanding them is essential

to participation in the Promethean enterprise called programming. More than anything else, the

uncovering and mastery of powerful organizational techniques accelerates our ability to create large,

significant programs. Conversely, since writing large programs is very taxing, we are stimulated to

invent new methods of reducing the mass of function and detail to be fitted into large programs.

---