Expose the state. Expose the control. Preserve the return path.
Use eleven canonical lesson programs to reconnect register state, instruction selection, suspended work, compilation, selective preservation, lexical lookup, heap tracing, labels, controller execution, instrumentation, and shared subroutine linkage.
Can you account for every value, every next instruction, every saved continuation, and the explicit work counters of a finite machine run?
- Represent all changing register values in one state
- Select the next instruction with a program counter
- Save suspended multiplication on an explicit stack
- Compile expression data before a separate machine executes it
- Insert only the save and restore operations required by register contracts
- Fetch a variable through frame depth and binding offset
- Trace heap references from roots and classify unreachable allocations
- Map controller labels to numeric instruction positions
- Execute resolved assign, test, branch, goto, and halt instructions
- Count fetched instructions, pushes, and maximum stack depth
- Return from shared and nested subroutines through an explicit continuation
Registers and pc make changing values and the next instruction visible. The stack stores suspended work or return information that must survive another controller path.
Compilation, preservation contracts, lexical addresses, and label resolution move information from source structure into machine-ready instructions and indexes before execution.
Heap tracing and instrumentation expose different kinds of machine history: references reachable from roots, fetched instruction counts, total saves, and maximum live stack depth.
The subroutine program gives the same controller segment different return addresses through continue. A nested call saves the outer continuation before assigning an inner one, then restores it before returning to the original caller. These are finite controller observations, not a general calling convention or hardware profile.
(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
- —
Each program returns the first expected observation from its corresponding Chapter 5 lesson. The instrumentation program returns (6 27 4 4 0). The shared-subroutine program returns (16 (3 7) (0 1 2 9 10 3 4 5 6 9 10 7 8)).
Locate register-state transitions, pc changes, stack growth and shrinkage, compile calls, preservation decisions, lexical indexes, heap-child traversal, label positions, resolved controller fetches, instrumentation counters, continue assignments, goto-register returns, and save/restore around a nested subroutine. The bounded trace describes only the selected run.
Eleven checks for reasoning about machines
What information must be present to resume a computation?
Answer 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.
How can one transition procedure represent several machine instructions?
Answer Instruction 0 tests b and either enters the remainder cycle or jumps to halt at pc 5. The other instructions move values through temp before returning control to the test.
What information does a machine save while it descends into a recursive problem?
Answer During return, each transition pops one saved multiplier and updates value. An empty stack means no suspended multiplication remains, so value is the final answer.
How does an expression tree become a linear instruction sequence?
Answer execute pushes constants. An arithmetic instruction pops the right and left values, combines them, and pushes the result. When no code remains, the stack top is the program value.
When does a compiler need to preserve a register between two instruction sequences?
Answer The wrapped first sequence now needs the register in order to save it and no longer exposes that register as modified after restore. If either side of the conflict is absent, composition emits no stack instructions.
What environment knowledge can compilation move out of runtime lookup?
Answer find-address performs the name search against the compiler environment, whose frames contain variable names. Once it produces (1 0) for x, the runtime can use that address to fetch 42 from matching value frames. The example makes the compiler and machine agree on one frame layout.
Which allocations must a storage manager preserve when references form a graph?
Answer The second heap contains a cycle from a through b and c back to a. contains? stops the revisit, while mark-roots starts a second traversal from x. unreachable then scans every allocation and classifies only dead outside the marked set. This lesson models tracing and classification, not memory reclamation itself.
How can a controller use readable labels before the machine needs numeric positions?
Answer assemble skips label symbols and asks resolve to replace only branch and goto targets. Ordinary instructions remain unchanged. The returned sequence is assembled controller data with numeric targets; this lesson does not execute that sequence or prove a complete machine assembler.
How does one numeric program counter coordinate assignment, testing, and control transfer?
Answer The first program executes the complete controller from n equal to 2 and leaves product equal to 2. The second records pc, n, product, and flag after every non-halt instruction while starting from n equal to 1. Both runs have a 40-step guard. This executor models only its listed instruction shapes and does not implement an arbitrary assembler, stack, or machine language.
What can controller-level counters reveal that the final register values alone cannot?
Answer With n equal to 1, the branch jumps directly to the base assignment and reaches halt after five fetched instructions with no stack use. With n equal to 3, the controller saves continue and n at two recursive levels, so it performs four pushes, reaches depth four, and fetches 27 instructions before halting with value 6 and an empty stack. These numbers describe this exact controller, input, and counting convention. They are not elapsed time, CPU instructions, allocation cost, or a general profiler.
How does a register machine return from shared and nested controller subroutines without duplicating their instructions?
Answer 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.