11.4.1 Lazy Interpreter
The Charme interpreter as well as the standard Scheme language evaluate application expressions eagerly: all operand subexpressions are evaluated whether or not their values are needed. This is known as eager evaluation. Eager evaluation means that any expression that does not always evaluate all of its subexpressions must be a special form. For example, there is no way to define a procedure that behaves like the if special form.
With lazy evaluation, an expression is evaluated only when its value is needed. Lazy evaluation changes the evaluation rule for applications of constructed procedures. Instead of evaluating all operand expressions, lazy evaluation delays evaluation of an operand expression until the value of the parameter is needed. To keep track of what is needed to perform the evaluation when and if it is needed, a special object known as a thunk is created and stored in the place associated with the parameter name. By delaying evaluation of operand expressions until their value is needed, we can enable programs to define procedures that conditionally evaluate their operands like the if special form.
The lazy rule for applying constructed procedures is:
Lazy Application Rule 2: Constructed Procedures. To apply a constructed procedure:
- Construct a new environment, whose parent is the environment of the applied procedure.
- For each procedure parameter, create a place in the frame of the new environment with the name of the parameter. Put a thunk in that place, which is an object that can be used later to evaluate the value of the corresponding operand expression if and when its value is needed.
- Evaluate the body of the procedure in the newly created environment. The resulting value is the value of the application.
The rule is identical to the Stateful Application Rule except for the bolded part of step 2. To implement lazy evaluation we modify the interpreter to implement the lazy application rule. We start by defining a Python class for representing thunks and then modify the interpreter to support lazy evaluation.
Making Thunks. A thunk keeps track of an expression whose evaluation is delayed until it is needed. Once the evaluation is performed, the resulting value is saved so the expression does not need to be re-evaluated the next time the value is needed. Thus, a thunk is in one of two possible states: unevaluated and evaluated.
Thunk class implements thunks:
def __init__(self, expr, env):
self._expr = expr
self._env = env
self._evaluated = False
if not self._evaluated:
self._value = force_eval(self._expr, self._env)
self._evaluated = True
Thunk object keeps track of the expression in the
_expr instance variable. Since the value of the expression may be needed when the evaluator is evaluating an expression in some other environment, it also keeps track of the environment in which the thunk expression should be evaluated in the
_env instance variable.
_evaluated instance variable is a Boolean that records whether or not the thunk expression has been evaluated. Initially this value is
False. After the expression is evaluated,
True and the
_value instance variable keeps track of the resulting value.
value method uses
force_eval (defined later) to obtain the evaluated value of the thunk expression and stores that result in
is_thunk procedure returns
True only when its parameter is a thunk:
Changing the evaluator. To implement lazy evaluation, we change the evaluator so there are two different evaluation procedures:
meval is the standard evaluation procedure (which leaves thunks in their unevaluated state), and
force_eval is the evaluation procedure that forces thunks to be evaluated to values. The interpreter uses
meval when the actual expression value may not be needed, and
force_eval to force evaluation of thunks when the value of an expression is needed.
meval procedure, a thunk evaluates to itself. We add a new
elif clause for thunk objects to the
force_eval procedure first uses
meval to evaluate the expression normally. If the result is a thunk, it uses the
Thunk.value method to force evaluation of the thunk expression. That method uses
force_eval to find the value of the thunk expression, so any thunks inside the expression will be recursively evaluated.
val = meval(expr, env)
if is_thunk(val): return val.value()
else: return val
Next, we change the application rule to perform delayed evaluation and change a few other places in the interpreter to use
force_eval instead of
meval to obtain the actual values when they are needed.
eval_application to delay evaluation of the operands by creating
Thunk objects representing each operand:
ops = map (lambda sexpr: Thunk(sexpr, env), expr[1:])
return mapply(force_eval(expr, env), ops)
Only the first subexpression must be evaluated to obtain the procedure to apply. Hence,
force_eval to obtain the value of the first subexpression, but makes Thunk objects for the operand expressions.
To apply a primitive, we need the actual values of its operands, so must force evaluation of any thunks in the operands. Hence, the definition for
mapply forces evaluation of the operands to a primitive procedure:
if is_thunk(expr): return expr.value()
else: return expr
ops = map (dethunk, operands)
elif isinstance(proc, Procedure):
... # same as in Charme interpreter
To evaluate an if expression, it is necessary to know the actual value of the predicate expressions. We change the
eval_if procedure to use
force_eval when evaluating the predicate expression:
if force_eval(expr, env) != False: return meval(expr,env)
else: return meval(expr,env)
This forces the predicate to evaluate to a value so its actual value can be used to determine how the rest of the if expression evaluates; the evaluations of the consequent and alternate expressions are left as
mevals since it is not necessary to force them to be evaluated yet.
The final change to the interpreter is to force evaluation when the result is displayed to the user in the
evalLoop procedure by replacing the call to