CMSC330 Spring 2011 Quiz #4 Name Discussion Time (circle one): 9am 10am 11am 12pm 1pm 2pm Instructions • Do not start this test until you are told to do so! • You have 15 minutes for this quiz. • This is a closed book test. No notes or other aids are allowed. • For partial credit, show all of your work and clearly indicate your answers. • Write neatly. Credit cannot be given for illegible answers. 1. (6 pts) Beta-reduction Write down what each of the following reduces to via a single beta-reduction step. a. (λx. (x x)) (λx. (x x)) RESULT = b. (λf.λx. (f x)) (λy. x) RESULT = c. (λx.λy. x) 0 1 RESULT = 2. (5 pts) Arithmetic Suppose you are given a lambda expression pred that computes the predecessor of a Church numeral n. That is: !"#$!! = !0 !"!! = 0! − 1 !"ℎ!"#$%! Using pred and other operators in class, give a function that, given Church numerals M and N, computes the Church numeral representation of M – N, where the result is 0 if N > M. Your function should have the following form: λM.λN. E for some E. Recall that Church numeral N has form λf.λx. f (f … (f x)), where f is applied N times to x.3. (4 pts) Free variables For each of the following expressions, write “yes” if variable x has at least one free (i.e. unbound) occurrence within the term and “no” if it does not. a. λx. x ANSWER = b. x (λx. x) ANSWER = c. λf. (λx. f (x x)) (λx. f (x x)) ANSWER = d. (λx.y) (λy. x) ANSWER
View Full Document
Unlocking...