CMPSC 461: Programming Language Concepts Assignment 1 Solutions

CMPSC 461: Programming Language Concepts Assignment 1 Solution Problem 1 [6pt] Add parentheses to the following lambda terms so that the grouping of sub-terms becomes explicit. For example, the term λx. x λy. y with parentheses is λx. (x (λy. y)). a) (3pt) λx. λy. x y z Solution: λx. (λy. ((x y) z)) b) (3pt) λx. λy. (λx. x x) y λz. x z Solution: λx. (λy. (((λx. (x x)) y) (λz. (x z)))) Problem 2 [6pt] Fully evaluate the following λ-term so that no further β-reduction is possible. (λx. (λy. y y) x) y λx. x Solution: ((λx. (λy. (y y)) x) y) (λx. x) = ((λx. (λz. (z z)) x) y) (λx. x) (α − reduction) = ((λz. (z z)) y) (λx. x) (β − reduction) = (y y) (λx. x) (β − reduction) Problem 3 [10pt] Recall that under Church encoding, addition is defined as follows: + , λn1 n2 f z . (n1 f (n2 f z)) Show that (+ 2 3) = 5 under Church encoding, where n , λf z . fn z. Solution: + 2 3 = (λn1 n2 f z . (n1 f (n2 f z))) 2 3 (definition of +) = (λf z . (n1 f (n2 f z))){2/n1}{3/n2} (β − reduction) = λf z. (2 f (3 f z))) = λf z. (2 f ((λf z . f 3 z) f z))) (definition of 3) = λf z. (2 f (f 3 z)) (β − reduction) = λf z. ((λf z . f 2 z) f (f 3 z)) (definition of 2) = λf z. ((f 2 z){f /f}{(f 3 z)/z} (β − reduction) = λf z. (f 2 (f 3 z)) = λf z. (f (f (f