SICP 2a
Higher-order Procedures

Table of Contents

1 Déjà vu

aib i

(define (sum-int a b)
  (if (> a b)
      0
      (+ a (sum-int (1+ a) b))))

aib i2

(define (sum-sq a b)
  (if (> a b)
      0
      (+ (sq a) (sum-int (1+ a) b))))

Computers were created to take care of menial tasks, so avoid repitition. Divide everything into smaller pieces, then each small piece needs to be debugged/understood only once.

aib by 4 1i(i + 2)

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/1 (* a (+ a 2)))
         (pi-sum (+ a 4) b))))

2 Procedure as argument

When dealing with patterns, find the abstraction.

General pattern in the above sums:

(define (<name> a b)
  (if (> a b)
      0
      (+ (<term> a)
         (<name> (<next> a) b))))

And now more correctly:

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

term and next are both procedural arguments.

Rewritten sum-int, sum-sq and pi-sum are shown below.

(define (sum-int a b)
  (define (identity a) a)
  (sum identity a 1+ b))

(define (sum-sq a b)
  (sum sq a 1+ b))

(define (pi-sum a b)
  (sum (lambda (i) (/ 1 (* i (+ i 2))))
       a
       (lambda (i) (+ i 4))
       b))

There are multiple ways of implementing sum. Below is an iterative version.

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

3 Procedure as value

Computers to make people happy, not people to make computers happy.

Returning to the square root procedure, note that we have been searching for a fixed point of f. (x is a fixed point of f if f(x)=x .)

y 𝑓 y+ xy 2

f(x) = x

(define (sqrt x)
  (fixed-point
   (lambda (y) (average (/x y) y))
   1))

(define (fixed-point f start)
  (define tolerance 0.00001)
  (define (close-enough? u v)
    (< (abs (- u v)) tolerance))
  (define (iter old new)
    (if (close-enough? old new)
        new
        (iter new (f new))))
  (iter start (f start)))

Note that y x y with y = 1 and x = 2 leads to a never-ending oscillation. The dampener is required to ensure that progress towards to answer is maintained.

More clearly stated:

(define (sqrt x)
  (fixed-point
   (average-damp (lambda (y) (/ x y)))
   1))
(define average-damp
  (lambda (f)
    (lambda (x) (average (f x) x)))

average-damp takes a procedure as an argument and returns a procedure as a value.

4 Newton's method

Newton's method, also known as the Newton-Raphson method, is an algorithm to produce successively better approximations to the zeroes (i.e. roots) of functions. (Find y 𝑦 y s.t. f ( y ) = 0 𝑓 𝑦 0 f(y)=0 .)

Start with a guess y + 0 𝑦 0 y+0 . Then

y n + 1 = y n - f ( y n ) d f d y | y = y n subscript 𝑦 𝑛 1 subscript 𝑦 𝑛 𝑓 subscript 𝑦 𝑛 evaluated-at 𝑑 𝑓 𝑑 𝑦 𝑦 subscript 𝑦 𝑛 y_{n+1}=y_{n}-\dfrac{f(y_{n})}{\frac{df}{dy}|_{y=y_{n}}}

Re-implementing sqrt using Newton's method:

(define (sqrt x)
  (newton (lambda (y) (- x (square y)))
          1))

(define (newton f guess)
  (define df (deriv f))
  (fixed-point
   (lambda (x) (- x (/ (f x) (df x))))
   guess))

Use wishful thinking to assume magic can be done with anything with a name. Wishful thinking is essential for good computer science.

(define deriv
  (lambda (f)
    (lambda (x)
      (/ (- (f (+ x dx))
            (f x))
         dx))))
(define dx 0.000001)

And magically we have the derivative! Evidently this isn't perfect and should make numerical analysts skin crawl.

5 A thousand words

2a-sqrt-newton.png

6 First-class citizens

Christopher Strachey, grandfather of computer science, logician and inventor of denotational semantics, was one of the first to make procedures first-class citizens in programming langauges.

The rights & privileges of first-class citizens

  • To be named by variables.
  • To be passed as arguments to procedures.
  • To be returned as values of procedures.
  • To be incorporated into data structures.

Turning procedures into first-class citizens allows for powerful abstractions.

Note to self: orgmode and latexml are lifesavers.