validate

func BodyIsFrameReleasable ¶

func BodyIsFrameReleasable(proc ValidatedBodyAndParams, selfSym *syntax.SyntaxSymbol, env *environment.EnvironmentFrame) bool

BodyIsFrameReleasable reports whether proc's activation frame may be released to the pool at its tail calls (the OpReleaseEnvFrame optimization — fib-shaped general tail recursion). Unlike OpSelfTailCall it does NOT rebind in place or hardcode a jump: it releases the dead frame and performs a normal apply (which re-resolves the callee). So it needs neither the define's stability nor a self-tail call — only that the body can never expose its frame to a continuation:

• no capture operator in the body (no call/cc &c.),
• no escaping closure, and
• every callee is the self name or a capture-safe, non-rebindable primitive (bodyCalleesAllCaptureSafe) — a callee that could capture would pin the frame.

This is a conservative, per-body approximation of the interprocedural classifier (ClassifyFrameReclaim): it covers self-recursion over capture-safe primitives (fib, tak) but refuses a tail call to another user-defined function (mutual recursion), which the full call graph would admit. Sound either way; the call-graph precision is a later refinement.

func BodyIsSelfTailReusable ¶

func BodyIsSelfTailReusable(
	proc ValidatedBodyAndParams,
	selfSym *syntax.SyntaxSymbol,
	env *environment.EnvironmentFrame,
) bool

BodyIsSelfTailReusable is the compiler entry point: it builds the production capture-operator identity test from env (hygiene-correct: a locally-shadowed call/cc is not the primitive) and runs the self-tail-reuse safety predicate. selfSym is the closure's own binder identifier, or nil for an anonymous body.

NOTE: this is the IN-BODY safety half. The caller must additionally ensure the self BINDING is immutable against cross-unit redefinition — for a top-level define that means IsStable() at the emit site; for a lexical named-let loop the in-body ¬set! this predicate checks is the whole story.

func CallbackIsCaptureSafe ¶

func CallbackIsCaptureSafe(arg ValidatedExpr, env *environment.EnvironmentFrame) bool

CallbackIsCaptureSafe reports whether a callback ARGUMENT at a call site is provably capture-safe — the D2 proof the inline-HOF dispatch (callback specialization Strategy A) requires before inlining a curated tail HOF's reclaiming loop with this callback substituted. Inlining a capturing callback into a frame-reclaiming loop would be a use-after-release, so this answers true only with positive proof; everything uncertain is false (the soundness asymmetry — a false negative merely forgoes the optimization).

Two positive forms:

• a symbol resolving to a binding that is IsCaptureSafe() AND IsStable() — the same gate bodyCalleesAllCaptureSafe applies to a loop's callees: capture-safe (cannot invoke a Scheme procedure, so cannot capture) and stable (not rebindable to something that can), or
• a lambda literal whose body ProcedureBodyIsCaptureSafe proves cannot capture the caller's continuation. The self symbol is nil — an argument callback is anonymous, so no callee is exempted as a self-recursive tail call.

Anything else — a procedure-invoking, unbound, or rebindable symbol; a lambda that runs a capture operator or a procedure-invoking callee; or a computed operator expression (neither symbol nor lambda) — returns false.

func ClassifyFrameReclaim ¶

func ClassifyFrameReclaim(
	unit []ValidatedExpr,
	env *environment.EnvironmentFrame,
) map[ScopedBindingKey]bool

ClassifyFrameReclaim returns, for every top-level function define in unit, whether its frame is reclaimable at its tail calls. It is the exported entry point over the Layer-B/C internals: build the call graph, run the greatest-fixpoint mayCapture, and project to a per-identity verdict map. The verdict is conservative (any uncertainty ⇒ not reclaimable).

The map is keyed by ScopedBindingKey — the define name's (Sym.Key, scope fingerprint) — NOT by Sym.Key alone, and its value is the reclaimable bool. Two hygiene-distinct top-level binders of one name (a macro-introduced define and a user define) carry different scope sets, so each gets its own verdict instead of sharing one. The read side (compilation.frameReuseForDefine) looks up the identity of the very define it is compiling, an exact match against the key built from that same define here, so reference→verdict resolution cannot diverge. The identity is value-stable — it survives env.Copy and cross-library sharing — unlike the *Binding pointer a scope-keyed global slot happens to mint. A name-oriented consumer reads the define name back off the key (id.Key).

Same-unit-define immutability is the callee node's rebindStable (d.StableInUnit ∧ the namespace's ImmutableTopLevel), computed thread-locally from the ValidatedDefine and an engine-construction-time flag — never read from the callee's *Binding (the T1.5 decoupling). The tier-(a) vs tier-(b) distinction is therefore a property of WHAT is passed: defines whose StableInUnit is unset, or a namespace without immutable top-level, yield mutable same-unit edges (tier-(a)); StableInUnit defines under immutable top-level yield immutable edges (tier-(b)).

env is still consulted, but only for binding-side FACTS about non-same-unit callees: capture-operator identity (makeIsCaptureOp) and the capture-safe-primitive gate (Binding.IsCaptureSafe ∧ IsStable). Those reads are fail-safe on a nil/unstamped binding (⇒ unsafe), so an un-stamped env costs only primitive-callee precision, never soundness — though a measurement still wants a positive control.

func ForEachOpaqueLiveSymbol ¶ added in v1.20.0

func ForEachOpaqueLiveSymbol(expr ValidatedExpr, fn func(*syntax.SyntaxSymbol)) bool

ForEachOpaqueLiveSymbol calls fn for every symbol in a LIVE position of expr's concealed syntax, and reports whether expr was opaque at all. It does NOT descend into validated children: a caller that already walks the tree (every caller so far does) recurses itself and asks this at each node.

It is exported so that pkg/machine/compilation's boxing pass can ask the question this package already answers, instead of concluding "nothing in there" from WalkSubExprs reporting an opaque node childless. That blindness is what left a `set!` inside a quasiquote or a cond-expand invisible to the ref index, so a captured local was never boxed and the closure kept a stale copy — (let ((n 0)) (let ((f (lambda () n))) `(,(set! n 99)) f)) returned 0.

WHY NOT EXPORT forEachRawSymbol. Its second parameter is the entry depth, and the depth differs by SHAPE: a quasiquote Template has already been stepped into (quasiDepthTemplate), a passthrough form has not (quasiDepthCode). Exporting the raw walker moves that choice to the call site, where getting it wrong under-marks silently — the exact failure mode this file exists to prevent. The classification stays here, with the switch that defines it.

The boolean and fn answer DIFFERENT questions, per opaqueRawSyntax's contract: an opaque node with a nil payload calls fn zero times and still reports true, because a nil payload is when we know least.

func InternalDefineFrameReleasable ¶ added in v1.19.1

func InternalDefineFrameReleasable(
	d *ValidatedDefine,
	body []ValidatedExpr,
	env *environment.EnvironmentFrame,
) bool

InternalDefineFrameReleasable is LetBindingFrameReleasable's twin for the OTHER spelling of a local recursive binding group: internal defines. R7RS §5.3.2 gives them letrec* semantics, but they are never rewritten into a ValidatedLet — they stay ValidatedDefine nodes compiled in the enclosing lambda's own frame — so the let-binding predicate never sees them, while the shape and the hazard are identical. body is the enclosing body sequence whose internal defines form the group; d must be one of them.

This is the spelling that occurs in practice: benchmarks/larceny/src alone carries 255 internal defines in compiler.scm and 32 in earley.scm, against zero explicit letrec forms in either corpus. Mutual recursion between two internal defines allocated a frame per iteration (2.0 measured) for exactly the reason the letrec form did — a call to a sibling resolves through env.GetBinding, finds nothing because the sibling is local, and refuses.

The co-induction, the uniform group answer, and the per-binding escape clause are LetBindingFrameReleasable's, unchanged; see there for why each is shaped that way. Only the seed differs (withInternalDefines rather than withLet).

MEMBERSHIP IS CHECKED, and that check is load-bearing rather than defensive hygiene. The group arrives from the compiler, which must supply the body that predeclared d — there are three such sites. If a caller ever passes a STALE enclosing body, an unrelated define sharing a sibling's name would be recorded as evidence for a call to a different procedure entirely, which is unsound. A stale body does not contain d, so refusing when d is absent converts that whole class of plumbing error into a forgone optimization.

func IsOpaqueSubtree ¶ added in v1.20.0

func IsOpaqueSubtree(expr ValidatedExpr) bool

IsOpaqueSubtree reports whether an expression is an opaque subtree — the boolean half of opaqueRawSyntax, without the payload.

It is exported because the classification is needed OUTSIDE this package and must not be re-derived there. pkg/machine/compilation's Pass 1 asks the same question for a different reason: an opaque subtree may hold an outer reference free-variable enumeration cannot name, so the closure keeps its static link. That is "not enumerable ⇒ retain"; this package's own consumer (bodyReferencesCaptureOperator) reads the same shapes as "not analysable ⇒ may capture".

Two justifications, one classification, and the frame-release gates depend on them agreeing: a closure whose template retains the lexical env pins the creating frame, and the only thing keeping the release gates off such a body is that the capture walk refuses it too. That agreement was previously an unenforced coincidence between this function and a hand-copy in compilation. Adding a third opaque shape to opaqueRawSyntax now moves both walks at once.

func LetBindingFrameReleasable ¶ added in v1.19.1

func LetBindingFrameReleasable(v *ValidatedLet, i int, env *environment.EnvironmentFrame) bool

LetBindingFrameReleasable reports whether the i-th binding's lambda may have its OWN activation frame released at its tail calls (OpReleaseEnvFrame) — the local analogue of BodyIsFrameReleasable, and the release-path sibling of LetBindingSelfTailReusable.

WHAT THIS COVERS THAT SELF-TAIL DOES NOT. A loop whose tail call is to a SIBLING binding rather than to itself: mutual local recursion, which has no depth-0 self call and so fails bodyIsSelfTailReusable's clause (4) outright. Measured at 2 env-frame allocations per iteration before this predicate existed. A loop whose self call sits inside a further let is NOT covered — that call is at depth > 0, where the reuse disposition is cleared on the let descent (compile_let.go), so no arming here can reach it.

THE CO-INDUCTION, AND WHY IT IS A GROUP PREDICATE. Clearing a call to sibling `o` rests on `o` not capturing, which is exactly the property being proven for `o`. The shadow set therefore seeds the WHOLE letrec group (withLet), and this function discharges the resulting assumption by verifying every lambda-bound member under that same seed. Verifying only the binding asked about would leave the assumption standing on itself. The group answer is uniform — one unsafe member refuses the whole group — which loses precision when an unrelated sibling is unsafe, and is the conservative direction.

Only a lambda init is ever assumed anything: withLet records evidence solely for lambda inits (letBindingLocal), so a sibling bound to a parameter or a computed value stays opaque and refuses at its call site. A sibling set! within the let is likewise already folded in as localBinding.mutated, so a name that can be rebound to a capturing procedure is never cleared.

TWO CHECKS BELOW ARE REDUNDANT TODAY, and are kept as explicit tightenings (they can withhold a verdict, never grant one — the subsystem's kill-don't-guard rule). Both survive mutation testing, so neither is load-bearing at present and a reader must not infer that it is:

• The InitsInScope precondition. The group seed is withLet's INIT scope, which for a plain let binds every name opaquely, so a sibling call already refuses there. The guard becomes load-bearing the moment that seed changes to the body scope.
• The group capture-operator scan. An INVOKED capture operator is also a call operator, and call/cc carries no CaptureSafe stamp, so the callee walk refuses it first. The scan is what would catch a capture reached other than by direct invocation, and it keeps this predicate's shape identical to bodyCannotCaptureCaller's.

PRECONDITION: v.Kind must be recursive (letrec family), or the bindings are not in scope in each other's inits and the group seed would describe outer bindings.

func LetBindingSelfTailReusable ¶

func LetBindingSelfTailReusable(v *ValidatedLet, i int, env *environment.EnvironmentFrame) (int, bool)

LetBindingSelfTailReusable reports the arity and eligibility of the i-th binding of a recursively-scoped let (letrec / letrec* / named-let) for in-place self-tail reuse — the local-binding analogue of selfTailForDefine. ok is true iff

• the binding's Init is a lambda whose body is self-tail-reusable on the binding name (BodyIsSelfTailReusable, i.e. the in-body facts AND bodyCalleesAllCaptureSafe), AND
• the binding name is immutable across the WHOLE let: never set! in any binding init or in the let body.

The second clause is the local immutability story. bodyIsSelfTailReusable only inspects the lambda's own body, but a sibling init or the let body could set! the name, which would make a hardcoded jump-to-pc=0 unsound. A lexical letrec binding cannot be mutated from outside the let, so set!-freedom within the let is sufficient (no IsStable() is needed, unlike a top-level define).

PRECONDITION: the caller must ensure v.Kind is recursive (letrec-family) so the lambda can see itself; in a plain let/let* the name is not in scope in the init.

func LetIsOrShaped ¶ added in v1.19.1

func LetIsOrShaped(v *ValidatedLet) (init ValidatedExpr, alt ValidatedExpr, ok bool)

LetIsOrShaped recognizes

(let ((t E)) (if t t B))

and returns E and B. This is what `or` expands to (bootstrap_macros.scm), one let per operand beyond the first, and it is the single most common macro-introduced environment frame in the tree: 340 occurrences across the stdlib and the larceny corpus, none of them written in any .scm file.

THE FRAME IS UNOBSERVABLE, which is what makes removing it a rewrite rather than an optimization with a side condition. `t` is bound only to be tested and returned, and OpBranchOnFalseValue reads the value register without clobbering it, so the value E already left there IS the consequent's value. The form compiles to E, a branch, and B — no slot, no OpPushEnv, and no reload.

Note what this does NOT require: nothing about E's type. An earlier design lowered `or` to (if E #t B), which is only valid when E yields a boolean and would have needed the primitive return-type annotation carried across the registry/validate layering. The register passthrough returns E's own value, so (or 5 1) is still 5 and the type question does not arise.

WHY THE ALTERNATIVE IS SCANNED. Lowering evaluates B in the enclosing frame instead of the let's, so a reference to `t` there would resolve to a different binding or to none. `or`'s temp is hygienic and cannot appear in B, but the same shape written by hand can, and (cond (test => f)) produces a sibling shape whose consequent consumes the value. Both are refused.

The scan matches by name AND binderScopes ⊆ refScopes — Flatt's rule, through the same syntax.ScopesCompatible the environment's resolveLocal uses, so it cannot drift from real resolution. Over-approximating in that direction is safe: a genuine reference necessarily carries the binder's name and satisfies the subset relation, so none is missed, while an unrelated same-name occurrence at a compatible scope merely costs the lowering. Refusing is always the free direction here — the frame stays, exactly as it does today.

The head positions need no such scan. Test and Conseq must BE this binding's symbol, and no form intervenes between the let and them that could rebind the name, so a match there is exact rather than approximate.

func ProcedureBodyIsCaptureSafe ¶

func ProcedureBodyIsCaptureSafe(proc ValidatedBodyAndParams, selfSym *syntax.SyntaxSymbol, env *environment.EnvironmentFrame) bool

ProcedureBodyIsCaptureSafe reports whether CALLING proc can never capture the caller's continuation — the property that lets the frame-reclaim classifier trust proc as a callee. It is exactly bodyCannotCaptureCaller (BodyIsFrameReleasable MINUS the escaping-closure check): a procedure that merely builds and returns a closure does not capture the caller's continuation when called, so it is safe as a callee even though its own frame is not releasable.

The compiler stamps a define's binding CaptureSafe from this verdict (compile_define.go), so a proven-safe Scheme procedure — stdlib (zero?, not) or a user helper — is trusted exactly like a capture-safe primitive, without a hand-maintained whitelist. Conservative on forward references: a callee not yet stamped reads IsCaptureSafe()==false, so proc is left unstamped (sound — a missed stamp only forgoes the optimization).

func UnitArityOf ¶ added in v1.20.0

func UnitArityOf(unit []ValidatedExpr) map[string]UnitArityInfo

UnitArityOf returns the arity of every top-level define in unit whose name the unit neither redefines nor mutates. Callers may trust each entry without re-checking a flag: an unstable name is absent rather than present-but-doubtful. Run it after validation, which is what stamps StableInUnit.

It answers the question Binding.Value() cannot for a same-unit define: the binding exists at compile time (that is what makes forward references resolve), but its closure is built by the emitted code at run time, so there is no callable to interrogate. The formals are the only compile-time evidence of that define's arity.

Gating on StableInUnit does two jobs, and the second is the non-obvious one.

The plain job: a name defined twice, or set! in unit, has no single arity, so there is nothing sound to record.

The load-bearing job: it is also what makes the string key safe. A symbol Key() drops hygiene, so two hygiene-distinct top-level bindings of one name collide here. binding_ref.go makes the parallel over-match safe for BindingRef by arguing it "can only forfeit an optimization, never wrongly apply one" — and that argument does NOT transfer to arity, where applying one h's arity to a hygiene-distinct h would be a false compile error on correct code. A collision means definedKeyCount[key] >= 2, which forfeits StableInUnit, so neither entry is recorded and the call site falls through unchecked. Do not relax this to last-definition-wins without first replacing the key with something hygiene-aware — and note a reference's scope set is a superset of its binder's, so a ScopeFingerprint cannot serve as that key.

func WalkBindingRefs ¶

func WalkBindingRefs(
	expr ValidatedExpr,
	visit func(sym *syntax.SyntaxSymbol, role RefRole, depth int),
)

WalkBindingRefs walks expr recursively, calling visit for every *syntax.SyntaxSymbol reference encountered, with its role and closure-nesting depth.

depth is the number of escaping closure boundaries crossed (0 = same closure as expr). Immediately-applied lambdas (ValidatedLambda or ValidatedCaseLambda as the Proc of a ValidatedCall or ValidatedApply) do NOT increment depth, since the closure does not escape.

ValidatedSetBang emits a synthetic RefSetBangTarget visit for its target name, then recurses into its value expression as a normal walk (the value's symbol references appear as RefInBody at the same depth).

There is no closure-body RefRole; "is this inside a closure?" is the depth > 0 predicate. (RoleClosureBody is a ChildRole, consumed internally by walkBindingRefsAt to bump depth.)

Role tagging is shallow: RefInCallProc and RefSetBangTarget are reported only on direct symbol children of the surrounding form. A symbol nested inside a non-leaf call-proc child — for example, the inner `f` and `g` in `((if c f g) x)`, or the inner symbols of `((f x) y)` — is reported as RefInBody, not RefInCallProc. The role describes the slot the symbol IS, not the slot of any enclosing non-symbol expression.

func WalkSubExprs ¶

func WalkSubExprs(expr ValidatedExpr, fn func(child ValidatedExpr, role ChildRole))

WalkSubExprs calls fn for every direct sub-expression of expr, reporting each child's structural role:

• RoleCallProc: the operator of ValidatedCall and ValidatedApply
• RoleClosureBody: body of ValidatedLambda, ValidatedCaseLambda clause, or ValidatedDefine (function form)
• RoleNormal: everything else (arguments, inits, branches, sequence bodies)

ValidatedSetBang: walks only the value expression (RoleNormal). The set! target is mutation (tracked by Mutable), not a reference.

ValidatedSymbol has no children — fn is not called. The caller handles symbols directly before calling WalkSubExprs.