# Assignment 5: Lambda calculus

Due: 5:00pm, Friday, September 28. Value: 30 pts.

Lambda Calculator [link] is a Web application for working with the lambda calculus. You should use it to define the eight additional operations enumerated below, subject to the following notes.

• Lambda Calculator does not save your work! This is particularly problematic since the program is new and is liable to crash. In case there are difficulties, your best bet is create a separate file of your own in which to record each definition.

• You may not use the Y combinator defined in class (which we used in defining the factorial function).

• Your definitions may assume that arguments have the correct type. That is, if the function expects a numeral as a parameter, then you need not worry about what you definition does if the argument is not in fact a numeral.

• The Web application pre-defines the Church numerals as described in class, as well as the numeric operations we studied in class (succ, pred, +, is0), the Boolean values true and false, and if. Also predefined is nil representing the empty list as defined below.

• The expressions for representing 0 and false (and as seen in the next bullet, nil) are equivalent: Each is a function taking two parameters and return the second argument. The Web application cannot distinguish these; consequently, when you expect a result of 0, it may instead report a result of false or nil. This is OK, since they are equivalent.

Similarly, if and 1 are equivalent, so you’ll likely see a result of if displayed when you expect a result of 1.

• In the latter four functions below, you’ll work with a specific technique for representing lists, illustrated by the following examples.

 `[]` = λc.λn.n `` = λc.λn.c 1 n `[2, 1]` = λc.λn.c 2 (c 1 n)

This is quite similar to the definition of integers: We’ve replaced the first parameter’s name s with c and the second parameter’s name z with n, but that’s not a real difference. (By the way, the name c stands for cons and n stands for nil; with Church numbers, s stands for successor and z stands for zero.) The only real distinction is that the c function expects two parameters rather than just one; the new parameter is an element of the list.

1. The and function

Write a lambda expression for computing the logical AND of two Boolean values expressed in this way. That is, with your definition in hand, I should be able to test it with the following.

 and false false ⇒ false and false true ⇒ false and true false ⇒ false and true true ⇒ true
2. The − function

Write a lambda expression for computing the difference of two numbers. For example, if − represents your expression, − 5 2 should return 3. Don’t worry about what happens when the result should be negative.

You’ll likely want to use the built-in pred function, which takes a numeral and returns the preceding numeral. The result of pred 5 is 4, for example.

3. The <= function

Write a lambda expression for determining whether one number is less than or equal to another; For example, <= 5 2 should return false while <= 2 5 should return true. (Hint: See what happens when you subtract one number from a smaller number (when the result ought to be negative).)

4. The = function

Write a lambda expression for determining whether one number is equal to another.

5. The cons function

Define the cons function similar to Haskell’s “`:`” operator for adding to the front of the list using the lambda-calculus representation described above. Its parameters will be an an element first and a list others, for which it returns a new list whose elements begin with first followed by the elements of others.

To test this, with the built-in nil representing the empty list, cons 2 (cons 1 nil) should return λcn.c 2 (c 1 n).

Define the head function, which returns the first element of its parameter list.

(The rest function is considerably more difficult. The easiest way is to base it on the pred function that returns a Church numeral that is one less than its argument, but the pred function is itself difficult. In case you’re interested, here’s the definition, but you won’t need anything like it for this assignment.)

rest = λscn.s (λefg.g e (f c)) (λg.n) (λxy.y)
7. The null function

Define the null function, which returns true if the parameter list is empty and false otherwise.

8. The length function

Define the length function, which returns the number of elements in the parameter list.