SICP Exercises 1.1 through 1.4

../img/necker-cube.png

Some time ago, I got a copy of the first edition of SICP on eBay. It’s a fascinating book, for many reasons. I’ve been slowly working through it in fits and starts, but I’ve decided that this year I’m going to really focus on finishing this book and doing all of the exercises.

Therefore, for the sake of completeness, I’d like to backtrack a bit and record my work on SICP exercises 1.1 through 1.4. My goal is to be able to do every single exercise from SICP (1st ed.) and explain it here. (You can see all of the SICP-related posts here.)

For each of the exercises below, I’ll first provide the problem text from the book, and then my answer (or attempt at an answer).

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.

Here are the expressions, followed by my answers.

Expression Result
10 10
(+ 5 3 4) 12
(- 9 1) 8
(/ 6 2) 3
(+ (* 2 4) (- 4 6)) 6
(define a 3) UNDEFINED
(define b (+ a 1)) 4
(+ a b (* a b)) 19
(= a b) #f
(if (and (> b a) (< b (* a b))) b a) 4
(cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25)) 16

Exercise 1.2

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

Here is the procedure definition, along with a couple of helpers.

(define (square x)
  (* x x))

(define (sos x y)
  (+ (square x) (square y)))

(define (sos-largest-two a b c)
  (let* ((sorted (sort (list a b c) >))
         (large (first sorted))
         (medium (second sorted)))
    (sos medium large)))

Exercise 1.3

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

An interpreter that uses applicative-order evaluation will enter an infinite recursion.

An interpreter that uses normal-order evaluation will return 0.

The reason for this is that an applicative-order interpreter follows the usual “evaluate arguments, then apply” recipe. I believe this is also known as “call-by-value”.

The normal-order interpreter never gets around to evaluating the second argument to test because it doesn’t need to (and of course, once inside test, the if form behaves as in the problem description).

Exercise 1.4

Alyssa P. Hacker doesn’t see why if needs to be provided as a
special form. “Why can’t I just define it as an ordinary
procedure in terms of cond?” she asks. Alyssa’s friend Eva Lu
Ator claims this can indeed be done, and she defines a new version
of if:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

Eva demonstrates the program for Alyssa:

==> (new-if (= 2 3) 0 5)
5

==> (new-if (= 1 1) 0 5)
0

Delighted, Alyssa uses new-if to rewrite the square-root program:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x) x)))

What happens when Alyssa attempts to use this to compute square
roots? Explain.

Running this procedure exceeded MIT Scheme’s maximum recursion depth. I decided to trace the procedure to better see what was happening (note that I renamed the procedures to alyssa-sqrt-iter and alyssa/sqrt to differentiate them from the original versions).

(trace alyssa-sqrt-iter)
;Unspecified return value

(alyssa/sqrt 100)
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 1.
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 50.5
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 26.24009900990099
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 15.025530119986813
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.840434673026925
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.032578510960604
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.000052895642693
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.000000000139897
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.
;;           100]
;;  ... et cetera ...

;Quit!

The last line, where the arguments to alyssa/sqrt-iter are 10 and 100, repeats hundreds of times. Even though the call to good-enough? (shown again below) returns #t, new-if still ends up evaluating the `else-clause’ and causing the linear recursion instead of returning the current value of guess (as it should).

(new-if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x))

This problem illustrates the reason we need if to be a special form: we need it to exhibit “short-circuiting” behavior, i.e., we need it to avoid evaluating all of its arguments.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s