Prompts for “Introduction to the Lambda Calculus, Part 2”

Due on Monday, October 1 by 10pm

Commit your response as a PDF to your short responses repository. You are encouraged (but not required) to use LaTeX to typeset your response.

1. To what number does this lambda expression evaluate? You will need to employ both beta reduction, our parentheses axiom, and the normal rules of arithmetic to solve this question. Write your reduction proof in two-column format, showing all steps. You should start by thinking through the associativity of application and insert parenthesis where appropriate.

    (λa.λb.(- a b)) 2 1 
   

2. What do you observe about the relationship between the positions of arguments and abstractions in an expression that has multiple applications?

Some reduction tricks I like to use are:

• Be careful to maintain the number and balance of parentheses I do this reduction. I explicitly eliminate parens as a step in my reduction. Sometimes I even color-code parentheses (e.g., with alternating red and black pens).
• If I am having trouble doing a reduction on paper, I paste the expression into Notepad on my computer. To do the reduction, I copy and systematically alter each line.