6 Assignment 6: Reduction and mutation

A function is not to be identified with the operation by which it is evaluated nor with its representation in the form of a table or other look-up medium. A function is a function, and the means chosen to find its value in a given case is independent of the function’s intrinsic meaning. This is no more than a restatement of a mathematical truism, but it is one which has been lost sight of by the designers of our programming languages.

——Donald Michie

Assignment

Place your code in a file named a6.rkt and submit it to Autograder.

This assignment has three parts. The first part is about beta reduction. The second part is about mutation. They then come together in the third part.

Part 1: Beta Reduction

In class we introduced beta reduction, which turns one expression into another by changing a subexpression that is a “((λ” (pronounced “left left lambda”, meaning an application of an abstraction).

In each question in this part, you will take a lambda calculus expression and keep beta-reducing it until it can no longer be beta-reduced. (An expression that cannot be beta-reduced is said to be in beta normal form.) Write out all the steps as a Racket list, defined as a constant in your code. Renaming variables (also known as alpha-conversion) does not count as a step and can be done anywhere at any time. Do not do any computation other than beta and alpha.

1. Reduce ((λ x (bake (x x))) (λ x (wash x))) to normal form and list the steps in q1.

2. Reduce ((λ x (λ y ((toss (x y)) (y x)))) (λ x ((stir x) y))) to normal form and list the steps in q2.

3. Reduce ((λ x ((y (λ y (y x))) (λ x (x z)))) (λ x ((stir x) y))) to normal form and list the steps in q3.

4. Reduce ((λ f ((f f) (f f))) (λ f (λ x (f (f x))))) to normal form and list the steps in q4. This one is longer, but trust that it will terminate. The lambda calculus is a small language but can express any computation.

Part 2: Programming with Mutation

5. Define explicit-accumulate to be an Expr that, when evaluated in the initial environment, creates a function that takes a number and returns the sum of all the numbers it has received so far. For instance, the program

   `((λ f ((+ (f 10)) (f 7)))

   ,explicit-accumulate)

   should produce 27, because (f 10) produces 10 then (f 7) produces 17. In contrast, the beta-reduced

   `((+ (,explicit-accumulate 10))

   (,explicit-accumulate 7))

   should produce 17, because two separate functions are created.

6. Mutation gives us a new way to achieve recursion. For instance, here is a function in our language that checks if the given number is even:

   (define explicit-even?

   '((λ e ((λ o ((λ _ ((λ _ (deref e))

   ((setref o)

   (λ n (if (zero? n) #f ((deref e) ((- n) 1)))))))

   ((setref e)

   (λ n (if (zero? n) #t ((deref o) ((- n) 1)))))))

   (newref 311)))

   (newref 311)))

   It may be easier to read this code from bottom up. The number 311 is just a dummy value that we use to initialize two locations, before overwriting them with functions that check whether the given number is even or odd. (Don’t you wish this language had let? Consider writing a compiler that turns programs with let into programs without.)
   Using this way to achieve recursion, define explicit-collatz to be an Expr that, when evaluated in the initial environment, creates a function that takes a positive integer and returns how many times the Collatz operation has to be applied to it before reaching 1. The Collatz operation turns one positive integer into another as follows:

   • If n is even then it becomes n/2.

   • If n is odd then it becomes 3n+1.

   For instance, the program `(,explicit-collatz 12) should produce 9, because 12 becomes 6 becomes 3 becomes 10 becomes 5 becomes 16 becomes 8 becomes 4 becomes 2 becomes 1, and that’s 9 times of applying the Collatz operation.

   Hint: First define a function that halves an even number.

7. Now write the same programs in our lambda calculus with implicit references. Recall that the grammar of implicit references adds a new form := for assignment:

   Expr		=		Number
   		|		Boolean
   		|		Symbol
   		|		(λ Symbol Expr)
   		|		(Expr Expr)
   		|		(if Expr Expr Expr)
   		|		(Symbol := Expr)

   The initial environment only contains + - zero?

   Define implicit-accumulate and implicit-collatz, by analogy with explicit-accumulate and explicit-collatz above. (Do you notice that implicit-collatz runs more slowly than explicit-collatz?)

Part 3: Distinguishing Expressions

In class, we saw that two equivalent expressions may become no longer equivalent when side effects are added to the language. For instance, using beta-reduction to inline the rhs of a let may not preserve the behavior of the program if the rhs incurs the side effect of mutation or even just non-termination.

8. Without using references, define distinguish-numbers to be a context that distinguishes the expressions 1 and 2.

9. Without using references, define distinguish-functions to be a context that distinguishes the expressions (λ x 1) and (λ x 2).

10. In our lambda calculus with explicit references, define distinguish-times to be a context that distinguishes the expressions ((+ (x 311)) (x 311)) and ((λ x ((+ x) x)) (x 311)).

    These expressions cannot be distinguished without references.

11. In our lambda calculus with implicit references, define distinguish-order to be a context that distinguishes the expressions ((λ x ((+ x) (g 311))) (f 311)) and ((λ x ((+ (f 311)) x)) (g 311)).

    These expressions cannot be distinguished without references.

12. In our lambda calculus with implicit references, define distinguish-call to be a context that distinguishes the expressions ((λ _ 311) (x := (if x #t #t))) and ((λ x ((λ _ 311) (x := (if x #t #t)))) x).

    In our lambda calculus with explicit references, the expressions ((λ _ 311) ((setref x) (if x #t #t))) and ((λ x ((λ _ 311) ((setref x) (if x #t #t)))) x) cannot be distinguished.

Brainteasers

13. While studying machine learning 57 years ago, Michie came up with the idea of speeding up a function by making it memorize the inputs it receives and their corresponding outputs. When a new input arrives, if it matches an old input, then the memorized corresponding output can be returned right away and need not be recomputed. If the new input does not match any old input, then the function proceeds to compute the output as usual, but as it returns, it memorizes the new input and its corresponding output for future lookup. We assume the inputs are all numbers.

    Define explicit-memo to be an expression in our lambda calculus with explicit references, so that applying it to a function produces a new function “with a memo apparatus attached”. That is, when the new function is called with a number, that number is only passed to the old function (and the output memorized) if the new function has not received this input before. If the new function has received this input before, then return the memorized output from before.

    For instance, the program

    `((λ f ((+ ((+ (f 10)) (f 7))) (f 10)))

    (,explicit-memo ,explicit-accumulate))

    should produce 37, because (f 10) produces 10 twice and (f 7) produces 17.

    Hint: Because this language does not have cons, consider storing the lookup table as a function that takes a number as input. A second input to this function can be what to do if the number is not found.

    Make sure that all input-output pairs are memorized, even if the old function calls the new function.

14. In our lambda calculus with implicit references, define implicit-memo by analogy with explicit-memo above.