Csc 4330/6330, Programming Language Concepts (Summer 2020)

Homework 4 (Due: 14 July (Tuesday); Late Submission: 16 July (Thursday))

sudo handin4330 4 hw4.pdf

1. Draw expression trees for the following λ-expressions:
   1. λx.(x λy.(y x))
   2. λx.λy.((λx.y x p)(λz.z x))
2. Make all parentheses explicit in the following λ-expressions:
   1. (λp.p z) λq.w λw.w q z p
   2. λp.p q λp.q p
3. For each of the following terms, identify the free variables in each term and for each bound variable indicate (by drawing an arrow) to the λ to which it is bound.
   1. λs.s z λq.s q
   2. (λs.s z) λq. w λw.w q z s
4. Apply β-reductions to the folowing λ expressions as much as possible:
   1. (λz.z) (λz.z z) (λz.z q)
   2. (λs.λq.s q q) (λq.q) q
   3. ((λs.s s) (λq.q)) (λq.q)
5. Consider the following definitions for the booleans "true" and "false" and logical operator "and":

   true = λx.λy.x
   false = λx.λy.y
   and = λb1.λb2.(b1 b2 false)
   

   Using β-reductions, show that
   1. (and false true) reduces to false
   2. (and true true) reduces to true