7 Assignment 7: Parameter Passing and Tail Positions

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 a7.rkt and submit it to Autograder.

Part 1: Programming More with Mutation

1. 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.)
   This way to achieve recursion is called Landin’s knot. Using Landin’s knot, 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.

2. Now write the same program 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-collatz, by analogy with explicit-collatz above. (Do you notice that implicit-collatz runs more slowly than explicit-collatz?)

Part 2: 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.

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

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

5. 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.

6. 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.

7. 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).

   These two expressions are distinguishable under call-by-value but not call-by-reference. (This fact should help you do the next exercise.) And 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.

Part 3: Distinguishing Parameter-Passing Variations

8. Define call-by-what to be an Expr whose value is 1 under call-by-value, 2 under call-by-reference, 3 under call-by-name, and 4 under call-by-need.

   (Because 4 is greater than 3, a corollary is that in the presence of side effects such as mutation, a program can take longer to run under call-by-need than under call-by-name.)

   Tip: First distinguish call-by-value from the others. Then distinguish call-by-reference from call-by-n*. Finally distinguish call-by-name and call-by-need.

Part 4: Tail Positions

9. In binary-to-decimal-tails, list all the expressions in tail position in

   (define binary-to-decimal

   (lambda (n)

   (cond

   [(null? n) 0]

   [else (+ (car n) (* 2 (binary-to-decimal (cdr n))))])))

10. In star-tails, list all the expressions in tail position in

    (define star

    (lambda (m)

    (lambda (n)

    (* m n))))

11. In times-tails, list all the expressions in tail position in

    (define times

    (lambda (ls)

    (cond

    [(null? ls) 1]

    [(zero? (car ls)) 0]

    [else (* (car ls) (times (cdr ls)))])))

12. In remv-first-9*-tails, list all the expressions in tail position in

    (define remv-first-9*

    (lambda (ls)

    (cond

    [(null? ls) '()]

    [(pair? (car ls))

    (cond

    [(equal? (car ls) (remv-first-9* (car ls)))

    (cons (car ls) (remv-first-9* (cdr ls)))]

    [else (cons (remv-first-9* (car ls)) (cdr ls))])]

    [(eqv? (car ls) '9) (cdr ls)]

    [else (cons (car ls) (remv-first-9* (cdr ls)))])))

13. In find-tails, list all the expressions in tail position in

    (define find

    (lambda (u s)

    (let ((pr (assv u s)))

    (if pr (find (cdr pr) s) u))))

14. In fib-tails, list all the expressions in tail position in

    (define fib

    (lambda (n)

    ((lambda (fib)

    (fib fib n))

    (lambda (fib n)

    (cond

    [(zero? n) 0]

    [(zero? (sub1 n)) 1]

    [else (+ (fib fib (sub1 n)) (fib fib (sub1 (sub1 n))))])))))

Brainteasers

15. 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: To check if two numbers are equal, subtract them and check if the result is zero. 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. So, when you update the lookup table, make sure to retrieve the very latest version of the lookup table and base the update on it, lest you accidentally erase any entry that may have been added during the call to the old function.

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