Now we get onto some more interesting exercises, that explore the way that the Lisp interpreter works.

Exercise 1.4

Our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behaviour of the following procedure:

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

This is cool! We want the function to return a + |b|, which we can do by making it return a + b if b>0 and a - b otherwise. Because procedures are like any other data type in the language, they can be the return value of an expression. We use that to our advantage here, by using an if procedure that returns the procedure + in the case that b > 0 and - otherwise. Try doing that in Java!

Exercise 1.5

Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order or normal-order evaluation. He defines the following two procedures:

> (define (p) (p))

> (define (text x y)
    (if (= x 0)
        0
        y))

Then he evaluates the expression

> (test 0 (p))

What behaviour will Ben observe with an interpreter that uses applicative-order evaluation> What about normal-order?

The procedure p is defined in terms of itself, so if we ever try to evaluate p we will end up in an infinite loop. If we use applicative order application, then both arguments to test are evaluated before we call test with those arguments. Since this involves evaluating p, the interpreter will hang.

On the other hand, if we use normal-order application then we expand out the arguments without evaluating them, to get

(if (= 0 0)
    0
    (p))

now when we evaluate this, we first test if (= 0 0), which returns true, so we execute the first statement after the predicate: the second statement, which is p, is never evaluated, and the program happily returns 0.

About these ads