4.1.8 · Data as programs

A program can be constructed, transformed, inspected, and then evaluated.

Build expression trees with ordinary list operations, specialize a symbolic program by replacing one name, and run the result through an evaluator.

Guiding question

What becomes possible when the evaluator accepts the same list structures that ordinary procedures can construct and transform?

Construct a lambda application as ordinary symbolic list data
Inspect generated operator, parameter, and body structure before execution
Evaluate generated procedure data in an explicit environment
Transform every free occurrence of one symbol in an arithmetic expression
Keep program transformation separate from the evaluator that later executes it

make-linear-program returns the list ((lambda (x) (+ (* 3 x) 2)) 5). Before evaluation, ordinary car, cadr, and list selectors can inspect or rewrite that structure. tiny-eval then interprets the same data: lambda creates a represented compound procedure and application extends the stored environment with x = 5.

The second program treats a quadratic expression as data and recursively replaces the symbol x with 3. The transformation preserves arithmetic as symbolic data. arithmetic-eval then interprets + and * and produces 16. The lesson evaluator processes the listed arithmetic forms through the same explicit representation shared by the producer and transformer.

SICP code2,016 of 1,048,576 UTF-8 bytes

(begin
  (define (make-linear-program slope intercept input)
    (list
      (list 'lambda
            '(x)
            (list '+
                  (list '* slope 'x)
                  intercept))
      input))
  (define (lookup name environment)
    (let ((record (assoc name environment)))
      (if record (cdr record) 'unbound)))
  (define (extend parameters arguments environment)
    (if (null? parameters)
        environment
        (cons (cons (car parameters) (car arguments))
              (extend (cdr parameters)
                      (cdr arguments)
                      environment))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define (tiny-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 (tiny-eval (car expression) environment))
                  (arguments
                    (map (lambda (operand)
                           (tiny-eval operand environment))
                         (cdr expression))))
             (cond ((procedure? procedure)
                    (apply procedure arguments))
                   ((eq? (car procedure) 'compound)
                    (tiny-eval
                      (caddr procedure)
                      (extend (cadr procedure)
                              arguments
                              (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define primitive-environment
    (list (cons '+ +) (cons '* *)))
  (define program (make-linear-program 3 2 5))
  (list program
        (car (car program))
        (cadr (car program))
        (tiny-eval program primitive-environment)))

(begin
  (define (make-linear-program slope intercept input)
    (list
      (list 'lambda
            '(x)
            (list '+
                  (list '* slope 'x)
                  intercept))
      input))
  (define (lookup name environment)
    (let ((record (assoc name environment)))
      (if record (cdr record) 'unbound)))
  (define (extend parameters arguments environment)
    (if (null? parameters)
        environment
        (cons (cons (car parameters) (car arguments))
              (extend (cdr parameters)
                      (cdr arguments)
                      environment))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define (tiny-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 (tiny-eval (car expression) environment))
                  (arguments
                    (map (lambda (operand)
                           (tiny-eval operand environment))
                         (cdr expression))))
             (cond ((procedure? procedure)
                    (apply procedure arguments))
                   ((eq? (car procedure) 'compound)
                    (tiny-eval
                      (caddr procedure)
                      (extend (cadr procedure)
                              arguments
                              (cadddr procedure))))
                   (else 'not-a-procedure))))
          (else 'unknown-expression)))
  (define primitive-environment
    (list (cons '+ +) (cons '* *)))
  (define program (make-linear-program 3 2 5))
  (list program
        (car (car program))
        (cadr (car program))
        (tiny-eval program primitive-environment)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The generated-program run returns (((lambda (x) (+ (* 3 x) 2)) 5) lambda (x) 17). The specialization run returns ((+ (+ (* x x) (* 2 x)) 1) (+ (+ (* 3 3) (* 2 3)) 1) 16).

Trace focus

Separate list construction and replacement from later evaluation. In tiny-eval, follow the generated lambda into a compound record and the generated application into one extended environment. In arithmetic-eval, confirm that no symbolic replacement occurs during numeric interpretation.

Try it yourself

Change the program and compare the result.

Generate a two-parameter affine program (+ (* slope x) (* offset y)), inspect its parameter list, and evaluate it. Then specialize only x in the generated body while leaving y symbolic.

Show hint

Program generation should return data only. Extend pairs parameters and arguments in order; specialization can reuse replace-symbol before evaluation.

Complete this lesson

0 of 23 lessons complete in this chapter0%