Expose the state. Assemble the control. Preserve the graph and call boundary.
Use twenty-three canonical programs to reconnect register state, pc control, explicit stacks, labels and instruction procedures, operation and storage abstraction, performance counters, vector memory and copying collection, compiler targets and linkages, compiled expression and combination order, recursive compiled returns, the explicit-control evaluator, and cross-representation procedure calls.
Can you account for every register value, next instruction, stack entry, heap pointer, compiled instruction, return address, and procedure representation during one finite 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
- Run eval and apply through explicit evaluator registers, labels, and stack protocol
- Call interpreted and compiled procedures through one shared environment and apply boundary
- Assemble constants, registers, labels, operations, stack actions, and control transfers in one machine language
- Keep one controller stable while swapping operation packages or register-bank storage
- State the read, write, stack, and pc contract of every supported instruction
- Generate one execution closure per instruction and reuse the procedure sequence
- Represent pairs as addresses into parallel car and cdr vectors
- Copy reachable cells while forwarding shared and cyclic references
- Dispatch compiler procedures by source form while honoring target and linkage
- Compile definitions, assignment, branches, closures, sequences, and applications to a separate IR
- Compile operator and operands in visible source order before one call boundary
- Read and execute a complete recursive compiled procedure listing
The register-machine lessons make state and control concrete. Registers hold current values, pc selects the next instruction, labels become numeric positions, and save/restore preserve values that must survive another path. Generated execution procedures move instruction-tag dispatch from the run loop into assembly.
Machine-design abstraction separates controller text from named operation packages and register storage. Instruction summaries state the data, stack, and control effects each tag promises, while instrumentation measures one finite controller rather than wall-clock or hardware cost.
Vector memory replaces represented host pairs with explicit addresses into parallel car and cdr vectors. The copying collector starts from roots, installs a forwarding entry before following fields, copies reachable cells into to-space, preserves shared tails and cycles, and leaves unreachable cells uncopied.
The compiler lessons separate source classification from execution. Specialized compilers receive target and linkage, compose conservative instruction-sequence contracts, and emit an IR whose executor no longer asks whether source data was an if, lambda, define, or application.
Combination compilation preserves operator-first and left-to-right operand order before crossing one apply boundary. The recursive factorial listing then makes procedure entry, saved continuation and argument, base case, after-call code, indirect return, instruction count, and maximum stack depth visible in one controller.
The explicit-control evaluator combines the machine mechanisms into eval-dispatch and apply-dispatch. It preserves unfinished application work, restores the caller continuation before a sequence’s final expression, and routes conditionals, assignments, definitions, primitive calls, and compound calls through named paths.
The compiled/evaluator interface keeps interpreted and compiled procedures as distinct tagged values while sharing lexical environments, ordered arguments, and apply dispatch. Every observation here belongs to the selected educational machine and finite input, not to every compiler or the packaged runtime’s hidden layout.
- Output
- —
- Value
- —
- Diagnostic
- —
Each program returns the first expected observation from its corresponding Chapter 5 lesson. Representative new observations include a Euclid machine ending at 2 after 33 instructions, a three-cell vector-memory list rooted at (ptr 2), copying collection reducing five allocated cells to three live cells, compiled core forms returning (18 large 15), and a fifteen-instruction recursive factorial controller returning 120 after 66 fetched instructions with maximum stack depth 10.
Locate register writes, pc changes, flag decisions, stack growth and shrinkage, label resolution, generated execution closures, operation-package lookup, vector addresses, forwarding writes, compiler dispatch, target and linkage statements, IR execution, operator and operand order, recursive return transfers, evaluator dispatch, and cross-representation apply paths. The execution trace records the exact selected runs under fixed runtime limits.
Twenty-three checks for machines, memory, compilers, and evaluators
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. The instruction executor handles assign, test, branch, goto, and halt over the resolved controller vector.
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 the lesson’s explicit linkage and one stack slot.
What changes when the evaluator is no longer expressed by host-language recursion and must preserve every continuation explicitly?
Answer Sequence evaluation is tail recursive because ev-sequence-last-exp restores the caller continuation before sending the final expression back to eval-dispatch. The two sum-iter runs therefore reach the same measured maximum evaluator-stack depth even though one performs more recursive calls. Separate controller paths preserve and restore the expression, environment, and continuation around if, set!, and define. The final guest program combines recursion, lexical closure state, mutation, and a clean halt. These observations describe this finite simulator and controller, not hardware timing or every possible evaluator implementation.
Which runtime agreements let interpreted and compiled procedures call across their representation boundary without pretending they are the same object?
Answer apply-any is the interface. An evaluator application reaches it after evaluating an operator and operands. A compiled call instruction reaches the same boundary after popping its procedure and arguments from the VM stack. The evaluator-to-compiled run records (compiled primitive): add-three enters compiled code, whose addition calls a primitive. The compiled-to-evaluator run records (interpreted primitive): compiled code calls double, whose interpreted body multiplies through a primitive. The lesson model records the exact cross-call contract for both directions.
What common protocol lets one simulator execute controllers for very different machines?
Answer evaluate-source gives one meaning to const, reg, label, and op forms. execute-one! selects an already assembled instruction and applies the rule for its tag. The Euclid controller uses assignment, testing, branching, a label goto, and perform. The subroutine controller additionally saves and restores a continuation and returns through a register target. The lesson register-machine simulator executes the designated instruction set over explicit machine state.
Which boundaries let a machine design change locally instead of rewriting its controller?
Answer The second program gives the same counter controller two register banks. One bank stores mutable association records and the other stores values in a vector behind a name-to-index table. The controller sends read and write messages only. Equal observations show that the finite client contract survives the storage change.
What must a reader know about one instruction before reasoning about a complete controller?
Answer The micro-controller then exercises the same reference against execution. It assigns constants and an operation result, saves and restores val, stores a label position in continue, jumps indirectly through that register, tests, takes a branch, performs an observable operation, and halts. The summary is the exact reference for this finite simulator subset.
Which work can the assembler perform once so the machine loop only fetches and invokes an execution procedure?
Answer The first program shows that even the assignment skipped by a true branch receives an execution procedure, because assembly covers controller structure rather than one run path. The factorial program assembles six closures once and uses the same sequence with two fresh machine instances. The closures still receive the current machine, so registers, stack, flag, pc, and operation package remain instance-specific.
How can car, cdr, mutation, and sharing survive when a pair is represented by an integer address rather than a host pair?
Answer The sharing example allocates one tail and stores its pointer in two different outer cells. Changing the tail car through that one pointer changes both decoded lists. This is the same graph question as host-pair sharing, but the identity is now an explicit address. The fixed vector capacity and monotonically advancing free pointer remain visible limitations until a storage manager reclaims or copies live cells.
How can a collector compact live storage without duplicating shared objects or looping forever through a cycle?
Answer The first heap has five allocated cells but only three are reachable from the two roots. The copied left and right cells point to one copied shared tail, while both garbage cells retain false forwarding entries. The second heap contains a self-cycle; copying the cdr reaches the old pointer again and immediately reuses the already installed new pointer. This finite program performs one explicit collection within a fixed semispace capacity.
Which compiler decisions depend on source syntax, and which depend on the requested target register and linkage?
Answer Instruction sequences carry statements plus conservative needs and modifies sets. append-sequences combines those contracts while preserving order. The conditional example shows labels and linkage around recursively compiled predicate and branches. The lambda compiler recursively compiles its body and stores the resulting instruction data in a represented compiled procedure. This educational instruction set models the displayed SICP compiler structure with a generic apply-procedure operation.
What source-language decisions disappear from the execution loop after compilation?
Answer run-code dispatches on compiled instruction tags after compile-expression has classified the source forms. A compiled procedure extends the lexical environment captured at closure construction and runs its body code on a fresh operand stack. This lesson VM executes global definition, captured local assignment, quotation, branching, closures, and primitive application through the listed instruction set.
Which ordering and representation contracts must compiled application code preserve?
Answer The second program broadens the call boundary. Evaluator code calls a compiled add-three closure, and compiled code calls an interpreted double procedure. Both paths pass an ordered argument list through apply-any, while dispatch-log retains the actual primitive, interpreted, and compiled tags. This records the calling convention used by the lesson.
What machine state replaces the implicit call stack of a recursive source procedure?
Answer The instrumented run starts with n = 5 and continue pointing to done. Six entries are observed, including n = 0. Five suspended calls each hold two stack values, so maximum stack depth is 10. All ten values are restored before halt. The 66 fetched instructions and exact controller listing measure this finite compiled procedure.