Structure and Interpretation of Computer Programs, 2nd ed.  Harold Abelson, Geralde Jay Sussman, wth Julie Sussman.

The language possesses unique features that make it an excellent medium for studying important programming constructs and data structures and for relating them to the linguistic features that support them.  The most significant of these features is the fact that Lisp descriptions of processes, called procedures, can themselves be represented and manipulated as Lisp data.  The importance of this is that there are powerful program-design techniques that rely on the ability to blur the traditional distinction between ‘passive’ data and ‘active’ processes.  As we shall discover, Lisp’s flexibility in handling procedures as data also makes Lisp an excellent language for writing programs that must manipulate other programs as data, such as interpreters and compilers that support computer languages.” p 4.

A powerful programming language is more than just a means for instructing a computer to perform tasks.  The language also serves as a framework within which we organize our ideas about processes.  Thus, when we describe a language, we should pay particular attention to the means that the language provides for combining simple ideas to form more complex ideas.  Each powerful language has three mechanisms for accomplishing this:
   • primitive expressions, which represent the simplest entities the language is concerned with,
   • means of combination, by which compound elements are built from simpler ones
   • means of abstraction, by which compound elements can be named and manipulated as units.
In programming, we deal with two kinds of elements: procedures and data.  In-formally, data is ‘stuff’ that we want to manipulate, and procedures are descriptions of the rules for manipulating the data.  p 4.

One easy way to get started at programming is to examine some typical interactions with an interpreter.  Imagine that you are sitting at a computer terminal.  You type an expression, and the interpreter responds by displaying the result of its evaluating the expression.  p 5.

Expressions formed by delimiting a list of expressions within parentheses in order to denote procedure application, are called combinations.  The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.  p 6.

A critical aspect of a programming language is the means it provides for using names to refer to computational objects.  We say that the name identifies a variable whose value is the object.  p 7.

Substitution model of evaluation.  To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument. p p 14.

In general, when modeling phenomena in science and engineering, we begin with simplified, incomplete models. As we examine things in greater detail, these simple models become inadequate and must be replaced by more refined models. The substitution model is no exception.  In particular, when we address in chapter 3 the use of procedures with “mutable data,” we will see that the substitution model breaks down and must be replaced by a more complicated model of procedure application. p p 15.

The substitution model reveals a shape of expansion followed by contraction, indicated by the arrow in figure 1.3. The expansion occurs as the process builds up a chain of deferred operations (in this case, a chain of multiplications).  The contraction occurs as the operations are actually performed.  This type of process, characterized by a chain of deferred operations, is called  a recursive process.  Carrying out this process requires that the interpreter keep track of the operations to be performed later on.  p 34.

The second process does not grow and shrink.  An iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate.  p 34.

In general, programming languages impose restrictions on the way in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the “rights and privileges” of first-class elements are:
   • They may be named by variables.
   • They may be passed as arguments to procedures.
   • They may be returned as the results of procedures.
   • They may be included in data structures.
Lisp, unlike other common programming languages, awards procedures full first-class status.  This poses challenges for efficient implementation, but the resulting gain in expressive power is enormous.p 76-7.

Often the different data types are not completely independent, and there may be ways by which objects of one type may be viewed as being of another type.  This process is called coercion.  p 195.

In general, we can implement this idea by designing coercion procedures that transform an object of one type into an equivalent object of another type.  p 195.

When asked to apply an operation, we first check whether the operation is definedfor the argument’s types…If so, we dispatch the procedure found in the operation-and-type table.  Otherwise, we try coercion… We check the coercion table to see if objects of the first type can be coerced to the second type.  If so, we coerce the first argument and try the operation again.  If objects of the first type cannot in general be coerced to the second type, we try the coercion the other way aroundto see if there is a way to coerce the second argument to the type of the first argument.  Finally, if there is no known way to coerce either type to the other type, we give up. p 196.

complex ß real ß rational ß integer.  Figure 2.25  A tower of types.  p 197.

What we actually have is a so-called hierarchy of types, in which, for example, integers are a subtype of rational numbers (i.e., any operation that can be applied to a rational number can automatically be applied to an integer).  Conversely, we say that rational numbers form a supertype of integers. The particular hierarchy we have here is of a very simple kind, in which each type has at most one supertype and at most one subtype. Such a structure, called a tower, is illustrated in figure 2.25.  p 197.

Inadequacies of hierarchies.  If the data types in our system can be naturally arranged in a tower, this greatly simplifies the problems of dealing with generic operations on different types… Unfortunately, this is not the case. Figure 2.26 illustrates a more complex arrangement of mixed types, this one showing relations among different types of geometric figures. We see that, in general, at type may have more than one subtype… In addition, a type may have more than one supertype.  This multiple supertypes issue is particularly thorny, since it means that there is no unique way to “raise” a type in the hierarchy.  Finding the “correct” supertype in which to apply an operation to an object may involve considerable searching through the entire type network on the part of a procedure… Since there generally are multiple subtypes for a type, there is a similar problem in coercing a value “down” the type hierarchy.  p 198-9.

3.1.2 The Benefits of Introducing Assignment.  As we shall see, introducing assignment into our programming language leads us into a thicket of difficult conceptual issues.  p 225.

3.1.3 The Costs of Introducing Assignment.  As we have seen, the set! operation enables us to model objects that have local state.  However, this advantage comes at a price.  Our programming language can no longer be interpreted in terms of the substitution model of procedure application… Moreover, no simple model with “nice” mathematical properties can be an adequate framework for dealing with objects and assignment in programming languages.  p 229.

So long as we do not use assignments, two evaluations of the same procedure with the same arguments will produce the same result, so that procedures can be viewed as computing mathematical functions.  Programming without any use of assignments, as we did throughout the first two chapters of this book, is accordingly known as functional programming.  p 230.

The trouble here is that substitution is based ultimately on the notion that the symbols in our language are essentially names for values.  But as soon as we introduce set! and the idea that the value of a variable can change, a variable can no longer be simply a name.  Now a variable somehow refers to a place where a value can be stored, and the value stored at this place can change.  In section 3.2 we will see how environments play this role of “place” in our computational model.  p 231.

Sameness and change.  The issue surface here is more profound than the mere breakdown of a particular model of computation.  As soon as we introduce change into our computational models, many notions that were previously straightforward become problematical.  Consider the concept of two things being ‘the same.'  p 232.

A language that supports the concept that ‘equals can be substituted for equals’ in an expression without changing the value of the expression is said to be referentially transparent.  Referential transparency is violated when we include set! in our computer language.  This makes it tricky to determine when we can simplify expressions by substituting equivalent expressions.  Consequently, reasoning about programs that use assignment becomes drastically more difficult.
  Once we forgo referential transparency, the notion of what it means for computational objects to be ‘the same’ becomes difficult to capture in a formal way.  Indeed, the meaning of ‘same’ in the real world that our programs model is hardly clear in itself.  In general, we can determine that two apparently identical objects are indeed ‘the same one’ only by modifying one object and then observing whether to other object has changed in the same way.  But how can we tell if an objects has ‘changed’ other than by observing the ‘same’ object twice and seeing whether some property of the object differs from one observation to the next?  Thus, we cannot determine ‘change’ without some a priori notion of ‘sameness’, and we cannot determine sameness without observing the effects of change.  p 232-3.

In contrast to functional programming, programming that makes extensive use of assignment is known as imperative programming. In addition to raising complications about computational models, programs written in imperative style are susceptible to bugs that cannot occur in functional programs.  p 234.

In general, programming with assignment forces us to carefully consider the relative orders of the assignments to make sure that each statement is using the correct version of the variables that have been changed.  This issue simply does not arise in functional programs. [1]p 235.

3.2 The Environment Model of Evaluation.  When we introduced compound procedures in chapter 1, we used the substitution model of evaluation (section 1.1.5) to define what is meant by applying a procedure to arguments:
    • To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.
   Once we admit assignment into our programming language, such a definition is no longer adequate. In particular, section 3.1.3 argued that, in the presence of assignment, a variable can longer be considered to be merely a name for a value. Rather, a variable must somehow designate a “place” in which values can be stored. In our new model of evaluation, these places will be maintained in structures called environments.
   An environment is a sequence of frames. Each frame is a table (possibly empty) of bindings, which associate variable names with their corresponding values. (A single frame may contain at most one binding for any variable.) Each frame also has a pointer to its enclosing environment, unless, for the purpose of discussion, the frame is considered to be global. The value of a variable with respect to an environment is the value given by the binding for that variable. If no frame in the sequence specifies a binding for the variable, then the variable is said to be unbound in the environment.   p 236-7.

The environment is crucial to the evaluation process, because it determines the context in which an expression should be evaluated.  Indeed, one could say that expressions in a programming language do not, in themselves, have any meaning.  Rather, an expression acquires a meaning only with respect to some environment in which it is evaluated.  p 237.

We also specify that defining a symbol using define creates a binding in the current environment frame and assigns to the symbol the indicated value.  Finally, we specify the behavior of set!, the operation that forced us to introduce the environment model in the first place.  Evaluating the expressions (set! <variable> <value>) in some environment locates the binding of the variable in the environment and changes the binding to indicate the new value.  That is, one finds the first frame in the environment that contains a binding for the variable and modifies that frame.  If the variable is unbound in the environment, then set! signals an error.  p 240-1.

Chapter 4.  Metalinguistic Abstraction.  In our study of program design, we have seen that expert programmers control the complexity of their designs with the same general techniques used by designers of all complex systems.  They combine primitive elements to form compound objects, they abstract compound objects to form higher-level building blocks, and they preserve modularity by adopting appropriate large-scale views of system structure.  In illustrating these techniques, we have used Lisp as a language for describing processes and for constructing computational data objects and processes to model complex phenomena in the real world.  However, as we confront increasingly complex problems, we will find that Lisp, or indeed any fixed programming language, is not sufficient for our needs.  We must constantly turn to new languages in order to express our ideas more effectively. Establishing new languages is a powerful strategy for controlling complexity in engineering design; we can often enhance our ability to deal with a complex problem by adopting a new language that enables us to describe (and hence to think about) the problem in a different way, using primitives, means of combination, and means of abstraction that are particularly well suited to the problem at hand. [2]
   Programming is endowed with a multitude of languages.  There are physical languages, such as the machine languages for particular computers.  These languages are concerned with the representation of data and control in terms of individual bits of storage and primitive machine instructions.  The machine-language programmer is concerned with using the given hardware to erect systems and utilities for the efficient implementation of resource-limited computation.  High-level languages, erected on a machine-language substrate, hide concerns about the representation of data as collections of bits and the representation of programs as sequences of primitive instructions.  These languages have means of combination and abstraction, such as procedure definition, that are appropriate to the larger-scale organization of systems.
   Metalinguistic abstraction—establishing new languages—plays an important role in all branches of engineering design.  It is particularly important to computer programming, because in programming not only can we formulate new languages but we can also implement these languages by constructing evaluators.  An evaluator (or interpreter) for a programming language is a procedure that, when applied to an expression of the language, performs the actions required to evaluate the expression.
   It is no exaggeration to regard this as the most fundamental idea in programming:
   The evaluator, which determines the meaning of expressions in a programming language, is just another program.
   To appreciate this point is to change our image of ourselves as programmers.  We come to see ourselves as designers of languages, rather than only users of languages designed by others.
   In fact, we can regard almost any program as the evaluator for some language.  For instance, the polynomial manipulation system of section 2.5.3 embodies the rules of polynomial arithmetic and implements them in terms of operations on list-structured data.  If we augment this system with procedures to read and print polynomial expressions, we have the core of a special-purpose language for dealing with problems in symbolic mathematics.  The digital-logic simulator of section 3.3.4 and the constraint propagator of section 3.3.5 are legitimate languages in their own right, each with its own primitives, means of combination, and means of abstraction.  Seen from this perspective, the technology for coping with large-scale computer systems merges with the technology for building new computer languages, and computer science itself becomes no more (and no less) than the discipline of construction appropriate descriptive languages.  p 359-61.

Section 4.3 implements a more ambitious linguistic change, whereby expressions have many values, rather than just a single value.  In this language of nondeterministic computing, it is natural to express processes that generate all possible values for expressions and then search for those values that satisfy certain constraints.  In terms of models of computation and  time, this is like having time branch into a set of “possible futures” and then searching the appropriate time lines.  With our nondeterministic evaluator, keeping track of multiple values and performing searches are handled automatically by the underlying mechanisms of the language. [3]

[1] In view of this, it is ironic that introductory programming is most often taught in a highly imperative style.  This may be a vestige of the belief, common throughout the 1960s and 1970s, that programs that call procedures must inherently be les efficient than programs that perform assignments. (Steele (1997) debunks this argument.)  Alternatively it may reflect a view that step-by-step assignment is easier for beginners to visualize than procedure call.  Whatever the reason, it often saddles beginning programmers with “should I set this variable before or after that one” concerns that can complicate programming and obscure the important ideas.

[2] The same idea is pervasive throughout all engineering.  For example, electrical engineers use many different languages for describing circuits.  Two of these are the language of electrical networks and the language of electrical systems.