Why separate parsing from execution?

Question

In chapter 4 of SICP, the metacricular evaluator is modified by splitting the parser into execution, making the eval procedure look like this:

 (define (eval exp env) ((analyze exp) env)) 

and the book says that this will save work, since analyze will be called once in the expression, and the execution procedure can be called many times.

My question is: how does this optimization work? It will work for recursive procedure calls, but what about other cases? The evaluator evaluates the expressions one by one, eval will still be called for each expression, even if they have the same form.

Answer 1

You need to see a few things: (a) the analyze function passes through each expression exactly once, (b) there is no code outside analyze that scans the syntax, (c) the function that analyze return does not call itself, so running this function never leads to further scan the syntax, (d) this is all in contrast to the usual evaluation functions, when calling the function twice means that its syntax is scanned twice.

BTW, the much better name for analyze is compile - it really translates the input language (sexprs) to the target language (a function that acts like machine code here).

Answer 2

The difference between the compiler and the interpreter is as follows:

The compiler scans the source code only once and changes it to the execution code (possibly machine code). The next time you run your program, you directly execute the execution code without analyzing the source code, which is efficient.

The interpreter, however, analyzes the source code each time you run your program.

This optimization only makes sense when your program will run more than once.

As @Eli Barzilay said, “a much better name for analyze is compile ” your functions being analyzed are like executable code. Recursive functions are similar to programs that will be executed more than once.

Answer 3

analyze simply parses once and saves the converted definition , etc. in an environment that can be used through lookup-variable-value directly when performing the corresponding procedure.

In contrast, the original metacircular evaluator twists the syntax analysis and execution, which causes each execution to also reference the parsing.

This link may be useful: http://www.cs.brandeis.edu/~mairson/Courses/cs21b/Handouts/feeley-notes.pdf