SICP Exercise 1.1–1.5

So yesterday I hit the 50-problem mark on Project Euler. The problem was the one about how many ways can you make 200 GBP. SICP implemented this problem and I just happened to be reading it, so after I read the problem I went and implemented it in Haskell. While it ran in under a minute, I thought it was rather slow….Anyway that's totally not what this is about. Perhaps I'll make a post about this problem later.

In light of finishing 50 problems, I'm going to be taking a wee break (like, a week? less, quite possibly) and start doing the exercises from SICP. I've actually done nearly all the ones from chapter 2, but then it occurred to me to do something logical and start from chapter one…. So without furthur ado:

---

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.

I'm only posting the more complex ones, or the ones I was not entirely sure about. All solutions are easily verifiable with an interpreter. Wrote some comments in, as well.

]=> (+ (* 2 4) (- 4 6)) ;; (+ 8 (-2))
6
]=> (define a 3)
a
]=> (define b (+ a 1))
b
]=> (+ a b (* a b))
;; (+ 3 4 (* 3 4)) -> (+ 3 4 12) 
19
]=> (= a b)
#f
]=> (if (and (> b a) (< b (* a b)))
        b
        a)
4
]=> (cond ((= a 4) 6) ;; a is 3, this condition false
          ((= b 4) (+ 6 7 a)) ;; b is 4, this condition true
          (else 25))
16
]=> (+ 2 (if (> b a) b a))
6 ;; (+ 2 b) -> (+ 2 4)
]=> (* (cond ((> a b) a) ;;false
((< a b) b) ;;true
             (else -1))
       (+ a 1))
;; (* b (+ a 1)) -> (*4 4)
16

Exercise 1.2. Translate the […] 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-squares-largest a b c)
  (cond ((and (< a b) (< a c)) (+ (* b b) (* c c))) ;a is smaller than b & c so sum the squares of b & c
 ((and (< b c) (< b a)) (+ (* a a) (* c c)))
 (else (+ (* a a) (* b b)))))

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

If b is a positive number we will add b to a. If b is a negative number, subtract b from a. This expression is essentially adding the absolute value of b to a.

Exercise 1.5. (Paraphrased!) Ben Bitdiddle (what is the clever pun in his name? I know there must be one, but I don't understand it…) is trying to test if his interpreter is using applicative–order evaluation or normal–order evaluation. He defines these expresions:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

When he evaluates (test 0 (p)) what will be returned if the interpreter is applicative–order, and what will be returned if the interpreter is normal–order?

normal The interpreter will look to see if (= x 0), which is true, so it will return 0 and stop. applicative will never terminate. The interpreter will try to evaluate the arguments—it will "plug–in" 0 for x, and then try to do the same, plugging in p for y, but because p is recursively defined, the interpreter will be doing this plugging–in forever.