5.1.3 · Subroutines and continuation linkage

One controller segment can return to more than one caller.

A shared machine subroutine receives its return address through a continue register, and saving the old continuation preserves the original caller.

Guiding question

How does a register machine return from shared and nested controller subroutines without duplicating their instructions?

Store a caller-specific return address in a continue register
Jump into one shared controller segment from two call sites
Return through goto-register rather than a fixed label
Save an outer continuation before a nested subroutine call
Restore the original continuation before returning to the first caller

The first controller calls one double subroutine twice. Before each goto, the caller writes a different pc value into continue. The shared subroutine changes val and executes goto-register continue, so the same two instructions return first to the instruction that saves the left result and later to the instruction that adds the two doubled values. The recorded pc path shows both entries into indices 9 and 10 without copying the routine.

The second controller calls a double-then-add-one subroutine, and that subroutine calls double. The nested call needs continue for its own return address, so the outer subroutine saves the caller’s value first. After double returns, restore recovers the original address, add1 finishes the outer routine, and goto-register returns to main. This finite executor models the lesson’s explicit linkage and one stack slot.

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

(begin
  (define controller
    (vector
      '(assign val constant 3)
      '(assign continue constant 3)
      '(goto 9)
      '(assign left copy val)
      '(assign val constant 5)
      '(assign continue constant 7)
      '(goto 9)
      '(assign result add left val)
      '(halt)
      '(assign val double val)
      '(goto-register continue)))
  (define (register-index name)
    (cond ((eq? name 'val) 0)
          ((eq? name 'left) 1)
          ((eq? name 'result) 2)
          ((eq? name 'continue) 3)
          ((eq? name 'pc) 4)))
  (define (run-machine)
    (let ((registers (vector 0 0 0 0 0))
          (path '())
          (return-addresses '()))
      (define (get name)
        (vector-ref registers (register-index name)))
      (define (put! name value)
        (vector-set! registers (register-index name) value))
      (define (advance!) (put! 'pc (+ (get 'pc) 1)))
      (define (assignment instruction)
        (let ((operation (caddr instruction)))
          (cond ((eq? operation 'constant)
                 (cadddr instruction))
                ((eq? operation 'copy)
                 (get (cadddr instruction)))
                ((eq? operation 'double)
                 (* 2 (get (cadddr instruction))))
                ((eq? operation 'add)
                 (+ (get (cadddr instruction))
                    (get (list-ref instruction 4)))))))
      (define (execute remaining-steps)
        (if (= remaining-steps 0)
            'step-limit
            (let* ((pc (get 'pc))
                   (instruction (vector-ref controller pc))
                   (operation (car instruction)))
              (set! path (cons pc path))
              (cond
                ((eq? operation 'halt)
                 (list (get 'result)
                       (reverse return-addresses)
                       (reverse path)))
                ((eq? operation 'assign)
                 (let ((target (cadr instruction))
                       (value (assignment instruction)))
                   (put! target value)
                   (if (eq? target 'continue)
                       (set! return-addresses
                             (cons value return-addresses)))
                   (advance!)
                   (execute (- remaining-steps 1))))
                ((eq? operation 'goto)
                 (put! 'pc (cadr instruction))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto-register)
                 (put! 'pc (get (cadr instruction)))
                 (execute (- remaining-steps 1)))))))
      (execute 100)))
  (run-machine))

(begin
  (define controller
    (vector
      '(assign val constant 3)
      '(assign continue constant 3)
      '(goto 9)
      '(assign left copy val)
      '(assign val constant 5)
      '(assign continue constant 7)
      '(goto 9)
      '(assign result add left val)
      '(halt)
      '(assign val double val)
      '(goto-register continue)))
  (define (register-index name)
    (cond ((eq? name 'val) 0)
          ((eq? name 'left) 1)
          ((eq? name 'result) 2)
          ((eq? name 'continue) 3)
          ((eq? name 'pc) 4)))
  (define (run-machine)
    (let ((registers (vector 0 0 0 0 0))
          (path '())
          (return-addresses '()))
      (define (get name)
        (vector-ref registers (register-index name)))
      (define (put! name value)
        (vector-set! registers (register-index name) value))
      (define (advance!) (put! 'pc (+ (get 'pc) 1)))
      (define (assignment instruction)
        (let ((operation (caddr instruction)))
          (cond ((eq? operation 'constant)
                 (cadddr instruction))
                ((eq? operation 'copy)
                 (get (cadddr instruction)))
                ((eq? operation 'double)
                 (* 2 (get (cadddr instruction))))
                ((eq? operation 'add)
                 (+ (get (cadddr instruction))
                    (get (list-ref instruction 4)))))))
      (define (execute remaining-steps)
        (if (= remaining-steps 0)
            'step-limit
            (let* ((pc (get 'pc))
                   (instruction (vector-ref controller pc))
                   (operation (car instruction)))
              (set! path (cons pc path))
              (cond
                ((eq? operation 'halt)
                 (list (get 'result)
                       (reverse return-addresses)
                       (reverse path)))
                ((eq? operation 'assign)
                 (let ((target (cadr instruction))
                       (value (assignment instruction)))
                   (put! target value)
                   (if (eq? target 'continue)
                       (set! return-addresses
                             (cons value return-addresses)))
                   (advance!)
                   (execute (- remaining-steps 1))))
                ((eq? operation 'goto)
                 (put! 'pc (cadr instruction))
                 (execute (- remaining-steps 1)))
                ((eq? operation 'goto-register)
                 (put! 'pc (get (cadr instruction)))
                 (execute (- remaining-steps 1)))))))
      (execute 100)))
  (run-machine))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The shared-subroutine program returns (16 (3 7) (0 1 2 9 10 3 4 5 6 9 10 7 8)). The nested-call program returns (9 1 0 (3 8) (0 1 2 5 6 7 11 12 8 9 10 3 4)).

Trace focus

In the first run, locate each assignment to continue, both jumps to the same subroutine pc, and the two goto-register returns to different callers. In the second, follow save before the nested continue assignment, the inner return to pc 8, restore of the original pc 3, and the final return to main. The explicit path and stack depth describe these finite controllers only.

Try it yourself

Change the program and compare the result.

Add a third caller that doubles 7 and includes it in the final sum. Predict its return address and the new pc path before running the machine.

Show hint

The shared subroutine still begins at pc 9. The new caller needs its own instruction immediately after the goto and must place that pc in continue.

Complete this lesson

0 of 23 lessons complete in this chapter0%