SICP - Higher order procedures

After a brief break to go play in Visual Studio I'm back at it with the MIT lectures. This one looked at passing and returning procedures from other procedures.  Talked about the square root procedure again, how it is really just a fixed point for a function. Then we looked at Newton's method and built up a rather elaborate program for computing square root based on derivatives. Fun stuff.



Worked out a few of the code examples in Scheme, found you need to be really careful with those damn parens! If you find yourself getting a "Can't bind name to null syntactic environment:" type error, check your parens again...

Here are my notes from the lecture:

Starting out with a few abstractions, some of which
apparently can't be written easily in other programming
languages.

Sum up a range of integers:
(define (sum-int a b)
(if (> a  b)
0
(+ a
(sum-int (1+ a) b)))

Sum of squares of range:
(define (sum-sq a b)
(if (> a b)
0
(+ (square a)
(sum-sq (1+ a) b))))

Almost identical procedures. In the above two programs, in mathematical
notation they both use the same sigma notation.

Leibnitz formula for finding pi over 8:
(define (pi-sum a b)
(if (> a b)
0
(+ (/ 1 (* a (+ a 2)))
(pi-sum (+ a 4) b))))

Still very much like the two above summation problems, warrants further abstraction

General pattern of the above cases:
(define (<name> a b)
(if (> a b)
0
(+ (<term> a)
(<name> (<next> a) b))))

<name> - procedure being defined
<term> - modification to the index a
<next> - iteration interval of index a

Procedural arguments.
(Define (sum term a next b)
term and next are procedure

term is a procedure which produced the value of that term for a given index
next returns the next index
definition is pretty much verbatim of the above described general case
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))

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

This procedure does the same thing as the sum of integers procedure above.

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

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

Lambda expressions(λ(i)) allow us to define a procedure

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

Important to note the difference between passing the procedure and passing the evaluation of a procedure.
In the sum definition, the recursive call to sum passes term and next as the arguments for term and next, while a
is being passed as the evaluation of (next a)

Abstraction intended to make programs easier to write and understand.

Back to the square root calculation problem
Heron of Alexandria's algorithm reduces to a fix point problem.
With some functions, you can find the fixed point by iterating the function

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

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

Other functions can find the fixed point:

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

average-damp must return a procedure

(define average-damp
(λ (f)
(λ (x) (average (f x) x))))

ALTERNATIVELY
(define (average-damp f)
(λ (x) (average (f x) x))))

YET AGAIN WITHOUT LAMBDAS
(define (average-damp f)
(define (foo x)
(define (f x) x))
foo)

This procedure based on the idea of dampeners in signal processing dampener.
The whole anonymous procedures really messed the class up, I can identify ha.

Higher order procedures take procedures as arguments and return procedures.

Newtons method finds the roots (zeros) of functions
- to find a y such that f(y) = 0, start with a guess, y0
y(n+1) = yn - (f(yn))/(df/dy|y=yn)

Lets start with the square root of x problem by assuming we know how to use
Newton's method (we don't)
(define (sqrt x)
(newton (λ (y) (- x (square y)))
1))

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

(define deriv
(λ (f)
(λ (x)
(/ (- (f (+ x dx))
(f x))
dx))))

(define dx 0.000001)

Chris Strachey - "The rights and privileges of first-class citizens"
- To be named by variables
- To be passed as argument to procedures
- To be returned as values of procedures
- To be incorporated into data structures
Advocated making procedures "first class citizens"
Allows us to make powerful abstractions.