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 ) (foo 120) 10 (cube (factorial 5)) (cube ) (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)) (* ) (* 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)) (count1 4) (begin (our-display 4) (count1 3)) (count1 3) (begin (our-display 3) (count1 2)) (count1 2) (begin (our-display 2) (count1 1)) (count1 1) (begin (our-display 1) (count1 0)) (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)) (begin (begin (begin (our-display 2) (our-display 3)) (our-display 4)) (our-display 5)) (begin (begin (our-display 3) (our-display 4)) (our-display 5)) (begin (our-display 4) (our-display 5)) (our-display 5) => 5 -----------------------------------------------------