Structure and Interpretation of Computer Programs

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

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:

primitive expressions, which represent the simplest entities the language is concerned with,

means of combination, by which compound elements are built from simpler ones, and

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. (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.

4

 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 way to get started at programming is to examine some typical interactions with an interpreter

for the Scheme dialect of Lisp. Imagine that you are sitting at a computer terminal. You type 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 Lisp with a number

486

the interpreter will respond by printing

5

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 a list of expressions within parentheses in order to

denote procedure application, are called combinations. The leftmost element in the list is 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 placing the operator to the left of the operands is known as prefix notation, and it

may be somewhat confusing at first because it departs significantly from the customary mathematical

convention. Prefix notation has several advantages, however. One of them is that 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 leftmost element and the entire

combination is delimited by the parentheses.

A second advantage of prefix 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 Lisp 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. We can help ourselves by writing such an

expression in the form

(+ (* 3

      (+ (* 2 4)

         (+ 3 5)))

   (+ (- 10 7)

      6))

following a formatting convention known as pretty-printing, in which each long combination is

written so that the operands are aligned vertically. The resulting indentations display clearly the

structure of the expression.

6

Even with complex expressions, the interpreter always operates in the same basic cycle: It reads an

expression from the terminal, 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.

7

---

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 the Scheme dialect of Lisp, we name things with 

define

. Typing

(define size 2)

causes the interpreter to associate the value 2 with the name 

size

.

8

 Once the name 

size

 has been

associated with the number 2, we can refer to the value 2 by name:

size

2

(* 5 size)

10

Here are further examples of the use of 

define

:

(define pi 3.14159)

(define radius 10)

(* pi (* radius radius))

314.159

(define circumference (* 2 pi radius))

circumference

62.8318

Define

 is 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 Lisp

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).

9

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.

To evaluate a combination, do the following:

---