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

---

Due on Wednesday, February 23 by 10pm

---

Read “Introduction to the Lambda Calculus, Part 1” in the course packet.

---

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. I say without any evidence at all that the lambda expression λx.x is equivalent to the following Java generic function:

   T identity<T>(T t) {
       return t;
   }
   

   except that λx.x is a kind of “nameless function.” For what it’s worth, here’s the “same function” in Python:

   def identity(t):
       return t
   

   What do you think I mean when I say that these are “the same”? There are two ways to think about sameness: syntax or semantics. Syntax is how something looks; semantics is how something behaves. How are the lambda expression and the Java/Python function syntactically similar? How are the lambda expression and Java/Python function semantically similar? We have not talked yet in much detail about the lambda calculus, so I am asking you to make your best guess.

   If you’re stuck, try thinking about the parts of the Java function: name, arguments, body, return value, etc. Then try to identify those same parts in the lambda expression.

---

Length

Your response should be short: at least 150 words and no more than 400 words total.

---

Submission Instructions

Commit your response to your short responses repository. You must commit both your .tex source file and your generated .pdf. You are required to use LaTeX to typeset your response.

FILE MUST BE NAMED reading03.pdf.