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

Due on Monday, September 24 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. Generate any two valid lambda expressions, except x, λx.x, and λx.xx, using the grammar given in the reading.
2. Draw the parse trees for those two expressions.
3. As mentioned in the reading, the lambda calculus is capable of expressing all computable functions. In a sense, this means that it is the most powerful programming language that we know. Why, then, do we have so many programming languages? Supposing for a moment that both C and Java are as powerful as the lambda calculus (hint: they are), why bother making a new language?