Description

• Two important reduction strategies in the lambda-calculus are leftmost-outermost (LO) and leftmost-innermost (LI). For each of the two operations mentioned below, compare LI and LO with respect to the number of reduction steps needed to compute the normal form as a function of the size of the input Church numerals.  Assume the Church numeral for number n is of size n.
• The ‘add’ operation – for addition of two Church numerals
• The ‘times’ operation – for multiplication of two Church numerals

See file defs.txt in the LAMBDA directory posted on Piazza for their definitions.

For the ‘add’ operation, consider invocations of the form ((add n1) n2), where n1 ≥ 0 and n2 ≥ 0.   For the ‘times’ operation, consider only invocations of the form ((times n) 1), where n ≥ 0.

Use the Lambda Calculus Simulator to run the ‘add’ and ‘times’ operations on sample inputs to understand how they work for the two reduction strategies.   The simulator accepts Arabic numerals as inputs and converts them to Church numerals internally for performing reductions.

Write a few sentences comparing LI and LO for each of the two operations.  Be sure to state the number of steps each strategy takes for each of the two operations as a function of the size of the input Church numerals.    Write your answer in a file compare.txt.

• Develop in the lambda-calculus a representation for binary trees following the technique outlined in Lecture 25, slides 7-10. Show the representation for the following binary tree:

node(node(node(leaf(NY), leaf(PA)), leaf(MA)), node(leaf(OH), leaf(CT)))

Write your answer in a file tree.txt by introducing a ‘let’ definition of the form:

let tree = ______________

Next, define in the lambda-calculus a function that counts the number of leaf nodes in a binary tree. Write your answer in file tree.txt by adding a ‘let’ definition of the form:

let leafcount =  Lt._____________

Hint:  (1)  You do not need to start with a recursive definition.   A concise non-recursive definition is                     possible similar to – but not exactly the same as – the ‘size’ function for lists.

(2)  You may include, as a ‘helper’ function, one of the arithmetic operations from defs.txt.

Test your answer by deriving the normal form of (leafcount tree).   Your answer should be the Church numeral for 5.