Structure and Interpretation of Computer Programs

12

 Observe that there are two different operations being combined here: we are creating the procedure,

and we are giving it the name 

square

. It is possible, indeed important, to be able to separate these

two notions -- to create procedures without naming them, and to give names to procedures that have

already been created. We will see how to do this in section 1.3.2. 

13

 Throughout this book, we will describe the general syntax of expressions by using italic symbols

delimited by angle brackets -- e.g., <name> -- to denote the ‘‘slots’’ in the expression to be filled in

when such an expression is actually used. 

14

 More generally, the body of the procedure can be a sequence of expressions. In this case, the

interpreter evaluates each expression in the sequence in turn and returns the value of the final

expression as the value of the procedure application. 

15

 Despite the simplicity of the substitution idea, it turns out to be surprisingly complicated to give a

rigorous mathematical definition of the substitution process. The problem arises from the possibility of

confusion between the names used for the formal parameters of a procedure and the (possibly

identical) names used in the expressions to which the procedure may be applied. Indeed, there is a long

history of erroneous definitions of substitution in the literature of logic and programming semantics. 

See Stoy 1977 for a careful discussion of substitution. 

16

 In chapter 3 we will introduce stream processing, which is a way of handling apparently ‘‘infinite’’

data structures by incorporating a limited form of normal-order evaluation. In section 4.2 we will

modify the Scheme interpreter to produce a normal-order variant of Scheme. 

17

 ‘‘Interpreted as either true or false’’ means this: In Scheme, there are two distinguished values that

are denoted by the constants 

#t

 and 

#f

. When the interpreter checks a predicate’s value, it interprets 

#f

 as false. Any other value is treated as true. (Thus, providing 

#t

 is logically unnecessary, but it is

convenient.) In this book we will use names 

true

 and 

false

, which are associated with the values 

#t

 and 

#f

 respectively. 

18

 

Abs

 also uses the ‘‘minus’’ operator 

-

, which, when used with a single operand, as in 

(- x)

,

indicates negation. 

19

 A minor difference between 

if

 and 

cond

 is that the <e> part of each 

cond

 clause may be a

sequence of expressions. If the corresponding <p> is found to be true, the expressions <e> are

evaluated in sequence and the value of the final expression in the sequence is returned as the value of

the 

cond

. In an 

if

 expression, however, the <consequent> and <alternative> must be single

expressions. 

20

 Declarative and imperative descriptions are intimately related, as indeed are mathematics and

computer science. For instance, to say that the answer produced by a program is ‘‘correct’’ is to make

a declarative statement about the program. There is a large amount of research aimed at establishing

techniques for proving that programs are correct, and much of the technical difficulty of this subject

has to do with negotiating the transition between imperative statements (from which programs are

constructed) and declarative statements (which can be used to deduce things). In a related vein, an

important current area in programming-language design is the exploration of so-called very high-level

languages, in which one actually programs in terms of declarative statements. The idea is to make

interpreters sophisticated enough so that, given ‘‘what is’’ knowledge specified by the programmer,

they can generate ‘‘how to’’ knowledge automatically. This cannot be done in general, but there are

important areas where progress has been made. We shall revisit this idea in chapter 4. 

---

21

 This square-root algorithm is actually a special case of Newton’s method, which is a general

technique for finding roots of equations. The square-root algorithm itself was developed by Heron of 

Alexandria in the first century 

A

.

D

. We will see how to express the general Newton’s method as a Lisp

procedure in section 1.3.4. 

22

 We will usually give predicates names ending with question marks, to help us remember that they

are predicates. This is just a stylistic convention. As far as the interpreter is concerned, the question

mark is just an ordinary character. 

23

 Observe that we express our initial guess as 1.0 rather than 1. This would not make any difference

in many Lisp implementations. MIT Scheme, however, distinguishes between exact integers and

decimal values, and dividing two integers produces a rational number rather than a decimal. For

example, dividing 10 by 6 yields 5/3, while dividing 10.0 by 6.0 yields 1.6666666666666667. (We

will learn how to implement arithmetic on rational numbers in section 2.1.1.) If we start with an initial

guess of 1 in our square-root program, and x is an exact integer, all subsequent values produced in the

square-root computation will be rational numbers rather than decimals. Mixed operations on rational

numbers and decimals always yield decimals, so starting with an initial guess of 1.0 forces all

subsequent values to be decimals. 

24

 Readers who are worried about the efficiency issues involved in using procedure calls to implement

iteration should note the remarks on ‘‘tail recursion’’ in section 1.2.1. 

25

 It is not even clear which of these procedures is a more efficient implementation. This depends

upon the hardware available. There are machines for which the ‘‘obvious’’ implementation is the less

efficient one. Consider a machine that has extensive tables of logarithms and antilogarithms stored in a

very efficient manner. 

26

 The concept of consistent renaming is actually subtle and difficult to define formally. Famous

logicians have made embarrassing errors here. 

27

 Lexical scoping dictates that free variables in a procedure are taken to refer to bindings made by

enclosing procedure definitions; that is, they are looked up in the environment in which the procedure

was defined. We will see how this works in detail in chapter 3 when we study environments and the

detailed behavior of the interpreter. 

28

 Embedded definitions must come first in a procedure body. The management is not responsible for

the consequences of running programs that intertwine definition and use. 

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

---