recitation 2: lambda & the substitution model ----------------------------------------------------------------- * 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 * syntactic sugar, syntax vs. semantics (define <name> <==> (define (<name> <args>) (lambda (<args>) <body>)) <body>) ----------------------------------------------------------------- (define four 4) (define six (lambda () 6)) four => 4 six => procedure (+ four 1) => 5 (+ six 1) => error, can't add non-numbers (+ (four) 1) => error, 4 is not a procedure (+ (six) 1) => 7 (define f-add (lambda (x y) (+ (x) (y)))) (f-add six (lambda () four)) => 10 (define (p) (p)) p => procedure (p) => infinite loop!! ----------------------------------------------------------------- what can we deduce about the ? note: there are many correct answers for each part! (define a ?) a => 6 (define a (+ 4 2)) (define b ?) (b 2) => 6 (define b (lambda (x) (* x 3))) (define c ?) (+ 2 (c)) => 6 (define c (lambda (x) 4)) (define d ?) (d 10 11) => 10 (d + -) => proc (define d (lambda (x) x)) (define e ?) (e 4) => 6 (e 5) => 7 (e 6) => error, divide by zero (e 7) => proc (define e (lambda (x) (cond ((< x 6) (+ x 2)) ((= x 6) (/ x 0)) (else +)))) ----------------------------------------------------------------- Suppose we're designing an order-tracking system for a fast food restaurant with 4 options: Classic Single Combo (hamburger with one patty), Classic Double With Cheese Combo (2 patties), and Classic Triple with Cheese Combo (3 patties), Avant-Garde Quadruple with Guacamole Combo (4 patties). We shall encode these combos as 1, 2, 3, and 4 respectively. Each meal can be "biggie-sized" to acquire a larger box of fries and drink. A biggie-sized combo is represented by 5, 6, 7, and 8 respectively. (a) Write a procedure named biggie-size which when given a regular combo returns a biggie-sized version. (define biggie-size (lambda (combo) (+ 4 combo))) (b) Write a procedure named unbiggie-size which when given a biggie-sized combo returns a non-biggie-sized version. (define unbiggie-size (lambda (combo) (- combo 4))) (c) Write a procedure named biggie-size? which when given a combo, returns true if the combo has been biggie-sized and false otherwise. (define biggie-size? (lambda (combo) (> combo 4))) (d) Write a procedure named combo-price which takes a combo and returns the price of the combo. Each patty costs $1.17, and a biggie-sized version costs $.50 extra overall. (define combo-price (lambda (combo) (if (biggie-size? combo) (+ .5 (* 1.17 (unbiggie-size combo))) (* 1.17 combo)))) (e) An order is a collection of combos. We encode an order as multi-digit number where each digit represents a combo. For example, the order 327 represents a Triple, Double, and biggie-sized Triple. Write a procedure named empty-order which takes no arguments and returns an empty order. (define empty-order (lambda () 0)) (f) Write a procedure named add-to-order which takes an order and a combo and returns a new order which contains the contents of the old order and the new combo. (define add-to-order (lambda (order combo) (+ (* 10 order) combo))) (g) Write a procedure named order-size which takes an order and returns the number of combos in the order. For example, (order-size 237) => 3. (define order-size (lambda (order) (if (= order 0) 0 (+ 1 (order-size (quotient order 10)))))) (h) Write a procedure named order-cost which takes an order and returns the total cost of all the combos. You may find quotient (integer division) useful. (define order-price (lambda (order) (if (= order 0) 0 (+ (combo-price (remainder order 10)) (order-price (quotient order 10))))))