In this section we will implement a normal-order language that is the same as JavaScript except that compound functions are non-strict in each argument. Primitive functions will still be strict. It is not difficult to modify the evaluator of section 4.1.1 so that the language it interprets behaves this way. Almost all the required changes center around function application.
The basic idea is that, when applying a function, the interpreter must determine which arguments are to be evaluated and which are to be delayed. The delayed arguments are not evaluated; instead, they are transformed into objects called thunks.[1]
The thunk must contain the information required to produce the value of the argument when it is needed, as if it had been evaluated at the time of the application. Thus, the thunk must contain the argument expression and the environment in which the function application is being evaluated.
The process of evaluating the expression in a thunk is called forcing.[2]
In general, a thunk will be forced only when its value is needed: when it is passed to a primitive function that will use the value of the thunk; when it is the value of a predicate of a conditional; and when it is the value of an operator that is about to be applied as a function. One design choice we have available is whether or not to memoize thunks, as we did with delayed objects in section 3.5.1. With memoization, the first time a thunk is forced, it stores the value that is computed. Subsequent forcings simply return the stored value without repeating the computation. We'll make our interpreter memoize, because this is more efficient for many applications. There are tricky considerations here, however.[3]
The main difference between the lazy evaluator and the one in section 4.1 is in the handling of function applications in evaluate and apply.
The is_application clause of evaluate becomes
is_application(exp) ? apply(actual_value(operator(exp), env), operands(exp), env)
This is almost the same as the is_application clause of evaluate in section 4.1.1. For lazy evaluation, however, we call apply with the operand expressions, rather than the arguments produced by evaluating them. Since we will need the environment to construct thunks if the arguments are to be delayed, we must pass this as well. We still evaluate the operator, because apply needs the actual function to be applied in order to dispatch on its type (primitive versus compound) and apply it.
Whenever we need the actual value of an expression, we use
function actual_value(exp, env) { return force_it(evaluate(exp, env)); }
Our new version of apply is also almost the same as the version in section 4.1.1. The difference is that evaluate has passed in unevaluated operand expressions: For primitive functions (which are strict), we evaluate all the arguments before applying the primitive; for compound functions (which are non-strict) we delay all the arguments before applying the function.
function apply(fun, args) { if (is_primitive_function(fun)) { return apply_primitive_function( fun, // following line changed list_of_arg_values(args, env)); } else if (is_compound_function(fun)) { const result = evaluate(function_body(fun), extend_environment( function_parameters(fun), // following line changed list_of_delayed_args(args, env), function_environment(fun))); if (is_return_value(result)) { return return_value_content(result); } else { return undefined; } } else { Error("Unknown function type in apply", fun); } }
The functions that process the arguments are just like list_of_values from section 4.1.1, except that list_of_delayed_args delays the arguments instead of evaluating them, and list_of_arg_values uses actual_value instead of evaluate:
function list_of_arg_values(exps, env) { return no_operands(exps) ? null : pair(actual_value(first_operand(exps), env), list_of_arg_values(rest_operands(exps), env)); } function list_of_delayed_args(exps, env) { return no_operands(exps) ? null : pair(delay_it(first_operand(exps), env), list_of_delayed_args( rest_operands(exps), env)); }
The other place we must change the evaluator is in the handling of if, where we must use actual-value instead of eval to get the value of the predicate expression before testing whether it is true or false:
function eval_conditional_expression(exp, env) { return is_true(actual_value(cond_expr_pred(exp), env)) ? evaluate(cond_expr_cons(exp), env) : evaluate(cond_expr_alt(exp), env); }
Finally, we must change the eval_toplevel function (section 4.1.4) to use actual_value instead of evaluate, so that if a delayed value is propagated back to the evaluator it will be forced before being printed.
function eval_toplevel(stmt) { const value = actual_value(stmt, the_global_environment); if (is_return_value(value)) { error("return not allowed " + "outside of function definitions"); } else { return value; } }
With these changes made, we can start the evaluator and test it. The successful evaluation of the try expression discussed in section 4.2.1 indicates that the interpreter is performing lazy evaluation:
eval_toplevel(parse( "function try(a, b) { " + " return a === 0 ? 1 : b; " + "} " + "try(0, head(null)); " ));
Our evaluator must arrange to create thunks when functions are applied to arguments and to force these thunks later. A thunk must package an expression together with the environment, so that the argument can be produced later. To force the thunk, we simply extract the expression and environment from the thunk and evaluate the expression in the environment. We use actual_value rather than evaluate so that in case the value of the expression is itself a thunk, we will force that, and so on, until we reach something that is not a thunk:
function force_it(obj) { return is_thunk(obj) ? actual_value(thunk_exp(obj), thunk_env(obj)) : obj; }
One easy way to package an expression with an environment is to make a list containing the expression and the environment. Thus, we create a thunk as follows:
function delay_it(exp, env) { return list("thunk", exp, env); } function is_thunk(obj) { return is_tagged_list(obj, "thunk"); } function thunk_exp(thunk) { return head(tail(thunk)); } function thunk_env(thunk) { return head(tail(tail(thunk))); }
Actually, what we want for our interpreter is not quite this, but rather thunks that have been memoized. When a thunk is forced, we will turn it into an evaluated thunk by replacing the stored expression with its value and changing the thunk tag so that it can be recognized as already evaluated.[4]
function is_evaluated_thunk(obj) { return is_tagged_list(obj, "evaluated_thunk"); } function thunk_value(evaluated_thunk) { return head(tail(evaluated_thunk)); } function force_it(obj) { if (is_thunk(obj)) { const result = actual_value( thunk_exp(obj), thunk_env(obj)); set_head(obj, "evaluated_thunk"); // replace exp with its value set_head(tail(obj), result); // forget unneeded env set_tail(tail(obj), null); return result; } else if(is_evaluated_thunk(obj)) { return thunk_value(obj); } else { return obj; } }
let count = 0; function id(x) { count = count + 1; return x; }
read_eval_print_loop(""); // enter: <count and id as defined above> // response: ? // enter: const w = id(id(10)); // response: ? // enter: count // response: ? // enter: w // response: ? // enter: count // response: ?
read_eval_print_loop(""); // enter: <count and id as defined above> // response: ? // enter: function square(x) { return x * x; } // response: ? // enter: square(id(10)); // response: ? // enter: count // response: ?
function eval_sequence(exps, env) { if (is_last_exp(exps)) { evaluate(first_exp(exps), env); } else { actual_value(first_exp(exps), env); eval_sequence(rest_exps(exps), env); } }
function for_each(fun, items) { if (is_null(items)){ return undefined; } else { fun(head(items)); for_each(fun, tail(items)); } }
read_eval_print_loop(""); // enter: <for_each as defined above> // response: ? // enter: for_each(x => display(x), list(57, 321, 88)); // response: 57 // 321 // 88 // response: done
function p1(x) { x = pair(x, list(2)); } function p2(x) { function p(e) { e; return x; } x = pair(x, list(2)); return p(x); }
function f(a, b, c, d) { parameters("strict", "lazy", "strict", "lazy-memo"); ... }
function callparameters is always the first statement in the body of a function declaration. You must also arrange for evaluate or apply to determine when arguments are to be delayed, and to force or delay arguments accordingly, and you must arrange for forcing to memoize or not, as appropriate.
thinking about) the expression could be done at compile time; thus, at run time, the expression would already have been
thunkabout (