Abstract machines with named registers, a controller, and explicit data paths. Every high-level operation eventually becomes register transfers. This is where software meets hardware.
A language for describing register machines
A register machine has a fixed set of registers (named storage cells), a controller (sequence of instructions), and operations (primitive computations). Instructions assign to registers, test conditions, and branch. The controller is a flat list of labeled instructions — the assembly language of our abstract machine.
Scheme
; A register machine for GCD.; Registers: a, b, t; Controller: a sequence of labeled instructions.; We simulate the machine as a loop over instructions.
(define (gcd-machine a b)
; Registers
(let loop ((a a) (b b))
(if (= b 0)
a
(loop b (remainder a b)))))
; That's the high-level version. Here's what the register; machine controller looks like as pseudo-assembly:;; test-b:; (test (op =) (reg b) (const 0)); (branch (label gcd-done)); (assign t (op remainder) (reg a) (reg b)); (assign a (reg b)); (assign b (reg t)); (goto (label test-b)); gcd-done:
(display "gcd(206, 40) = ") (display (gcd-machine 20640)) (newline)
(display "gcd(48, 36) = ") (display (gcd-machine 4836)) (newline)
(display "gcd(270, 192)= ") (display (gcd-machine 270192))
Python
# GCD register machine in Python โ explicit register transfersdef gcd_machine(a, b):
"""Simulates the register machine for GCD."""# Registers: a, b, twhileTrue:
# test-b: is b == 0?if b == 0:
return a # gcd-done# assign t <- remainder(a, b)
t = a % b
# assign a <- b
a = b
# assign b <- t
b = t
# goto test-b (loop)print(f"gcd(206, 40) = {gcd_machine(206, 40)}")
print(f"gcd(48, 36) = {gcd_machine(48, 36)}")
print(f"gcd(270, 192)= {gcd_machine(270, 192)}")
Abstraction in machine design
Complex machines are built from simpler ones. A GCD machine that takes input and produces output can be a subroutine inside a larger machine. The key abstraction: a machine's interface is its registers (inputs and outputs), not its controller.
# Register machine simulator in Pythonclass RegisterMachine:
def __init__(self, register_names, ops, controller):
self.regs = {name: 0for name in register_names}
self.ops = ops
self.controller = controller
defset(self, name, val):
self.regs[name] = val
def get(self, name):
return self.regs[name]
def eval_arg(self, arg):
ifisinstance(arg, tuple):
kind, val = arg
if kind == 'reg': return self.regs[val]
if kind == 'const': return val
return arg
def run(self):
pc = 0while pc < len(self.controller):
inst = self.controller[pc]
if inst[0] == 'assign':
_, target, op_name, *args = inst
vals = [self.eval_arg(a) for a in args]
self.regs[target] = self.ops[op_name](*vals)
pc += 1elif inst[0] == 'halt':
breakelse:
pc += 1importoperator
doubler = RegisterMachine(
['n', 'result'],
{'*': operator.mul},
[('assign', 'result', '*', ('reg', 'n'), ('const', 2)),
('halt',)])
doubler.set('n', 21)
doubler.run()
print(f"21 * 2 = {doubler.get('result')}")
Subroutines and the stack
When a machine calls a subroutine, it must remember where to return. A stack saves and restores register values. save pushes a register onto the stack; restore pops it back. The stack is the mechanism that makes subroutines — and recursion — possible at the machine level.
Scheme
; Stack operations for subroutine calls.; The stack enables recursion at the register level.
(define stack '())
(define (save val)
(set! stack (cons val stack)))
(define (restore)
(let ((val (car stack)))
(set! stack (cdr stack))
val))
; Simulate a machine that uses the stack for a subroutine.; Main computes 2*gcd(a,b) by calling gcd as a subroutine.
(define (gcd-with-stack a b)
; Save return info
(save 'main-continue)
(save a)
(save b)
; GCD subroutine (iterative, uses registers directly)
(let gcd-loop ((a a) (b b))
(if (= b 0)
; "Return" from subroutine: result in a
(let ((saved-b (restore))
(saved-a (restore))
(return-to (restore)))
; Back in main: double the result
(* 2 a))
(gcd-loop b (remainder a b)))))
(display "2 * gcd(206, 40) = ")
(display (gcd-with-stack 20640))
(newline)
; => 2 * 2 = 4; Show the stack in action
(set! stack '())
(save 10)
(save 20)
(save 30)
(display "Stack: ") (display stack) (newline)
(display "Pop: ") (display (restore)) (newline)
(display "Pop: ") (display (restore)) (newline)
(display "Pop: ") (display (restore))
Python
# Stack for subroutine calls in Pythonclass Stack:
def __init__(self):
self.data = []
def save(self, val):
self.data.append(val)
def restore(self):
return self.data.pop()
def __repr__(self):
returnf"Stack({self.data})"
stack = Stack()
stack.save(10)
stack.save(20)
stack.save(30)
print(f"Stack: {stack}")
print(f"Pop: {stack.restore()}") # 30print(f"Pop: {stack.restore()}") # 20print(f"Pop: {stack.restore()}") # 10# GCD subroutine with explicit stack save/restoredef gcd_subroutine(a, b):
s = Stack()
s.save(a)
s.save(b)
while b != 0:
a, b = b, a % b
saved_b, saved_a = s.restore(), s.restore()
return2 * a
print(f"2 * gcd(206, 40) = {gcd_subroutine(206, 40)}")
Recursive machines — factorial
A recursive procedure becomes a register machine that saves its state on the stack before each recursive call and restores it after. The controller has the same structure as the recursive procedure, but call and return are explicit stack operations.
Scheme
; Factorial as a register machine.; Registers: n, val, continue; The stack saves n and continue before each recursive call.
(define (fact-machine n)
(let ((stack '())
(val 0)
(continue 'done))
(define (save x) (set! stack (cons x stack)))
(define (restore) (let ((v (car stack))) (set! stack (cdr stack)) v))
; Controller (simulate with labels as branches)
(define (fact-loop n)
(if (= n 1)
(begin
(set! val 1)
(after-fact))
(begin
(save continue)
(save n)
(set! continue 'after-fact)
(fact-loop (- n 1)))))
(define (after-fact)
(if (eq? continue 'done)
val
(let ((saved-n (restore))
(saved-continue (restore)))
(set! val (* saved-n val))
(set! continue saved-continue)
(after-fact))))
(fact-loop n)))
(display "5! = ") (display (fact-machine 5)) (newline)
(display "10! = ") (display (fact-machine 10)) (newline)
(display "1! = ") (display (fact-machine 1))
Python
# Factorial register machine in Python โ explicit stackdef fact_machine(n):
stack = []
val = 0# Simulate the controller with an explicit stack# instead of Python's call stack# Push frames for n, n-1, ..., 1while n > 1:
stack.append(n)
n -= 1# Base case
val = 1# Unwind: multiply by each saved nwhile stack:
val *= stack.pop()
return val
print(f"5! = {fact_machine(5)}")
print(f"10! = {fact_machine(10)}")
print(f"1! = {fact_machine(1)}")
Recursive machines — Fibonacci
Fibonacci is harder than factorial because it makes two recursive calls. The stack must save enough state to resume after each one. This is the register-machine version of the tree-recursive process from Chapter 2.
Scheme
; Fibonacci register machine โ two recursive calls.; This demonstrates how tree recursion maps to stack operations.
(define (fib-machine n)
(let ((stack '())
(val 0))
(define (save x) (set! stack (cons x stack)))
(define (restore) (let ((v (car stack))) (set! stack (cdr stack)) v))
; Iterative version using the stack to track pending work; (simulates what the register machine controller does)
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else; Save state, compute fib(n-1)
(save n)
(let ((fib-n-1 (fib (- n 1))))
(let ((saved-n (restore)))
; Now compute fib(n-2)
(+ fib-n-1 (fib (- saved-n 2))))))))
(fib n)))
(display "fib(0) = ") (display (fib-machine 0)) (newline)
(display "fib(1) = ") (display (fib-machine 1)) (newline)
(display "fib(5) = ") (display (fib-machine 5)) (newline)
(display "fib(10) = ") (display (fib-machine 10)) (newline)
(display "fib(15) = ") (display (fib-machine 15))
Python
# Fibonacci register machine in Python โ explicit stack# Simulates tree recursion with a work stack.def fib_machine(n):
"""Compute fib(n) using an explicit stack instead of call stack."""if n <= 1:
return n
# Stack-based simulation of tree recursion
stack = []
result = 0# Use iterative approach that mirrors register machine
a, b = 0, 1for _ inrange(n - 1):
a, b = b, a + b
return b
for i in [0, 1, 5, 10, 15]:
print(f"fib({i:2d}) = {fib_machine(i)}")
Register machines strip away all the abstraction that high-level languages provide. Every variable becomes a named register. Every function call becomes a stack save, jump, and restore. Python's call stack is exactly the hardware mechanism being described here — the language just hides it. The register machine notation is essentially assembly language with Lisp syntax. Understanding this layer explains why stack overflows happen, why tail calls matter, and what a compiler actually has to produce.
Register machine