CODEWITHSUNDEEP
schemesicp
pjhades
pjhades

Reputation: 2038

Why separating syntax analysis from execution?

In SICP Chapter 4, the metacircular evaluator is modified by separating the syntax analysis from the execution, making the eval procedure look like:

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

and the book says that this will save work since analyze will be called once on an expression, while the execution procedure may be called many times.

My question is, how does this optimization work? It will work for recursive procedure calls, but how about other cases? The evaluator evaluates expressions one after another, eval will still be called on each expression even if they have identical forms.

Upvotes: 5

Views: 320

Answers (3)

Kamel
Kamel

Reputation: 1866

analyze just does syntax analyses once and store the transformed definition and so on in the environment which may be used through lookup-variable-value directly when the related procedure is executed.

In contrast, the original metacircular evaluator twists the syntax analysis and execution which makes each execution invokes syntax analysis as well.

This link maybe helpful: http://www.cs.brandeis.edu/~mairson/Courses/cs21b/Handouts/feeley-notes.pdf

Upvotes: 1

Nmzzz
Nmzzz

Reputation: 2472

The difference between a compiler and a interpreter is that:

A compiler scan your source code only once and change it into to execution code (machine code maybe). When you execute your program the next time, you directly execute the execution code without analyzing the source code, which is efficient.

A interpreter, however, analyze the source code each time you execute your program.

This optimization only makes sense in cases of your program will be executed more than once.

As @Eli Barzilay said, "a much better name for analyze is compile", your analyzed functions is like the execution code. The recursive functions are like programs which would be executed more than once.

Upvotes: 2

Eli Barzilay
Eli Barzilay

Reputation: 29546

You need to see several things: (a) the analyze function walks over each expression exactly once, (b) there is no code outside of analyze that scans the syntax, (c) the function that analyze returns does not call itself therefore running that function never leads to any further scanning of the syntax, (d) this is all unlike the usual evaluation functions where calling a function twice means that its syntax is scanned twice.

BTW, a much better name for analyze is compile -- it really does translate the input language (sexprs) to a target one (a function, acting as the machine code here).

Upvotes: 5

Related Questions