# 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``[`

`1`]= λ `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`functionWrite 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`functionDefine 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 λ`c`.λ`n`.`c`2 (`c`1`n`).**6. The**`head`functionDefine 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`= λ`s`.λ`c`.λ`n`.`s`(λ`e`.λ`f`.λ`g`.`g``e`(`f``c`)) (λ`g`.`n`) (λ`x`.λ`y`.`y`)**7. The**`null`functionDefine the

`null`function, which returns`true`if the parameter list is empty and`false`otherwise.**8. The**`length`functionDefine 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.