The evaluator implemented above is simple, but it is very inefficient, because the syntactic analysis of expressions 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) factorial(4) using the following definition of factorial:
Original | JavaScript |
(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) | function factorial(n) { return n === 1 ? 1 : factorial(n - 1) * n; } |
Each time factorial is called, the evaluator must determine that the body is an if 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), factorial(n - 1) * n, or the subexpressions (factorial (- n 1)) factorial(n - 1) and (- n 1), n - 1, the evaluator must perform the case analysis in eval evaluate to determine that the expression is an application, and must extract its operator and operands. 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 eval, evaluate, which takes an expression a component and an environment, into two parts. The procedure function analyze takes only the expression. component. It performs the syntactic analysis and returns a new procedure function, the execution procedure function, that encapsulates the work to be done in executing the analyzed expression. component. The execution procedure function takes an environment as its argument and completes the evaluation. This saves work because analyze will be called only once on an expression, a component, while the execution procedure function may be called many times.
With the separation into analysis and execution, eval evaluate now becomes
Original | JavaScript |
(define (eval exp env) ((analyze exp) env)) | function evaluate(component, env) { return analyze(component)(env); } |
The result of calling analyze is the execution procedure function to be applied to the environment. The analyze procedure function is the same case analysis as performed by the original eval evaluate of section 4.1.1, except that the procedures functions to which we dispatch perform only analysis, not full evaluation:
Original | JavaScript |
(define (analyze exp) (cond ((self-evaluating? exp) (analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted exp)) ((variable? exp) (analyze-variable exp)) ((assignment? exp) (analyze-assignment exp)) ((definition? exp) (analyze-definition exp)) ((if? exp) (analyze-if exp)) ((lambda? exp) (analyze-lambda exp)) ((begin? exp) (analyze-sequence (begin-actions exp))) ((cond? exp) (analyze (cond->if exp))) ((application? exp) (analyze-application exp)) (else (error "Unknown expression type - - ANALYZE" exp)))) | 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 procedure, which handles self-evaluating expressions. function, which handles literal expressions. It returns an execution procedure function that ignores its environment argument and just returns the expression: value of the literal:
Original | JavaScript |
(define (analyze-self-evaluating exp) (lambda (env) exp)) | function analyze_literal(component) { return env => literal_value(component); } |
Original | JavaScript | |
Looking up a variable value the value of a name must still be done in the execution phase, since this depends upon knowing the environment.[2]
Original | JavaScript |
(define (analyze-variable exp) (lambda (env) (lookup-variable-value exp env))) | function analyze_name(component) { return env => lookup_symbol_value(symbol_of_name(component), env); } |
Original | JavaScript | |
To analyze an application, we analyze the function expression and argument expressions and construct an execution function that calls the execution function of the function expression (to obtain the actual function to be applied) and the argument-expression execution functions (to obtain the actual arguments). We then pass these to execute_application, which is the analog of apply in section 4.1.1. The function execute_application differs from apply in that the function body for a compound function has already been analyzed, so there is no need to do further analysis. Instead, we just call the execution function for the body on the extended environment. function analyze_application(component) { const ffun = analyze(function_expression(component)); const afuns = map(analyze, arg_expressions(component)); return env => execute_application(ffun(env), map(afun => afun(env), afuns)); } function execute_application(fun, args) { if (is_primitive_function(fun)) { return apply_primitive_function(fun, args); } else if (is_compound_function(fun)) { const result = function_body(fun) (extend_environment(function_parameters(fun), args, function_environment(fun))); return is_return_value(result) ? return_value_content(result) : undefined; } else { error(fun, "unknown function type -- execute_application"); } } |
Original | JavaScript | |
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)); } |
Analyze-assignment 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 assignment-value expression can be analyzed (recursively) during analysis is a major gain in efficiency, because the assignment-value expression assignment-value expression will now be analyzed only once. The same holds true for definitions. constant and variable declarations.
Original | JavaScript |
(define (analyze-assignment exp) (let ((var (assignment-variable exp)) (vproc (analyze (assignment-value exp)))) (lambda (env) (set-variable-value! var (vproc env) env) 'ok))) (define (analyze-definition exp) (let ((var (definition-variable exp)) (vproc (analyze (definition-value exp)))) (lambda (env) (define-variable! var (vproc env) env) 'ok))) | 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; }; } |
Original | JavaScript | |
For if expressions, we extract and analyze the predicate, consequent, and alternative at analysis time. (define (analyze-if exp) (let ((pproc (analyze (if-predicate exp))) (cproc (analyze (if-consequent exp))) (aproc (analyze (if-alternative exp)))) (lambda (env) (if (true? (pproc env)) (cproc env) (aproc env))))) Analyzing a lambda expression also achieves a major gain in efficiency: We analyze the lambda body only once, even though procedures resulting from evaluation of the lambda may be applied many times. (define (analyze-lambda exp) (let ((vars (lambda-parameters exp)) (bproc (analyze-sequence (lambda-body exp)))) (lambda (env) (make-procedure vars bproc env)))) Analysis of a sequence of expressions (as in a begin or the body of a lambda expression) is more involved.[4] Each expression in the sequence is analyzed, yielding an execution procedure. These execution procedures are combined to produce an execution procedure that takes an environment as argument and sequentially calls each individual execution procedure with the environment as argument. (define (analyze-sequence exps) (define (sequentially proc1 proc2) (lambda (env) (proc1 env) (proc2 env))) (define (loop first-proc rest-procs) (if (null? rest-procs) first-proc (loop (sequentially first-proc (car rest-procs)) (cdr rest-procs)))) (let ((procs (map analyze exps))) (if (null? procs) (error "Empty sequence - - ANALYZE")) (loop (car procs) (cdr procs)))) To analyze an application, we analyze the operator and operands and construct an execution procedure that calls the operator execution function (to obtain the actual procedure to be applied) and the operand execution procedures (to obtain the actual arguments). We then pass these to execute-application, which is the analog of apply in section 4.1.1. Execute-application differs from apply in that the procedure body for a compound procedure has already been analyzed, so there is no need to do further analysis. Instead, we just call the execution procedure for the body on the extended environment. (define (analyze-application exp) (let ((fproc (analyze (operator exp))) (aprocs (map analyze (operands exp)))) (lambda (env) (execute-application (fproc env) (map (lambda (aproc) (aproc env)) aprocs))))) (define (execute-application proc args) (cond ((primitive-procedure? proc) (apply-primitive-procedure proc args)) ((compound-procedure? proc) ((procedure-body proc) (extend-environment (procedure-parameters proc) args (procedure-environment proc)))) (else (error "Unknown procedure type - - EXECUTE-APPLICATION" proc)))) |
Our new evaluator uses the same data structures, syntax procedures, functions, and run-time support procedures runtime support functions as in sections 4.1.2, 4.1.3, and 4.1.4.
Original | JavaScript | |
Extend the evaluator in this section to support the special form let. (See exercise 4.9.) | Extend the evaluator in this section to support while loops. (See exercise 4.11.) |
Original | JavaScript |
(define (analyze-sequence exps) (define (execute-sequence procs env) (cond ((null? (cdr procs)) ((car procs) env)) (else ((car procs) env) (execute-sequence (cdr procs) env)))) (let ((procs (map analyze exps))) (if (null? procs) (error "Empty sequence - - ANALYZE")) (lambda (env) (execute-sequence procs env)))) | function analyze_sequence(stmts) { function execute_sequence(funs, env) { if (is_null(funs)) { return undefined; } else if (is_null(tail(funs))) { return head(funs)(env); } else { const head_val = head(funs)(env); return is_return_value(head_val) ? head_val : execute_sequence(tail(funs), env); } } const funs = map(analyze, stmts); return env => execute_sequence(funs, env); } |