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