4.2.1 · Normal order and applicative order

Evaluation order decides when an argument becomes work.

Run the same guest applications through strict and non-memoized normal-order evaluators, then count a probe when an argument is unused or referenced twice.

Guiding question

How can two evaluators return the same value while performing different argument work?

Evaluate every operand before strict compound application
Bind unevaluated operand expressions as normal-order thunks
Force a thunk only when variable lookup needs its value
Observe an unused argument under both strategies
Observe duplicated work when a normal-order parameter is referenced twice
Compare two explicit guest evaluation strategies

strict-eval evaluates the operand before applying the compound procedure. The ignored x argument therefore calls probe once even though the body returns 1. normal-eval instead binds x to a thunk containing the operand expression and its environment. Because the body never looks up x, probe does not run.

In the second expression the body uses x twice. Strict evaluation computes probe once and binds the resulting 10. The non-memoized normal evaluator forces the saved expression for each lookup, so probe runs twice. Both return 20, but the work differs. These two evaluators are explicit guest models; they do not switch the evaluation order of the host Lispex program running them.

SICP code4,328 of 1,048,576 UTF-8 bytes

(begin
  (define probes 0)
  (define (probe value)
    (set! probes (+ probes 1))
    value)
  (define (lookup name environment)
    (let ((record (assoc name environment)))
      (if record (cdr record) 'unbound)))
  (define (extend names values environment)
    (if (null? names)
        environment
        (cons (cons (car names) (car values))
              (extend (cdr names) (cdr values) environment))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define (compound? value)
    (and (pair? value) (eq? (car value) 'compound)))
  (define (strict-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression) (lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let ((procedure
                  (strict-eval (car expression) environment))
                 (arguments
                  (map (lambda (operand)
                         (strict-eval operand environment))
                       (cdr expression))))
             (cond ((procedure? procedure)
                    (apply procedure arguments))
                   ((compound? procedure)
                    (strict-eval
                      (caddr procedure)
                      (extend (cadr procedure)
                              arguments
                              (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define (make-thunk expression environment)
    (list 'thunk expression environment))
  (define (thunk? value)
    (and (pair? value) (eq? (car value) 'thunk)))
  (define (force-normal value)
    (if (thunk? value)
        (normal-eval (cadr value) (caddr value))
        value))
  (define (normal-lookup name environment)
    (force-normal (lookup name environment)))
  (define (delay-operands operands environment)
    (map (lambda (operand)
           (make-thunk operand environment))
         operands))
  (define (actual-operands operands environment)
    (map (lambda (operand)
           (normal-eval operand environment))
         operands))
  (define (normal-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression)
           (normal-lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let ((procedure
                  (normal-eval (car expression) environment)))
             (cond ((procedure? procedure)
                    (apply procedure
                           (actual-operands
                             (cdr expression)
                             environment)))
                   ((compound? procedure)
                    (normal-eval
                      (caddr procedure)
                      (extend
                        (cadr procedure)
                        (delay-operands
                          (cdr expression)
                          environment)
                        (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define primitive-environment
    (list (cons '+ +)
          (cons 'probe probe)))
  (define unused-expression
    '((lambda (x) 1) (probe 10)))
  (define duplicated-expression
    '((lambda (x) (+ x x)) (probe 10)))
  (set! probes 0)
  (define strict-unused
    (list (strict-eval unused-expression primitive-environment)
          probes))
  (set! probes 0)
  (define normal-unused
    (list (normal-eval unused-expression primitive-environment)
          probes))
  (set! probes 0)
  (define strict-duplicated
    (list (strict-eval duplicated-expression primitive-environment)
          probes))
  (set! probes 0)
  (define normal-duplicated
    (list (normal-eval duplicated-expression primitive-environment)
          probes))
  (list (list 'unused strict-unused normal-unused)
        (list 'duplicated strict-duplicated normal-duplicated)))

(begin
  (define probes 0)
  (define (probe value)
    (set! probes (+ probes 1))
    value)
  (define (lookup name environment)
    (let ((record (assoc name environment)))
      (if record (cdr record) 'unbound)))
  (define (extend names values environment)
    (if (null? names)
        environment
        (cons (cons (car names) (car values))
              (extend (cdr names) (cdr values) environment))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define (compound? value)
    (and (pair? value) (eq? (car value) 'compound)))
  (define (strict-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression) (lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let ((procedure
                  (strict-eval (car expression) environment))
                 (arguments
                  (map (lambda (operand)
                         (strict-eval operand environment))
                       (cdr expression))))
             (cond ((procedure? procedure)
                    (apply procedure arguments))
                   ((compound? procedure)
                    (strict-eval
                      (caddr procedure)
                      (extend (cadr procedure)
                              arguments
                              (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define (make-thunk expression environment)
    (list 'thunk expression environment))
  (define (thunk? value)
    (and (pair? value) (eq? (car value) 'thunk)))
  (define (force-normal value)
    (if (thunk? value)
        (normal-eval (cadr value) (caddr value))
        value))
  (define (normal-lookup name environment)
    (force-normal (lookup name environment)))
  (define (delay-operands operands environment)
    (map (lambda (operand)
           (make-thunk operand environment))
         operands))
  (define (actual-operands operands environment)
    (map (lambda (operand)
           (normal-eval operand environment))
         operands))
  (define (normal-eval expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression)
           (normal-lookup expression environment))
          ((and (pair? expression)
                (eq? (car expression) 'lambda))
           (make-procedure
             (cadr expression)
             (caddr expression)
             environment))
          ((pair? expression)
           (let ((procedure
                  (normal-eval (car expression) environment)))
             (cond ((procedure? procedure)
                    (apply procedure
                           (actual-operands
                             (cdr expression)
                             environment)))
                   ((compound? procedure)
                    (normal-eval
                      (caddr procedure)
                      (extend
                        (cadr procedure)
                        (delay-operands
                          (cdr expression)
                          environment)
                        (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define primitive-environment
    (list (cons '+ +)
          (cons 'probe probe)))
  (define unused-expression
    '((lambda (x) 1) (probe 10)))
  (define duplicated-expression
    '((lambda (x) (+ x x)) (probe 10)))
  (set! probes 0)
  (define strict-unused
    (list (strict-eval unused-expression primitive-environment)
          probes))
  (set! probes 0)
  (define normal-unused
    (list (normal-eval unused-expression primitive-environment)
          probes))
  (set! probes 0)
  (define strict-duplicated
    (list (strict-eval duplicated-expression primitive-environment)
          probes))
  (set! probes 0)
  (define normal-duplicated
    (list (normal-eval duplicated-expression primitive-environment)
          probes))
  (list (list 'unused strict-unused normal-unused)
        (list 'duplicated strict-duplicated normal-duplicated)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The program returns ((unused (1 1) (1 0)) (duplicated (20 1) (20 2))). Each pair contains the value followed by the number of probe calls.

Trace focus

In strict-eval, find probe before the compound body begins. In normal-eval, follow each parameter binding to a thunk and force it only at variable lookup. The unused body performs no force; the duplicated body reaches the same thunk expression twice because this model deliberately does not memoize.

Try it yourself

Change the program and compare the result.

Add ((lambda (x) (+ x (+ x x))) (probe 4)). Predict strict and normal probe counts, then add a memo cell to the thunk and predict the call-by-need count.

Show hint

Strict evaluation computes the argument once. Non-memoized normal order computes once per x lookup. A memoized thunk computes at most once.

Complete this lesson

0 of 23 lessons complete in this chapter0%