MIT 6.001 SICP Notes

L1

lecture-notes

Computer science

~~Science~~ engineering or art
~~Computer~~ process
cs & geometry
- Declarative Knowledge //geometry
  - What is square root
- Imperative Knowledge //cs
  - How to find a square root
  - procedure: describe how-to
  - process: sequence of steps by evaluating the procedure

Controlling complexity <- ==Key Idea in 6.001==

Black-box abstraction
- Primitive objects
  - Primitive procedures
  - Primitive data
- Means of combination
  - Procedure composition
  - Construction of compound data
- Means of abstraction // using procedure as primitive
  - Procedure definition
  - Simple data abstraction
- Capturing common patterns // find sqrt -> find fixed point
  - High-order procedures
  - Data as procedures
Conventional interfaces
- OOP
- Manifest typing // List <- Lisp
- Stream // Text & file <- Unix
Meta-linguistic abstraction
- Making new languages

Scheme

Black-box abstraction
- primitives
  +,1,2.5,#f,#t,"string"...
- means of combination
  () if...
- means of abstraction - names
  (define (sq x) (* x x))
  (define sq2 (λ(x) (* x x)))
  (define pi 3.14)
  (define plus +)
Substitution Model
1. eval the operator to get procedure
2. eval the operands to get args
3. apply the procedure to the args:
  copy the procedure, substituting the args
4. eval the result //goto 1
Kinds of expressions
- Numbers
- Symbols
- Lambda expressions
- Definitions
- Conditionals
- Combinations

Peano Arithmetic
参考：皮亚诺公理

# two ways to add whole numbers, both recursive definitions
# linear iteration time:O(x) space:O(1)
(define (+ x y)
	(if (= x 0)
		y
		(+ (-1+ x) (1+ y))))
# linear recursion time:O(x) space:O(x)
(define (+ x y)
	(if (= x 0)
		y
		(1+ (+ (-1+ x) y ))))

recursive fibonacci
time: O(~1.618^n) space: O(n) // longest path of tree
feeling the procedure to processes
general rule break to many instances of local rule

recursive hanoi

#lang racket
(define (move n src dest temp)
  (if (> n 0)
      (begin
        (move (- n 1) src temp dest)
        (printf "move ~a from ~a to ~a~n" n src dest)
        (move (- n 1) temp dest src))
      "done"))
(move 3 "src" "dest" "temp")

L2

High-order procedures

SICP 1.3

$\sum_\limits{i=a}^bi$

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

$\sum_\limits{i=a}^bi^2$

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

$\sum$ not depending upon $i$

… making complicated system and understand them, it’s crucial to divide the things up into as many pieces as I can, each of which I understand separately … having debugged it once and unserstood it once and been able to share that …

Leibnitz’s formula, pi-sum, different ways of sum
$\sum_{i=a, by~4}^b\frac1{i(i+2)}$

General pattern

(define (<name> a b)
	(if (> a b)
		0
		(+ (<term> a)
			(<name> (<next> a) b))))
			
(define (sum term a next b)
	(if (> a b)
		0
		(+ (term a)
			(sum term
				(next a)
				next
				b))))
				
(define (pi-sum a b)
	(sum (λ(i)(/ 1(* i (+ i 2))))
		a
		(λ(i)(+ i 4))
		b))

Iterative sum

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

Heron’s square root algorithm
$y \to \frac{y+\frac{x}y}{2}$
$f(\sqrt{x})=\sqrt{x}$
Look for a Fixed-Point of $f$

(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)))

how converge
$y \to \frac{x}y$
damp out oscillations

(define (sqrt x)
	(fixed-point
		(average-damp (λ(y)(/ x y)))
		1))
# high-order procedure
(define average-damp
	(λ(f)
		(λ(x)(average (f x) x))))

// formal parameter(parameter), actual parameter(argument)

Newton’s method

to find a $y$ such that
$f(y)=0$
start with a guess, $y0$
$y{n+1}=y_n-\frac{f(yn)}{\frac{df}{dy}\big|{y=y_n}}$

Wishful thinking, essential to good engineering…

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

// derivative, quotient

Denotational semantics

The rights and 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

Compound Data

SICP 2.1

build system in layers

rational number math
$\frac{n_1}{d_1}\frac{n_2}{d_2}=\frac{n_1n_2}{d_1*d_2}$

# abstract data
define make-rat n d //constructor
define numer x	 //selector
define denom x
(define (*rat x y)
	(make-rat (* (numer x)(numer y)
					(* (denom x)(denom y))))

*rat(n1, d1, n2, d2)
// numerator, denominator

List structure
Pairs: box and pointer notation

1
2
3

(cons x y) # constructs a pair
(car p) # selects the 1st part
(cdr p) # selects the 2nd part

+rat *rat -rat
make-rat / numer / denom <- abstraction layer
pairs

1
2
3

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

# bad way: defining *rat w/o data abstraction
(define (*rat x y)
	(make-rat (* (car x)(car y)
					(* (cdr x)(cdr y))))

Data Abstration -> seperate the use and representation

If you have the name of the spirit, you get control over it

Deferring decisions

To reatin flexibility, never make up your mind about anything until you’re forced to do it. Use abstractions.

Layered system:
L1. segments # is pairs of vectors
constructors/selectors
L2. vectors # is pairs of numbers
constructors/selectors
L3. pairs

calc the length of segment

calc by vectors
calc by pairs <- hard to read, hard to change

What a rational number is really?

Axiom for rational number:
if x = (make-rat n d)
then (numer x)/(denom x) = n/d

What are Pairs really?

Axiom for pairs:
For any x and y
(car (cons x y)) is x
(cdr (cons x y)) is y

==spoiler alert==

(define (cons a b)
	(λ(pick)
		(cond ((= pick 1) a)
				((= pick 2) b))))
(define (car x) (x 1))
(define (cdr x) (x 2))

reinfore the idea of abstraction
introduce an idea about blurring the line between procedure and data

L3

SICP 2.2

Closure

elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set
an implementation technique for representing procedures with free variables not use this sense in this book

LIST

Conventional Interface
(1,*)->(2,*)->(3,*)->(4,) // conventional
(list 1 2 3 4) // syntactic sugar

General pattern to process list

map

(define (map p l)
	(if (null? l)
		nil
		(cons (p (car l))	# cons up
			(map p (cdr l))))) # cdring down

for-each

Escher - Square Limit

Tackling complex system: build a language
- primitives
  - picture
- means of combination
  - rotate, flip, beside, above
- mean of abstraction
embedded languages
making full use of surrounding language
Two kinds of design
- Layers of language
  
  Language of Schemes of Combination
  Language of Geometric Positions
  Language of Primitive Pictures
  - full range of linguistic power at each level
  - more robust
  - vocabularies fro talking about the degsign at different levels
- Trees of task
  - each node representing a specific task
The powerful of Lisp

the design process is not so much implementing programs as implementing languages

Symbolic Differentiation

SICP 2.3

Robust system

Insensitive to small changes, the space of solutions ought to be a continuous in this space of problems

How-to
- Solve a problem at every level of
  decomposition of the problem at the subproblems
- Solve the class of problems which are a neightborhood of the particulare problem, by producing a language at that level of detail in which the solutions to that class of problems is representable in that language

make changes to the problems == change the solution constructed by that language

Rest of the lecture:
Translate derivative rules to lisp

L4

Pattern-maching: Rule-based Substitution

Pattern ----Rule----> Skeleton
|                   |
|Match              |Instantiation
|                   |
Expressions --------> Expressions
Source                Target

Full code of 4A

(define deriv-rules
	'(
		((dd (?c c) (? v)) 0)
		((dd (?v v) (? v)) 1)
		; ...
		; Derivative of (+ x1 x2) in respect to v
		((dd (+ (? x1) (? x2)) (? v))
			(+
				(dd (: x1) (: v))
				(dd (: x2) (: v))))
		;...

# Pattern match
foo		- matches exactly foo
(f a b)	- matches list in which first element if f, second is a, third is b
(? x)		- matches anything, call it x
(?c x)	- matches constant, call it x
(?v x)	- matches variable, call it x
# Skeletons
foo		- instantiates itself
(f a b)	- instantiates to a 3-list => results of initializing f, a, b
(: x)		- initialize to the value of x in the matched pattern

Matcher

              Pattern
                |
Expression -> Matcher -> Dictionary
                |
              Dictionary

Pattern: (+ (* (? x) (? y)) (? y))
Expression: (+ (* 3 x) x)
traverse two tees simultaneously, result: matched, dict{x=3, y=’x}

Instantiate

1
2
3

              Skeleton
                |
Dictionary -> Matcher -> Expression

Simplifier
// GIGO

(define (simplifier the-rules)
	(define (simplify-exp exp)
		(try-rules (if (COMPOUND? exp)
						(simplify-parts exp)
						exp))
	)
	(define (simplify-parts exp)
		(if (NULL? exp)
			'() ; empty expression
			(cons
				(simplify-exp (car exp))
				(simplify-parts (cdr exp)))
		)
	)
	(define (try-rules exp)
		(define (scan rules) ; Loop through rules
			(if (NULL? rules)
				exp
				(let ((dict
					(match (pattern (car rules)); try first rule 
						exp
						(empty-dictionary))))
				(if (EQ? dict 'failed)			; if failed, try other rules 
					(scan (cdr (rules))
					(simplify-exp				; Side-effects, hide!
						(instantiate
							(skeleton (car rules) dict))))))
			))
		(scan the-rules) 
	)
	simplify-exp)

Dictionary

Generic Operators

SICP 2.4

Horizontal barrier: between use(interface) and representation(implementation)
Vertical barrier: between different representations

Complex number arithmetic

// real-part, imaginary-part, magnitude, angle

Two representations
- Polar // easy to multiply
- Rectangular // easy to add
Typed data
(define (attach-type type contents) (cons type contents))
Generic operator
- dispatch on type
  - a manager check the type and call the right procedures
- data-directed programming
  - use a table to replace manager
    - (put key1 key2 value)
    - (get key1 key2 value)
  ~ | polar | rectangular
  — | — | —
  real-part | real-polar | real-rect
  imag-part | ~ | ~
  mag | mag-polar | mag-rect
  angle | ~ | ~
  1
  2
  3
  4
  5
  6
  (define (operate op obj)
  (let
  ((proc (get (type obj) op)))
  (if (not (null? proc))
  (proc (contents obj))
  (error "undefined op"))))
Generic ADD/SUB/MUL/DIV
- operate rational, complex, ordinary, polynomial …
- chains of types
  - (complex,)->(rect,)->(1,2)
  - (poly,)->(poly,)->…->(complex,)->(rect,)->(2,3)

L5

SICP 3.1 & 3.2

Variable
- Introduce time in procedure
Functional ~ Imperative

# functional
(define (fact n)
  (define (iter rlt i)
    (cond ((> i n) rlt)
          (else (iter (* rlt i) (add1 i)))))
  (iter 1 1))
# imperative
(define (fact-i n)
  (let ((i 1) (rlt 1))
    (define (loop)
      (cond ((> i n) rlt)
            (else
             # sequence sensitive, can't switch below two
             (set! rlt (* i rlt)) 
             (set! i (add1 i))
             (loop))))
    (loop)))

Substitution model not working
Environment model
- Bound variables & Free variables
  - (λ(x) (* x y)) y is free, * is free, x is bound
- Scope
  - bind by lambda
- Environment
  - Sequence of linked frames
- Frame
  - Map variables to values //on name conflict, child’s shadow parent’s
- Procedure
  - Compound of procedure code and environment
Why assignment
- for objects with local state
- for decomposition

SICP 3.3

Circuits simulator
Agenda
Mutable CONS