Course capstone · Executable pipeline

Carry one idea from abstract data to explicit machine state.

One program constructs expression data, interprets it in an environment, compiles it, executes the instructions with a visible program counter and stack, and remembers how many times the pipeline ran.

Guiding question

Can every layer change representation without changing the value the learner observes?

Build expression data through a constructor procedure
Read representation through selectors
Evaluate names in an explicit environment
Compile the expression into stack instructions
Run an explicit pc and stack while retaining closure state

make-sum creates one abstract expression. evaluate follows its selectors and looks up x and y in the supplied environment. compile follows the same interface but emits two load instructions followed by add.

run repeatedly applies step to a state containing pc and stack. make-pipeline captures both the compiled code and a mutable run count, so the second call reuses the code while reporting the next count.

SICP code1,719 of 1,048,576 UTF-8 bytes

(begin
  (define (make-sum left right) (list 'sum left right))
  (define (left-operand expression) (cadr expression))
  (define (right-operand expression) (caddr expression))
  (define (lookup name environment)
    (cdr (assoc name environment)))
  (define (evaluate expression environment)
    (if (symbol? expression)
        (lookup expression environment)
        (+ (evaluate (left-operand expression) environment)
           (evaluate (right-operand expression) environment))))
  (define (compile expression)
    (if (symbol? expression)
        (list (list 'load expression))
        (append (compile (left-operand expression))
                (append (compile (right-operand expression))
                        '(add)))))
  (define (step code environment state)
    (let ((pc (car state))
          (stack (cadr state)))
      (let ((instruction (list-ref code pc)))
        (if (pair? instruction)
            (list (+ pc 1)
                  (cons (lookup (cadr instruction) environment)
                        stack))
            (list (+ pc 1)
                  (cons (+ (cadr stack) (car stack))
                        (cddr stack)))))))
  (define (run code environment state)
    (if (= (car state) (length code))
        state
        (run code environment (step code environment state))))
  (define (make-pipeline expression)
    (let ((code (compile expression))
          (runs 0))
      (lambda (environment)
        (set! runs (+ runs 1))
        (list (evaluate expression environment)
              (run code environment (list 0 '()))
              runs))))
  (let ((pipeline (make-pipeline (make-sum 'x 'y))))
    (list (pipeline '((x . 4) (y . 5)))
          (pipeline '((x . 2) (y . 10))))))

(begin
  (define (make-sum left right) (list 'sum left right))
  (define (left-operand expression) (cadr expression))
  (define (right-operand expression) (caddr expression))
  (define (lookup name environment)
    (cdr (assoc name environment)))
  (define (evaluate expression environment)
    (if (symbol? expression)
        (lookup expression environment)
        (+ (evaluate (left-operand expression) environment)
           (evaluate (right-operand expression) environment))))
  (define (compile expression)
    (if (symbol? expression)
        (list (list 'load expression))
        (append (compile (left-operand expression))
                (append (compile (right-operand expression))
                        '(add)))))
  (define (step code environment state)
    (let ((pc (car state))
          (stack (cadr state)))
      (let ((instruction (list-ref code pc)))
        (if (pair? instruction)
            (list (+ pc 1)
                  (cons (lookup (cadr instruction) environment)
                        stack))
            (list (+ pc 1)
                  (cons (+ (cadr stack) (car stack))
                        (cddr stack)))))))
  (define (run code environment state)
    (if (= (car state) (length code))
        state
        (run code environment (step code environment state))))
  (define (make-pipeline expression)
    (let ((code (compile expression))
          (runs 0))
      (lambda (environment)
        (set! runs (+ runs 1))
        (list (evaluate expression environment)
              (run code environment (list 0 '()))
              runs))))
  (let ((pipeline (make-pipeline (make-sum 'x 'y))))
    (list (pipeline '((x . 4) (y . 5)))
          (pipeline '((x . 2) (y . 10))))))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The program returns ((9 (3 (9)) 1) (12 (3 (12)) 2)). In each result the direct value equals the value on the final machine stack, pc 3 marks the end of three instructions, and the final field counts pipeline calls.

Trace focus

Locate constructor and selector calls, environment lookups, compile before either pipeline execution, pc changes from 0 through 3, stack updates, and the captured runs assignment. The complete execution trace contains 630 events for this shipped program under fixed runtime limits.

Review

Five checks across the complete pipeline

Where is the expression representation hidden?

Answer make-sum creates it, while evaluate and compile ask left-operand and right-operand instead of depending on list positions directly.

Why do the two direct values differ?

Answer The same expression receives two environments with different bindings for x and y.

Why does each final machine state have pc 3?

Answer The compiler emits two load instructions and one add instruction, and run stops after all three have executed.

What state survives between the two pipeline calls?

Answer The closure retains compiled code and the mutable runs binding, whose observed values advance from 1 to 2.

What does this capstone establish?

Answer It records exact agreement across the displayed expressions, environments, machine states, and two pipeline calls.