* Lecture 1B
https://youtu.be/V_7mmwpgJHU

the spells we write direct a process

#+BEGIN_SRC scheme

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

#+END_SRC

#+RESULTS:
: 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))))

#+BEGIN_SRC scheme

;; (+ 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

#+END_SRC

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