Computer Science 6220
Fall 1999
Assignment 5

Due: Oct. 14

1. An expression of -calculus is in normal form if there are no -reductions that can be done on it. Reduce each of the following to normal form.
   1. 
   2. 
   3. 
2. Let . Assume that rules are arithmetic are available for reducing arithmetic expressions to numbers. Let sq = . Evaluate the following. Remember that function application associates to the left, so .
   1. 
   2. 
   3. 
3. Suppose that the operations of addition and subtraction and test for zero are available, and that natural numbers are primitive things. (That is, do not be concerned with the representation of numbers as functions.) Write a definition of the multiplication function on natural numbers, using the Y operator. Your definition should have the form mult = ..., where you just give a definition of mult. You may use if-then-else in your definition, as a primitive concept.
4. You can write the Y operator in Astarte, using recursion. Here it is, but called fix instead of Y.

        Lazylet fix ?f ?x = f (fix f) x.

   Implement your definition of multiplication using fix. Try it to see if it works.

• About this document ...