NSynC: Normalised Synthesis of Computation
Zoey Shepherd, Ohad Kammar, Elizabeth Polgreen · 2026
Read NSynC: Normalised Synthesis of Computation by Zoey Shepherd, Ohad Kammar, Elizabeth Polgreen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30703.txt.
Introduction
Zoey Shepherd, Ohad Kammar and Elizabeth Polgreen speed up program synthesis, the automatic search for a program that meets a specification. Search usually enumerates program syntax, and many syntactically different programs mean the same thing. A synthesiser wastes effort evaluating and rejecting each duplicate separately. Their system, NSynC, enumerates semantics instead: it searches the space of normal forms for a typed lambda calculus with sums.
Because each candidate is semantically unique by construction, every evaluation counts. A top-down, type-directed algorithm steers the search through that normal-form space. On a synthetic benchmark suite, preliminary results showed a geometric-mean speedup of about eight point nine times over the unrestricted syntax-based algorithm. The authors present the approach as synthesis by semantics, trading a harder search space design for freedom from duplicate work. The typed setting also guarantees that every candidate is at least type-correct.
Catalog record
| CREATOR | Zoey Shepherd, Ohad Kammar, Elizabeth Polgreen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30703
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
NSynC: Normalised Synthesis of Computation Zoey Shepherd, Ohad Kammar, Elizabeth Polgreen Abstract Inductive program synthesis algorithms search a space of programs to find one that meets some specification. Enumerating according to the syntax of a programming language leads to a large search space, and hence slow synthesis, due in large part to semantic duplication . A synthesiser may have to evaluate—and reject—multiple semantically identical but syntactically different programs, wasting resources. To avoid this duplication, we present NSynC , a synthesis-by-semantics approach. By enumerating the semantics of the target language directly, we guarantee that each candidate program is semantically unique and that each evaluation of a candidate is meaningful. Specifically, we search the space of normal forms for the simply-typed lambda calculus with sums using a top-down, type-directed synthesis algorithm. Our preliminary results show a geomean speedup of 8.93x on a synthetic benchmark suite over the unrestricted algorithm. Introduction. Program synthesis is the task of taking a program specification to a concrete program that meets it. Deductive approaches (e.g. [ 6 ] ) are limited in what programs they can produce, so search-based approaches like Counter-Example Guided Inductive Synthesis [ 8 ] are more common for modern program synthesis [ 3 ] . These search-based approaches search over syntax . That is, if the syntax of the target language includes the production rule for Booleans \texttt{Bool}\Coloneqq\texttt{True}\>|\>\texttt{False}\>|\>a\>|\>b\>|\>\texttt{Bool}\mathbin{\&}\texttt{Bool}\>|\>\neg\texttt{Bool} , then a naïve synthesiser will consider the syntactically distinct terms a\mathbin{\&}b , b\mathbin{\&}a , a\mathbin{\&}(b\mathbin{\&}\texttt{True}) , \neg(\neg(a\mathbin{\&}b)) , and so on to be distinct "guesses" for a target program of type Bool . Of course, all of these programs are semantically identical, but a synthesiser might have to consider each of them individually to be able to discount them all. Many synthesisers take steps to reduce the impact of semantic duplication. The standard formulation of bottom-up enumeration [ 9 ] removes observationally equivalent programs from its pool at each step, preventing duplicates from surviving for more than one iteration and avoiding construction of terms like a\mathbin{\&}(b\mathbin{\&}\texttt{True}) —but not, say, a\mathbin{\&}b and b\mathbin{\&}a . In Semantics-Guided Synthesis [ 5 ] , semantics are provided to the solver as a logical specification, making the process of ruling out duplicates easier but leaving them in the search space. Our Approach. To fully eliminate semantic duplication, an algorithm would search the space of semantics , rather than syntax. We propose leveraging Normalisation by Evaluation, which constructs unique normal forms for semantic fragments of languages, to provide this search space. As a proof of concept, we present NSynC (Normalised Synthesis of Computation), which synthesises terms of the simply-typed lambda calculus with sums (STLC+) restricted to unique normal forms based on Balat et al. [ 4 ] . NSynC uses the same top-down, type-directed framework as Myth [ 7 ] . STLC+ is a simple but powerful language fragment with a lot of semantic redundancy. It extends STLC, which has anonymous functions, with pairs, a unit type 1 with sole value \langle\rangle , and sum types \tau_{1}+\tau_{2} equipped with left and right injections \texttt{in}_{L}^{\tau_{1}+\tau_{2}}t and \texttt{in}_{R}^{\tau_{1}+\tau_{2}}t and match terms \delta(t,\,x_{1}.t_{1},\,x_{2}.t_{2}) analogous to \displaystyle\texttt{match}\;t\; with t is the scrutinee \displaystyle\texttt{in}_{L}x_{1}\Rightarrow t_{1} where t_{1} is the left branch, binding x_{1} \displaystyle\texttt{in}_{R}x_{2}\Rightarrow t_{2} \displaystyle\text{$t_{2}$ is the right branch, binding $x_{2}$}. We can express Boolean logic using STLC+: type \texttt{Bool}\triangleq 1+1 , and terms \texttt{True}\triangleq\texttt{in}_{L}^{\texttt{Bool}}\langle\rangle , \texttt{False}\triangleq\texttt{in}_{R}^{\texttt{Bool}}\langle\rangle , \texttt{if}\,t\,\texttt{then}\,t_{1}\,\texttt{else}\,t_{2}\triangleq\delta(t,\,x_{1}.t_{1},\,x_{2}.t_{2}) , and a\mathbin{\&}b\triangleq\texttt{if}\,a\,\texttt{then}\,b\,\texttt{else}\,\texttt{False} . Myth already eliminates some of the semantic duplication in STLC+ by synthesising only \beta -normal, \eta -long forms—where every computation is fully simplified and every term is expanded into its maximal structural form. This allows Myth to skip terms like \texttt{if}\,\texttt{True}\,\texttt{then}\,\dots , but it doesn’t fully cover the semantics of match terms, which induce several semantic duplicates like \texttt{if}\,a\,\texttt{then}\,t\,\texttt{else}\,t=t or a\mathbin{\&}b=b\mathbin{\&}a . Balat et al. [ 4 ] account for both \beta - \eta equivalences—as Myth does—and the strong sum extensionality axiom, which is responsible for equalities like above. Their normal forms eliminate redundant branches like \texttt{if}\,a\,\texttt{then}\,t\,\texttt{else}\,t , and our extension with an ordering on scrutinees chooses between, e.g., a\mathbin{\&}b and b\mathbin{\&}a , giving unique normal forms (proof in Appendix 0.B ). These normal forms define a fragment of STLC+ with full expressibility and no semantic duplication, giving an ideal search space for synthesis. NSynC , like Myth , iteratively applies a set of synthesis rules. The derivation of these rules is the core of our approach: a direct application of Myth to STLC+ gets its rules directly from the language’s definition, whereas NSynC draws them from the rules on normal forms. One such rule, for synthesising match terms, is \displaystyle\frac{\begin{array}[]{c}[\mathrm{\Gamma};\tau_{1}+\tau_{2}],\hbox to11.13pt{\vbox to11.11pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{}{}{}\lx@inpgf@ignorespaces\lxSVG@begingroup@{_scopebegin} {}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}\lxSVG@begingroup@{fill} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} \lxSVG@fill\lxSVG@drawpath@unclipped{M 0 0 L 0 15.37 L 15.4 15.37 L 15.4 0 Z}{stroke:none} \lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@begingroup@{_scopebegin} {}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}\lxSVG@begingroup@{fill} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} \lxSVG@fill\lxSVG@drawpath@unclipped{M 0.55 0.55 L 0.55 14.81 L 14.84 14.81 L 14.84 0.55 Z}{stroke:none} \lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@begingroup@{_scopebegin} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} {{{\lx@inpgf@ignorespaces}}{{\lx@inpgf@ignorespaces}}{{\lx@inpgf@ignorespaces}}{{}}{{}}{{}}{{}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{3.4pt}{3.4pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{67}\lxSVG@closescope }\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rightsquigarrow_{\mathrm{M}}M\\ X_{1}\triangleq\{\sigma\cdot[v^{\prime}/x_{1}]\mapsto v\>|\>\sigma\mapsto v\in X,M[\sigma]\rightarrow^{*}\texttt{in}_{L}^{\tau_{1}+\tau_{2}}(v^{\prime})\}\\ X_{2}\triangleq\{\sigma\cdot[v^{\prime}/x_{2}]\mapsto v\>|\>\sigma\mapsto v\in X,M[\sigma]\rightarrow^{*}\texttt{in}_{R}^{\tau_{1}+\tau_{2}}(v^{\prime})\}\\ \forall i\in\{1,2\}.\;X_{i}\neq\emptyset\land X_{i}:\mathrm{Ex}[\mathrm{\Gamma},x_{i}:\tau_{i};\tau],\hbox to35.93pt{\vbox to16.8pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{}{}{}\lx@inpgf@ignorespaces\lxSVG@begingroup@{_scopebegin} {}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}\lxSVG@begingroup@{fill} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} \lxSVG@fill\lxSVG@drawpath@unclipped{M 0 0 L 0 23.25 L 49.71 23.25 L 49.71 0 Z}{stroke:none} \lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@begingroup@{_scopebegin} {}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}\lxSVG@begingroup@{fill} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} \lxSVG@fill\lxSVG@drawpath@unclipped{M 0.55 0.55 L 0.55 22.69 L 49.16 22.69 L 49.16 0.55 Z}{stroke:none} \lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@begingroup@{_scopebegin} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} {{{\lx@inpgf@ignorespaces}}{{\lx@inpgf@ignorespaces}}{{\lx@inpgf@ignorespaces}}{{}}{{}}{{}}{{}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{3.4pt}{5.9pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{67}\lxSVG@closescope }\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rightsquigarrow_{\mathrm{N}}N_{i}\\ \hbox to183.95pt{\vbox to16.8pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{}{}{}\lx@inpgf@ignorespaces\lxSVG@begingroup@{_scopebegin} {}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}\lxSVG@begingroup@{fill} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} \lxSVG@fill\lxSVG@drawpath@unclipped{M 0 0 L 0 23.25 L 254.53 23.25 L 254.53 0 Z}{stroke:none} \lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@begingroup@{_scopebegin} {}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}\lxSVG@begingroup@{fill} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} \lxSVG@fill\lxSVG@drawpath@unclipped{M 0.55 0.55 L 0.55 22.69 L 253.98 22.69 L 253.98 0.55 Z}{stroke:none} \lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@begingroup@{_scopebegin} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} {{{\lx@inpgf@ignorespaces}}{{\lx@inpgf@ignorespaces}}{{\lx@inpgf@ignorespaces}}{{}}{{}}{{}}{{}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{3.4pt}{5.9pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{67}\lxSVG@closescope }\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\end{array}}{X:\mathrm{Ex}[\mathrm{\Gamma};\tau],\hbox to11.13pt{\vbox to11.11pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{}{}{}\lx@inpgf@ignorespaces\lxSVG@begingroup@{_scopebegin} {}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}\lxSVG@begingroup@{fill} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} \lxSVG@fill\lxSVG@drawpath@unclipped{M 0 0 L 0 15.37 L 15.4 15.37 L 15.4 0 Z}{stroke:none} \lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@begingroup@{_scopebegin} {}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}\lxSVG@begingroup@{fill} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} \lxSVG@fill\lxSVG@drawpath@unclipped{M 0.55 0.55 L 0.55 14.81 L 14.84 14.81 L 14.84 0.55 Z}{stroke:none} \lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@begingroup@{_scopebegin} \lxSVG@fill@opacity{1.0}\lxSVG@begingroup@{fill-opacity} {{{\lx@inpgf@ignorespaces}}{{\lx@inpgf@ignorespaces}}{{\lx@inpgf@ignorespaces}}{{}}{{}}{{}}{{}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{3.4pt}{3.4pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{67}\lxSVG@closescope }\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rightsquigarrow_{\mathrm{N}}\delta(M,\,x_{1}.N_{1},\,x_{2}.N_{2})} which begins with producing a scrutinee M of sum type, then separates the example set X accordingly to synthesise branches N_{1} and N_{2} . The boxes highlight our divergence from Myth : the constraints c and M\sqsubset force scrutinees to appear in our chosen order, and the final precondition forces the two branches to be distinct. We show how our other rules differ from Myth in Appendix 0.C.2 . The NSynC algorithm exhaustively applies the synthesis rules until a solution emerges. To avoid non-termination in any subproblem, we impose size limits on neutral terms—that is, scrutinees and terms of base type—and a limit on the depth of match terms. The user inputs a search procedure over these limits, gradually increasing them until NSynC finds a satisfying term. Theoretical Results. We show bounded correctness of NSynC in Appendix 0.C.3 . Specifically, we show bounded completeness : if the normal form of a term t does not have any branching argument—a function that branches on its input and is given as an argument to a higher-order function—then NSynC can produce that normal form. Since Myth has the same restriction, we have that restricting to normal forms maintains solvability. We also show semantic optimality : all of NSynC ’s candidate terms are semantically distinct. Empirical Evaluation. We evaluate NSynC