Exercise 1.1

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
=> 10


(+ 5 3 4)
=> 12
(- 9 1)
=> 8

(/ 6 2)
=> 3
(+ (*2 4) (- 4 6))
=> 6

(define a 3)
(define b (+ a 1))
(+ a b (* a b))
=> 19
(= a b)
=> false

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

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
=> 16

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

( * (cond ((> a b) a)
          ((< a b) b)
          (else -1))
    (+ a 1))
=> 16

Exercise 1.2: Translate the following expression into prefix form.

(/ (+ 5
      4
      (- 2
         (- 3
            (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7)))

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

(define (sum-of-larger-squares x y z)
  (define (sum-of-squares x y) (+ (* x x) (* y y)))
  (cond ((and (< x y) (< x z)) (sum-of-squares y z))
        ((and (< y x) (< y z)) (sum-of-squares x z))
        (else (sum-of-squares x y)))

)

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

This procedure demonstrates that operators in Lisp can be the result of evaluating expressions, not just literal operators. The procedure a-plus-abs-b computes a + |b| (a plus the absolute value of b).

Here’s how it works:

• The if expression (if (> b 0) + -) evaluates to either the + operator (if b is positive) or the - operator (if b is negative or zero)
• This operator is then applied to the arguments a and b
• If b > 0: the expression becomes (+ a b), which gives a + b
• If b ≤ 0: the expression becomes (- a b), which gives a - b (since b is negative, this effectively adds the absolute value)

In both cases, the result is a + |b|, demonstrating how compound expressions can serve as operators in Lisp combinations.

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

Answer:

Applicative-order evaluation: With applicative-order evaluation, the interpreter will hang in an infinite loop. Here’s why:

1. When evaluating (test 0 (p)), applicative-order evaluation requires all arguments to be evaluated before applying the procedure
2. The interpreter first evaluates 0 (which gives 0)
3. Then it tries to evaluate (p)
4. The procedure (p) is defined as (define (p) (p)), which calls itself recursively
5. This creates an infinite recursion: (p) → (p) → (p) → …
6. The interpreter never gets to actually call the test procedure because it gets stuck evaluating the argument (p)

Normal-order evaluation: With normal-order evaluation, the interpreter will return 0. Here’s why:

1. Normal-order evaluation delays the evaluation of arguments until they are actually needed
2. When evaluating (test 0 (p)), the interpreter substitutes the arguments into the body of test without evaluating them first
3. This gives us: (if (= 0 0) 0 (p))
4. The predicate (= 0 0) is evaluated first (as specified in the problem), which gives #t
5. Since the condition is true, the if expression returns the consequent 0
6. The alternative (p) is never evaluated, so the infinite recursion is avoided

This test effectively demonstrates the key difference between the two evaluation strategies: applicative-order evaluates arguments immediately, while normal-order delays evaluation until the values are actually needed.

Applicative-Order vs Normal-Order Evaluation

Applicative-Order Evaluation (Eager Evaluation):

• When arguments are evaluated: Arguments are evaluated immediately when a procedure is called, before the procedure body is executed
• Evaluation strategy: “Evaluate the arguments and then apply”
• Also known as: Eager evaluation, call-by-value
• Used by: Most programming languages including Scheme/Lisp interpreters

Example:

(define (square x) (* x x))
(square (+ 2 3))

With applicative-order:

1. First evaluate (+ 2 3) → 5
2. Then apply square to 5 → (* 5 5) → 25

Normal-Order Evaluation (Lazy Evaluation):

• When arguments are evaluated: Arguments are not evaluated until their values are actually needed in the computation
• Evaluation strategy: “Fully expand and then reduce”
• Also known as: Lazy evaluation, call-by-name
• Used by: Some functional languages like Haskell, and in mathematical evaluation

Example:

(define (square x) (* x x))
(square (+ 2 3))

With normal-order:

1. Substitute the argument directly: (* (+ 2 3) (+ 2 3))
2. Only evaluate (+ 2 3) when needed: (* 5 5) → 25

Key Differences:

Practical Example - The Difference:

(define (test-if x y z)
  (if x y z))

(define (infinite-loop) (infinite-loop))

(test-if #t 42 (infinite-loop))

• Applicative-order: Will hang because (infinite-loop) is evaluated before calling test-if
• Normal-order: Will return 42 because (infinite-loop) is never evaluated since the condition is true

When Each is Better:

• Applicative-order: Better for most practical programming due to predictable performance and side effects
• Normal-order: Better for mathematical computations and when you want to avoid unnecessary calculations