The evaluator implemented above is simple, but it is very inefficient, because the syntactic analysis of components is interleaved with their execution. Thus if a program is executed many times, its syntax is analyzed many times. Consider, for example, evaluating factorial(4) using the following definition of factorial:

function factorial(n) {      
    return n === 1
           ? 1
           : factorial(n - 1) * n;
}

Each time factorial is called, the evaluator must determine that the body is a conditional expression and extract the predicate. Only then can it evaluate the predicate and dispatch on its value. Each time it evaluates the expression factorial(n - 1) * n, or the subexpressions factorial(n - 1) and n - 1, the evaluator must perform the case analysis in evaluate to determine that the expression is an application, and must extract its function expression and argument expressions. This analysis is expensive. Performing it repeatedly is wasteful.

We can transform the evaluator to be significantly more efficient by arranging things so that syntactic analysis is performed only once.[1] We split evaluate, which takes a component and an environment, into two parts. The function analyze takes only the component. It performs the syntactic analysis and returns a new function, the execution function, that encapsulates the work to be done in executing the analyzed component. The execution function takes an environment as its argument and completes the evaluation. This saves work because analyze will be called only once on a component, while the execution function may be called many times.

With the separation into analysis and execution, evaluate now becomes

function evaluate(component, env) {      
    return analyze(component)(env);
}

The result of calling analyze is the execution function to be applied to the environment. The analyze function is the same case analysis as performed by the original evaluate of section 4.1.1, except that the functions to which we dispatch perform only analysis, not full evaluation:

function analyze(component) {
    return is_literal(component)
           ? analyze_literal(component)
           : is_name(component)
           ? analyze_name(component)
           : is_application(component)
           ? analyze_application(component)
           : is_operator_combination(component)
           ? analyze(operator_combination_to_application(component))
           : is_conditional(component)
           ? analyze_conditional(component)
           : is_lambda_expression(component)
           ? analyze_lambda_expression(component)
           : is_sequence(component)
           ? analyze_sequence(sequence_statements(component))
           : is_block(component)
           ? analyze_block(component)
           : is_return_statement(component)
           ? analyze_return_statement(component)
           : is_function_declaration(component)
           ? analyze(function_decl_to_constant_decl(component))
           : is_declaration(component)
           ? analyze_declaration(component)
           : is_assignment(component)
           ? analyze_assignment(component)
           : error(component, "unknown syntax -- analyze");
}

Here is the simplest syntactic analysis function, which handles literal expressions. It returns an execution function that ignores its environment argument and just returns the value of the literal:

function analyze_literal(component) {      
    return env => literal_value(component);
}

Looking up the value of a name must still be done in the execution phase, since this depends upon knowing the environment.[2]

function analyze_name(component) {      
    return env => lookup_symbol_value(symbol_of_name(component), env);
}

For conditionals, we extract and analyze the predicate, consequent, and alternative at analysis time.

function analyze_conditional(component) {	
    const pfun = analyze(conditional_predicate(component));
    const cfun = analyze(conditional_consequent(component));
    const afun = analyze(conditional_alternative(component));
    return env => is_truthy(pfun(env)) ? cfun(env) : afun(env);
}

Analyzing a lambda expression also achieves a major gain in efficiency: We analyze the lambda body only once, even though functions resulting from evaluation of the lambda expression may be applied many times.

function analyze_lambda_expression(component) {
    const params = lambda_parameter_symbols(component);
    const bfun = analyze(lambda_body(component));
    return env => make_function(params, bfun, env);
}

Analysis of a sequence of statements is more involved.[3] Each statement in the sequence is analyzed, yielding an execution function. These execution functions are combined to produce an execution function that takes an environment as argument and sequentially calls each individual execution function with the environment as argument.

function analyze_sequence(stmts) {
    function sequentially(fun1, fun2) {
        return env => {
                   const fun1_val = fun1(env);
                   return is_return_value(fun1_val)
                          ? fun1_val
                          : fun2(env);
               };
    }
    function loop(first_fun, rest_funs) {
        return is_null(rest_funs)
               ? first_fun
               : loop(sequentially(first_fun, head(rest_funs)),
                      tail(rest_funs));
    }
    const funs = map(analyze, stmts);
    return is_null(funs) 
           ? env => undefined
           : loop(head(funs), tail(funs));
}

The body of a block is scanned only once for local declarations. The bindings are installed in the environment when the execution function for the block is called.

function analyze_block(component) {
    const body = block_body(component);
    const bfun = analyze(body);
    const locals = scan_out_declarations(body);	    
    const unassigneds = list_of_unassigned(locals);
    return env => bfun(extend_environment(locals, unassigneds, env));
}

For return statements, we analyze the return expression. The execution function for the return statement simply calls the execution function for the return expression and wraps the result in a return value.

function analyze_return_statement(component) {
    const rfun = analyze(return_expression(component));
    return env => make_return_value(rfun(env));
}

The function analyze_assignment must defer actually setting the variable until the execution, when the environment has been supplied. However, the fact that the assignment-value expression can be analyzed (recursively) during analysis is a major gain in efficiency, because the assignment-value expression will now be analyzed only once. The same holds true for constant and variable declarations.

function analyze_assignment(component) {
    const symbol = assignment_symbol(component);
    const vfun = analyze(assignment_value_expression(component));
    return env => {
               const value = vfun(env);
               assign_symbol_value(symbol, value, env);
               return value;
           };
}
function analyze_declaration(component) {
    const symbol = declaration_symbol(component);
    const vfun = analyze(declaration_value_expression(component));
    return env => {
               assign_symbol_value(symbol, vfun(env), env);
               return undefined;
           };
}

Our new evaluator uses the same data structures, syntax functions, and runtime support functions as in sections 4.1.2,  4.1.3, and 4.1.4.