Csc 4980/6980, Functional Programming (Fall 2026)

Homework 1 (Due: 13 September - Sunday)

SOLUTION

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)

      (lambda z z) (lambda z z z) (lambda z z q)
      (((lambda z z) (lambda z (z z))) (lambda z (z q)));
      
      LAMBDA> (((lambda z z) (lambda z (z z))) (lambda z (z q)));
      
      INPUT:  (((LAMBDA Z Z) (LAMBDA Z (Z Z))) (LAMBDA Z (Z Q)))
      BETA:  ((LAMBDA Z (Z Z)) (LAMBDA Z (Z Q)))
      BETA:  ((LAMBDA Z (Z Q)) (LAMBDA Z (Z Q)))
      BETA:  ((LAMBDA Z (Z Q)) Q)
      BETA:  (Q Q)
      BETA REDUCT:  (Q Q)
      
      ANSWER:  (Q Q) 
      

   2. (λs.λq.s q q) (λq.q) q

      (lambda s lambda q s q q)(lambda q q) q
      (((lambda s (lambda q ((s q) q)))(lambda q q)) q);
      
      LAMBDA> (((lambda s (lambda q ((s q) q)))(lambda q q)) q);
      
      INPUT:  (((LAMBDA S (LAMBDA Q ((S Q) Q))) (LAMBDA Q Q)) Q)
      BETA:  ((LAMBDA Q (((LAMBDA Q Q) Q) Q)) Q)
      BETA:  (((LAMBDA Q Q) Q) Q)
      BETA:  (Q Q)
      BETA REDUCT:  (Q Q)
      
      ANSWER:  (Q Q)
      

   3. ((λs.s s) (λq.q)) (λq.q)

      ((lambda s s s) (lambda q q)) (lambda q q)
      (((lambda s (s s)) (lambda q q)) (lambda q q));
      
      LAMBDA> (((lambda s (s s)) (lambda q q)) (lambda q q));
      
      INPUT:  (((LAMBDA S (S S)) (LAMBDA Q Q)) (LAMBDA Q Q))
      BETA:  (((LAMBDA Q Q) (LAMBDA Q Q)) (LAMBDA Q Q))
      BETA:  ((LAMBDA Q Q) (LAMBDA Q Q))
      BETA:  (LAMBDA Q Q)
      BETA REDUCT:  (LAMBDA Q Q)
      
      ANSWER:  (LAMBDA 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

      (and false true)
      ((and false) true)
      (((lambda b1 (lambda b2 ((b1 b2) (lambda x (lambda y y))))) (lambda x (lambda y y))) (lambda x (lambda y x)));
      
      LAMBDA> (((lambda b1 (lambda b2 ((b1 b2) (lambda x (lambda y y))))) (lambda x (lambda y y))) (lambda x (lambda y x)));
      
      INPUT:  (((LAMBDA B1 (LAMBDA B2 ((B1 B2) (LAMBDA X (LAMBDA Y Y))))) (LAMBDA X (LAMBDA Y Y))) (LAMBDA X (LAMBDA Y X)))
      BETA:  ((LAMBDA B2 (((LAMBDA X (LAMBDA Y Y)) B2) (LAMBDA X (LAMBDA Y Y)))) (LAMBDA X (LAMBDA Y X)))
      BETA:  (((LAMBDA X (LAMBDA Y Y)) (LAMBDA X (LAMBDA Y X))) (LAMBDA X (LAMBDA Y Y)))
      BETA:  ((LAMBDA Y Y) (LAMBDA X (LAMBDA Y Y)))
      BETA:  (LAMBDA X (LAMBDA Y Y))
      BETA REDUCT:  (LAMBDA X (LAMBDA Y Y))
      
      ANSWER:  (LAMBDA X (LAMBDA Y Y))
      

   2. (and true true) reduces to true

      (and false true)
      ((and false) true)
      (((lambda b1 (lambda b2 ((b1 b2) (lambda x (lambda y y))))) (lambda x (lambda y x))) (lambda x (lambda y x)));
      
      LAMBDA> (((lambda b1 (lambda b2 ((b1 b2) (lambda x (lambda y y))))) (lambda x (lambda y x))) (lambda x (lambda y x)));
      
      INPUT:  (((LAMBDA B1 (LAMBDA B2 ((B1 B2) (LAMBDA X (LAMBDA Y Y))))) (LAMBDA X (LAMBDA Y X))) (LAMBDA X (LAMBDA Y X)))
      BETA:  ((LAMBDA B2 (((LAMBDA X (LAMBDA Y X)) B2) (LAMBDA X (LAMBDA Y Y)))) (LAMBDA X (LAMBDA Y X)))
      BETA:  (((LAMBDA X (LAMBDA Y X)) (LAMBDA X (LAMBDA Y X))) (LAMBDA X (LAMBDA Y Y)))
      BETA:  ((LAMBDA Y (LAMBDA X (LAMBDA Y X))) (LAMBDA X (LAMBDA Y Y)))
      BETA:  (LAMBDA X (LAMBDA Y X))
      BETA REDUCT:  (LAMBDA X (LAMBDA Y X))
      
      ANSWER:  (LAMBDA X (LAMBDA Y X))
      

What to submit? p1.pdf