Problem EC (200pts): Tail Recursion

The staff will prioritize helping students with required questions. TAs will not offer helps for this question (but senior students may).

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:

$ python3 ok -q EC