Indexed text attachment
coherent-specialization-on-graalvm.tex
Source for Coherent Specialization on GraalVM
View paper · Download original file
Lines 303–402 of 803. Source text is displayed literally.
303 304\subsection{A bank of finite impulse response filters}305 306A specification fixes a window of length $m\ge 2$ and a finite, nonempty ordered bank. For a bank entry $b$, the shape gives a symmetry sign $\epsilon_b\in\{1,-1\}$, while the static inputs include the bank selector, every independent pair coefficient $c_{b,i}$, and the center coefficient if needed. Put $q=\lfloor m/2\rfloor$ and $j(i)=m-1-i$. For $0\le i<q$, the coefficient vector satisfies307\[308h_{b,i}=c_{b,i},\qquad h_{b,j(i)}=\epsilon_b c_{b,i}.309\]310An odd symmetric window takes its center coefficient as a static input. An odd antisymmetric window chooses center zero as part of the specification. This choice fixes the center even though $2c=0$ also admits a nonzero class in $R$.311 312The generator emits a bank selector built from equality tests over the static bank index. Each pair is compiled to $c_{b,i}(x_i+\epsilon_b x_{j(i)})$, with addition or subtraction determined by the bank shape. A coefficient-zero conditional wraps each contribution and a static bank dispatch wraps the bank terms. Specialization therefore keeps a single bank branch and removes every pair whose coefficient is zero. The named-parameter binder validates the index. The generic source term is total, with default result zero for an index outside the bank.313 314For each valid static assignment and each dynamic sample window $x$, the convolution dot product agrees with the result of the selected residual function.315\begin{align*}316\sum_{i=0}^{m-1}h_{b,i}x_i317&= \sum_{i=0}^{q-1}\bigl(c_{b,i}x_i+318 \epsilon_b c_{b,i}x_{j(i)}\bigr)+\delta_b(x)\\319&= \sum_{i=0}^{q-1}c_{b,i}(x_i+\epsilon_b x_{j(i)})+\delta_b(x).320\end{align*}321Here $\delta_b(x)$ is the center contribution when present and zero otherwise. The first equality partitions the coordinate projections into pairs and a possible singleton. The second is distributivity in $R$. Each remaining summand uses at most one multiplication per pair. The domain compiler constructs this factored expression before CATPE specializes it.322 323\subsection{An ensemble of decision trees}324 325A forest specification fixes the number of sample ports, an ordered set $F$ of features, and a list of finite binary tree shapes. Each feature $i\in F$ specifies two input projections $\pi_{a_i}$ and $\pi_{b_i}$. Static scale $s_i$ and bias $d_i$ give the affine feature326\[327\alpha_i(x)=\pi_{a_i}(x)+s_i\pi_{b_i}(x)+d_i\in R.328\]329The shapes are the initial algebra of $X\mapsto 1+F\times X\times X$ in sets. An occurrence of a leaf receives a static output word. An occurrence of a split receives a static cut word and compares the indicated feature to it. Each tree also has a static inclusion flag, with zero meaning disabled. The source uses a nested chain of \texttt{let} bindings for feature values. The branches refer to the bound features, so a surviving feature is shared by every split citing it.330 331For a fixed assignment to all settings, define the score of each tree recursively. A leaf yields its assigned word. A split with feature $i$, cut $\tau$, and children $L,H$ yields $L$'s score when $\operatorname{sgnrep}(\alpha_i(x))<\operatorname{sgnrep}(\tau)$ and $H$'s score otherwise. The ensemble score is the sum of all enabled scores. This semantics factors through the product map $x\mapsto(\alpha_i(x))_{i\in F}$. The lowering of a leaf is its parameter projection. The lowering of a split composes the relevant feature projection, the signed comparison, and source conditional selection. Induction on the initial-algebra constructors proves equality with the recursive score for every tree. Applying the flag tests and summing then proves equality for the forest. Static specialization removes disabled subtrees. If a feature is unused throughout the residual forest, purity and totality justify removing its binding.332 333The two examples require different categorical structure in the lowering. The filter expresses a ring polynomial using paired coordinate projections. The forest folds a branching inductive shape into a family of morphisms and factors the result through a common product of derived features. Each construction lands in the same typed source fragment, and each residual uses the same Truffle invocation interface.334 335 336\section{Compiling finite-dimensional quantum evolution}337\label{sec:quantum}338 339Let $H$ be a finite-dimensional Hermitian matrix and fix units with340$\hbar=1$. A time interval $t$ specifies341$U(t)=\exp(-itH)\colon\mathcal H\to\mathcal H$.342By the spectral theorem, $U(t)^*U(t)=I$ and343$U(t+s)=U(t)U(s)$. Hamiltonians with different spectra induce different344families of specialization constants. The state is dynamic, so an345individual compiled evolution can be applied to any state of the required346dimension or repeatedly reused in a time-stepping loop.347 348The functor of restriction of scalars from complex to real vector spaces349sends $U=A+iB$ to350\[351 \mathcal R(U)=352 \begin{pmatrix} A&-B\\ B&A\end{pmatrix}.353\]354The ordered basis used by the code interleaves the real and imaginary355coordinates. The displayed block order and the stored order differ by a356permutation of coordinates. For $z=x+iy$,357$U z=(Ax-By)+i(Ay+Bx)$. This identity follows by bilinearity and358$i^2=-1$. It implies359$\mathcal R(UV)=\mathcal R(U)\mathcal R(V)$ and360$\mathcal R(U^*)=\mathcal R(U)^\top$. In particular realification361takes a unitary to an orthogonal operator. This algebraic property362justifies the translation from a complex map to paired real linear forms.363 364The compiler constructs a pair of term templates per row. For row $j$ the365two static parameter lists hold its $A_{jk}$ and $B_{jk}$. The real and366imaginary outputs are built from367\[368\begin{split}369 r_j(x,y)&=\sum_k(A_{jk}x_k-B_{jk}y_k),\\370 i_j(x,y)&=\sum_k(A_{jk}y_k+B_{jk}x_k).371\end{split}372\]373The specification uses a balanced sum with a fixed operation order. The374runtime binds the coefficients, producing $2\dim\mathcal H$ executable375roots. A guest callable vector step holds these roots and supplies the376same state to each. The method uses dense storage and arithmetic,377$O((\dim\mathcal H)^2)$ for a step after coefficient generation. The378precomputation of $U(t)$ is part of the respective domain compiler.379Changing $t$ binds new coefficients.380 381In binary64 this construction evaluates the arithmetic expression that382its source specifies. Orthogonality and group composition hold in exact383real arithmetic. Computing the coefficients, performing products and384sums, and applying many steps introduce rounding. We therefore measure385defects of norm preservation, inverse recovery, and composition and386compare both examples to separately computed dynamical references.387Both quantum examples also measure energy conservation.388 389\section{Compiling free-electron time evolution}390\label{sec:electron}391 392With $\hbar=1$, consider the spatial wavefunction of one free electron on a periodic grid with $N\ge3$ sites, spacing $a>0$, and mass $m>0$. The Hamiltonian is spin independent, so this evolution acts on either spin component. The input to each compiled evolution is a state $\psi\in\mathbb C^N$ with interleaved real and imaginary coordinates. The discretization uses the centered second difference on $\mathbb Z/N\mathbb Z$. Indices are cyclic and the Hamiltonian is393\[394(H\psi)_j=\frac{2\psi_j-\psi_{j-1}-\psi_{j+1}}{2ma^2}.395\]396The lattice evolution solves $i\partial_t\psi=H\psi$ in continuous time. The grid and finite volume specify the spatial model. In particular, for a fixed physical wavenumber $\kappa=2\pi k/(Na)$ along grids of fixed length, its dispersion approaches the continuum value $\kappa^2/(2m)$ with an error of order $a^2$ as $a\to0$.397 398The normalized Fourier basis diagonalizes every circulant operator \cite{strangdct}. For $\omega=\exp(2\pi i/N)$ and $v_k(j)=N^{-1/2}\omega^{jk}$, the two cyclic shifts multiply $v_k$ by $\omega^{k}$ and $\omega^{-k}$. This gives399\[400Hv_k=E_k v_k,\qquad E_k=\frac{2}{ma^2}\sin^2\!\left(\frac{\pi k}{N}\right).401\]402Let $F$ denote the unitary forward Fourier transform whose $k,j$ entry is $N^{-1/2}\omega^{-kj}$. Then