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.

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).

6. The head function

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.

Submitting your work

Add the symbol ‘#’ to the dictionary mapping to your name(s). That is, type your name(s) into the top blank and press Enter; then type ‘#’ into the lower blank and press Enter.

To submit, copy Lambda Calculator’s record of your dictionary into the Moodle submission page. You can get this record by selecting the dictionary icon near the screen’s top and then pressing the Show Text button to get the plain ASCII version that you should submit.