Home Notes SICP
https://yaxe1.com/notes/sicp/chapter1/

Chapter 1 - Building Abstractions With Procedures [32/45]

Section 1.1 - The Elements of Programming

DONE Exercise 1.1 

10
(+ 5 3 4)
(- 9 1)
(/ 6 2)
(+ (* 2 4) (- 4 6))
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
(= a b)
(if (and (> b a) (< b (* a b)))
    b
    a)
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
(+ 2 (if (> b a) b a))
(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))

DONE Exercise 1.2

It helps to draw the expression tree on a sheet of paper.

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

DONE Exercise 1.3 

; Defined in section 1.1.4:
(define (square x) (* x x))
(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (sum-of-squares-of-two-largest x y z)
  (cond ((and (>= y x) (>= z x)) (sum-of-squares y z))
        ((and (>= x y) (>= z y)) (sum-of-squares x z))
        ((and (>= x z) (>= y z)) (sum-of-squares x y))))

DONE Exercise 1.4

The body of this procedure is a combination whose operator is itself an if-statement. If \(b > 0\), the operator will be +. Otherwise, it will be -, in this way ensuring that a is summed with the absolute value of b.

DONE Exercise 1.5

An interpreter using applicative-order evaluation will hang in an infinite loop, since the arguments to test will be evaluated first and p is infinitely recursive.

On the other hand, a normal-order evaluation would evaluate to 0, because p doesn’t get invoked unless the predicate in the if statement is false.

DONE Exercise 1.6

This new-if procedure is not a special form but rather a procedure call, and therefore all of the arguments will be evaluated first before they are passed to cond. This means that the predicate is ignored and the new sqrt-iter procedure will call itself recursively forever.

DONE Exercise 1.7

“Limited precision” in this context means that we are using a finite amount of bits to represent a real number with a potentially infinite decimal representation. IEEE floating point arithmetic is defined as real-number arithmetic truncated to the closest representable float, introducing errors in calculations.

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

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

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

(define (improve guess x)
    (average guess (/ x guess)))

(define epsilon 1e-10)
(define (good-enough? guess x)
    (< (abs (- guess (improve guess x)))
        (* guess epsilon)))

(define (sqrt x)
    (sqrt-iter 1.0 x))

Section 1.2 - Procedures and the Processes They Generate

DONE Exercise 1.9 

(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7)
(inc 8)
9

(+ 4 5)
(+ (dec 4) (inc 5))
(+ (dec 3) (inc 6))
(+ (dec 2) (inc 7))
(+ (dec 1) (inc 8))
(+ 0 9)
9

DONE Exercise 1.10 

(A 1 10)
; 1024

(A 2 4)
; 65536

(A 3 3)
; 65536

; f(n) = 2n
; g(n) = 2^n
; h(n) = { n = 0: 0; otherwise 2^h(n-1) }

DONE Exercise 1.11 

(define (f n)
    (if (< n 3)
        n
        (+ (f (- n 1))
           (* 2 (f (- n 2)))
           (* 3 (f (- n 3))))))

Like in fib-iter, we can use variables to keep track of our running state.

(define (g n)
  (define (g-iter i a b c)
    (if (= i n)
        c
        (g-iter (+ i 1) b c (+ c (* 2 b) (* 3 a)))))
  (if (< n 3)
      n
      (g-iter 2 0 1 2)))

DONE Exercise 1.12 

(define (pascals x y)
  (if (or (= y 1) (= x 0) (= x y))
      1
      (+ (pascals (- x 1) (- y 1))
         (pascals x (- y 1)))))

; From the discord
(define (print-pascals n)
  (define (print-row y)
    (define (print-number x)
      (if (<= x y)
          (begin
            (display (pascals x y))
            (display " ")
            (print-number (+ x 1)))))
    (print-number 0)
    (newline))
  (define (print-all-rows i)
    (if (< i n)
        (begin
          (print-row i)
          (print-all-rows (+ i 1)))))
  (print-all-rows 0))

DONE Exercise 1.13

Recorded and uploaded to YouTube!

DONE Exercise 1.14

The count-change procedure is defined as follows:

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

DONE Exercise 1.15

  1. When (sine 12.15) is evaluated, p is applied 5 times.

       (p (sine 4.05))
   (p (p (sine 1.35)))
   (p (p (p (sine 0.45))))
   (p (p (p (p (sine 0.15)))))
   (p (p (p (p (p (sine 0.05))))))
   (p (p (p (p (p 0.05)))))

  2. For any given angle, there will be some number of halvings proportional to log base 2 of angle for a given epsilon (in this case 0.1). Therefore, the procedure grows logarithmically in number of steps, as well as in space because each recursive procedure call grows the call stack.

DONE Exercise 1.16

As the hint says, we’ll use a state variable and the invariant \(a(b^n)\). For odd values of \(n\), we’ll turn \(a(b^n)\) into \((ab)(b^{n-1})\).

; Defined in the text
(define (square x) (* x x))

(define (fast-expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter (square b) (/ n 2) a))
        (else (fast-expt-iter b (- n 1) (* a b)))))

(define (fast-expt b n)
  (fast-expt-iter b n 1))

DONE Exercise 1.17

For binary computers, halving and doubling can be implemented very efficiently by shifting bits left and right.

(I’m doing this one in Racket because it implements arithmetic-shift)

(define (double n) (arithmetic-shift n 1)) ; bitwise shift left
(define (halve n) (arithmetic-shift n -1)) ; bitwise shift right

(define (* a b)
  (cond ((= b 0) 0)
        ((= b 1) a)
        ((even? b) (* (double a) (halve b)))
        (else (+ a (* a (- b 1))))))

DONE Exercise 1.18

Let’s try that trick from 1.16 of introducing the state variable again. We’ll choose the invariant \(ab + k\), which mutates into \((2a)(b/2) + k\) for even \(b\) and \(a(b-1) + (k+a)\) for odd \(b\).

(define (double n) (arithmetic-shift n 1)) ; bitwise shift left
(define (halve n) (arithmetic-shift n -1)) ; bitwise shift right

(define (fast-mul a b)
  (define (fast-mul-iter a b k)
    (cond ((= b 0) k)
          ((even? b) (fast-mul-iter (double a) (halve b) k))
          (else (fast-mul-iter a (- b 1) (+ k a)))))
  (fast-mul-iter a b 0))

TODO Exercise 1.19

DONE Exercise 1.20

Let’s toss some print statements in there to see what’s going on normally.

(define (gcd a b)
  (printf "(gcd ~s ~s)~%" a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(gcd 206 40)

Now let’s try it with normal-order evaluation (by hand).

(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
(gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
... TODO

DONE Exercise 1.21 

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

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

DONE Exercise 1.22 

; From the text
(define (square x) (* x x))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

; My solution
(define (runtime) (* (current-inexact-milliseconds) 1000))

(define (search-for-primes start end limit)
  (cond [(or (<= limit 0) (> start end)) '()]
        [(even? start) (search-for-primes (+ start 1) end limit)]
        [(< start 3) (cons start (search-for-primes (+ start 1) end (- limit 1)))]
        [(timed-prime-test start) (cons start (search-for-primes (+ start 2) end (- limit 1)))]
        [else (search-for-primes (+ start 2) end limit)]))

(define (timed-prime-test n)
  (let [(start-time (runtime))]
    (if (prime? n)
        (begin
          (sleep 1e-3) ; Slow my computer down
          (display n)
          (display " -> ")
          (display (- (runtime) start-time))
          (display " μs")
          (newline)
          #t)
        #f)))

; Tests
(search-for-primes 1000 9999 3)
(search-for-primes 10000 99999 3)
(search-for-primes 100000 999999 3)
(search-for-primes 1000000 9999999 3)

Oddly, this doesn’t follow the sqrt(n) scaling that the book says we should expect.

TODO Exercise 1.23

TODO Exercise 1.24

TODO Exercise 1.25

TODO Exercise 1.26

TODO Exercise 1.27

TODO Exercise 1.28

Section 1.3 - Formulating Abstractions with Higher-Order Procedures

DONE Exercise 1.29

From Wikipedia:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (integral-1 f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

(define (sum-int term i n)
  (if (> i n)
      0
      (+ (term i)
         (sum-int term (+ i 1) n))))

(define (integral-2 f a b n)
  (let [(h (/ (- b a) n))]
    (define (x i) (+ a (* i h)))
    (* 1/3
       h
       (sum-int (lambda (i) (+ (f (x (- (* 2 i) 2)))
                               (* 4 (f (x (- (* 2 i) 1))))
                               (f (x    (* 2 i)))))
            1
            (/ n 2)))))

(define (cube x) (* x x x))

DONE Exercise 1.30 

(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
  (iter a 0))

; Tests
(define (identity x) x)
(define (inc x) (+ x 1))

(sum identity 0 inc 100)
(/ (* 100 101) 2) ; n(n+1)/2

DONE Exercise 1.31

Part A:

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* result (term a)))))
  (iter a 1))

(define (identity n) n)
(define (increment n) (+ n 1))

(define (factorial n) (product identity 1 increment n))

(define (even i) (* 2 i))
(define (odd i) (+ (* 2 i) 1))

(define (square n) (* n n))

(define (pi n)
  (* 2 (product (lambda (i) (/ (* 4 i i) (- (* 4 i i) 1))) 1 increment n)))

Part B:

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

DONE Exercise 1.32

Part A:

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner (term a) result))))
  (iter a null-value))

(define (sum term a next b)
  (accumulate + 0 term a next b))

(define (product term a next b)
  (accumulate * 1 term a next b))

Part B:

(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a) (accumulate combiner null-value term (next a) next b))))

TODO Exercise 1.33 

(define (filtered-accumulate combiner null-value term a next b filter)
  (if (> a b)
      null-value
      (if (filter (term a))
          (combiner (term a) (filtered-accumulate combiner null-value term (next a) next b))
          (filtered-accumulate combiner null-value term (next a) next b))))

(define (identity x) x)

(define (sum-of-squared-primes a b)
  (filtered-accumulate + 0 identity a (lambda (n) (if (even? n) (+ n 1) (+ n 2))) b prime?))

; TODO

DONE Exercise 1.34 

(f f)
(f 2)
(2 2) ; not a valid expression, since 2 is not a procedure

DONE Exercise 1.35

At the fixed point, the equation \(x = 1 + \frac{1}{x}\) will be true. Rearranging the terms, we get \(x^2 - x - 1\) and use the quadratic formula to solve for x, which ends up being \(\frac{1 ± \sqrt{5}}{2}\).

Computing this value with fixed-point, we get:

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let [(next (f guess))]
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

DONE Exercise 1.36 

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let [(next (f guess))]
      (display next)
      (newline)
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

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

TODO Exercise 1.37

TODO Exercise 1.38

TODO Exercise 1.39

DONE Exercise 1.40 

; From the text
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (deriv g)
  (define dx 0.00001)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

(define (fixed-point f first-guess)
  (define tolerance 0.00001)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let [(next (f guess))]
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (cubic a b c)
  (lambda (x)
    (+ (* x x x) (* a x x) (* b x) c)))

DONE Exercise 1.41 

(define (double f)
  (lambda (x) (f (f x))))

(((double (double double)) inc) 5)

DONE Exercise 1.42 

(define (compose f g)
  (lambda (x) (f (g x))))

DONE Exercise 1.43 

(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))

DONE Exercise 1.44 

(define (average . args) ; using variadic arguments so I don't have to rewrite
  (define (iter args sum count)
    (if (null? args)
        (if (= count 0)
            0
            (/ sum count))
        (iter (cdr args) (+ sum (car args)) (+ count 1))))
  (iter args 0 0))

(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))

(define (smooth f)
  (define dx 0.00001)
  (lambda (x) (average (f (- x dx)) (f x) (f (+ x dx)))))

(define (n-fold-smooth f n)
  (repeated smooth n))

TODO Exercise 1.45

TODO Exercise 1.46