Structure and Interpretation of Computer Programs

The world's best computer science textbook, now for Snap!

View the Project on GitHub Bluebaritone21/Wizard-Book

Chapter 1

Building Abstractions with Procedures

The acts of the mind, wherein it exerts its power over simple ideas, are chiefly these three: 1. Combining several simple ideas into one compound one, and thus all complex ideas are made. 2. The second is bringing two ideas, whether simple or complex, together, and setting them by one another so as to take a view of them at once, without uniting them into one, by which it gets all its ideas of relations. 3. The third is separating them from all other ideas that accompany them in their real existence: this is called abstraction, and thus all its general ideas are made.

~ John Locke, An Essay Concerning Human Understanding (1690)

We are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells.

A computational process is indeed much like a sorcerer’s idea of a spirit. It cannot be seen or touched. It is not composed of matter at all. However, it is very real. It can perform intellectual work. It can answer questions. It can affect the world by disbursing money at a bank or by controlling a robot arm in a factory. The programs we use to conjure processes are like a sorcerer’s spells. They are carefully composed from symbolic expressions in arcane and esoteric programming languages that prescribe the tasks we want our processes to perform.

A computational process, in a correctly working computer, executes programs precisely and accurately. Thus, like the sorcerer’s apprentice, novice programmers must learn to understand and to anticipate the consequences of their conjuring. Even small errors (usually called bugs or glitches) in programs can have complex and unanticipated consequences.

Fortunately, learning to program is considerably less dangerous than learning sorcery, because the spirits we deal with are conveniently contained in a secure way. Real-world programming, however, requires care, expertise, and wisdom. A small bug in a computer-aided design program, for example, can lead to the catastrophic collapse of an airplane or a dam or the self-destruction of an industrial robot.

Master software engineers have the ability to organize programs so that they can be reasonably sure that the resulting processes will perform the tasks intended. They can visualize the behavior of their systems in advance. They know how to structure programs so that unanticipated problems do not lead to catastrophic consequences, and when problems do arise, they can debug their programs. Well-designed computational systems, like well-designed automobiles or nuclear reactors, are designed in a modular manner, so that the parts can be constructed, replaced, and debugged separately.

Programming in Snap!

We need an appropriate language for describing processes, and we will use for this purpose the programming language Snap!. Just as our everyday thoughts are usually expressed in our natural language (such as English, French, or Japanese), and descriptions of quantitative phenomena are expressed with mathematical notations, our procedural thoughts will be expressed in Snap!. Snap! was invented around 2008 as a modification of Scratch that added recursion equations, making it more suitable for college students. The language was conceived by Jens Mönig and Brian Harvey, and is documented in Dr. Harvey’s paper, “Why do we Need to Learn this Baby Language?” (Harvey 2019)

Despite its inception as a mod of Scratch, Snap! is its own language. Modern Snap! was rewritten from the ground up. Snap! is maintained almost exclusively by Jens Mönig, with the cloud storage systems maintained by a small team and paid for by him. Snap! was designed to provide symbol-manipulating capabilities for attacking programming problems such as the symbolic differentiation and integration of algebraic expressions. It included for this purpose new first-class lists and blocks, which set it apart from most other block-based languages.

If Snap! is not a mainstream language, why are we using it as the framework for our discussion of programming? Because 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 Snap! descriptions of processes, called procedures, can themselves be represented and manipulated as Snap! 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, Snap!’s flexibility in handling procedures as data makes it one of the most convenient languages in existence for exploring these techniques. The ability to represent procedures as data also makes Snap! an excellent language for writing programs that must manipulate other programs as data, such as the interpreters and compilers that support computer languages. Above and beyond these considerations, programming in Snap! is great fun.

1.1

The Elements of Programming

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. Every powerful language has three mechanisms for accomplishing this:

In programming, we deal with two kinds of elements: procedures and data. (Later we will discover that they are really not so distinct.) Informally, data is “stuff” that we want to manipulate, and procedures are descriptions of the rules for manipulating the data. Thus, any powerful programming language should be able to describe primitive data and primitive procedures and should have methods for combining and abstracting procedures and data.

In this chapter we will deal only with simple numerical data so that we can focus on the rules for building procedures. In later chapters we will see that these same rules allow us to build procedures to manipulate compound data as well.

1.1.1

Expressions

One easy to get started at programming is to examine some typical interactions with Snap!. Imagine that you are sitting at a computer. You drag together an expression, and the interpreter responds by displaying the result of its evaluating that expression.

One kind of primitive expression you might type is a number. (More precisely, the expression that you type consists of the numerals that represent the number in base 10.) If you present Snap! with a number

((486) + () $<:>)

the interpreter will respond by printing

486

Expressions representing numbers may be combined with an expression representing a primitive procedure (such as + or *) to form a compound expression that represents the application of the procedure to those numbers. For example:

((137) + (349) $<:>) //486
((1000) - (334)) //666
((5) * (99) $<:>) //495
((10) / (5)) //2
((2.7) + (10) $<:>) //12.7

Expressions such as these, formed by delimiting values inside a block, are called combinations. The block is also called the operator, and the other elements are called operands. 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.

The convention of making the operator be represented is very useful partially because it can accommodate procedures that may take an arbitrary number of arguments, as in the following examples:

((21) + (35) + (12) + (7) $<:>) //75

((25) * (4) * (12) $<:>) //1200

No ambiguity can arise, because the operator is always the outermost block. (You can obtain these multi-input variants by clicking the little arrows on the right edge of the block)

A second advantage of of this notation is that it extends in a straightforward way to allow combinations to be nested, that is, to have combinations whose elements are themselves combinations:

(((3) * (5) $<:>) + ((10) - (6)) $<:>) //19

There is no limit (in principle) to the depth of such nesting and to the overall complexity of the expressions that the Snap! interpreter can evaluate. It is we humans who get confused by still relatively simple expressions such as

(((3) * (((2) * (4) $<:>) + (3) + (5) $<:>) $<:>) + ((10) - (7)) + (6) $<:>)

which the interpreter would readily evaluate to be 57. Luckily, Snap! uses a feature called zebra striping, where blocks alternate between light and dark, to help us keep track of the nesting of blocks.

Even with complex expressions, the interpreter always operates in the same basic cycle: it detects when the user clicks a block, evaluates the expression, and prints the result. This mode of operation is often expressed by saying that the interpreter runs in a read-eval-print loop. Observe in particular that it is not necessary to explicitly instruct the interpreter to print the value of the expression.

1.1.2

Naming and the Environment

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.

In Snap!, we name things with the Make a variable button (found in the “Variables” category). Creating a variable (size :: variables) and running set [size V] to [2] causes the interpreter to associate the value 2 with the name size. Once the name size has been associated with the number 2, we can refer to the value 2 by name:

(size :: variables) //2
((5) * (size :: variables) $<:>) // 10

Here are further examples of the use of set [ V] to []:

set [tau V] to [6.283185]

set [radius V] to [10]

( (0.5) * ((tau) * (radius) $<:>) * (radius) $<:>) // 314.159

set [circumference V] to ((tau) * (radius) $<:>)

(circumference) //62.8318

Make a variable and set [ V] to [] are our language’s simplest means of abstraction, for it allows us to use simple names to refer to the results of compound operations, such as the (circumference) computed above. In general, computational objects may have very complex structures, and it would be extremely inconvenient to have to remember and repeat their details each time we want to use them. Indeed, complex programs are constructed by building, step by step, computational objects of increasing complexity. The interpreter makes this step-by-step program construction particularly convenient because name-object associations can be created incrementally in successive interactions. This feature encourages the incremental development and testing of programs and is largely responsible for the fact that a Snap! program usually consists of a large number of relatively simple procedures.

It should be clear that the possibility of associating values with symbols and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment (more precisely the global environment, since we will see later that a computation may involve a number of different environments).

1.1.3

Evaluating Combinations

One of our goals in this chapter is to isolate issues about thinking procedurally. As a case in point, let us consider that, in evaluating combinations, the interpreter is itself following a procedure.

Even this simple rule illustrates some important points about processes in general. First, observe that the first step dictates that in order to accomplish the evaluation process for a combination we must first perform the evaluation process on each element of the combination. Thus, the evaluation rule is recursive in nature; that is, it includes, as one of its steps, the need to invoke the rule itself.

Notice how succinctly the idea of recursion can be used to express what, in the case of a deeply nested combination, would otherwise be viewed as a rather complicated process. For example, evaluating

(((2) + ((4) * (6) $<:>) $<:>) * ((3) + (5) + (7) $<:>) $<:>)

requires that the evaluation rule be applied to four different combinations. We can obtain a picture of this process by representing the combination in the form of a tree, as shown in figure 1.1. Each combination is represented by a node with branches corresponding to the operator and the operands of the combination stemming from it. The terminal nodes (that is, nodes with no branches stemming from them) represent either operators or numbers. Viewing evaluation in terms of the tree, we can imagine that the values of the operands percolate upward, starting from the terminal nodes and then combining at higher and higher levels. In general, we shall see that recursion is a very powerful technique for dealing with hierarchical, treelike objects. In fact, the “percolate values upward” form of the evaluation rule is an example of a general kind of process known as tree accumulation.

A depiction of a tree Figure 1.1: Tree representation, showing the value of each subcombination.

For people whose browsers can't render images 
390
| (() * () $<:>)
+ 26
| | (() + () $<:>)
| | 2
| + 24
| | | (() * () $<:>)
| | | 4
| | | 6
+ 15
| | (() + () $<:>)
| | 3
| | 5
| | 7

Next, observe that the repeated application of the first step brings us to the point where we need to evaluate, not combinations, but primitive expressions such as numerals, built-in operators, or other names. We take care of the primitive cases by stipulating that

We may regard the second rule as a special case of the third one by stipulating that symbols such as (() + () @<:>) and (() * () @<:>) are also included in the global environment, and are associated with the sequences of machine instructions that are their “values.” The key point to notice is the role of the environment in determining the meaning of the symbols in expressions. In an interactive language such as Snap!, it is meaningless to speak of the value of an expression such as ((x) + (1) $<:>) without specifying any information about the environment that would provide a meaning for the symbol (x) (or even for the symbol (() + () $<:>)). As we shall see in chapter 3, the general notion of the environment as providing a context in which evaluation takes place will play an important role in our understanding of program execution.

Notice that the evaluation rule given above does not handle definitions. For instance, evaluating set [x V] to [3] does not apply set [ V] to [] to two arguments, one of which is the value of the symbol (x) and the other of which is 3, since the purpose of the define is precisely to associate (x) with a value. (That is, set [x V] to [3] is not a combination.)

Such exceptions to the general evaluation rule are called special forms. set [ V] to [] is the only example of a special form that we have seen so far, but we will meet others shortly. Each special form has its own evaluation rule. The various kinds of expressions (each with its associated evaluation rule) constitute the syntax of the programming language. In comparison with most other programming languages, Snap! has a very simple syntax; that is, the evaluation rule for expressions can be described by a simple general rule together with specialized rules for a small number of special forms.

1.1.4

Compound Procedures

We have identified in Lisp some of the elements that must appear in any powerful programming language:

Now we will learn about procedure definitions, a much more powerful abstraction technique by which a compound operation can be given a name and then referred to as a unit.

We begin by examining how to express the idea of “squaring.” We might say, “To square something, multiply it by itself.” This is expressed in our language by pressing Make a block and building the script

{(square (x)::operators)}::define+
report ((x) * (x) $<:>)

We can understand this in the following way:

{(square (x)::operators)}::define+ // to square something
report ((x) * (x) $<:>) // multiply it by itself

(Make sure to press Ok)

We have here a compound procedure, which has been given the name (square ()::operators). The procedure represents the operation of multiplying something by itself. The thing to be multiplied is given a local name, (x), which plays the same role that a pronoun plays in natural language. Evaluating the definition creates this compound procedure and associates it with the name square.

The general form of a procedure definition is

A Snap<i>!</i> block definition

The <label> is a symbol to be associated with the procedure definition in the environment. The <formal parameters> are the names used within the body of the procedure to refer to the corresponding arguments of the procedure. The <body> is an expression that will yield the value of the procedure application when the formal parameters are replaced by the actual arguments to which the procedure is applied. The <label> and the <formal parameters> are displayed in a block, just as they would be in an actual call to the procedure being defined.

Having defined (square ()::operators), we can now use it:

(square (21)::operators) //441
(square ((2) + (5) $<:>)::operators) //49
(square (square (3)::operators)::operators) //81

We can also use square as a building block in defining other procedures. For example, (x^{2} + y^{2}) can be expressed as ((square (x)::operators) + (square (y)::operators) $<:>). We can easily define a procedure (sum-of-squares () ()::operators) that, given any two numbers as arguments, produces the sum of their squares:

{(sum-of-squares (x) (y)::operators)}::define+
report ((square (x)::operator) + (square (y)::operator) $<:>)

Now we can use (sum-of-squares () ()::operators) as a building block in constructing further procedures

{(f (a))}::define+
report (sum-of-squares ((a) + (1) $<:>) ((a) * (2) $<:>))

(f (5)) //136

Compound procedures are used in exactly the same way as primitive procedures. Indeed, one could not tell by looking at the definition of sum-of-squares given above whether square was built into the interpreter, like + and *, or defined as a compound procedure.

1.1.5

The Substitution Model for Procedure Application

Contents | Previous: Acknowledgments