sicpsgjd/1/2/jord/lecture.org

• Lecture 1B
  • the shapes of programs for shapes of processes

Lecture 1B

https://youtu.be/V_7mmwpgJHU

the spells we write direct a process

(define (sum-of-squares x y)
  (+ (square x) (square y)))
(define (square x)
  (* x x))
(sum-of-squares 3 4) ;; --> 25

25

we can develop mental models for how these processes behave the simplest of these is the substitution model

KINDS OF EXPRESSIONS (* denotes special case):

• numbers

• symbols

• λ-expressions*

• definitions*

• conditionals*

• combinations

SUBSTITUTION RULE: to evaluate an application,

• evaluate operator to get procedure

• evaluate operands to get arguments

• apply the procedure to the arguments

  • copy body of the procedure, sub args for formal params

  • exaluate resulting body

(sum-of-squares 3 4) (+ (square 3) (square 4)) (+ (square 3) (* 4 4)) (+ (square 3) 16) (+ (* 3 3) 16) (+ 9 16) 25

learn to ignore details! what not to compute! what not to think!

to evaluate an IF expr:

• evaluate the predicate

  • if it yields TRUE

    • evaluate consequent

  • otherwise

    • evaluate alternate

(IF <predicate> <consequent> <alternative>)

"any sorceror will tell you, if you have the name of something, you have power over it"

an important program we will revisit using "peano arithmetic" (define (+ x y) (if (= x 0) y (+ (-1+ x) (1+ y))))

(+ 3 4) (if (= 3 0) 4 (+ (-1+ 3) (1+ 4)) (+ (-1+ 3) (1+ 4)) (+ (-1+ 3) 5) (+ 2 5) (if (= 2 0) 5 (+ (-1+ 2 (1+ 5)))) (+ 1 6) (+ 0 7) 7

the shapes of programs for shapes of processes

like photography, there are simple rules, but to be a creative person, we must be able to do analysis. to get an imagined result, what techniques must be employed.

back to peano arithmetic, two ways to add whole numbers: (define (+ x y) (if (= x 0) y (+ (-1+ x) (1+ y)))) (define (+ x y) (if (= x 0) y (1+ (+ (-1+ x) y))))

;; (+ 3 4)         (+ 3 4)
;; (+ 2 5)         (+1 (+ 2 4))
;; (+ 1 6)         (+1 (+1 (+ 1 4)))
;; (+ 0 7)         (+1 (+1 (+1 (+ 0 4))))
;; 7               (+1 (+1 (+1 4)))
;;                 (+1 (+1 5))
;;                 (+1 6)
;;                 7

on the left: time = O(x), space = O(1) ;;iterative! on the rght: time = O(x), space = O(x) ;;recursive!

recursion is bureaucratic ("keeps more ppl employed!") iteration has all its state in its variables recursion keeps some information under the table

here are some programs, using probably the worst way you can write them

for fibbonacci numbers, (define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))

; fib 4 ; / \ ; fib 3 fib 2 ; / \ / \ ; fib 2 fib 1 fib 1 fib 0 ; / \ | | | ; fib 1 fib 0 1 1 0 ; | | ; 1 0

time: O(fib n) space: O(n)

ppl think programming is hard bc you are describing a general process to describe any specific case.

for towers of hanoi, (define (move n from to spare) (cond ((= n 0) "done") (else (move (-1+ n) from spare to) (print-move from to) (move (-1+ n) spare to from)))) (move-tower 4 1 2 3) ;; move 4-high tower using pegs 1, 2, 3 (move-tower 3 1 3 2) - (move … (move-tower 2 1 2 3) - (move … (move-tower 1 1 3 2) - (move …