About the Book

To know more about programming, I have decided to start reading the famous Structure and Interpretation of Computer Programs (SICP, or the Wizard Book), which is first published by MIT in 1985. The Wizard Book used MIT Scheme, which is a dialect of Lisp, as the demonstrating language. This language is so different from the languages I know (C++ and JavaScript, which are both inspired by C). However, the book does not talk much about the characteristics of the language. It focus on teaching important concepts in Computer Science, but not teaching a particular language. I am sure that the book and the interesting language can help me to become a better programmer! (but not just a coder XD) This book is available online under Creative Common (CC) so you may take a look at it too!

Important Quotes from the Book

1. Evaluate the subexpressions of the combination. (recursively!)
2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

My Solution to the Exercises

Exercise 1.1

In this exercise, I only need to write down the result of each expression. I have put a semi-colon(;) before the result.

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

Exercise 1.2

In this exercise, I need to translate a mathematical expression into a complex combination in Scheme.

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

Exercise 1.3

In this exercise, I need to write a procedure that take three numbers as arguments and returns the sum of the squares of the two larger numbers.

(define (sum-of-squares-of-larger-two a b c)
  (cond ((and (<= a b) (<= a c)) (+ (* b b) (* c c)))
		((and (<= b a) (<= b c)) (+ (* a a) (* c c)))
		(else (+ (* a a) (* b b)))))

Exercise 1.4

In this exercise, I need to explain the behaviour of the following procedure:

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

When b is positive, the procedure return a+b.
When b is 0 or negative, the procedure returns a-b (a-b = a-(-|b|) = a+|b|, given b<=0)

Exercise 1.5

Given the following code, is the result different when applicative order and normal order are used?

(define (p) (p))

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

(test 0 (p))

Applicative Order:

(test 0 (p))

This method would first evaluate all the subexpressions of the combination.
(p) calls (p) again so there is an infinite loop. (runtime_error)

Normal Order:

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

This method would first substitute operand expressions for parameters until it obtained an expression involving only primitive operators, and would then perform the evaluation. (p) is not evaluated until it is needed, so no infinite loop appears. (0 is returned)

Exercise 1.6

Why the built-in if is a special form instead of a procedure? Given the following definition of a new-if:

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

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

Exercise 1.7

In the sample (sqrt x) procedure in this chapter, a good-enough procedure is used to judge whether the approximation of the sqrt is accurate enough:

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (average x y)
  (/ (+ x y) 2.0))

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

(define (sqrt x)
  (define (good-enough? guess old-guess)
    (< (abs (/ (- guess old-guess)
            old-guess))
       0.00000001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess old-guess)
    (if (good-enough? guess old-guess)
        guess
        (sqrt-iter (improve guess)
                   guess)))
  (sqrt-iter 1.0 -1.0))

Exercise 1.8

This one is similar to 1.7 but this time I am solving for the cube root.

(define (pow x y)
  (if (= y 0)
      1
      (* x (pow x (- y 1)))))

(define (cube-root x)
  (define (good-enough? guess old-guess)
    (< (abs (/ (- guess old-guess)
               old-guess))
       0.00000001))
  (define (improve guess)
    (/ (+ (/ x (pow guess 2))
          (* 2 guess))
       3))
  (define (cube-root-iter guess old-guess)
    (if (good-enough? guess old-guess)
        guess
        (cube-root-iter (improve guess)
                        guess)))
  (cube-root-iter 1.0 -1.0))

(cube-root -8)

Do you find coding in Scheme interesting? Or are you interested in the Wizard Book? Join me to read the book so that we can share our thoughts!