(jordyn sicp)

Lecture 1B: Procedures and Processes; Substitution Model

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

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