Registers make every changing value explicit.
A machine state can be represented as a fixed collection of register values, while one transition computes the next state.
What information must be present to resume a computation?
- Represent registers as one explicit state value
- Separate a single transition from repeated execution
- Read a final state instead of only a final number
The state list holds a, b, and the number of completed transitions. step performs one Euclidean reduction and returns a new list without hiding any changing value.
run does not contain the arithmetic rule itself. It asks whether b is zero and otherwise repeats step, so the transition rule and the controller remain separate.
(begin
(define (step state)
(let ((a (car state))
(b (cadr state))
(steps (caddr state)))
(if (= b 0)
state
(list b (remainder a b) (+ steps 1)))))
(define (run state)
(if (= (cadr state) 0)
state
(run (step state))))
(run (list 206 40 0)))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns the final register state (2 0 4). The gcd is 2 and four transitions completed.
Follow each step application and watch the old b become the next a. The state value records the transition count alongside the arithmetic registers.
Change the program before you read the hint.
Run the machine with a equal to 30 and b equal to 18. Predict the complete final state, including the transition count.
Show one hint
Write one new list after each remainder operation.