Hello people of the internet,
I am working on a project for a class and cannot solve this bug for the life of me. The project is to write a Scheme interpreter in Python. Much of the code was given to me and I had to fill in the rest. I am on the last portion where we are implementing tail call optimization. When I implemented it, it worked for most test cases, but all cases using "and" and "or" operations suddenly stopped working.
After some investigation, I found out why: As my program works through the operands to the and/or expression, it returns an Unevaluated object to be evaluated later.
def optimize_tail_calls(original_scheme_eval):
"""Return a properly tail recursive version of an eval function."""
def optimized_eval(expr, env, tail=False):
"""Evaluate Scheme expression EXPR in Frame ENV. If TAIL,
return an Unevaluated containing an expression for further evaluation.
"""
if tail and not scheme_symbolp(expr) and not self_evaluating(expr):
return Unevaluated(expr, env)
result = Unevaluated(expr, env)
# BEGIN PROBLEM EC
while isinstance(result, Unevaluated):
result = original_scheme_eval(result.expr, result.env)
return result
# END PROBLEM EC
return optimized_eval
This^ is the code that optimizes tail calls.
def do_and_form(expressions, env):
"""Evaluate a (short-circuited) and form.
>>> env = create_global_frame()
>>> do_and_form(read_line("(#f (print 1))"), env) # evaluating (and #f (print 1))
False
>>> # evaluating (and (print 1) (print 2) (print 4) 3 #f)
>>> do_and_form(read_line("((print 1) (print 2) (print 3) (print 4) 3 #f)"), env)
1
2
3
4
False
"""
# BEGIN PROBLEM 12
current = expressions
if current is nil:
return True
while not (current is nil):
val = scheme_eval(current.first, env, True) #Optimize tail call
if is_scheme_false(val):
return False
if current.rest is nil:
return val
else:
current = current.rest
# END PROBLEM 12
This^ is the code that executes "and" expressions.
def do_or_form(expressions, env):
current = expressions
if current is nil:
return False
while not (current is nil):
val = scheme_eval(current.first, env, True) #Optimize tail call
if is_scheme_true(val):
return val
if current.rest is nil:
return False
else:
current = current.rest
Similar, this^ is the code for "or" expressions.
As this code is, the issue I'm running into is that the expressions aren't being evaluated since they're staying Unevaluated objects. Take this test case for example:
scm> (define x 0)
x
scm> (and (define x (+ x 1))
.... (define x (+ x 10))
.... (define x (+ x 100))
.... (define x (+ x 1000)))
x
scm> x
1000
# Error: expected
# 1111
# but got
# 1000
You can see that the first 3 define functions became Unevaluated objects and only the last one was returned and evaluated, leaving x to be 1000 instead of 1111. I tried remedying this by adding the following to "and" and "or" forms:
if isinstance(val, Unevaluated):
val = scheme_eval(val.expr, val.env)
This^ did solve my issue with those cases, but now when I am given test cases that attempt to recurse over 1000 times, (the limit in Python) it throws a maximum recursion depth error, meaning this doesn't implement tail recursion correctly. Here is the test case they give me for that:
scm> (define (sum n total)
.... (or (and (zero? n) total)
.... (add n (+ n total))))
sum
scm> (define add (lambda (x+1 y) (sum (- x+1 1) y)))
add
scm> (sum 1001 0)
0
# Error: expected
# 501501
Also, as a final note, most of the variable names are pretty self-explanatory, but I would be happy to clarify what anything means. A previous, modified version of this exact problem can be found here: https://github.com/melissakly/CS61A/blob/master/scheme3/scheme3.py
I know this is a long problem, but I would greatly appreciate anyone who could point me in the right direction!