SICP Study Notes

Solutions to exercises and notes accompanying the SICP course.

Installing and Running Scheme

On a mac you can install Scheme with:

brew install rlwrap
brew install mit-schema

To start the REPL:

rlwrap mit-scheme

To load a file:

rlwrap mit-scheme --load solutions/ch1.scm

Hello World:

(write "Hello world")

1.1 The Elements of Programming

Every powerful programming language has three fundamental mechanisms:

Primitives
Combinations
Abstractions

In programming we deal with procedures and data.

1.1.7 Example: Square Roots by Newton's Method

(define (square-root x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x))
       0.01))
  (define (average a b)
    (/ (+ a b) 2))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (try guess x)
    (if (good-enough? guess x)
      guess
      (try (improve guess x) x)))
  (try 1 x))

(square-root 9) ; => 3.00009155413138

1.2 Procedures and the Processes They Generate

1.2.1 Linear Recursion and Iteration

Linear recursive processes are linear in time and space
Iterative processes are linear in time and constant in space

The recursive process builds up a chain of deferred operations. The contraction occurs as the operations are actually performed.

Scheme tail-recursive, i.e. has tail-call optimization so that iteration can programmed as a recursive procedure.

Recursive factorial:

(define (factorial-rec n)
  (if (= n 1)
    1
    (* n (factorial-rec (- n 1)))))
(factorial-rec 5) ; => 120

Iterative factorial:

(define (factorial-iter n)
  (define (iter counter product)
    (if (> counter n)
      product
      (iter (+ counter 1) (* product counter))))
  (iter 1 1))
(factorial-iter 5) ; => 120

Recursive addition:

(define (add a b)
  (if (= a 0)
    b
    (+ 1 (add (- a 1) b))))
(add 3 5) ; => 8

Iterative addition:

(define (add a b)
  (if (= a 0)
    b
    (add (- a 1) (+ b 1))))
(add 3 5) ; => 8

1.2.2 Tree Recursion

Tree recursive fibonacci implementation:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))
(fib 10) ; => 55
; 0 1 2 3 5 8 13 21 34 55

1.2.5 Greatest Common Divisors

The GCD of integers a and b is the largest integer that divides both a and b with no remainder.

GCD(a, b) = GCD(b, r)

(define (gcd a b)
  (if (= b 0)
    a
    (gcd b (remainder a b))))
(gcd 40 206) ; => 2

1.3 Formulating Abstractions with Higher Order Procedures

Summing integers between a and b:

(define (sum-integers a b)
  (if (> a b)
    0
    (+ a (sum-integers (+ a 1) b))))
(sum-integers 1 5) ; => 15

Generalized sum between a and b:

(define (sum term next a b)
  (if (> a b)
    0
    (+ (term a) (sum term next (next a) b))))
(sum (lambda (x) x) 1+ 1 5) ; => 15

peter/sicp