recitation 3: substitution model

-----------------------------------------------------
rules of the substitution model
1. if self-eval, return the value
2. if name, replace with value associated with that name
3. if special form
   * if lambda, create procedure and return it
   * same for "if" "and", etc.
4. if combination
   * evaluate subexpressions in any order
   * if primitive procedure, just do it
   * if compound procedure (lambda)
     substitute the value of each subexpression
     into the procedure body and evaluate body

-----------------------------------------------------
* do one thing at a time
* take small steps
* sometimes we have a choice of what to evaluate next

(if (= (+ 5 2) 7) (* (+ 2 3) 5) (/ 4 (- 7 5)))
(if (= 7 7) (* (+ 2 3) 5) (/ 4 (- 7 5)))
(if #t (* (+ 2 3) 5) (/ 4 (- 7 5)))
(* (+ 2 3) 5)
(* 5 5)
25

-----------------------------------------------------
applicative order vs. normal order

(define (foo x) 10)
(define (cube x) (* x x x))
(define (factorial x) (if (= x 1) 1 (* x (factorial (- x 1)))))

applicative order (regular scheme):

(factorial 3) 
(if (= 3 1) 1 (* 3 (factorial (- 3 1))))
(if #f 1 (* 3 (factorial (- 3 1))))
(* 3 (factorial (- 3 1)))
(* 3 (factorial 2))
(* 3 (if (= 2 1) 1 (* 2 (factorial (- 2 1)))))
(* 3 (if #f 1 (* 2 (factorial (- 2 1)))))
(* 3 (* 2 (factorial (- 2 1))))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (if (= 1 1) 1 (* 1 (factorial (- 1 1))))))
(* 3 (* 2 (if #t 1 (* 1 (factorial (- 1 1))))))
(* 3 (* 2 1))
(* 3 2)
6

(foo (factorial 5)) 
(foo <lots of steps>)
(foo 120) 
10

(cube (factorial 5))
(cube <lots of steps>)
(cube 120)
(* 120 120 120)
1728000

normal order (lazy - don't do any work until you have to):

(foo (/ 5 0))
10

(foo (factorial 5))
10

(cube (factorial 5))
(* (factorial 5) (factorial 5) (factorial 5))
(* <lots of steps> <lots of steps> <lots of steps>)
(* 120 120 120)
1728000

(factorial (factorial 5))
  * how much work is this?

-----------------------------------------------------

(define (our-display x) (display x) x)

(define (count1 x)
  (if (= x 0) 
      0
      (begin (our-display x)
	     (count1 (- x 1)))))

(define (count2 x)
  (if (= x 0) 
      0
      (begin (count2 (- x 1))
	     (our-display x))))

(count1 5)
54321
;Value: 0

(count2 5)
12345
;Value: 5

(count1 5)
(begin (our-display 5) (count1 4)) <PRINT 5>
(count1 4)
(begin (our-display 4) (count1 3)) <PRINT 4>
(count1 3)
(begin (our-display 3) (count1 2)) <PRINT 3>
(count1 2)
(begin (our-display 2) (count1 1)) <PRINT 2>
(count1 1)
(begin (our-display 1) (count1 0)) <PRINT 1>
(count1 0)
=> 0

(count2 5)
(begin (count2 4) (our-display 5))
(begin (begin (count2 3) (our-display 4)) (our-display 5))
(begin (begin (begin (count2 2) (our-display 3)) (our-display 4)) (our-display 5))
(begin (begin (begin (begin (count2 1) (our-display 2)) (our-display 3)) (our-display 4)) (our-display 5))
(begin (begin (begin (begin (begin (count2 0) (our-display 1)) (our-display 2)) (our-display 3)) (our-display 4)) (our-display 5))
(begin (begin (begin (begin (our-display 1) (our-display 2)) (our-display 3)) (our-display 4)) (our-display 5)) <PRINT 1>
(begin (begin (begin (our-display 2) (our-display 3)) (our-display 4)) (our-display 5)) <PRINT 2>
(begin (begin (our-display 3) (our-display 4)) (our-display 5)) <PRINT 3>
(begin (our-display 4) (our-display 5)) <PRINT 4>
(our-display 5) <PRINT 5>
=> 5

-----------------------------------------------------