Calls, closures, objects, and memory management need representations that outlive a single arithmetic instruction.
By the end: Distinguish operand stacks, call frames, reachable heap objects, and runtime specialization.
A frame records one invocation
A call frame can hold return information, local values, saved registers, and other state according to the implementation and ABI. Recursive calls need distinct invocation state even though they execute the same function body. An operand stack for bytecode evaluation is a different concept, though some VMs store both within related structures.
Objects or captured bindings that outlive a call cannot rely on discarded storage unless the implementation preserves an equivalent representation. Escape analysis can sometimes prove that an allocation need not live on the heap, or eliminate the allocation entirely. Source syntax alone does not force every object into one storage region.
Follow invocation state through a return
Consider a separate pseudocode function that computes factorial by returning one for zero and otherwise multiplying n by factorial of n minus one. Calling it with three creates invocations for three, two, one, and zero. Each invocation needs its own n and enough information to continue after its recursive call. The function body has one source definition, but four invocations are active at the deepest point. Sharing one mutable slot for every invocation's n would lose the earlier values before their multiplications finish.
Trace the returns before deciding where the implementation stores anything. The zero invocation returns one. The invocation with n equal to one multiplies one by that result and returns one. The next invocation multiplies two by one and returns two. The original invocation multiplies three by two and returns six. At the deepest point, the pending continuations require multiplications by one, two, and three. This is a description of required behavior, not a requirement that every implementation allocate four identical physical frames.
Four invocations, three pending multiplications
Invocation at deepest point
Retained n
Continuation after child returns
factorial(3)
3
Multiply child result by 3; return
factorial(2)
2
Multiply child result by 2; return
factorial(1)
1
Multiply child result by 1; return
factorial(0)
0
Return 1 immediately
Separate pseudocode. Rows describe logical invocation state, not physical frame sizes. Returns produce 1, 1, 2, then 6.
A conventional call frame gives one invocation a place for its continuation and retained state. A return address identifies where execution resumes, while saved values let the caller continue correctly. The ABI decides which values a caller must preserve around a call and which registers a callee must restore. Some arguments and locals can stay in registers rather than frame slots. Optimizations can inline calls or omit a frame pointer, so a source function does not imply one fixed memory layout on every target.
Compare this invocation state with the SmallExpr operand stack. During evaluation of 2 + 3 * 4, that stack temporarily contains two, three, and four before multiplication reduces the last two entries to twelve. Those entries are operands of unfinished arithmetic operations, not three function invocations. SmallExpr has no call instruction and creates no recursive source-level calls. A larger VM may put operand areas inside call frames, but that arrangement joins two responsibilities without making their meanings identical. Follow what each stored item is needed for.
Now change the pseudocode factorial into an accumulator version whose recursive call is the final action. There is no pending multiplication after that call returns because the next accumulator already contains the product. A language implementation with an appropriate tail-call strategy may reuse invocation storage. This contrasts with the original definition, where multiplication remains after the recursive call. Whether reuse is guaranteed depends on the language and implementation. Tail position is a property of the continuation, not simply the presence of recursion or a short function body.
Use the two traces below to practice identifying required state. At the deepest original call, list each pending multiplication and the invocation that owns it. Then cross out the zero invocation after its return and check which continuation becomes active. For the accumulator version, follow the pairs of argument values until the result reaches six. Explain why the same result does not establish identical stack usage. This paper trace tests lifetime reasoning without suggesting that the expression editor accepts functions or measures native stack consumption.
Move multiplication before the recursive call
Step
Original factorial return
Accumulator call arguments
Start
Wait for factorial(2)
n = 3, acc = 1
Next
Wait for factorial(1)
n = 2, acc = 3
Next
Wait for factorial(0)
n = 1, acc = 6
Base case
Return 1, then multiply on return
n = 0, acc = 6; return 6
Accumulator rule: when n is nonzero, call the function with n − 1 and acc × n as the final action. Equal results do not guarantee equal physical stack use.
Reachability is not usefulness
A tracing garbage collector starts from roots such as active references in registers, stacks, and globals, then follows references to mark reachable objects. An unreachable cycle can be reclaimed by tracing even though its members refer to one another. Reference counting without cycle handling can retain such a cycle.
A reachable object can still be useless to the program if an unwanted reference keeps it alive. Garbage collection does not prove absence of memory leaks in that broader sense, and it does not determine the correct time to release every external resource. Files, locks, and native resources may need explicit lifecycle rules.
Preserve captured bindings after a call ends
Suppose a pseudocode factory creates a mutable count initialized to zero and returns two closures. One increments count; the other reads it. Under the assumed shared-binding capture rule, both closures must refer to the same count. Calling the increment closure once and then the read closure returns one. Copying zero independently into each closure would instead leave the reader at zero. Name resolution identifies the binding that both uses mean, while runtime representation must preserve that binding's changing state after the factory returns.
A possible representation allocates an environment object containing one mutable cell and puts a reference to that environment in each closure. Each closure also needs an entry point for its executable behavior. Returning the closures then preserves access to the environment without preserving every local value from the factory invocation. The cell is shared because the language behavior requires shared updates in this example. A language that captures immutable values, or explicitly requests a copy, can require a different representation and different observable results.
Two closures share one captured cell
Arrows are strong references. The environment contains the one count cell. Nodes and distances are schematic, not object sizes or addresses. Both root paths survive the factory return.
Compare a local calculation whose object never escapes its creating invocation. If analysis proves that no later computation can observe the object's identity or access its storage after return, the compiler may use local storage or remove the object and retain only its fields. This is escape analysis followed by a possible representation change. The proof must consider returned references and references stored elsewhere. Merely observing that the object does not escape on one test input is not a static proof that it never escapes on any permitted path.
The root set connects this lifetime question to tracing collection. While both returned closures remain in a global variable, that global can reach the closures, their environment, and the count cell. When the program drops one closure, the other still preserves a path to the shared state. When it drops both and no other references exist, the environment becomes unreachable under our graph assumptions. The end of the factory's call and the end of the environment's reachability therefore occur at different events in this execution.
Draw those events rather than guessing a storage region from source syntax. Start with two root references to the closures and arrows from each closure to one environment. Remove the first root and mark everything still reachable from the remaining root. The cell must remain available for the reader even if no further increment will occur. Then remove the second root and repeat the traversal. This exercise separates required lifetime from usefulness, since a retained closure can keep state alive even when the programmer never calls it again.
A dangling reference would arise if the implementation returned access to a cell in discarded invocation storage without preserving an equivalent cell elsewhere. A managed implementation must avoid that error under its supported semantics; another language may reject the capture, copy a value, or require explicit lifetime discipline. The heap illustration here models ordinary strong references only. It does not implement closures, escape analysis, or a collector. Its purpose is to make the representation obligation testable by tracing exactly which reference permits each later read.
A returned environment can outlive its creating call
Event
Remaining strong paths
Count cell needed?
Factory returns
Roots → increment and read closures → environment
Yes; both closures share it
Increment called once
Same paths; count changes from 0 to 1
Yes; reader must observe 1
Increment root removed
Read root → read closure → environment
Yes; reader still has access
Read root also removed
No paths, assuming no other references
Unreachable under this graph model
Rows are ordered execution events, not equal time intervals. Dropping a reference is distinct from performing a collection.
Work through the mechanism
Arrows represent references. Ordinary tracing from the root retains A and B; the unreachable C–D cycle is eligible for collection. Object positions and box sizes do not encode address or allocation size.
Representation
Lifetime question
Call frame
Which invocation still needs this state?
Captured environment
Which closures can still access it?
Heap object
Which roots can reach it?
External resource
Which lifecycle rule releases it?
The heap drawing is a conceptual reachability example, not a collector implementation.
Compute reachability as a graph traversal
Take the heap drawing as a snapshot with fixed roots and references. The root points to A, and A points to B. Separately, C points to D and D points back to C. Start with an empty marked set and a worklist containing the root's referent A. Mark A, inspect its reference, and schedule B. Mark B and find no further references. The worklist becomes empty with exactly A and B marked. Neither cycle member entered the traversal.
A visited mark prevents repeated work when reachable objects also contain cycles. If B pointed back to A, inspecting B would encounter an already marked object and would not schedule A again. That change would preserve the marked set rather than cause infinite traversal. After marking, a simple sweep examines the allocated objects and reclaims unmarked ones. In this four-object snapshot, C and D are eligible while A and B remain. The arithmetic counts objects only; their memory sizes need not be equal in a real heap.
Trace from roots before sweeping
Completed action
Pending worklist
Marked objects
Schedule root referent
A
None
Mark A; inspect A → B
B
A
Mark B; no outgoing edge
Empty
A, B
Sweep allocated A, B, C, D
Empty
Keep A, B; C, D eligible
Original fixed graph: root → A → B and C ↔ D. Worklist entries and marked objects are object identities, not bytes or elapsed time.
Plain reference counting asks a different local question. In the original snapshot, C has an incoming reference from D, and D has one from C. Removing all external paths to the pair does not lower either internal count to zero. A scheme that frees an object only when its count becomes zero cannot reclaim this pair through that rule alone. Tracing instead asks whether a path exists from a root. Some reference-counted systems add cycle handling, so the counterexample describes the plain rule rather than every implementation that maintains reference counts.
To see why root accuracy matters, add a root reference directly to D. Now the traversal must mark D and then C, so all four objects survive. If a real collector omitted that live root, it might reclaim storage that execution still needs. If it retained an obsolete root, it might keep objects longer than necessary. Native code and a collector therefore need an agreement about how references appear in registers and frames at collection points. Optimized storage locations are part of that agreement, not something a collector can infer from source variable names alone.
Try two graph edits separately. First remove A's reference to B while keeping the root to A. B becomes unreachable, so the marked set becomes just A. Restore the original edge, then add a reference from B to C. This time tracing reaches A, B, C, and D, despite the cycle. These outcomes depend on directed paths, not on the objects' positions or the lengths of the arrows. Predict the marked set before consulting the comparison table, and justify every retained object with a complete path from a root.
This snapshot traversal avoids complications that would require more machinery. A program that changes references concurrently with tracing can create paths after the collector has already inspected an object. Such collectors need coordination rules, often including barriers on relevant memory operations. Weak references and finalization also require policies beyond the ordinary strong-edge model. Those omissions define the snapshot reasoning's domain. Keep the proof about this fixed graph separate from claims about pause times, collection frequency, or the behavior of a particular production runtime.
Check each graph edit from the original snapshot
Independent edit
Root paths
Marked set
No edit
root → A → B
A, B
Add B → A
The existing path now includes a cycle
A, B
Add root → D
root → D → C also exists
A, B, C, D
Remove A → B
Only root → A remains
A
Add B → C
root → A → B → C → D
A, B, C, D
Each row changes only the original graph, not the preceding row. Directed root paths determine reachability, not incoming-reference counts.
JIT specialization adds assumptions
A just-in-time compiler can use observed types or frequently taken paths to specialize code. It may insert guards that check the assumptions and fall back or deoptimize when they fail. Deoptimization must reconstruct a state consistent with the language’s execution model.
Warmup, compilation overhead, allocation behavior, and changing inputs can affect performance measurements. A fast steady-state trace does not describe every workload. The SmallExpr VM is deliberately simpler: no heap, calls, collector, profile-guided specialization, or deoptimization is hidden behind its instruction counter.
Audit a specialized path and its fallback
Consider a separate dynamic-language pseudocode operation that adds two values. Assume integers and strings are both valid inputs, with arithmetic for two integers and concatenation for two strings. Repeated integer inputs may motivate a JIT compiler to generate a path for integers. Observed inputs justify choosing a promising optimization to attempt, but they do not prove that later inputs are integers. The implementation still owes the language's specified behavior when another permitted pair arrives. A profile is evidence about past execution, not a changed language contract.
A guarded fast path checks the necessary representation conditions before using specialized instructions. If both values have the expected integer representation, it performs the arithmetic under the language's overflow policy. If the guard fails, it transfers to code that handles the general operation or another valid specialization. The guard must precede operations that rely on its assumption. Checking a value after interpreting its bits as an incompatible object layout would be too late. This is a dynamic check during execution, unlike a static type proof covering all accepted inputs.
A guard separates two execution paths
Separate dynamic-language pseudocode. Integer addition and string concatenation are assumed semantics here. Paths are control flow, not probabilities or measured durations.
Deoptimization requires more than choosing another instruction address. Suppose optimized code has kept a local only in a register and replaced another local by a known constant. A less-specialized interpreter may expect both locals in its frame representation. Metadata can tell the runtime to reconstruct the first from the register and the second from the constant. The resumed state must correspond to a valid point in the original execution. Effects already performed must not run twice merely because control changed engines, and required effects must not disappear.
For a concrete checkpoint, assume the original state expects locals a equal to four and b equal to five, with the next action computing their sum. Optimized code holds a in register R and knows b as the constant five. A reconstruction description can populate the interpreter's a slot from R and its b slot from five, then resume before addition. Resuming after addition without reconstructing its result would be invalid. This is an invented state-mapping example, not metadata emitted by SmallExpr or a claim about any particular JIT format.
Follow the guard comparison with one integer pair and one string pair. Four and five take the arithmetic path and produce nine under our assumed small-value example. The strings ab and cd fail the integer guard and reach general concatenation, producing abcd. Ask what evidence would justify removing the guard entirely. A proof that the program point receives only integers would differ from a long integer-only trace. Neither the current SmallExpr bindings nor its instruction counter supplies such a proof for this separate dynamic language.
Finally separate execution cost from counts in the diagrams. Compilation consumes time before any specialized instruction executes. Guard failures, state reconstruction, allocation, and collection can add work outside a short arithmetic trace. To compare two runtime strategies, state whether measurement includes startup and warmup, hold the input workload fixed, and verify matching results and effects. The lesson's expression VM reports abstract instructions only. Its bounded arithmetic evaluator, ASCII token rules, and lack of calls or heap objects do not secretly provide a benchmark for these runtime mechanisms.
Reconstruct a valid less-specialized state
Original state requirement
Optimized representation
Reconstruction
Local a = 4
Register R contains 4
Copy R into interpreter slot a
Local b = 5
Known constant 5; no slot needed
Populate interpreter slot b with 5
Next action: add a and b
Checkpoint before addition
Resume before addition; obtain 9
Already performed effects
Must remain performed exactly as required
Do not replay them during reconstruction
Invented metadata obligations, not a SmallExpr feature or real JIT output. Reconstructing operands alone would not justify resuming after their addition.
Exercises
An unreachable cycle
Objects C and D refer to each other, but no program root can reach either. Can a tracing collector reclaim them?
Hint
Tracing starts at roots, not at every nonzero reference count.
Worked answer
Tracing follows paths from roots; the isolated cycle is unreachable.
Object group
Root-reachable?
Ordinary tracing result
A and its child B
Yes
Retain
Cycle C ↔ D
No
Eligible for collection
The diagram marks reachability rather than whether an object is useful.
Yes, under the ordinary tracing model and absent special retention mechanisms. The cycle does not make itself reachable from a root. Plain reference counting can retain it because each object still has an incoming reference from the other. Different collectors provide different additional mechanisms.
A JIT guard fails
Specialized code assumes a value has one runtime type, but a later input has another. Is continuing with the old unchecked representation correct?
Hint
The optimization depended on an assumption that no longer holds.
Worked answer
Situation
Required consideration
Assumption holds
Specialized path may run
Assumption fails
Safe alternate handling
Deoptimization
Reconstruct valid program state
The exact mechanism is implementation-dependent.
Not generally. A valid implementation must guard, dispatch, invalidate, or otherwise handle the changed condition according to its design. If it deoptimizes, it must reconstruct an appropriate less-specialized state. The existence of a fast path does not remove the semantic obligation on other inputs.
Sources and further reading
The explanations, examples, and worked answers are complete without these optional links. The sources describe specific implementations and language contracts, not one universal compiler pipeline. SmallExpr and the later pseudocode models are constructed teaching examples. Source notes identify the selected material reviewed; this is not an exhaustive compiler survey, production conformance test, or independent specialist review.
Selected overview and register-allocation material describing instruction selection, target constraints, liveness, and native-code generation. The storage lab is not an implementation of LLVM’s allocator. The reviewed register-allocation example has inconsistent def/use prose; the lesson follows explicit assignment direction instead.