Programming Languages Concepts CMPSC 461, FALL 2016 Midterm #1 Solutions

Programming Languages Concepts CMPSC 461, FALL 2016 Midterm #1 Solution This exam is closed book, closed notes. You may not use any additional materials during the exam. All electronic devices must be put away. You may have nothing on your desk except this exam and writing instruments. The exam consists of 8 questions and 1 bonus question on 6 pages, totaling 100 points + 10 bonus points. Read each question carefully and use your time judiciously. The problems are not ordered by their difficulty. Problem 1 [28pt] 1. (8pt) Circle all free (unbound) variable occurrences in the following terms • λx. x z λy. x y λx. x z λy. x y • λx. x y λx. y x λx. x y λy. y x 2. (8pt) Consider a λ-term: λx y z. (x z) (y z) • Write this terms in the fully curried form λx .(λy. (λz. ((x z) (y z)))) • Fully evaluate: (λx y z. (x z) (y z)) u v (λx y z. (x z) (y z)) u v = (λx .(λy. (λz. ((x z) (y z))))) u v = (λy. (λz. ((u z) (y z)))) v = λz. ((u z) (v z)) 3. (6pt) Given the following encodings: OR , λx y. (x TRUE y), TRUE , λx y. x, and FALSE , λx y. y, show that (OR FALSE TRUE) evaluates to TRUE. OR FALSE TRUE = λx. λy. ((x TRUE) y) FALSE TRUE = FALSE TRUE TRUE = (λx. (λy . y)) TRUE TRUE = TRUE 4. (6pt) Encode the NOT operation in λ-calculus, so that NOT TRUE = FALSE and NOT FALSE = TRUE, where TRUE and FALSE are defined as in