Csc 4980/6980, Functional Programming (Fall 2026)

Homework 1 (Due: 13 September - Sunday)

sudo handin4980 1 file1 ...

For all of these problems, your should try to solve by hand and then use the command-line interpreter and/or the Visualizer to verify your solution. Submit only screenshots of the final solution from the interpreter/visualizer. You may have to convert the lambda-expressions to the text form and include all relevant parentheses (using the rules for missing parentheses from the slides) so that the expressions are accepted by the interpreter/visualizer.

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. 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
3. 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)
4. 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

What to submit? p1.pdf