Problem EC (200pts): Tail Recursion

Hint1: The staff will prioritize helping students with required questions.

Hint2: If you get stuck, try to take a look at the debugging guide.

Why current interpreter cannot properly process tail call?

Consider such scheme code:

(define (factor n acc)
  (if (= n 0)
      acc
      (factor (- n 1) (* acc n))))

(factor 10 1)

The current evaluation process is:

     scheme_eval(`(factor 10 1))
===> return scheme_eval(`(factor 9 10))
===> return (return scheme_eval(`(factor 8 90)))
...

The problem is python interpreter does not properly perform tail call.

There're mainly three way to solve this problem:

• transform the scheme interpreter to an non-recursive interpreter, i.e., eliminate all recursive call to scheme_eval. That can be accomplished by
  • rewrite this interpreter to an CEK interpreter. ('C' means control, 'E' means environment, 'K' means continuation). See here and Chap. 5 of ESSENTIALS OF PROGRAMMING LANGUAGES.
  • rewrite this interpreter to an trampolined interpreter. We use this approach.
• transform the source scheme code, e.g. Continuation-Passing Style transformation.

The trampoline technique is the simplest one. So we use this approach.

Trampoline

The trampoline technique is a simple technique to perform proper tail call in a "bad" language (e.g. Python, C, C++, Java, ...).

For example, we can define a sum recursive function in python:

def sum(n, acc):
    if n == 0:
        return acc
    else:
        return sum(n - 1, acc + n)

And sum(10000, 0) will produce a StackOverflow error. Now we "trampoline" such function:

class Unevaluated:
    def __init__(self, n, acc):
        self.n = n
        self.acc = acc

def sum_tram(n, acc):
    if n == 0:
        return acc
    else:
        return Unevaluated(n - 1, acc + n)

def sum(n, acc):
    # use do-while here is better, but Python does not support that
    res = sum_tram(n, acc)
    while isinstance(res, Unevaluated):
        res = sum_tram(res.n, res.acc)
    return res

Now sum(10000, 0) will properly works. This can be generalized to transform all recursive functions to loops, see here. But the above form is enough for our problem.

The Tasks

Complete the function optimize_tail_calls in scheme_eval_apply.py. It returns an alternative to scheme_eval that is properly tail recursive. That is, the interpreter will allow an unbounded number of active tail calls in constant space. It has a third argument tail that indicates whether the expression to be evaluated is in a tail context.

The Unevaluated class represents an expression that needs to be evaluated in an environment. When optimized_eval receives a non-atomic expression in a tail context, it returns an Unevaluated instance. Otherwise, it should repeatedly call original_scheme_eval until the result is a value, rather than an Unevaluated.

A successful implementation will require changes to several other functions, including some functions that we provided for you. All expressions throughout your interpreter that are in a tail context should be evaluated by calling scheme_eval with True as the third argument (now called tail). Your goal is to determine which expressions are in a tail context throughout your code and change calls to scheme_eval as needed.

Once you finish, uncomment the following line in scheme_eval_apply.py to use your implementation:

scheme_eval = optimize_tail_calls(scheme_eval)

Use Ok to test your code:

$ python ok -q EC