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:

  1. Construct a new environment, whose parent is the environment of the applied procedure.
  2. 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.
  3. 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.

The Thunk class implements thunks:

class Thunk:
    def __init__(self, expr, env):
        self._expr = expr
        self._env = env
        self._evaluated = False
    def value(self):
        if not self._evaluated:
            self._value = force_eval(self._expr, self._env)
            self._evaluated = True
        return self._value

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

The _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, _evaluated is True and the _value instance variable keeps track of the resulting value.

The value method uses force_eval (defined later) to obtain the evaluated value of the thunk expression and stores that result in _value.

The is_thunk procedure returns True only when its parameter is a thunk:

def is_thunk(expr): return isinstance(expr, 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.

In the meval procedure, a thunk evaluates to itself. We add a new elif clause for thunk objects to the meval procedure:

    elif is_thunk(expr):        return expr

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.

def force_eval(expr, env):
    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.

We change eval_application to delay evaluation of the operands by creating Thunk objects representing each operand:

def eval_application(expr, env):
    ops = map (lambda sexpr: Thunk(sexpr, env), expr[1:])
    return mapply(force_eval(expr[0], env), ops)

Only the first subexpression must be evaluated to obtain the procedure to apply. Hence, eval_application uses 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:

def mapply(proc, operands):    
    def dethunk(expr):
        if is_thunk(expr): return expr.value()
        else: return expr

    if (is_primitive_procedure(proc)):
        ops = map (dethunk, operands)
        return proc(ops)
    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:

def eval_if(expr,env):
    if force_eval(expr[1], env) != False: return meval(expr[2],env)
    else: return meval(expr[3],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 meval with force_eval.