SICP Chapter 1 exercises

I discovered SICP almost two years ago. I watched the video lectures that summer which served as a nice overview of some of the ideas in the book. It certainly helped the way I thought about computer programming in some way, but at the same time I don’t feel that I have the kind of “enlightenment” that people say it gives you – well to be honest, I barely know scheme or any lisp despite my infrequent experimentation.

So as a simple way to fulfill my new years resolution I will try to answer the exercises in SICP here and perhaps discuss what I’ve learned from the chapter. Here we go!

1.1

10 # 10
(+ 5 3 4) # 12
(- 9 1) # 8
(/ 6 2) # 3
(+ (* 2 4) (- 4 6)) # (+ 8 -2) # 6
(define a 3) # I assumed that this was nil, but in fact the return value for "define" is undefined in the specification.
(define b (+ a 1)) # similarly also undefined
(+ a b (* a b)) # 19
(= a b) # false in guile (the implementation I am using) represented by #f
(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 

Comments: Of course the first exercise in the book is going to be simple.

1.2
Translate the following expression into prefix form: Exercise 1.2

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

Comments: That was pretty much practice organizing braces in scheme.

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-2-larger-squares x y z)
        (cond ((and (> x z) (> y z)) (+ (* x x) (* y y)))
              ((and (> x y) (> z y)) (+ (* x x) (* z z)))
              (else (+ (* y y) (* z z)))))

Comments: Braces made me a bit dizzy, but this forced me to get familiar with the cond and define syntaxes. Since the question asked for a single procedure, there’s a lot of repetition, but it works.

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

Comments: Something I would have missed if I didn’t try these exercises. Whether you sum the two numbers or subtract the second from the first depends on whether the second value is greater than zero. The result is adding the absolute value of b to a.

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

Applicative-order:

The operator and arguments need to all be evaluated first. test evaluates to test, 0 to 0 and (p) to the result of (p). However it will have to keep evaluating (p) as it keeps evaluating to itself and so the interpreter will never stop evaluating it.

Normal-order:

The test procedure is expanded to the if special form first. Due to the rules of the special form, the predicate is first evaluated, and the result is true. This means that the consequent is evaluated, which in this case is simply 0. Therefore the test procedure evaluates to 0.

Comments: I found this harder than I probably should have. It took several readings of the descriptions of applicative order and normal order, and a btter understanding of the if special form to get this. I also had to cheat and take a look at other people’s answers to make sure I was on the right track.

Well that’s the first 5 questions from section 1.1 in SICP. I wanted to do all of them, but it’s not as trivial as I had thought when I first started. I’ll try to finish it off tomorrow and hopefully I can get a good chunk of the next section done as well.

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