SICP - Procedures, Processes, and the Substitution Model

I was skeptical about learning in LISP, but after reading Paul Graham's letter regarding the use of LISP in his start up Viaweb, I was intrigued. So I'll muddle through this lecture series and see what I learn about LISP, and about computing fundamentals.  Covered a couple interesting topics today, including the substitution model, and covered some real basic concepts related to time and space complexity.  I had been thinking that I might want to learn more about recursion and it seems like I'm going to get the opportunity in this class.



I took pretty copious notes this time around, mostly related to writing out the program substitutions long hand. Probably unnecessary but an interesting exercise regardless. I tried using Notepad++ for my notes this time around, hopefully it is less of a fiasco than using Google Docs:

Substitution model - models how procedures are mapped to processes.

Kinds of symbols:
     Numbers
     Symbols
     Lambda expressions
     Definitions
     Conditionals
     Combinations

Substitution rule
To evaluate a combination:
     Evaluate the operator to get procedure
     Evaluate the operands to get arguments
     Apply the procedure to the arguments
          Copy the body of the procedure
               substituting the arguments supplied
               for the formal parameters of the
               procedure
     Evaluate the resulting new body

Sum of squares example:
(SOS 3 4)
(+ (Square 3) (Square 4))
(+ (Square 3) (* 4 4))
(+ (Square 3) 16)
(+ (* 3 3) 16)
(+ 9 16)
25


To evaluate an IF expression
     Evaluate the predicate expression (the part that is true or false)
          if it yields TRUE
               evaluate the consequent expression
          otherwise
               evaluate the alternative expression

(define (+ x y) (Peano arithmatic)
     (if (= x 0)
          y
          (+ (-1+ x) (1+ y))))

-1+ decrementer
1+ incrementer

Another version:
(define (+ x y)
     (if (= x 0)
          y
          (1+ (+ (-1+ x) y))))

First version
(+ 3 4)
(if (= 3 0) 4 (+ (-1+ 3) (1+ 4)))
(if (= 3 0) 4 (+ 2 5))
(if (= 2 0) 5 (+ (-1+ 2) (1+ 5)))
(if (= 2 0) 5 (+ 1 6)))
(if (= 1 0) 6 (+ (-1+ 1) (1+ 6)))
(if (= 1 0) 6 (+ 0 7))))
(if (= 0 0) 7 (+ (-1+ 0) (1+ 7)))
7
time complexity is proportional to x => O(x)
space complexity is constant => O(1)
Linear Iteration.

Second version
(+ 3 4)
(if (= 3 0) 4 (1+ (+ (-1+ 3) 4)))
(if (= 3 0) 4 (1+ (+ 2 4)))
(if (= 3 0) 4 (1+ (if (= 2 0) 4 (1+ (+ (-1+ 2) 4)))))
(if (= 3 0) 4 (1+ (if (= 2 0) 4 (1+ (+ 1 4)))))
(if (= 3 0) 4 (1+ (if (= 2 0) 4 (1+ (if (= 1 0) 4 (1+ (+ (-1+ 1) 4)))))))
(if (= 3 0) 4 (1+ (if (= 2 0) 4 (1+ (if (= 1 0) 4 (1+ (+ 0 4)))))))
(if (= 3 0) 4 (1+ (if (= 2 0) 4 (1+ (if (= 1 0) 4 (1+ (if (= 0 0) 4 (1+ (+ (-1+ 0) 4)))))))))
(if (= 3 0) 4 (1+ (if (= 2 0) 4 (1+ (if (= 1 0) 4 (1+ 4))))))
(if (= 3 0) 4 (1+ (if (= 2 0) 4 (1+ (if (= 1 0) 4 5)))))
(if (= 3 0) 4 (1+ (if (= 2 0) 4 (1+ 5))))
(if (= 3 0) 4 (1+ (if (= 2 0) 4 6)))
(if (= 3 0) 4 (1+ 6))
(if (= 3 0) 4 7)
7
time complexity is proportional to x => O(x)
space complexity is proportional to x => O(x)
Linear Recursion.

Fibonacci program
(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)) (fib 1)) (+ (fib 1) (fib 0)))
(+ (+ (+ (fib 1) (fib 0)) (fib 1)) (+ 1 0))
(+ (+ (+ (fib 1) (fib 0)) (fib 1)) 1)
(+ (+ (+ 1 0) (fib 1)) 1)
(+ (+ 1 (fib 1)) 1)
(+ (+ 1 1) 1)
(+ 2 1)
3

time complexity = O(fib n)
space complexity = O(n)
NOT GOOD!

Towers of Hanoi problem (n discs and 3 towers)
(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 4 1 2 3)
(move 3 1 3 2)...
(move 2 1 2 3)...
(move 1 1 3 2)

Wants us to think about if there is an iterative algorithm for this problem...
Asked about saving intermediate work (regards the Fibonacci problem)