Programming Language Concepts CMPSC 461, FALL 2018 Midterm #1 Solutions

Programming Language Concepts CMPSC 461, FALL 2018 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 4 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 [8pt] Circle all free (unbound) variable occurrences in the following terms • x λx. x z λy. y x x λx. x z λy. y x • (λx. x y) λy. y x (λx. x y) λy. y x Problem 2 [13pt] Combinatory logic (introduced by Moses Schonfinkel and Haskell Curry) is ¨ a simplified model of computation, used in computability theory and proof theory. Computation in combinatory logic is formalized by combinators. Using λ-calculus, we can define combinators I, K, S as follows: I , λx. x K , λx y. x S , λx y z. (x z (y z)) 1. (4pt) α-reduce the definition of S so that z is renamed to u. λx y u. (x u (y u)) 2. (4pt) Write down K and S in their fully curried forms. K , λx . (λy . x) S , λx . (λy . (λz . ((