Skip to content# SICP — (Book + MIT 6.001 + Berkeley CS61A) Notes

# MIT 6.001 Structure and Interpretation, 1986

## Lecture 1A: Overview and Introduction to Lisp

## Lecture 1B: Procedures and Processes; Substitution Model

## Lecture 2A: Higher-order Procedures

## Lecture 2B: Compound Data

— Book notes — 2 min read

- Fixed point of a function.
- 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.
- Big Topic 1: Black-Box Abstraction
**Capturing Common Patterns**i. High-order procedures ii. Data as procedures - Big Topic 2: Conventional Interfaces i. Generic operations ii. Large-scale structure and modularity iii. Object-orientated programming iv. Operation on aggregates
- Big Topic 3: Metalinguistic Abstraction - making new languages i. Interpretation: Apply-Eval ii. Example: Logic programming iii. Register machine
- 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).

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

- 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.

`1; Implementation of SIGMA (i) from INDEX to UPPER_BOUND2(DEFINE (SUM_INT index upper_bound)3 (IF (> index upper_bound)4 0 ; Easy case5 (+6 index7 (SUM_INT (1+ index) upper_bound) ; Reduced simpler problem -- subproblem to solve for8 )9 )10)`

`1; Implementation of SIGMA (i²) from INDEX to UPPER_BOUND2(DEFINE (SUM_SQUARE index upper_bound)3 (IF (> index upper_bound)4 05 (+6 (SQUARE index)7 (SUM_SQUARE (1+ index) upper_bound)8 )9 )10)`

- Generalizing summation using higher order procedures

`1; Recursively2(DEFINE (SUMMATION term index index_stepper upper_bound)3 (IF (> index upper_bound)4 05 (+6 (term index) ; term provides term at index7 (SUMMATION8 term9 (index_stepper index)10 index_stepper11 upper_bound12 )13 )14 )15)1617; Iteratively18(DEFINE (SUMMATION term lower_bound index_stepper upper_bound)19 (DEFINE (ITER index accumulator)20 (IF (> index upper_bound)21 accumulator22 (ITER23 (index_stepper index)24 (+25 accumulator26 (term index)27 )28 )29 )30 )3132 (ITER lower_bound 0)33)`

`1(DEFINE (SUM_INT index upper_bound)2 (SUMMATION3 (LAMBDA (x) x)4 index5 +16 upper_bound7 )8)`

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

`1(define (sqrt x)2 (define tolerance 0.00001)34 (define (good-enough? candidate)5 (<6 (abs (- (* candidate candidate) x))7 tolerance8 )9 )1011 (define (improve candidate)12 (average13 (/ x candidate)14 candidate15 )16 )1718 (define (find-sqrt candidate)19 (if (good-enough? candidate)20 candidate21 (find-sqrt (improve candidate))22 )23 )2425 (find-sqrt 1)26)2728(define (average m n)29 (/30 (+ m n)31 232 )33)`

- 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 = 3Therefore, the fixed-point of the function

improve(candidate) is what is desired.

- 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.

`1(define (fixed-point function start)2 3 (define tolerance 0.00001)45 ; Checks if two input are close enough as defined by the tolerance6 (define (close-enough m n)7 (<8 (abs (- m n))9 tolerance10 )11 )1213 ; Repeat until old and new are close enough14 (define (iter old new)15 (if (close-enough old new)16 new17 (iter new (function new))18 )19 )2021 (iter start (function start))22)2324(define (sqrt x)25 (fixed-point26 (lambda (b)27 (/28 (+ b (/ x b))29 230 )31 )32 133 )34)`

- 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

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

`1(define (sqrt x)2 (fixed-point3 (average-damp4 (lambda (candidate)5 (/ x candidate)6 )7 )8 19 )10)1112; Higher-order procedure: Procedure that takes procedure as argument and returns a procedure as value.13(define average-damp14 (lambda (function)15 (lambda (x)16 (average (function x) x)17 )18 )19)`

- Procedure compute function
- Leibnitz formula for finding pi / 8.
- Newton's method

- 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.
- 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