Structure and Interpretation of Computer Programs

The word predicate is used for procedures that return true or false, as well as for expressions that

evaluate to true or false. The absolute-value procedure 

abs

 makes use of the primitive predicates 

>

, 

<

,

and 

=

.

18

 These take two numbers as arguments and test whether the first number is, respectively,

greater than, less than, or equal to the second number, returning true or false accordingly.

Another way to write the absolute-value procedure is

(define (abs x)

  (cond ((< x 0) (- x))

        (else x)))

which could be expressed in English as ‘‘If x is less than zero return - x; otherwise return x.’’ 

Else

 is

a special symbol that can be used in place of the <p> in the final clause of a 

cond

. This causes the 

cond

 to return as its value the value of the corresponding <e> whenever all previous clauses have

been bypassed. In fact, any expression that always evaluates to a true value could be used as the <p> 

here.

Here is yet another way to write the absolute-value procedure:

(define (abs x)

  (if (< x 0)

      (- x)

      x))

This uses the special form 

if

, a restricted type of conditional that can be used when there are

precisely two cases in the case analysis. The general form of an 

if

 expression is

(if <predicate> <consequent> <alternative>)

To evaluate an 

if

 expression, the interpreter starts by evaluating the <predicate> part of the

expression. If the <predicate> evaluates to a true value, the interpreter then evaluates the 

<consequent> and returns its value. Otherwise it evaluates the <alternative> and returns its value.

19

In addition to primitive predicates such as 

<

, 

=

, and 

>

, there are logical composition operations, which

enable us to construct compound predicates. The three most frequently used are these:

(and <e

1

> ... <e

n

>)

The interpreter evaluates the expressions <e> one at a time, in left-to-right order. If any <e>

evaluates to false, the value of the 

and

 expression is false, and the rest of the <e>’s are not

evaluated. If all <e>’s evaluate to true values, the value of the 

and

 expression is the value of the

last one.

(or <e

1

> ... <e

n

>)

The interpreter evaluates the expressions <e> one at a time, in left-to-right order. If any <e>

evaluates to a true value, that value is returned as the value of the 

or

 expression, and the rest of

the <e>’s are not evaluated. If all <e>’s evaluate to false, the value of the 

or

 expression is false.

(not <e>)

---

The value of a 

not

 expression is true when the expression <e> evaluates to false, and false 

otherwise.

Notice that 

and

 and 

or

 are special forms, not procedures, because the subexpressions are not

necessarily all evaluated. 

Not

 is an ordinary procedure.

As an example of how these are used, the condition that a number x be in the range 5 < x < 10 may be

expressed as

(and (> x 5) (< x 10))

As another example, we can define a predicate to test whether one number is greater than or equal to

another as

(define (>= x y)

  (or (> x y) (= x y)))

or alternatively as

(define (>= x y)

  (not (< x y)))

Exercise 1.1.  Below is a sequence of expressions. What is the result printed by the interpreter in

response to each expression? Assume that the sequence is to be evaluated in the order in which it is 

presented.

10

(+ 5 3 4)

(- 9 1)

(/ 6 2)

(+ (* 2 4) (- 4 6))

(define a 3)

(define b (+ a 1))

(+ a b (* a b))

(= a b)

(if (and (> b a) (< b (* a b)))

    b

    a)

(cond ((= a 4) 6)

      ((= b 4) (+ 6 7 a))

      (else 25))

(+ 2 (if (> b a) b a))

(* (cond ((> a b) a)

         ((< a b) b)

         (else -1))

   (+ a 1))

Exercise 1.2.  Translate the following expression into prefix form 

---

Exercise 1.3.  Define a procedure that takes three numbers as arguments and returns the sum of the

squares of the two larger numbers. 

Exercise 1.4.  Observe that our model of evaluation allows for combinations whose operators are

compound expressions. Use this observation to describe the behavior of the following procedure: 

(define (a-plus-abs-b a b)

  ((if (> b 0) + -) a b))

Exercise 1.5.  Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is

using applicative-order evaluation or normal-order evaluation. He defines the following two

procedures: 

(define (p) (p))

(define (test x y)

  (if (= x 0)

      0

      y))

Then he evaluates the expression 

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What

behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. 

(Assume that the evaluation rule for the special form 

if

 is the same whether the interpreter is using

normal or applicative order: The predicate expression is evaluated first, and the result determines

whether to evaluate the consequent or the alternative expression.) 

1.1.7  Example: Square Roots by Newton’s Method

Procedures, as introduced above, are much like ordinary mathematical functions. They specify a value

that is determined by one or more parameters. But there is an important difference between

mathematical functions and computer procedures. Procedures must be effective.

As a case in point, consider the problem of computing square roots. We can define the square-root

function as 

This describes a perfectly legitimate mathematical function. We could use it to recognize whether one

number is the square root of another, or to derive facts about square roots in general. On the other

hand, the definition does not describe a procedure. Indeed, it tells us almost nothing about how to

actually find the square root of a given number. It will not help matters to rephrase this definition in 

pseudo-Lisp:

(define (sqrt x)

  (the y (and (>= y 0)

              (= (square y) x))))

---