SICP 4.1.7
2024-07-28 Sun

Separating Syntactic Analysis from Execution

  • Our evaluator is inefficient in that it interleaves syntactic analysis and execution of expressions.
  • If a program is executed many times, then its syntax is expensively and wastefully analyzed each of those times.

  • Consider: 

    (define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

    Each time factorial is called the evaluator must determine that the body is an if statement and act accordingly. Each time (* (factorial (- n 1)) n), (factorial (- n 1)), and (- n 1) are evaluated, the evaluator must determine that they are applications and act accordingly.

  • Authors present a way, used by Jonathan Rees in 1982 and independently invented by Marc Feeley in 1986, to perform syntactic analysis only once.
  • Eval is split into two parts.
  • ``The procedure analyze takes only the expression. It performs the syntactic analysis and returns a new procedure, the execution procedure, that encapsulates the work to be done in executing the analyzed expression. The execution procedure takes an environment as its argument and completes the evaluation. This saves work because analyze will be called only once on an expression, while the execution procedure may be called many times.'' (394)

Here is the code: 

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

(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))
        ((begin? exp) (analyze-sequence (begin-action exp)))
        ((cond? exp) (analyze (cond->if exp)))
        ((application? exp) (analyze-application exp))
        (else
         (error "Unknown expression type -- ANALYZE" exp))))

(define (analyze-self-evaluating exp)
  (lambda (env) exp))

(define (analyze-quoted exp)
  (let ((qval (text-of-quotation exp)))
    (lambda (env) qval)))

;; Looking up a variable depends upon knowing the environment, so it
;; must be done at execution time (Sec. 5.5.6 will show, though, how
;; to perform an important part of the variable search as part of the
;; syntactic analysis).
(define (analyze-variable exp)
  (lambda (env) (lookup-variable-value exp env)))

;; Assignments and definitions, too, can be performed only when the
;; env is known. However, the recursive analysis of `assignment-value`
;; and `definition-value` during syntactic analys is a ``major gain in
;; efficiency''.
(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)))

;; We now analyze predicates, consequents, and alternatives of if
;; statements 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)))))

;; λ:
(define (analyze-lambda exp)
  (let ((vars (lambda-parameters exp))
        (bproc (analyze-sequence (lambda-body exp))))
    (lambda (env) (make-procedure vars bproc env))))

;; The analysis of sequences is ``more involved'': ...
(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))))

;; Finally, to analyze an application...
(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))))

Exercise 4.22

Exercise:

Extend the evaluator in this section to support the special form let. (See Exercise 4.6)

Answer: 

  (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)))
          ((let? exp) (analyze (let-combination exp)))
          ((application? exp) (analyze-application exp))
          (else
           (error "Unknown expression type -- ANALYZE" exp))))
;; where `let-combination' is the procedure (shown in the answer to
;; Exercise 4.6) that transforms a let expression into (the
;; application of) a lambda expression.

Exercise 4.23

Exercise:

Alyssa P. Hacker doesn't understand why analyze-sequence needs to be so complicated. All the other analysis procedures are straightforward transformations of the corresponding evaluation procedures (or eval clauses) in section 4.1.1. She expected analyze-sequence to look like this: 

(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))))

Eva Lu Ator explains to Alyssa that the version in the text does more of the work of evaluating a sequence at analysis time. Alyssa's sequence-execution procedure, rather than having the calls to the individual execution procedures built in, loops through the procedures in order to call them: In effect, although the individual expressions in the sequence have been analyzed, the sequence itself has not been.

Compare the two versions of analyze-sequence. For example, consider the common case (typical of procedure bodies) where the sequence has just one expression. What work will the execution procedure produced by Alyssa's program do? What about the execution procedure produced by the program in the text above? How do the two versions compare for a sequence with two expressions?

Answer:

Let's consider a sequence with one expression, the sequence which contains the self-evaluating expression 1: (1).

This is what happens when the program in the main text is applied to that sequence:

  • procs is assigned this value: 

    ((lambda (env) 1))

  • loop is called: 

    (loop (lambda (env) 1) nil)

  • final value: 

    (lambda (env) 1)
  • If we apply this latter value (which is a lambda) to an environment, then it evaluates to 1.

This, instead, is what happens with Alyssa's program:

  • procs are assigned the same value they are assigned by the program in the main text;

  • final value: 

    (lambda (env) (execute-sequence ((lambda (env) q))
                                env))

  • if this latter value is applied to an environment, then it evaluates to this call: 

    ((lambda (env) 1) env)

    which evaluates to 1.

Let's now consider the sequence with the self-evaluting expression 1 and the self-evaluting expression 2: (1 2).

This is what happens when the program in the main text is applied to that sequence:

  • procs is set to this value: 

    ((lambda (env) 1) (lambda (env) 2))

  • we perform this application: 

    (loop (lambda (env) 1) ((lambda (env) 2)))

  • then we perform this application: 

    (loop (lambda (env) (lambda (env) 1) (lambda (env) 2)) nil)

  • This is the final value: 

    (lambda (env) ((lambda (env) 1 env)) ((lambda (env) 2) env))

This is what happens with Alyssa's program:

  • procs is set to the same value as above;

  • Final value: 

    (lambda (env) (execute-sequence ((lambda (env) 1)
                                 (lambda (env) 2))
                                env))

  • When we apply this final value (which is a lambda) to an environment, we evaluate this application, which evaluates to 1: 

    ((lambda (env) 1) env)

    But also also this one: 

    (execute-sequence ((lambda (env) 2)) env)

    which evaluates to 

    ((lambda (env) 2 ) env)

    which evaluates to 2.

    The program in the main text and Alyssa's program give the same result. However, Alyssa's program returns a lambda which does more work when it is called; it has to construct the final lambda calls. The program in the main text returns a lambda whose body already contains those final lambda calls.

←

Send me an email for comments.

Created with Emacs 30.0.60 (Org mode 9.7.5)