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 81–180 of 803. Source text is displayed literally.

81executables across guest languages. Earlier modal accounts explain82binding time by a type discipline \cite{daviespfenning}; here the index83maps organize families of specializations and observations.84 85\section{Typed specifications and static contexts}86\label{sec:typed-core}87 88Let $W=\mathbb Z/2^{64}\mathbb Z$ and $B=\{\mathsf{false},\mathsf{true}\}$.89The signed interpretation $s:W\cong[-2^{63},2^{63}-1]\cap\mathbb Z$ chooses the unique representative in that interval. Addition, subtraction, and multiplication take place in $W$. Equality compares residues, and less-than compares their images under $s$. Each primitive is total. A public call consumes and returns words. Boolean terms act as internal conditions. Java's signed \texttt{long} implements the word operations with 64-bit precision and wrapping \cite[Section~4.2.2]{jls24}.90 91A context $\Gamma$ is a finite typed list of variables with types $W$ or $B$. Its carrier $X_\Gamma$ is the product of its variable carriers. A single-result term is built from variables, literals, the arithmetic and comparison primitives, typed conditional expressions, and let bindings. A tuple of terms with common context $\Gamma$ is a morphism $\Gamma\to\Delta$ when the term types match the entries of $\Delta$. Composition is simultaneous capture-avoiding substitution, and identities are tuples of variables. We use the equational quotient with alpha-conversion, let-substitution, branch selection for literal conditions, and valid primitive computations on literals. Products are concatenation of contexts and the empty context is terminal. This presents a finite-product category of specifications. At the level of syntax, let bindings remain available to express sharing without duplicating a subterm.92 93The interpretation $\operatorname{den}$ sends contexts to carriers and terms to functions. Conditional interpretation evaluates the condition and selects the corresponding branch. The interpretation of $\mathsf{let}\ x=u\ \mathsf{in}\ v$ at $\gamma$ evaluates $v$ at $(\gamma,\operatorname{den}(u)(\gamma))$. By induction on the term, evaluation after simultaneous substitution equals function composition. For the let case, lift the substitution through the binder by extending it with the fresh variable and then apply the inductive hypothesis to the two subterms. Every defining equation is preserved. Thus $\operatorname{den}$ is a finite-product functor to $\mathbf{Set}$. In particular, a compositional interpretation of a categorical specification is determined by its variable projections and its choices for the generators.94 95\subsection{Restriction and residual syntax}96 97Fix $t:\Gamma\to\tau$. A static assignment $a$ supplies typed literals for some variables of $\Gamma$. Write $\Gamma_a$ for the remaining context, $D_a=X_{\Gamma_a}$ for its carrier, and $k_a:D_a\to X_\Gamma$ for insertion of the literals in their original positions. If $a\leq b$, meaning that $b$ agrees with $a$ and supplies at least its literals, insertion of the additional literals defines $k_{a,b}:D_b\to D_a$. These maps satisfy $k_a\circ k_{a,b}=k_b$ and $k_{a,b}\circ k_{b,c}=k_{a,c}$. Write $t[a]:\Gamma_a\to\tau$ for the term obtained by syntactic substitution of the literals.98 99Define a structural residualizer $r_a$ as follows. Replace known variables by literals. Descend into primitives and compute a literal result when all arguments are literal. For a conditional, specialize the condition first. If it becomes a Boolean literal, specialize the selected branch. Otherwise preserve the conditional and specialize both branches. For a let binding, specialize the right-hand side. Extend the static assignment by the freshly bound variable when the result is a literal and replace the let by the specialized body. Otherwise keep the binding and specialize the body with that variable dynamic. Alpha-rename binders before extending an assignment. Each recursive call operates on a proper subterm of the original input, including when the static environment is extended at a let. Hence this residualizer terminates on finite input terms.100 101\paragraph{Specialization theorem.}102For every $t$ and $a$, the specialized term is well typed, and103\begin{equation}104  \operatorname{den}(r_a(t))=\operatorname{den}(t)\circ k_a.105  \label{eq:specialization-insertion}106\end{equation}107For $a\leq b$, put $b/a=b|_{\Gamma\setminus\operatorname{dom}(a)}$. Direct and staged specialization satisfy108\begin{equation}109  \operatorname{den}(r_{b/a}(r_a(t)))=\operatorname{den}(r_b(t)).110  \label{eq:staged-specialization}111\end{equation}112To prove \eqref{eq:specialization-insertion}, induct on the term. The variable case follows from the coordinate formula for $k_a$. A folded primitive evaluates to the same element of $W$ or $B$ by definition of its literal evaluation. A preserved primitive composes with the interpretations of its specialized arguments. In a conditional with a literal residual condition, the induction hypothesis fixes the same branch in both interpretations for every dynamic input. With a dynamic condition, it fixes the condition value and the result of each branch. For a let with a literal residual right-hand side, that literal is its evaluated value at every dynamic input. Applying the induction hypothesis to the body in the extended static assignment yields the source value. With a dynamic right-hand side, apply the induction hypothesis to the body at the dynamic context extended by the right-hand side's evaluated value. All replacements have the types of the subterms they replace. Applying \eqref{eq:specialization-insertion} twice and using the insertion identity proves \eqref{eq:staged-specialization}. This theorem concerns observable word or Boolean values. Different compilation orders can yield different residual artifacts and costs.113 114The same proof applies to a binary64 fragment with pure, total addition, subtraction, and multiplication interpreted as Java \texttt{double} operations in the stated evaluation order. Its observable carrier distinguishes signed zeros and infinities and treats NaNs as a single semantic class. Literal substitution and folding must preserve that interpretation \cite[Sections 4.2.3--4.2.4]{jls24}. Real or modular arithmetic identities require new proofs in the binary64 carrier before using them as rewrites. For example, under Java evaluation, $((2^{53}+1)-2^{53})$ evaluates to $0$ whereas $(2^{53}+(1-2^{53}))$ evaluates to $1$. For the circuit compiler, static construction supplies the complex coefficients and the scalar kernel applies the given sum-of-products order. The theorem preserves the chosen rounded operations. Approximation of exact Hilbert-space evolution is a further numerical question.115 116The first Futamura projection is another instance of restriction. If $P$ is a set of well-formed first-order program descriptions with an agreed interface $D\to Y$, write $I:P\times D\to Y$ for a total interpreter on that interface. For $p\in P$, the denotation of a residual executable is $I\circ\langle p\circ !,\mathrm{id}_D\rangle$, with $p:1\to P$ and $!:D\to1$. Partial evaluation tries to realize this restriction with interpreter dispatch removed. Truffle specializes an interpreter using a stable guest program and profiled state, while the typed residualizer above supplies a separate semantic model for source specialization \cite{futamura,jgs,wuerthinger,graalpe}.117 118\paragraph{Correspondence with the implemented pass.}119The implementation allocates a distinct integer slot for each lexical120binder, even when a nested binder reuses a name. Each recursive121result carries its free local slots. Correctness of that set follows122from the singleton set for a residual local variable, the empty123set 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$ on