← Church Machine

Figure 6 — Self-Describing Stack Frames

The capability stack interleaves CALL frames (tag=0) and LAMBDA frames (tag=1). Each frame is self-describing: RETURN inspects the top-of-stack tag bit to determine the restoration path. CALL frames carry full CR/DR/flag state; LAMBDA frames carry only two machine-status registers.

Capability Stack grows downward ↓ STACK DEPTH tag=0 CALL Frame Return PC (caller's NIA) CR0-CR7 (8 Context Registers) DR0-DR15 (16 Data Registers) Flags + lambdaActive + lambdaReturnNIA CR15 (namespace root GT) ~30 words tag=1 LAMBDA Frame lambdaReturnNIA (saved PC) lambdaActive = true (flag) 2 words tag=0 CALL Frame Return PC CR0-CR7 DR0-DR15 Flags + lambdaActive + lambdaReturnNIA CR15 ~30 words tag=1 LAMBDA Frame lambdaReturnNIA lambdaActive = true 2 words ... (deeper frames) ... SP → RETURN Dispatch Logic RETURN lambdaActive == true? YES Fast Path NO Read tag bit from TOS frame tag = stack[SP].tag tag? inspect tag=0 CALL tag=1 LAMBDA 1 Restore CRs, DRs, Flags Full register set from stack frame 2 Restore LAMBDA State lambdaActive, lambdaReturnNIA from frame 3 mLoad Revalidation Re-check version, seal, bounds on restored CRs 4 CR15 ← Caller's C-List PC ← return address, SP ← SP + frameSize ✓ Done (3+ cyc) 1 Restore lambdaActive lambdaActive ← true 2 Restore lambdaReturnNIA SP ← SP + 2 ✓ Done (~1 cyc) No revalidation CRs/DRs unchanged Frame Tag Format (1 bit) tag=0 CALL Frame — Full State PC + 8 CRs + 16 DRs + flags + LAMBDA state + CR15 tag=1 LAMBDA Frame — Minimal lambdaReturnNIA + lambdaActive (2 words only) Nesting Scenario: LAMBDA inside CALL 1. CALL Foo 2. LAMBDA Bar 3. RETURN (←Bar) 4. RETURN (←Foo) Stack: CALL frame [0] LAMBDA state saved in frame (was false) Stack: CALL frame [0] lambdaActive=true (in machine status) Stack: CALL frame [0] lambdaActive check → fast return to Bar Stack: (empty) tag=0 → full pop CRs/DRs/flags restored CALL saves LAMBDA state in its stack frame. RETURN from LAMBDA uses fast path (machine status). RETURN from CALL pops the full frame and restores LAMBDA state. Frame Size Comparison Frame Type Size RETURN Cost CALL Frame (tag=0) ~30 words 3+ cycles (revalidate) LAMBDA Frame (tag=1) 2 words ~1 cycle (no revalidation)
CALL frame (tag=0, full state)
LAMBDA frame (tag=1, minimal)
Machine-status registers
Design rationale