A software simulator for register machines. The assembler translates symbolic instructions into executable procedures. Testing machines before building hardware.
The machine model
A register machine has named registers, a program counter, and a stack. The model stores register contents in an association list. Each register is a pair: a name and a mutable value. The machine dispatches on message type — get, set, start.
# A register as a simple classclass Register:
def __init__(self, name):
self.name = name
self.contents = '*unassigned*'def get(self):
return self.contents
defset(self, value):
self.contents = value
r = Register('val')
print(f"initial: {r.get()}")
r.set(42)
print(f"after set: {r.get()}")
r.set(99)
print(f"after second set: {r.get()}")
The assembler — extract-labels
The assembler walks the instruction sequence and separates labels (symbols marking positions) from instructions (lists to execute). extract-labels builds two parallel structures: a list of label/position pairs and a list of instruction procedures.
Scheme
; extract-labels: separate labels from instructions.; Labels are symbols; instructions are lists.
(define (extract-labels text)
(if (null? text)
(cons '() '()) ; (labels . instructions)
(let ((result (extract-labels (cdr text))))
(let ((labels (car result))
(insts (cdr result)))
(let ((next-inst (car text)))
(if (symbol? next-inst)
; It's a label โ record position
(cons (cons (cons next-inst insts) labels)
insts)
; It's an instruction โ add to list
(cons labels
(cons next-inst insts))))))))
(define sample-text
'(start
(assign t (reg n))
(test (op =) (reg n) (const 0))
(branch (label done))
(assign n (op -) (reg n) (const 1))
(goto (label start))
done
(assign val (reg t))))
(let ((result (extract-labels sample-text)))
(display "Labels: ")
(display (map car (car result)))
(newline)
(display "Instructions: ")
(display (length (cdr result)))
(display " instructions"))
Each instruction type — assign, test, branch, goto, perform — gets a corresponding execution procedure. The procedure closes over the machine's registers and stack, so executing it is just a function call. No interpretation at runtime.
Scheme
; Execution procedures for a tiny instruction set.; Each returns a thunk that performs the operation.
(define (make-assign-proc reg-get reg-set value-fn)
(lambda ()
(reg-set (value-fn))
'done))
(define (make-test-proc op-fn arg-fns)
(lambda ()
(apply op-fn (map (lambda (f) (f)) arg-fns))))
; Simulate: assign val = 3 + 4
(define val 0)
(define set-val! (lambda (v) (set! val v)))
(define get-val (lambda () val))
(define exec-assign
(make-assign-proc
get-val
set-val!
(lambda () (+ 34))))
(exec-assign)
(display "val after assign: ") (display val) (newline)
; Simulate: test (= val 7)
(define exec-test
(make-test-proc = (list get-val (lambda () 7))))
(display "test (= val 7): ") (display (exec-test))
Python
# Execution procedures as closuresdef make_assign_proc(get_reg, set_reg, value_fn):
def execute():
set_reg(value_fn())
return'done'return execute
def make_test_proc(op_fn, arg_fns):
def execute():
args = [f() for f in arg_fns]
return op_fn(*args)
return execute
# Simulate: assign val = 3 + 4
val = [0] # mutable container
set_val = lambda v: val.__setitem__(0, v)
get_val = lambda: val[0]
exec_assign = make_assign_proc(get_val, set_val, lambda: 3 + 4)
exec_assign()
print(f"val after assign: {val[0]}")
# Simulate: test (= val 7)
exec_test = make_test_proc(lambda a, b: a == b, [get_val, lambda: 7])
print(f"test (= val 7): {exec_test()}")
A complete mini-simulator
Putting it together: a machine that computes factorial using registers, a stack, and a controller sequence. The simulator steps through instructions one at a time, dispatching on instruction type.
Scheme
; Mini factorial machine using explicit registers.; Registers: n, val, continue. Stack for saving state.
(define n 5)
(define val 1)
(define continue 'done)
(define stack '())
(define (push! v) (set! stack (cons v stack)))
(define (pop!) (let ((top (car stack)))
(set! stack (cdr stack)) top))
; Factorial controller โ iterative version
(define (run-fact-machine)
(set! val 1)
(let loop ()
(cond ((= n 0)
(display "fact result: ") (display val))
(else
(set! val (* val n))
(set! n (- n 1))
(loop)))))
(run-fact-machine)
Python
# Mini factorial machine with explicit registers
n = 5
val = 1
stack = []
def run_fact_machine():
global n, val
val = 1while n != 0:
val = val * n
n = n - 1print(f"fact result: {val}")
run_fact_machine()
Monitoring machine performance
Instrumenting the machine: count how many instructions execute, how deep the stack grows. These metrics reveal the complexity of the computation — iterative processes use constant stack depth, recursive ones grow linearly.
Scheme
; Instrumented factorial: count steps and max stack depth.
(define (fact-instrumented n)
(let ((steps 0)
(stack-depth 0)
(max-depth 0)
(val 1))
; Iterative: no stack growth
(let loop ((i n))
(set! steps (+ steps 1))
(cond ((= i 0)
(display "n=") (display n)
(display " result=") (display val)
(display " steps=") (display steps)
(display " max-stack=") (display max-depth)
(newline))
(else
(set! val (* val i))
(loop (- i 1)))))))
(fact-instrumented 5)
(fact-instrumented 10)
(fact-instrumented 20)
; Recursive version would show stack growth:
(define (fact-recursive-instrumented n)
(let ((steps 0) (max-depth 0))
(define (helper i depth)
(set! steps (+ steps 1))
(if (> depth max-depth) (set! max-depth depth))
(if (= i 0)
1
(* i (helper (- i 1) (+ depth 1)))))
(let ((result (helper n 0)))
(display "recursive n=") (display n)
(display " result=") (display result)
(display " steps=") (display steps)
(display " max-stack=") (display max-depth)
(newline))))
(fact-recursive-instrumented 5)
(fact-recursive-instrumented 10)
Python
# Instrumented factorial: iterative vs recursivedef fact_iterative(n):
steps, val = 0, 1for i inrange(n, 0, -1):
steps += 1
val *= i
print(f"iterative n={n} result={val} steps={steps} max_stack=0")
def fact_recursive(n):
steps = [0]
max_depth = [0]
def helper(i, depth):
steps[0] += 1
max_depth[0] = max(max_depth[0], depth)
if i == 0:
return1return i * helper(i - 1, depth + 1)
result = helper(n, 0)
print(f"recursive n={n} result={result} steps={steps[0]} max_stack={max_depth[0]}")
fact_iterative(5)
fact_iterative(10)
fact_recursive(5)
fact_recursive(10)
Notation reference
Scheme / Register Machine
Python
Meaning
(assign reg (op f) ...)
reg = f(...)
Assign result of operation to register
(test (op =) (reg n) (const 0))
flag = (n == 0)
Set condition flag
(branch (label done))
if flag: goto done
Conditional jump
(goto (label start))
goto start
Unconditional jump
(save reg) / (restore reg)
stack.push(reg) / reg = stack.pop()
Stack operations
(perform (op display) ...)
print(...)
Side effect (no assignment)
Translation notes
The register machine language is assembly-level: each instruction names an operation, its source registers, and its destination. The assembler closes over the machine state so that each instruction becomes a zero-argument procedure. This is the same trick interpreters use — compile once, execute many times. Python's equivalent is compile() turning source into bytecode objects.
Neighbors
Other reading pages
SICP Ch.18 — Register Machines (the design language this chapter simulates)
Emulator