Problem Set 10—Lambda Calculus

Purpose

This problem set reinforces your understanding of the lambda calculus. By the time you finish this exercise, you should be able to (1) write lambda expressions that solve simple problems, and (2) reduce lambda expressions.

Background

This problem set is based on material in the online “Tutorial Introduction to the Lambda Calculus” by Paul Rojas. We discussed, or will discuss, this material in classes between April 22 and April 29.

Many lambda expressions, particularly ones that represent function definitions, have no free variables. For example, the identity function, λx.x is such a definition. Lambda expressions with no free variables are called combinators. For example, the various functions Rojas defines and names, e.g., I, the Church numerals, S, etc. are combinators.

Rojas represents the ordered pair (a,b) as the lambda expression λf.(fab). In this exercise, you will use ordered pairs to define lambda calculus lists inductively, as follows: A list is either…

• 0 (the 0 combinator), or
• An ordered pair (a,L) where a is any lambda expression and L is a list. a is the list’s head and L is its tail.

For example, the expression λf.(f a λg.(gb0)) represents the list ( a, b ).

Although I don’t ask you to use them this way in this exercise, lists are valuable because they give you a way of representing arbitrarily large blocks of data, e.g., arrays, Turing machine tapes, etc.

Activity

Solve the following problems related to lists.

Problem 1

List processing systems have an operation for constructing lists, usually called CONS. Define CONS as a combinator that has arguments a and L and that yields a list whose head is a and whose tail is L. Do not use any of Rojas’s combinators in your definition of CONS.

Problem 2

Show the series of reductions that occur when your CONS combinator is applied to a and the result of applying CONS to b and 0.

Problem 3

Define a combinator, ONE, that tells you whether a list contains only 1 element. More precisely, if L is a list, L ONE should be true if L has exactly one element, and false otherwise. You may use Rojas’s combinators in your definition of ONE.

Problem 4

Define a combinator, SECOND, that takes a list, L as its argument and that returns the second element of that list. You may assume that the list has at least two elements. Do not use any of Rojas’s combinators in your definition.

Problem 5

Demonstrate your SECOND combinator by showing the series of reductions that happen when SECOND is applied to λf.(f a λg.(gb0)). (You should be able to show that SECOND applied to this expression reduces to b.)

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.