Independent scholarship · Open accessThe monthly digest

Indexed text attachment

coherent-specialization-on-graalvm.tex

Source for Coherent Specialization on GraalVM

View paper · Download original file

Lines 123–222 of 803. Source text is displayed literally.

123set for literals and inputs, union for ordinary constructors, and124removal of the bound slot from the body of a retained let. The125right-hand side is handled in the outer scope. Known slots produce126only literals in residual terms. When the residual body has no free127occurrence of the bound slot, its evaluation is independent of that128coordinate. The right-hand side is pure and total, so the pass129can erase the binding. The implementation also folds130\[131 x+0,\quad 0+x,\quad x-0,\quad x\cdot1,\quad 1\cdot x132\]133to \(x\), and \(x\cdot0\) and \(0\cdot x\) to \(0\).134These are identities in \(W\), and purity and totality justify the135erasure of an operand. The induction proving136\eqref{eq:specialization-insertion} therefore extends to137\texttt{Specializer.residualize} on type-checked specifications.138 139\paragraph{Normalization and composition.}140In the raw, binder-free syntax, there is a stronger form of the141composition law for a literal folder \(N\) that normalizes each142child, then computes all-literal primitive applications and143selects branches at literal conditions. Use a unique literal144representation for each primitive value. For every well-typed145simultaneous substitution \(\sigma\),146\begin{equation}147 N(t\circ \sigma)=N\bigl(N(t)\circ N(\sigma)\bigr).148 \label{eq:normalized-substitution}149\end{equation}150Each elementary literal or branch rewrite preserves \(N\). At the151root this follows from the definition of \(N\), including agreement152of the rules on an all-literal conditional. In a larger term it153follows because a node's normal form depends only on the normal154forms of its children. Every term reduces to \(N(t)\) by bottom-up155rewriting. The rewrite rules are stable under substitution, since156the literal data are closed and branch selection commutes with157substitution into the selected branch. Thus \(t\circ\sigma\)158reduces first to \(N(t)\circ\sigma\), then, by reducing substituted159terms at each occurrence, to \(N(t)\circ N(\sigma)\). This gives160\eqref{eq:normalized-substitution}. Normalized tuples form a161finite-product category with composition162\(g\star f=N(g\circ f)\): both bracketings of a triple163composition become \(N(h\circ g\circ f)\), identities and164projections are variables, and tupling preserves normal form.165 166\section{Coherent comparison of residual programs}167\label{sec:coherent}168 169The specialization theorem equates denotations. To retain a concrete reason why residual outputs agree, give each remaining context a category $\mathcal R_a$. Its objects are alpha-equivalence classes of terms of result type $\tau$. Its arrows are finite sequences of elementary rewrite steps, with composition by concatenation. Use the contextual closures of arithmetic evaluation on literals, literal branch selection, hygienic let-substitution, and the listed word identities as rewrite rules. Take rewrite edges to record a rule instance and its position, and take the free category on this graph. Static substitution sends an instance to the same rule at the same position after substituting its open data, so it induces a functor $\mathcal R_a\to\mathcal R_b$ for $a\leq b$. Here, substitution can be implemented by binding indices or by taking alpha-equivalence classes, so composition of these substitution functors is strict. A concrete $r_a(t)$ has a rewrite trace $p_a:t[a]\to r_a(t)$. For the static-let case, produce a trace for the right-hand side to its literal, apply the let rule, and continue with the body. A preserved let or conditional uses contextual rewrites. The let rule also erases a binding when its simplified body no longer uses it. This trace may be constructed from the structural algorithm independently of Truffle.170 171Let $K_a=|N\mathcal R_a|$ denote the space obtained by inverting all rewrite arrows. Equivalently, this is the groupoid completion of the rewrite category, a special case of relative localization \cite{dwyerkan}. Finite rewrite chains retain their classes as paths, and simplices of the nerve witness composition. Since each rewrite preserves denotation, interpretation factors through $K_a$ to the discrete space of functions $D_a\to\operatorname{den}(\tau)$. The map to the discrete space is compatible with substitution. Its fibers can depend on the chosen rewrite presentation. For example, the category generated by two distinct parallel elementary rewrite edges between two objects has a circle as its groupoid completion. Additional proof relations can identify such paths when justified by a more refined rewrite theory.172 173\paragraph{Coherence theorem.}174Let $P_t$ be the poset of static assignments ordered by refinement and let $K:P_t\to\mathcal S$ be the diagram $a\mapsto K_a$. The witnesses $p_a$ extend to a coherent family of residual terms with equivalences over every refinement. Over $a\leq b$, the comparison is represented by175\begin{equation}176  p_b\circ k_{a,b}^{*}(p_a)^{-1} :177  k_{a,b}^{*}r_a(t) \simeq r_b(t).178  \label{eq:coherent-path}179\end{equation}180The functorial family of unsimplified terms $a\mapsto t[a]$ gives a section of the left fibration $E\to NP_t$ classified by $K$ via unstraightening \cite[Section 2.2]{lurie}. In each fiber the trace $p_a$ gives a path from that section's value to the desired term. To see that all coherences can be chosen together, write $N=NP_t$ and $N_0\subset N$ for its vertex subcomplex. Let $J$ be the nerve of the groupoid on two isomorphic objects. A path in a Kan fiber extends to a map from $J$, since $\Delta^1\hookrightarrow J$ is a trivial cofibration for the Kan model structure. The section and the chosen fiber paths define a map over $N$ on181\[182  (N\times\{0\})\cup_{N_0\times\{0\}}(N_0\times J).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\[