One controller segment can return to more than one caller.
A shared machine subroutine receives its return address through a continue register. When a subroutine calls another subroutine, saving and restoring the old continuation preserves the original caller.
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 explicit linkage and one stack slot; it is not a general assembler, calling convention, or proof about hardware subroutine mechanisms.
(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))- Output
- —
- Value
- —
- Diagnostic
- —
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)).
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.
Change the program before you read the hint.
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 one 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.