MIT 6.001 Structure and Interpretation, 1986

Lecture 1A: Overview and Introduction to Lisp

1. Fixed point of a function.
2. We're not only building boxes that input and output numbers. We're building boxes that can compute methods. We can have procedures whose values is another procedure.
3. Big Topic 1: Black-Box Abstraction Capturing Common Patterns i. High-order procedures ii. Data as procedures
4. Big Topic 2: Conventional Interfaces i. Generic operations ii. Large-scale structure and modularity iii. Object-orientated programming iv. Operation on aggregates
5. Big Topic 3: Metalinguistic Abstraction - making new languages i. Interpretation: Apply-Eval ii. Example: Logic programming iii. Register machine
6. Learning a new language, know: i. Primitive elements. ii. Means of combination (create bigger things out of primitive elements) and iii. Means of abstraction (How to draw black-boxes around the combination -- give a combination a name so it can be used with its details suppressed -- as if they were primitive elements).

Lecture 1B: Procedures and Processes; Substitution Model

1. Substitution model
2. An iteration has all of its state in explicit variables. Recursion has implicit state.
3. Peano arithmetic recursively and iteratively. Linear iteration takes constant space and linear time. Linear recursion takes both linear time and space.
4. Recursive definition != Recursive process.
5. Recursion has work to be done later.
6. Forward euler method.
7. perturbation analysis
8. Towers of Hanoi problem

Lecture 2A: Higher-order Procedures

1. How to think recursively: a. Write down the answer to an easy case that is known. b. Reduce the problem to a simpler problem -- make a subproblem of the simpler problem and do something to the result.

Copycopy code to clipboard
1; Implementation of SIGMA (i) from INDEX to UPPER_BOUND
2(DEFINE (SUM_INT index upper_bound)
3   (IF (> index upper_bound)
4      0 ; Easy case
5      (+
6         index
7         (SUM_INT (1+ index) upper_bound) ; Reduced simpler problem -- subproblem to solve for
8      )
9   )
10)

Copycopy code to clipboard
1; Implementation of SIGMA (i²) from INDEX to UPPER_BOUND
2(DEFINE (SUM_SQUARE index upper_bound)
3   (IF (> index upper_bound)
4      0
5      (+
6         (SQUARE index)
7         (SUM_SQUARE (1+ index) upper_bound)
8      )
9   )
10)

2. Generalizing summation using higher order procedures

Copycopy code to clipboard
1; Recursively
2(DEFINE (SUMMATION term index index_stepper upper_bound)
3   (IF (> index upper_bound)
4      0
5      (+
6         (term index) ; term provides term at index
7         (SUMMATION
8            term
9            (index_stepper index)
10            index_stepper
11            upper_bound
12         )
13      )
14   )
15)
16
17; Iteratively
18(DEFINE (SUMMATION term lower_bound index_stepper upper_bound)
19   (DEFINE (ITER index accumulator)
20      (IF (> index upper_bound)
21         accumulator
22         (ITER
23            (index_stepper index)
24            (+
25               accumulator
26               (term index)
27            )
28         )
29      )
30   )
31
32   (ITER lower_bound 0)
33)

Copycopy code to clipboard
1(DEFINE (SUM_INT index upper_bound)
2   (SUMMATION
3      (LAMBDA (x) x)
4      index
5      +1
6      upper_bound
7   )
8)

3. Procedures are also data -- they are not special. They can be named.
4. A procedure for improving a guess of square roots.

Copycopy code to clipboard
1(define (sqrt x)
2   (define tolerance 0.00001)
3
4   (define (good-enough? candidate)
5      (<
6         (abs (- (* candidate candidate) x))
7         tolerance
8      )
9   )
10
11   (define (improve candidate)
12      (average
13         (/ x candidate)
14         candidate
15      )
16   )
17
18   (define (find-sqrt candidate)
19      (if (good-enough? candidate)
20         candidate
21         (find-sqrt (improve candidate))
22      )
23   )
24
25   (find-sqrt 1)
26)
27
28(define (average m n)
29   (/
30      (+ m n)
31      2
32   )
33)

5. A fixed-point is a place which has the property, that the input of the function is its output.

improve(candiate) -> (candidate + (x / candidate)) / 2

improve(sqrt(x)) = sqrt(x) Example: improve(sqrt(9)) = (3 + (9 / 3)) / 2 = (3 + 3) / 2 = 3

Therefore, the fixed-point of the function improve(candidate) is what is desired.

6. Some functions have the property that their fixed-point can be found by iterating the function itself -- essentially what is happening in the square-root procedure by Heron's method.

Copycopy code to clipboard
1(define (fixed-point function start)
2   
3   (define tolerance 0.00001)
4
5   ; Checks if two input are close enough as defined by the tolerance
6   (define (close-enough m n)
7      (<
8         (abs (- m n))
9         tolerance
10      )
11   )
12
13   ; Repeat until old and new are close enough
14   (define (iter old new)
15      (if (close-enough old new)
16         new
17         (iter new (function new))
18      )
19   )
20
21   (iter start (function start))
22)
23
24(define (sqrt x)
25   (fixed-point
26      (lambda (b)
27         (/
28            (+ b (/ x b))
29            2
30         )
31      )
32      1
33   )
34)

7. There are other functions whose fixed-point is the square root of x, eg:

improve(candidate) = (x / candidate)

However the example above oscilates when iterated.

when x = 2 improve(1) = 2 / 1 = 2 improve(2) = 2 / 2 = 1 improve(1) = 2 / 1 = 2

8. The function in (7) can be damped using averaging to find the fixed-point.

Copycopy code to clipboard
1(define (sqrt x)
2   (fixed-point
3      (average-damp
4         (lambda (candidate)
5            (/ x candidate)
6         )
7      )
8      1
9   )
10)
11
12; Higher-order procedure: Procedure that takes procedure as argument and returns a procedure as value.
13(define average-damp
14   (lambda (function)
15      (lambda (x)
16         (average (function x) x)
17      )
18   )
19)

9. Procedure compute function
10. Leibnitz formula for finding pi / 8.
11. Newton's method

Lecture 2B: Compound Data

1. Recap -- Framework for talking about languages: a. Primitives: Things built into the system. b. Means of combination: Where complicated things are built from primitive things. c. Means of abstraction: Where those complicated things can be named and used as simple building blocks.
2. The task of building things can be divorced from the task of implementing the parts using abstraction boundaries that allows a system to be built in layers. Eg: The sqrt function uses good-enough function. The implementation details of good-enough is irrelevant to sqrt -- it could be using abs or any other function for its implementation.

"I said that computer science is a lot like magic, and it's sort of good that it's like magic. There's a bad part of computer science that's a lot like religion. And in general, I think people who really believe that you design everything before you implement it basically are people who haven't designed very many things.

The real power is that you can pretend that you've made the decision and then later on figure out which one is right, which decision you ought to have made. And when you can do that, you have the best of both worlds."

~Harold Abelson, 1986