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 | Python |
| (define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) | def factorial(n): return 1 if n == 1 else 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 | Python |
| (define (eval exp env) ((analyze exp) env)) | def 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 | Python |
| (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)))) | def analyze(component): return analyze_literal(component) if is_literal(component) else analyze_name(component) if is_name(component) else analyze_application(component) if is_application(component) else analyze(operator_combination_to_application(component)) if is_operator_combination(component) else analyze_conditional(component) if is_conditional(component) else analyze_lambda_expression(component) if is_lambda_expression(component) else analyze_sequence(sequence_statements(component)) if is_sequence(component) else analyze_block(component) if is_block(component) else analyze_return_statement(component) if is_return_statement(component) else analyze(function_decl_to_constant_decl(component)) if is_function_definition(component) else analyze_declaration(component) if is_declaration(component) else analyze_assignment(component) if is_assignment(component) else error("unknown syntax -- analyze", component) |
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 | Python |
| (define (analyze-self-evaluating exp) (lambda (env) exp)) | def analyze_literal(component): return lambda env: (literal_value(component)) |
| Original | Python | |
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 | Python |
| (define (analyze-variable exp) (lambda (env) (lookup-variable-value exp env))) | def analyze_name(component): return lambda env: (lookup_symbol_value(symbol_of_name(component), env)) |
| Original | Python | |
| 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. def analyze_application(component): ffun = analyze(function_expression(component)) afuns = map(analyze, arg_expressions(component)) return lambda env: (execute_application(ffun(env), map(lambda afun: (afun(env)), afuns))) def execute_application(fun, args): if is_primitive_function(fun): return apply_primitive_function(fun, args) elif is_compound_function(fun): result = function_body(fun) (extend_environment(function_parameters(fun), args, function_environment(fun))) return return_value_content(result) if is_return_value(result) else None else: error("unknown function type -- execute_application", fun) |
| Original | Python | |
|
For conditionals, we extract and analyze the predicate, consequent, and alternative at analysis time. def analyze_conditional(component): pfun = analyze(conditional_predicate(component)) cfun = analyze(conditional_consequent(component)) afun = analyze(conditional_alternative(component)) return lambda env: (cfun(env) if is_truthy(pfun(env)) else 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. def analyze_lambda_expression(component): params = lambda_parameter_symbols(component) bfun = analyze(lambda_body(component)) return lambda 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. def analyze_sequence(stmts): def sequentially(fun1, fun2): def the_sequence(env): fun1_val = fun1(env) return (fun1_val if is_return_value(fun1_val) else fun2(env)) return the_sequence def loop(first_fun, rest_funs): return (first_fun if is_none(rest_funs) else loop(sequentially(first_fun, head(rest_funs)), tail(rest_funs))) funs = map(analyze, stmts) return ((lambda env: None) if is_none(funs) else 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. def analyze_block(component): body = block_body(component) bfun = analyze(body) locals = scan_out_declarations(body) unassigneds = list_of_unassigned(locals) return lambda 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. def analyze_return_statement(component): rfun = analyze(return_expression(component)) return lambda 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 | Python |
| (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))) | def analyze_assignment(component): symbol = assignment_symbol(component) vfun = analyze(assignment_value_expression(component)) def the_assignment(env): value = vfun(env) assign_symbol_value(symbol, value, env) return value return the_assignment def analyze_declaration(component): symbol = declaration_symbol(component) vfun = analyze(declaration_value_expression(component)) def the_declaration(env): assign_symbol_value(symbol, vfun(env), env) return None return the_declaration |
| Original | Python | |
|
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 | Python | |
| Extend the evaluator in this section to support the special form let. (See exercise .) | Extend the evaluator in this section to support while loops. (See exercise 4.7.) |
| Original | Python |
| (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)))) | def analyze_sequence(stmts): def execute_sequence(funs, env): if is_none(funs): return None elif is_none(tail(funs)): return head(funs)(env) else: head_val = head(funs)(env) return head_val if is_return_value(head_val) else execute_sequence(tail(funs), env) funs = map(analyze, stmts) return lambda env: (execute_sequence(funs, env)) |