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

1% Generated by expanding the section inputs from paper/main.tex.2\documentclass[10pt,twocolumn]{article}3\usepackage[letterpaper,margin=0.78in,columnsep=0.26in]{geometry}4\usepackage{amsmath,amssymb,amsthm}5\usepackage{microtype}6\usepackage{xcolor}7\usepackage[colorlinks=true,linkcolor=blue!55!black,urlcolor=blue!60!black,citecolor=blue!55!black]{hyperref}8\usepackage{graphicx}9\usepackage{booktabs}10\usepackage{tabularx}11\setlength{\emergencystretch}{1em}12\hypersetup{13  pdftitle={Coherent Specialization on GraalVM},14  pdfauthor={Anonymous author},15  pdfsubject={Higher categorical semantics and reproducible compiler artifact}16}17 18\title{\textbf{Coherent Specialization on GraalVM}\\[0.3em]19\large From categorical algorithm specifications to polyglot kernels}20\author{Anonymous author}21\date{November 2026}22 23\begin{document}24\maketitle25 26\begin{abstract}27We formulate Truffle-style partial evaluation as restriction along static28contexts and give a correctness proof for an executable residualizer. We29construct a space of certified implementations over each context, explain30how restriction transports these spaces coherently, and prove effective31descent of certification for families in an $\infty$-topos. The executable32artifact compiles typed specifications to Truffle call targets callable from33JavaScript and Python. Domain front ends lower finite impulse-response34filter banks, decision-tree ensembles, periodic free-electron evolution,35and an interacting finite fermion field. Word semantics are exact modulo36$2^{64}$. Quantum dynamics are unitary over the mathematical model and37executed in binary64 with independently checked numerical error.38Time sweeps expose the spread of a free-electron packet and isolate39the effect of the interaction on neighboring-particle probabilities.40\end{abstract}41 42\section{Introduction}43 44Graal's Truffle framework compiles language interpreters by specializing45them with respect to the guest AST and stable interpreter state. It combines46partial evaluation with profile-guided optimization and may fall back to47interpretation when an assumption fails \cite{graalpe,wuerthinger}. The48architecture realizes the first Futamura projection in a practical runtime.49In the usual equation, specializing an interpreter $I$ at a program $p$50produces an executable $I_p$ with51$I_p(d)=I(p,d)$ on its observation domain \cite{futamura,jgs}.52Binding a source program's static data before it reaches Truffle adds a53separate specialization stage. We formalize how these stages fit together54and give a library that exercises them.55 56Our main mathematical object is an implementation fiber over an57observation. A residual program together with a proof of its observation58defines a point of this fiber. Restricting the static context carries both59the program and the proof. In the higher formulation, paths between proofs60are retained and the comparison of restrictions is coherent. A descent61theorem says when measurements of equivalence over a cover suffice to62construct a global certified implementation. When all observations are63set-valued, this framework recovers an ordinary correctness statement.64 65There are four domain compilers over a shared typed algebra. The FIR66compiler exploits symmetry in a ring and specializes a filter bank at a67fixed index. The forest compiler shares affine feature calculations and68specializes static model parameters. The two quantum front ends generate69finite-dimensional evolutions and lower their real and imaginary rows to70separately callable scalar kernels. On the periodic lattice the free71Hamiltonian is diagonal in momentum. In the field example, an occupation72basis supports a hopping Hamiltonian with an interaction term. Both use73the same runtime and guest-language call protocol.74 75The journal's prior work on Futamura coherence and higher e-graphs76develops guarded local specialization, descent, and deployment77\cite{hcsfutamura,hcsegraphs}. Its Caprice manuscript studies partial78evaluation for a capture-aware regex language and a Cranelift back end79\cite{hcscaprice}. We give a typed restriction model centered on the80Truffle interpreter boundary and test reuse of the same generated81executables 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