OctoInformBeta

OpenAI preprint, September 2026 · §5. Observation spaces and substitution-stable candidates · §5

Layers, spaces, environments, goodness, and the graph exclusion: From signed profile graphs to candidate readouts for substituted types

Observation layers and their candidate interpretation.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

An observation of a dependent function records its response to a typed argument and an optional observation of that argument. The types at which these observations are available are selected by signed paths between sort profiles. Candidate readouts then assign sets of strongly normalizing terms to substituted types.

Fix a pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R), with arbitrary axiom and product-rule relations.✦ Terms are variables, sorts, applications, annotated abstractions λx:A.M\lambda x:A.M, and dependent products Πx:A.B\Pi x:A.B.✦ Write Γ⊢M:A\Gamma\vdash M:A for typing and M≃βNM\simeq_\beta N for the equivalence relation generated by full β\beta reduction, including reduction in annotations and binder bodies. A valid context is obtained from the empty context by extensions x:Ax:A with Γ⊢A:s\Gamma\vdash A:s.✦ Substitution into newest-first contexts uses de Bruijn indices; named binders in the formulas denote capture-avoiding substitution.

Assume system weak normalization: in every valid context, both the subjects and the expected types of typing judgments have a β\beta normal form.✦ Write T#T^\# for a chosen normal form. For sets I,J⊆SI,J\subseteq S of sorts, the sort profile, axiom successors, and product outputs are the sets in (1). πΓ(T)={s∈S∣Γ⊢T#:s},Ax⁡(s)={t∈S∣(s,t)∈𝒜},Out⁡(I,J)={c∈S∣∃a∈I∃b∈J(a,b,c)∈ℛ}.\begin{aligned} \pi_\Gamma(T)&=\{s\in S\mid\Gamma\vdash T^\#:s\},\\ \operatorname{Ax}(s)&=\{t\in S\mid(s,t)\in\mathcal A\},\\ \operatorname{Out}(I,J)&=\{c\in S\mid \exists a\in I\;\exists b\in J\;(a,b,c)\in\mathcal R\}. \end{aligned}(1) A feasible profile is a nonempty set I=πΓ(T)I=\pi_\Gamma(T) for a normal term TT in a valid context.✦ A feasible product triple, written 𝖥(I,J,K)\mathsf F(I,J,K), consists of three feasible profiles with K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦

A term is legal in Γ\Gamma when it occurs as the subject or the expected type of a typing judgment in Γ\Gamma.✦

The primary signed graph E1E_1 has positive edges I→JI\to J for proper inclusions J⊊IJ\subsetneq I between feasible profiles. Each feasible product triple gives a negative edge I→KI\to K and a positive edge J→KJ\to K. A signed walk has sign ++ or −- according to the parity of its negative edges; the empty walk has sign ++.✦ For a signed graph EiE_i, write I⤳εiJI\overset{\varepsilon}{\leadsto}_i J for a walk of sign ε\varepsilon and I⤳iJI\leadsto_i J when its sign is unrestricted. Write I⤳1,+JI\leadsto_{1,+}J for a walk using only positive primary edges.✦ A strongly connected component is a nonempty set of all vertices mutually reachable with one of its vertices.✦

A saturated context tower Ω\Omega is a sequence of valid context prefixes of length nn at stage nn, each extending its predecessor by a sorted type, in which every type available in a prefix is declared again arbitrarily late.✦ Tower terms use fixed levels for free variables; Ω⊢M:T\Omega\vdash M:T means that some prefix types both MM and TT after level-to-index reversal.✦ Write πΩ(T)={s∣Ω⊢T#:s}\pi_\Omega(T)=\{s\mid\Omega\vdash T^\#:s\}.✦

The top set TopT\mathrm{Top}_T, ground set GTG_T, and tested stacks at a type TT are defined together by (2) and the stack clause below, where SN\mathrm{SN} means strong normalization for full β\beta reduction and Mn→M\,\vec n denotes left-associated application. TopT={M∣Ω⊢M:T,M∈SN},GT={M∣Ω⊢M:T,∀n→ tested at T,Mn→∈SN}.\begin{aligned} \mathrm{Top}_T&=\{M\mid\Omega\vdash M:T,\ M\in\mathrm{SN}\},\\ G_T&=\{M\mid\Omega\vdash M:T,\ \forall\vec n\text{ tested at }T,\ M\,\vec n\in\mathrm{SN}\}. \end{aligned}(2) A tested stack n→\vec n at a tower type TT is an argument list that is empty, or, at T=Πx:D.ET=\Pi x:D.E, has first argument n∈TopDn\in\mathrm{Top}_D and a tail tested at (E[n/x])#(E[n/x])^\#.✦ A normalization candidate UU at a tower type TT is a set between GTG_T and TopT\mathrm{Top}_T closed under typed head expansion: if (λx:D.b)nn→(\lambda x:D.b)\,n\,\vec n has tower type TT, its annotation, body and arguments are strongly normalizing, and b[n/x]n→b[n/x]\,\vec n belongs to UU, then so does the uncontracted term.✦ Strong normalization of an argument list uses reduction of one component at a time.

An actual type TT is a term that is either a sorted normal term in the tower or a literal sort.✦ Write Cand⁡(T)\operatorname{Cand}(T) for the collection of normalization candidates at TT.✦ A base assignment b∈ℬb\in\mathcal B chooses a member of Cand⁡(T)\operatorname{Cand}(T) for every actual type TT.✦ The top assignment chooses TopT\mathrm{Top}_T at every coordinate✦, and a coordinate update replaces the candidate at one specified actual type.✦

The Definition

Definition 1. Let CC be a family of sort profiles. The set 𝒪C\mathcal O_C of observation layers relative to CC consists of the profiles specified by (3). 𝒪C={I∣∃s∈S,{s}∈C,Ax⁡(s)≠⌀,Ax⁡(s)⤳1,+I}.\mathcal O_C=\{I\mid\exists s\in S,\ \{s\}\in C,\ \operatorname{Ax}(s)\ne\varnothing,\ \operatorname{Ax}(s)\leadsto_{1,+}I\}.(3)✦ The secondary signed graph E2E_2 is specified by (4), where Ei+E_i^+ and Ei−E_i^- denote the positive and negative edge relations of EiE_i. E2+(I,J)⇔I,J∈𝒪CandE1+(I,J),E2−(I,K)⇔I,K∈𝒪Cand∃J∈𝒪C,𝖥(I,J,K).\begin{aligned} E_2^+(I,J)&\iff I,J\in\mathcal O_C\ \text{and}\ E_1^+(I,J),\\ E_2^-(I,K)&\iff I,K\in\mathcal O_C\ \text{and}\ \exists J\in\mathcal O_C,\ \mathsf F(I,J,K). \end{aligned}(4)✦ A direct layer II relative to CC is an observation layer that occurs as the domain of a feasible product triple whose other profiles lie in CC, as in (5). 𝖣C(I)⇔I∈𝒪Cand∃J,K∈C,𝖥(I,J,K).\mathsf D_C(I)\iff I\in\mathcal O_C\ \text{and}\ \exists J,K\in C,\ \mathsf F(I,J,K).(5)✦ An active layer II relative to CC is a profile from which a direct layer is reachable in the secondary graph, as in (6). 𝖠C(I)⇔∃D,𝖣C(D)andI⤳2D.\mathsf A_C(I)\iff\exists D,\ \mathsf D_C(D)\ \text{and}\ I\leadsto_2 D.(6)✦ A plain layer II relative to CC is a profile having walks of both signs in the secondary graph to direct layers, with possibly different endpoints, as in (7). 𝖯C(I)⇔(∃D,𝖣C(D),I⤳+2D)and(∃D,𝖣C(D),I⤳−2D).\mathsf P_C(I)\iff \bigl(\exists D,\ \mathsf D_C(D),\ I\overset{+}{\leadsto}_2D\bigr) \ \text{and}\ \bigl(\exists D,\ \mathsf D_C(D),\ I\overset{-}{\leadsto}_2D\bigr).(7)✦ A free layer II of sign ε\varepsilon relative to CC is a nonplain profile with a walk of that sign in the secondary graph to a direct layer, as in (8). 𝖫Cε(I)⇔¬𝖯C(I)and∃D,𝖣C(D),I⤳ε2D.\mathsf L_C^\varepsilon(I)\iff \neg\mathsf P_C(I)\ \text{and}\ \exists D,\ \mathsf D_C(D),\ I\overset{\varepsilon}{\leadsto}_2D.(8)✦ A forbidden configuration for PP and CC is a strongly connected component 𝒟\mathcal D of the secondary graph with the properties in (9); the component condition is denoted by SCC⁡2\operatorname{SCC}_2. $$\begin{aligned} \mathsf{Forbidden}(P,C)\iff\exists\mathcal D,\quad& \operatorname{SCC}_2(\mathcal D),\quad \forall H\in\mathcal D,\ \mathsf P_C(H),\\ &\exists H,K\in\mathcal D,\ E_2^-(H,K),\\ &\exists I,J,K,s,\quad \mathsf F(I,J,K),\quad J,K,\{s\}\in\mathcal D,\\ &\hspace{27mm}\operatorname{Ax}(s)\ne\varnothing,\quad \operatorname{Ax}(s)\leadsto_{1,+}I. \end{aligned}$$(9)✦

For the observation spaces, let SS be finite and suppose there is no forbidden configuration. A normalized active type is a normal term TT with Ω⊢T:s\Omega\vdash T:s for some sort and 𝖠C(πΩ(T))\mathsf A_C(\pi_\Omega(T)).✦ A plain node TT is a normal term with Ω⊢T:s\Omega\vdash T:s for some sort ss and with plain profile πΩ(T)\pi_\Omega(T).✦ An application key kk at a normalized active type TT is a pair consisting of a decomposition T=Πx:D.ET=\Pi x:D.E and a normal argument qq with Ω⊢q:D\Omega\vdash q:D and active profile πΩ(E[q/x])\pi_\Omega(E[q/x]). Its target is (E[q/x])#(E[q/x])^\#✦; its optional domain is DD when the domain profile is active, and is absent otherwise.

A plain observation schema 𝒮\mathscr S is an assignment of application keys, target nodes, and optional domain nodes to each node.✦ A continuation path pp from a node nn is a finite sequence of application keys starting at nn, each subsequent key being at the preceding target.✦ A slot (j,d)(j,d) of a continuation path pp is an occurrence of a domain node dd along pp, with jj distinguishing occurrences.✦ Parameters for a path assign an observation to each slot✦; parameters for one frame assign an observation to its optional domain.✦ The recursive domain relation d≺nd\prec n holds when a key on a continuation path from nn has domain node dd.✦

For a plain observation schema whose recursive domain relation is well-founded, the plain observation space 𝒫B(n)\mathcal P_B(n) is the recursive table space in (10), where BB is the set of base outputs, Path⁡(n)\operatorname{Path}(n) is the set of continuation paths from nn, and Slot⁡(p)\operatorname{Slot}(p) consists of the domain-node occurrences (j,d)(j,d) along pp, with jj distinguishing occurrences, including repeated ones. 𝒫B(n)≅∏p∈Path⁡(n)((∏(j,d)∈Slot⁡(p)𝒫B(d))→B).\mathcal P_B(n)\cong \prod_{p\in\operatorname{Path}(n)} \left(\left(\prod_{(j,d)\in\operatorname{Slot}(p)} \mathcal P_B(d)\right)\longrightarrow B\right).(10)✦ The actual plain schema uses the plain nodes and application keys above; an active domain is itself a plain node.✦ Prefix decomposition separates the empty path’s base output from the continuation at each first key.✦ A constant table with output b∈Bb\in B is the distinguished plain observation.✦ For a family KK of parameter spaces, a plain observation table at nn assigns a base output in BB to each continuation path from nn and each assignment of an element of K(d)K(d) to every occurrence of a domain node dd on that path.✦

For sets Q,V,B,OQ,V,B,O and a set XX of opposite observations, a free frame ff is a pair consisting of a key in QQ and a payload in 1+X+V1+X+V.✦ Its continuation stacks are finite lists of frames✦, and an exit stack is a continuation stack followed by a terminal frame.✦ A free table assigns a base output to each continuation stack and an exit output to each exit stack.✦ Write 𝒯(X)\mathcal T(X) for this table space. The negative and positive spaces are given by (11), using the stage inclusions induced by double reindexing of tables. $$X_0=\varnothing,\qquad X_{n+1}=\mathcal T(\mathcal T(X_n)),\qquad \mathcal M=\varinjlim_n X_n,\qquad \mathcal U=\mathcal T(\mathcal M).$$(11) Each negative observation has a represented behavior in 𝒯(𝒰)\mathcal T(\mathcal U). Finite stages embed into ℳ\mathcal M✦, and positive tables restrict along these embeddings.✦ Reindexing changes opposite payloads; slicing prefixes one frame to each stack.✦ Constant tables give positive and negative defaults. A negative behavior determines a negative observation by choosing a representative when it has one, and by taking the default otherwise.✦ Finite stage behavior assigns a table over 𝒰\mathcal U to each finite stage observation; at stage n+1n+1 it reindexes the observation along restriction of positive tables to stage nn.✦ The negative observation slice of m∈ℳm\in\mathcal M at a frame over 𝒰\mathcal U is a chosen negative observation whose represented behavior is the slice of the represented behavior of mm.✦ A raw lambda table over 𝒰\mathcal U is specified by a base output, a negative observation for each first frame, and an exit output for each terminal frame. Its empty continuation has the prescribed base output, a lone terminal frame uses the exit output, and every longer stack uses the represented behavior of the negative observation selected by its first frame.✦

For actual observations, take QQ to be the term set, B=ℬB=\mathcal B, and VV to be the set of pairs (n,p)(n,p) with nn a plain node and p∈𝒫ℬ(n)p\in\mathcal P_{\mathcal B}(n); take O=1+VO=1+V. A raw observation is a plain pair, a positive observation in 𝒰\mathcal U, or a negative observation in ℳ\mathcal M.✦ Write Raw\operatorname{Raw} for their disjoint union. A raw observation v∈Rawv\in\operatorname{Raw} fits an actual type TT when it is a plain observation at exactly TT, a positive observation with 𝖫C+(πΩ(T))\mathsf L_C^+(\pi_\Omega(T)), or a negative observation with 𝖫C−(πΩ(T))\mathsf L_C^-(\pi_\Omega(T)).✦ The typed observation space is (12). Val⁡(T)={v∈Raw⁡∣v fits T}.\operatorname{Val}(T)=\{v\in\operatorname{Raw}\mid v\text{ fits }T\}.(12)✦ An optional payload pp fits an actual type DD when pp is absent and πΩ(D)\pi_\Omega(D) is inactive, or pp is present and its value fits DD.✦ An active matching payload determines a typed value.✦ The base assignment of an observation is its empty-path output, using represented behavior for a negative observation.✦

Each normalized active type TT has a distinguished value in Val⁡(T)\operatorname{Val}(T). The prescribed base value at TT for b∈ℬb\in\mathcal B has empty-path output bb and retains all nonempty observations of the distinguished default.✦ For a normalized active type TT, observation value application sends a value v∈Val⁡(T)v\in\operatorname{Val}(T), an application key at TT, and a matching domain payload to a typed observation value at the key’s target. A lambda action ℓ\ell at a normalized active type TT is an assignment of a typed observation value at the target to every application key at TT and matching domain payload.✦ Plain lambda values use prefix decomposition. Free lambda values use continuation tables until a plain target gives an exit. The gate for a frame requires its argument and payload to match a key, and its exit flag to agree with plainness of the target.✦ Ineligible continuations use the top base assignment and an absent exit. Projection retains a fitting raw value and otherwise selects a distinguished value✦; an exit uses this projection on a present plain value and the distinguished value on an absent one.✦ Plain payload encoding turns a matching optional payload for a plain application key into its single frame parameters, retaining the matching plain observation.✦ Plain payload decoding returns the plain observation at the domain node when the domain profile is active, and returns absence otherwise.✦ A positive application frame has a term as its key and a payload that is absent, a tagged plain observation, or a negative observation.✦ A negative application frame has a term as its key and a payload that is absent, a tagged plain observation, or a positive observation.✦ Positive frame payload encoding at a positive free type retains absence and plain observations and places a matching negative observation in the opposite payload.✦ Positive frame payload decoding returns the corresponding absent, plain, or negative raw payload.✦ Negative frame payload encoding at a negative free type retains absence and plain observations and places a matching positive observation in the opposite payload.✦ Negative frame payload decoding returns the corresponding absent, plain, or positive raw payload.✦ The default plain observation at a plain node is the constant plain table whose output is the top candidate assignment.✦ Plain observation application at a plain source takes the continuation coordinate of its prefix decomposition at the application key and matching domain payload, giving a typed value at the normalized target.✦ The positive lambda continuation at a positive free type uses the positive observation in the lambda action result when the decoded frame passes the continuation gate; otherwise it is the positive default with top base assignment and absent exit.✦ The negative lambda continuation at a negative free type uses the negative observation in the lambda action result when the decoded frame passes the continuation gate; otherwise it is the negative default with top base assignment and absent exit.✦ The lambda exit operation returns a tagged plain observation from the lambda action when the decoded frame passes the exit gate, and returns absence otherwise.✦ The positive lambda table has the top candidate assignment on the empty continuation, follows the positive lambda continuation after a first continuing frame, and uses the lambda exit operation with positive payload decoding at a terminal frame.✦ The negative lambda behavior is the raw lambda table with top candidate assignment as base, negative lambda continuation as body action, and the lambda exit operation with negative payload decoding as exit action.✦

A typing tree tt at Γ⊢M:T\Gamma\vdash M:T is a finite tree generated by (13), every node satisfying its displayed ordinary typing judgment. Write 𝖳𝗋𝖾𝖾Γ(M:T)\mathsf{Tree}_\Gamma(M:T) for the collection of these trees and Γ(x)=A\Gamma(x)=A for context lookup with AA expressed in the full context. Γ(x)=AT≃βA𝖳𝗋𝖾𝖾Γ(x:T)(s,t)∈𝒜T≃βt𝖳𝗋𝖾𝖾Γ(s:T)𝖳𝗋𝖾𝖾Γ(A:a)𝖳𝗋𝖾𝖾Γ,x:A(B:b)(a,b,c)∈ℛT≃βc𝖳𝗋𝖾𝖾Γ(Πx:A.B:T)𝖳𝗋𝖾𝖾Γ(A:a)𝖳𝗋𝖾𝖾Γ,x:A(m:B)Γ⊢Πx:A.B:sT≃βΠx:A.B𝖳𝗋𝖾𝖾Γ(λx:A.m:T)𝖳𝗋𝖾𝖾Γ(f:Πx:A.B)𝖳𝗋𝖾𝖾Γ(n:A)T≃βB[n/x]𝖳𝗋𝖾𝖾Γ(fn:T).\begin{gathered} \frac{\Gamma(x)=A\qquad T\simeq_\beta A} {\mathsf{Tree}_\Gamma(x:T)} \qquad \frac{(s,t)\in\mathcal A\qquad T\simeq_\beta t} {\mathsf{Tree}_\Gamma(s:T)} \\[2mm] \frac{\mathsf{Tree}_\Gamma(A:a)\quad \mathsf{Tree}_{\Gamma,x:A}(B:b)\quad (a,b,c)\in\mathcal R\quad T\simeq_\beta c} {\mathsf{Tree}_\Gamma(\Pi x:A.B:T)} \\[2mm] \frac{\mathsf{Tree}_\Gamma(A:a)\quad \mathsf{Tree}_{\Gamma,x:A}(m:B)\quad \Gamma\vdash\Pi x:A.B:s\quad T\simeq_\beta\Pi x:A.B} {\mathsf{Tree}_\Gamma(\lambda x:A.m:T)} \\[2mm] \frac{\mathsf{Tree}_\Gamma(f:\Pi x:A.B)\quad \mathsf{Tree}_\Gamma(n:A)\quad T\simeq_\beta B[n/x]} {\mathsf{Tree}_\Gamma(f\,n:T)}. \end{gathered}(13)✦

An observation environment e=(σ,p)∈Env⁡(Γ)e=(\sigma,p)\in\operatorname{Env}(\Gamma) for a context Γ\Gamma is a pair consisting of an actual substitution σ\sigma and optional parameters pxp_x satisfying (14). Env⁡(Γ)={(σ,p)|for every context lookup Γ(x)=A,Ω⊢σ(x):Aσ,px fits (Aσ)#}.\operatorname{Env}(\Gamma)= \left\{(\sigma,p)\ \middle|\ \begin{array}{l} \text{for every context lookup }\Gamma(x)=A,\\ \Omega\vdash\sigma(x):A\sigma,\quad p_x\text{ fits }(A\sigma)^\# \end{array}\right\}.(14)✦ Extension by an argument nn of tower type AσA\sigma and a matching payload extends both the actual substitution and its parameters.✦ A typing judgment Γ⊢M:T\Gamma\vdash M:T determines the actual type (Tσ)#(T\sigma)^\#✦; a judgment Γ⊢A:s\Gamma\vdash A:s also determines the actual expression (Aσ)#(A\sigma)^\#.✦

For a typing tree tt with root Γ⊢M:T\Gamma\vdash M:T and an observation environment e=(σ,p)∈Env⁡(Γ)e=(\sigma,p)\in\operatorname{Env}(\Gamma), put Me=(Mσ)#M_e=(M\sigma)^\# and Te=(Tσ)#T_e=(T\sigma)^\#. Structural preevaluation preEval⁡(t,e)\operatorname{preEval}(t,e) of a typing tree tt in an observation environment ee is the pair of value and candidate readout in (15). preEval⁡(t,e)=(Val⁡t(e),Read⁡t(e))∈(𝖠C(πΩ(Te))→Val⁡(Te))×Cand⁡(Me).\operatorname{preEval}(t,e)= \bigl(\operatorname{Val}_t(e),\operatorname{Read}_t(e)\bigr) \in \bigl(\mathsf A_C(\pi_\Omega(T_e))\longrightarrow \operatorname{Val}(T_e)\bigr) \times\operatorname{Cand}(M_e).(15)✦ The variable operation uses context lookup in the environment. The sort operation gives a distinguished value and the top readout.✦ Abstraction and application use lambda actions and value application. The optional parameter of a result is its value when the expected type is active, and is absent otherwise.✦ A base readout takes the observation’s base assignment at MeM_e when πΩ(Me)∈C\pi_\Omega(M_e)\in C, the expected type is a literal sort ss with {s}∈C\{s\}\in C, and TeT_e is active; in every other case it is TopMe\mathrm{Top}_{M_e}.✦ A base evaluation result pairs the assigned observation values at an active expected type with their base candidate readout.✦

A product instance ι\iota is a tuple consisting of formation judgments Γ⊢D:a\Gamma\vdash D:a and Γ,x:D⊢E:b\Gamma,x:D\vdash E:b, a permitted rule (a,b,c)∈ℛ(a,b,c)\in\mathcal R, and an observation environment e∈Env⁡(Γ)e\in\operatorname{Env}(\Gamma).✦ Its substituted domain and body are DσD\sigma and Eσ+E\sigma^+, where σ+\sigma^+ fixes the bound variable and shifts the images of the other variables. Their normal forms are denoted D0,E0D_0,E_0, and Tn=(E[n/x,σ])#T_n=(E[n/x,\sigma])^\#. Given a domain readout dd and body readouts b(n,p)b(n,p) indexed by typed arguments and matching payloads, the product candidate is the indexed product test in (16). Ad={d,πΩ(D0)∈C,TopD0,otherwise,𝒞b(n)={{b(n,p)∣p fits D0},Ω⊢n:D0,πΩ(Tn)∈C,{TopTn},Ω⊢n:D0,πΩ(Tn)∉C,⌀,otherwise,Prod⁡(d,b)={f∈TopΠx:D0.E0∣∀n∈Ad∀U∈𝒞b(n),fn∈U}.\begin{aligned} A_d&=\begin{cases} d,&\pi_\Omega(D_0)\in C,\\ \mathrm{Top}_{D_0},&\text{otherwise}, \end{cases}\\ \mathcal C_b(n)&=\begin{cases} \{b(n,p)\mid p\text{ fits }D_0\},& \Omega\vdash n:D_0,\ \pi_\Omega(T_n)\in C,\\ \{\mathrm{Top}_{T_n}\},& \Omega\vdash n:D_0,\ \pi_\Omega(T_n)\notin C,\\ \varnothing,&\text{otherwise}, \end{cases}\\ \operatorname{Prod}(d,b)&= \{f\in\mathrm{Top}_{\Pi x:D_0.E_0}\mid \forall n\in A_d\;\forall U\in\mathcal C_b(n),\ f\,n\in U\}. \end{aligned}(16)✦ Product evaluation uses the domain and body evaluation readouts in this test to obtain its candidate readout.✦ When its expected type is active, its product observation updates the candidate coordinate at the normalized substituted product with this product candidate. Its body environments extend ee by the tested argument and its payload.✦ The raw instantiated target substitutes the tested argument for the bound variable of the product body and the environment images for its other free variables.✦ Its chosen normal form is the normalized instantiated target TnT_n.✦ The product tester set AdA_d uses the domain readout when the normalized domain profile lies in CC, and the top set at that domain otherwise.✦ The product candidate fibers 𝒞b(n)\mathcal C_b(n) collect all body candidates over matching payloads when nn has the normalized domain type and its target profile lies in CC; for a typed argument outside that case they contain only the top set at its target, and for an untyped argument they are empty.✦ For a typed argument nn with active target, the normalized argument frame is the application key at the normalized product whose argument is n#n^\#, whose domain and body are D0D_0 and E0E_0, and whose target retains the same normal form.✦

For a typing tree tt and a raw actual substitution σ\sigma, the recursive evaluation goodness conditions 𝔤t(σ)\mathfrak g_t(\sigma) concern its value and readout. The two goodness predicates are (17) and (18). ValGood⁡(t,σ)=pr⁡1𝔤t(σ).\operatorname{ValGood}(t,\sigma) =\operatorname{pr}_1\mathfrak g_t(\sigma).(17)✦ ReadGood⁡(t,σ)=pr⁡2𝔤t(σ).\operatorname{ReadGood}(t,\sigma) =\operatorname{pr}_2\mathfrak g_t(\sigma).(18)✦ At a variable, the value condition is automatic; at a sort, both conditions are automatic. For a product with domain subtree dd, body subtree bb, and result sort cc, the required recursive condition is readout goodness of dd when πΩ(Dσ)∈C\pi_\Omega(D\sigma)\in C, together with readout goodness of bb at every Ω⊢n:Dσ\Omega\vdash n:D\sigma whose substituted body has profile in CC. The product value condition imposes this requirement when both {c}∈C\{c\}\in C and the substituted product profile lies in CC; its readout condition imposes it when the latter profile lies in CC. The abstraction value clause requires value goodness of the body for every typed argument with active target. For application, an active function type requires value goodness of the function and of the argument when its domain is active; an inactive function type requires a neutral application.

For Γ⊢A:s\Gamma\vdash A:s, the normal readout NRead⁡Γ(A,e)\operatorname{NRead}_\Gamma(A,e) is the readout obtained by preevaluating a chosen typing tree for Γ⊢A#:s\Gamma\vdash A^\#:s, regarded as a candidate at (Aσ)#(A\sigma)^\#.✦ The component interpretation RΓ(A;e)\mathrm R_\Gamma(A;e) of a term AA in context Γ\Gamma and observation environment ee is the set in (19), using a chosen sort witness in its first case. RΓ(A;e)={NRead⁡Γ(A,e),πΓ(A)∈CandΓ⊢A:s for some s,Top(Aσ)#,otherwise.\mathrm R_\Gamma(A;e)= \begin{cases} \operatorname{NRead}_\Gamma(A,e),& \pi_\Gamma(A)\in C\ \text{and}\ \Gamma\vdash A:s \text{ for some }s,\\ \mathrm{Top}_{(A\sigma)^\#},&\text{otherwise}. \end{cases}(19)✦

What Is Checked

The layer definitions concern the primary profile graph of a specification and a family CC of profiles. The observation constructions concern a finite sort set, a saturated context tower, system weak normalization, and exclusion of the forbidden configuration; evaluation takes a typing tree and a typed observation environment, while goodness is stated for a raw substitution.

Every typing judgment admits a typing tree.✦ Exclusion of the forbidden configuration makes the actual plain domain dependency well-founded.✦ A nonplain continuation of a free application key retains its sign✦, and decoding plain frame parameters gives a matching payload.✦ Normalization of a substituted product has domain D0D_0 and body E0E_0✦; a tester typed at D0D_0 is also typed at the substituted domain✦, and the body substitution determined by a frame has the frame target as its normal form.✦ Every dependent product occurring as the type of a function has a sort.✦ At a plain node every typed value is represented by a plain observation✦, while at a positive or negative free type every typed value has the corresponding free tag.