Indexed text attachment
coherent-specialization-on-graalvm.tex
Source for Coherent Specialization on GraalVM
View paper · Download original file
Lines 183–282 of 803. Source text is displayed literally.
183\]184The inclusion into $N\times J$ is a trivial cofibration in the Joyal model structure. It is the pushout product of $N_0\subset N$ and the trivial cofibration $\{0\}\subset J$ \cite[Corollary 2.2.5.4]{lurie}. The map $E\to N$ is an inner fibration, and equivalences in the base, which are identities, lift. Hence it is a fibration between quasi-categories in the Joyal model structure and admits a lift on $N\times J$ \cite[Corollary 2.4.6.5]{lurie}. Its endpoint at $1$ is the desired section and the homotopy gives the coherent comparisons. Transport in the left fibration applied to the resulting natural-equivalence square yields \eqref{eq:coherent-path}. In particular, for $a\leq b\leq c$, the middle witness cancels up to homotopy, and the lift supplies the compatibilities for longer chains. The trace from $k_{a,b}^{*}r_a(t)$ to $r_{b/a}(r_a(t))$ compares the staged residual to the direct residual through \eqref{eq:coherent-path}. Passing to discrete denotations recovers \eqref{eq:staged-specialization}.185 186The theorem applies to the specified source rewrite theory. To include a Truffle optimization as another edge, establish its correctness judgment and compatibility with substitution for the chosen semantics.187 188\section{Internal families, descent, and guarded execution}189\label{sec:descent}190 191Let $\mathcal X$ be an $\infty$-topos and take a program denotation $F:S\times D\to Y$. In the slice $\mathcal X_{/S}$, a static context is an object $a:A\to S$. Its residual denotation is $F_a=F\circ(a\times\mathrm{id}_D)$. Equivalently $F_a$ determines a map $A\times D\to A\times Y$ over $A$. For $u:(A',a')\to(A,a)$ in the slice, pullback identifies $F_{a'}$ with $u^*F_a$ through the specified homotopy between $a'$ and $a\circ u$. Changing the static context gives a contravariant functor on denotations whose higher coherence is the functoriality of pullback. The term interpretation above takes values in the $0$-truncated part of the model with $\mathcal X=\mathcal S$.192 193Consider a presheaf of candidate residual artifacts $R:(\mathcal X_{/S})^{\mathrm{op}}\to\mathcal S$ with a natural semantic map to194\[195 H(A)=\operatorname{Map}_{\mathcal X}(A\times D,Y).196\]197Here a point of $R(A)$ is an artifact, and paths identify artifacts according to the chosen execution or proof semantics. The family $F_a$ is a section $s_F:1\to H$. Define the presheaf $C_F=R\times_H1$ using the homotopy pullback. An element of $C_F(A)$ carries both an implementation and a path from its denotation to $F_a$. Higher paths include compatibility between certificates. Its restriction maps follow simultaneously from $R$, $H$, and the section $s_F$.198 199\paragraph{Certification descent.}200If $R$ satisfies descent along the \v{C}ech nerve of an effective epimorphism $U\to A$ in $\mathcal X_{/S}$, then so does $C_F$. Indeed, cartesian closure identifies $H(A)$ with $\operatorname{Map}_{\mathcal X}(A,Y^D)$. The \v{C}ech nerve $U_\bullet$ realizes to $A$, so mapping into $Y^D$ turns it into a limit diagram \cite[Corollary 6.2.3.5]{lurie}. The constant terminal presheaf also has this property. Limits commute with the pullback defining $C_F$, giving201\begin{equation}202 C_F(A)\simeq\lim_{[n]\in\Delta} C_F(U_n).203 \label{eq:descent}204\end{equation}205Thus an implementation with coherently matching certificates206descends along the cover. Given a point of the limit, the space207of global lifts equipped with identifications with that point is208contractible, since it is the homotopy fiber of an equivalence.209Applying the theorem to executable artifacts requires specifying210their gluing semantics and establishing that it satisfies descent.211 212\paragraph{Representable implementation families.}213An instance that supplies this structure uses input,214observation, and candidate families \(D_S,Y_S,C\) in215\(\mathcal X_{/S}\). These may vary with the static parameter.216Interpret execution as \(e:C\times_S D_S\to Y_S\), and write217\(f:D_S\to Y_S\) for the specification. Transposing in the218locally cartesian closed slice gives219\(e^\sharp:C\to[D_S,Y_S]_S\) and220\(f^\sharp:S\to[D_S,Y_S]_S\). Model the family of witnessed221residuals by the homotopy pullback222\[223 S\times_{[D_S,Y_S]_S}C .224\]225Mapping into this object over \(S\) gives candidates and226correctness paths over any context \(A\to S\), by exponential227adjunction and the defining property of the pullback. This228assigns a space of witnesses to each context with all higher229restriction maps induced by precomposition. It satisfies230\eqref{eq:descent} because mapping out of a \v{C}ech231colimit in the slice takes it to a limit. A relabeling between232candidate representations lifts to a comparison between233certified candidates when its execution homotopy is234compatible with their correctness paths. Higher comparisons235are given by the same homotopy pullback.236 237For a higher example take $\mathcal X=\mathcal S$, $S=S^2$, $D=*$, and $Y=K(\mathbb Z,2)$. Let $F$ represent the generator of $H^2(S^2;\mathbb Z)$ and let $R=1$ supply one candidate with constant basepoint denotation over every $A$. At a point of $S$, the certificate space is equivalent to $\Omega K(\mathbb Z,2)\simeq K(\mathbb Z,1)$ after choosing a path to the basepoint. Take $U$ to be the disjoint union of the complements of the north and south poles, mapped to $S^2$. Each complement is contractible. The map $U\to S^2$ is an effective epimorphism in spaces because it is surjective on components. Both restrictions of $F$ are nullhomotopic, so $C_F(U)$ is inhabited. A global certificate would nullhomotope a generator, which is impossible. Equation \eqref{eq:descent} identifies the obstruction as failure to complete these local certificates to a compatible \v{C}ech diagram. This example tests the semantics of higher certificates. The executable word-valued compiler uses the discrete instance.238 239\paragraph{Guarded refinement.}240For a fixed context \(A\), let \(g:A\times D\to 1\sqcup1\)241be a decidable guard. Its two pullbacks split \(A\times D\)242as \(G\sqcup\bar G\), since coproducts in an243\(\infty\)-topos are disjoint and universal. Let \(J:G\to Y\)244be the fast branch, \(s:\bar G\to Q\) a checkpoint on guard245failure, and \(j:Q\to Y\) its generic continuation.246Given paths \(J\simeq F_a|_G\) and247\(j\circ s\simeq F_a|_{\bar G}\), the dispatcher248\([J,j\circ s]\) is observationally equivalent to \(F_a\).249The mapping space out of the coproduct is the product of the250branch mapping spaces, where the two certificates form the two251components of the desired path. Both the guard decomposition and252the assembly of certificates commute with pullback.253 254An entry guard can checkpoint the original arguments. After255observable work, the checkpoint hypothesis demands a simulation256relating optimized state to an interpreter state at a valid257continuation, and preservation of any trace already produced.258For instance, restarting the call after a write can repeat the259write even when the return value agrees. A mutable speculative260assumption also needs valid synchronization through its use when261calls and invalidation can occur concurrently.262 263 264\section{From residual syntax to Truffle calls}265\label{sec:graal}266 267\paragraph{Two stages.}268The compiler takes a checked algorithm $t$ and static parameters $s$ in its declared scalar type. It substitutes the parameters, simplifies the resulting term, and lowers the residual tree to a Truffle \texttt{RootNode}. Each executable kernel holds the call target of that root. For dynamic inputs $d$, the call target executes the lowered tree through Truffle. Graal can specialize the interpreter with respect to the root and its stable structure. Schematically,269\begin{align*}270 r_s &= \operatorname{simplify}(t[s]), \\271 K_s &= \operatorname{callTarget}(\operatorname{lower}(r_s)), \\272 K_s(d) &= \operatorname{exec}_{\mathrm{Truffle}}(r_s,d).273\end{align*}274The first stage fixes source-level parameters. The second stage uses the constructed AST as static interpreter state, in the sense of Truffle's first-Futamura-projection architecture \cite{graalpe,wuerthinger}. Constructing $K_s$ yields an executable value immediately. Compilation to machine code depends on the engine, the runtime tier, the workload, and compilation heuristics \cite{graalroot}.275 276\paragraph{Lowering invariant.}277Input and local nodes read distinct logical environments. Constants and input indices are fixed at construction. For \texttt{i64}, Java \texttt{long} addition, subtraction, and multiplication compute in $W=\mathbb Z/2^{64}\mathbb Z$ and comparison uses signed order. The \texttt{f64} case decodes the stored bits, performs the corresponding Java \texttt{double} operation, and re-encodes numerical results. The representation preserves signed zero and canonicalizes NaN payloads. The internal representations of false and true are $0$ and $1$, with the type checker controlling their use. A conditional evaluates its test and only the selected branch. A \texttt{LET} first evaluates its definition and writes the result to its assigned frame slot. References in the body read the frame slot for their lexical binder. A fresh execution frame prevents previous calls from supplying local values.278 279For each subterm $u$, let $\eta$ map its free local variables to assigned slots, and let $F$ be a frame with dynamic arguments $d$ and slot values representing an environment $\rho$. The lowering invariant is280\[281 \operatorname{run}(\operatorname{lower}_{\eta}(u),F)282 = \operatorname{encode}(\operatorname{den}(u)(d,\rho)).