►C311/  H311/  A596 Spring 2025 – Programming Languages
▼Assignments
•7 Assignment 7:   Parameter Passing and Tail Positions
    contents  ← prev  up  next → 

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

Recall the grammar of our lambda calculus with explicit references:
  Expr = Number
  | Boolean
  | Symbol
  | (λ Symbol Expr)
  | (Expr Expr)
  | (if Expr Expr Expr)
The initial environment contains the following functions:

  • + is a curried function that adds two given numbers.

  • - is a curried function that subtracts the second given number from the first.

  • zero? is a function that tests whether the given number is zero.

  • newref is a function that stores the given value in a new location.

  • deref is a function that retrieves the current value in the given location.

  • setref is a curried function that mutates the given location to store the given value instead.

In this part, we ask you to practice more programming in this language.

  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.

More precisely, the presence of side effects such as mutation makes it possible to distinguish two expressions using a context. A context is like a program, except with an expression in it replaced by a hole []. For instance, each line below is a context:
[]
(λ x [])
((λ x []) ((+ 3) 11))
([] ((λ x (x x)) (λ x (x x))))
For the purpose of this assignment, we require a context that does not inhibit termination (so, not the last line above) and that does not shadow the names + - zero? newref deref setref in the initial environment. Your job in this part is to come up with contexts to distinguish certain pairs of expressions.

What does it mean for a context to distinguish two expressions? For instance, what does it mean for a context to distinguish the expressions ((+ x) 1) and ((- x) 1)? After all, if we just evaluate those expressions in the initial environment, then they both produce an error “variable not bound”, so they are not distinguished by the trivial context []. Instead, take the context
((λ x []) ((+ 3) 11))
and replace its hole [] by each of the two expressions. We get two programs
((λ x ((+ x) 1)) ((+ 3) 11))
((λ x ((- x) 1)) ((+ 3) 11))
and running them produces values 15 and 13, which are observably different. Two values are observably different if

  • they are not both functions,

  • they are not both references,

  • they are not equal numbers, and

  • they are not equal booleans.

For instance, the context
(λ x [])
does not distinguish the expressions ((+ x) 1) and ((- x) 1), because the values produced by running the two programs
(λ x ((+ x) 1))
(λ x ((- x) 1))
are both functions and thus not observably different.

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

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

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

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

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

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

In class we discussed how some function calls can be treated as mere jumps, whereas other function calls cannot because they grow the control context. A function call can be treated as a mere jump if it occurs in tail position. A tail position is

  • either the body of a lambda,

  • or the body of a let that is itself in tail position,

  • or a branch answer of a cond/match/if that is itself in tail position.

In this part, we give you some Racket programs and ask you to identify their tail positions.

For instance, suppose we ask you to “In even?-tails, list all the expressions in tail position in
(define even?
  (lambda (n)
    (cond [(= n 0) #t]
          [else (not (even? (- n 1)))])))
”. This code has three tail positions: the lambda body, and the two cond branch answers. So, you can put
(define even?-tails
  '((cond [(= n 0) #t]
          [else (not (even? (- n 1)))])
    #t
    (not (even? (- n 1)))))
in your code (note the quote). The order of the list doesn’t matter, but the number of times an expression appears in the list matters; for instance, if the same expression appears in two tail positions, then your list must contain that expression twice. Do not rename any variables. You can either locate these tail positions manually or write a program to automate the work.

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

  2. In star-tails, list all the expressions in tail position in
    (define star
      (lambda (m)
        (lambda (n)
          (* m n))))

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

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

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

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

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

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

    contents  ← prev  up  next →