Extended Abstract: Towards a Performance Comparison of Syntax and Type-Directed NbE
Chester J.F. Gould, William J. Bowman · 2025
Read Extended Abstract: Towards a Performance Comparison of Syntax and Type-Directed NbE by Chester J.F. Gould, William J. Bowman (2025) 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-2509-13489.txt.
Introduction
Chester J. F. Gould and William J. Bowman present work in progress on comparing type equality checking methods in a 2025 extended abstract. Every dependent type checker must decide, again and again, whether two types count as equal. That single step sits at the heart of checking. A piece of folklore surrounds it. Equality driven by syntax is said to run faster. Equality driven by types is said to say more.
Real systems pick one road or the other, never both, so the two can never be raced on the same track. Gould and Bowman are building that track: a realistic platform where both approaches run side by side, apples to apples. With it they can measure how much slower the type-directed road really is. They can also study where the time goes, and what might win some of it back.
Catalog record
| CREATOR | Chester J.F. Gould, William J. Bowman |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-13489
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Extended Abstract: Towards a Performance Comparison of Syntax and Type-Directed NbE Chester J.F. Gould, William J. Bowman Abstract . A key part of any dependent type-checker is the method for checking whether two types are equal. A common claim is that syntax-directed equality is more performant, although type-directed equality is more expressive. However, this claim is difficult to make precise, since implementations choose only one or the other approach, making a direct comparison impossible. We present some work-in-progress developing a realistic platform for direct, apples-to-apples, comparison of the two approaches, quantifying how much slower type-directed equality checking is, and analyzing why and how it can be improved. 1. Introduction Dependently typed languages treat types as first class values, enabling computation in types. Consider the following. int_or_str : (b : Bool) -> (if b then Int else String) int_or_str = \b -> if b then 3141 else "Hello, World!" When applied to true , it will return the Int 3141. When applied to false , it will return the String "Hello, World!" . We can even express such facts as types. int_or_str_theorem : int_or_str(true) = 3141 int_or_str_theorem = reflexivity Type-checking these requires deciding equality between two expressions. The typing judgement \Gamma\vdash e:A (expression e has type A with free variables \Gamma ), must reason about equality of expressions. In the true branch of int_or_str we make the judgement \vdash 3141:\\ ({\small\verb|if true then Int else String|}) , and must reason that this type is equal to Int . Equality is captured by judgements of the form \Gamma\vdash e_{1}=e_{2}:A ( e_{1} is equal to e_{2} at type A with free variables \Gamma ). The two judgements interact through the following typing rule. \frac{\Gamma\vdash e:B\quad\Gamma\vdash A=B:\texttt{Type}}{\Gamma\vdash e:A}\quad\textsc{left=Conv} An expression e of type B can also be considered of type A so long as A and B are equal. How to implement decision procedures for judgements of this form is an oft debated topic. Our example relies on the following two rules. \frac{}{\Gamma\vdash(\text{\textbackslash}x\to b)a=b[x\mapsto a]:A}\quad\textsc{left=App-$\beta$}\par\frac{}{\Gamma\vdash\text{if true then }a\text{ else }b=a:A}\quad\textsc{left=if-true-$\beta$} Both are \beta rules, which capture the execution of a program. App- \beta is the familiar \lambda -calculus \beta rule, where a function literal applied to an argument is equal to the body of the function with the argument substituted for the parameter variable. These rules are syntax-directed; we can see the type A is not relevant in either rule. Another group of rules, called \eta rules, give us additional equalities that rely on the type, rather than capturing the execution of a program. \frac{\Gamma,x:A\vdash f\hskip 1.99997ptx=g\hskip 1.99997ptx:B}{\Gamma\vdash f=g:(x:A)\to B}\quad\textsc{left=Fun-$\eta$}\par\frac{}{\Gamma\vdash a=b:\text{Unit}}\quad\textsc{left=Unit-$\eta$} The Fun- \eta rule looks similar to the function extensionality principle and says that two functions are definitionally equal if they are definitionally equal when applied to an abstract variable. The Unit- \eta rule implies the Unit type has the single element \langle\rangle . Since there is only one element of the Unit type, all expressions of Unit type are equal. This rule lets us type-check the following program. unit_contractible : (x : Unit) -> (y : Unit) -> x = y unit_contractible x y = reflexivity As Abel 2013 shows, a widely used approach for deciding judgemental equality is normalization by evaluation (NbE). An NbE algorithm maps the syntax of a language into a semantic domain and then back into syntax. Since judgementally equal pieces of syntax will be equal in the semantic domain, going there, then back into syntax makes them syntactically equal (a process referred to as “normalization"). NbE uses this process to turn the problem of deciding judgemental equality into one of giving semantics to syntax and then deciding syntactic equality. Simple NbE algorithms implement an environment passing interpreter such as Coquand 1996 or Chapman et al. 2005 . These interpreters can have performance competitive with the widely used dependently typed languages, as Kovács 2023 demonstrates with smalltt, a small but realistic, and very performant, type-checker for a dependent type theory. However, another design decision remains: how to handle the type-directed \eta rules (if at all). Claims abound that syntax-directed approaches are more performant than those that integrate type-directed rules. But how much more performant, in what situations, and is that performance worth the loss in expressivity? It could be the case that handling type-directed rules causes untenable performance loss, or requires unwieldy implementation, meaning theories which require them should be avoided. On the other hand, perhaps handling type-directed rules has only minimal performance cost and is quite simple to implement. The problem is that no apples-to-apples comparison between type-directed and syntax-directed approaches has been made, and so there is currently no good way to decide between them beyond consulting a developer who has tried both, in an unknown context, and applying their subjective judgement to your context. We would like to make these folklore claims more precise, and enable better informed choices. 2. Benchmarking Platform Our approach is to compare two versions of smalltt ( Kovács 2023 ) . The existing version uses a syntax-directed approach with \eta rules for functions. We implement two modified versions of smalltt with type-directed rules, trying to stay true to the performance consideration of smalltt. The first merely transitions to a type-directed approach, while the second extends the type theory with \eta for dependent pairs ( \Sigma ) and Unit. Our two modified versions are available at https://github.com/ChesterJFGould/smalltt on the master and sigma-unit branches respectively. To implement the type-directed algorithm, we follow the approach of Chapman et al. 2005 , who provide a systematic approach to derive an algorithm that supports type-directed rules by giving the type of the two normalized terms as an argument to the procedure deciding their equality. The procedure can then inspect the type when it comes across a situation in which a type-directed rule is applicable. This algorithm uses an approach similar to bidirectional typing ( Dunfield and Krishnaswami 2021 ) to reduce the amount of type information that is carried through the equality judgement. Chapman et al. 2005 divide equality into two judgements: the check judgement \Gamma\vdash n=n^{\prime}\Leftarrow A , which takes a type as an input and in which \eta rules can be implemented, and the synth judgement \Gamma\vdash\nu=\nu^{\prime}\Rightarrow A which checks two neutral forms for equality and additionally outputs their type. We give an excerpt of the type-directed equality rules in Figure 1 . In these judgements, the metavariable n indicates terms that are normal with respect to \beta rules, while \nu indicates a neutral term, that is, a series of destructors applied to a free variable. \frac{\text{fst }n\Downarrow n_{f}\quad\text{fst }n^{\prime}\Downarrow n_{f}^{\prime}\quad\Gamma\vdash n_{f}=n_{f}^{\prime}\Leftarrow n_{1}\quad e_{2}[x\mapsto n_{f}]\Downarrow n_{2}\quad\text{snd }n\Downarrow n_{s}\quad\text{snd }n^{\prime}\Downarrow n_{s}^{\prime}\quad\Gamma\vdash n_{s}=n_{s}^{\prime}\Leftarrow n_{2}}{\Gamma\vdash n=n^{\prime}\Leftarrow\Sigma x:n_{1}.\text{ }e_{2}}\quad\textsc{left=$\Sigma$-$\eta$}\par\frac{\Gamma\vdash n_{1}=n_{1}^{\prime}\Leftarrow\text{Type}\qquad\Gamma\vdash y\text{ fresh}\qquad e_{2}[x\mapsto y]\Downarrow n_{2}\quad e_{2}^{\prime}[x^{\prime}\mapsto y]\Downarrow n_{2}^{\prime}\quad\Gamma\vdash n_{2}=n_{2}^{\prime}\Leftarrow\text{Type}}{\Gamma\vdash\Sigma x:n_{1}.\text{ }e_{2}=\Sigma x^{\prime}:n_{1}^{\prime}.\text{ }e_{2}^{\prime}\Leftarrow\text{Type}}\quad\textsc{left=$\Sigma$-T${=}$}\par\frac{\Gamma\vdash\nu=\nu^{\prime}\Rightarrow\Sigma x:n_{1}.\text{ }e_{2}}{\Gamma\vdash\text{fst }\nu=\text{fst }\nu^{\prime}\Rightarrow n_{1}}\quad\textsc{left=$\Sigma$-E1${=}$}\par\frac{\Gamma\vdash\nu=\nu^{\prime}\Rightarrow\Sigma x:n_{1}.\text{ }e_{2}\quad e_{2}[x\mapsto\text{fst }\nu]\Downarrow n_{2}}{\Gamma\vdash\text{snd }\nu=\text{snd }\nu^{\prime}\Rightarrow n_{2}}\quad\textsc{left=$\Sigma$-E2${=}$}\par\frac{}{\Gamma\vdash n=n^{\prime}\Leftarrow\text{Unit}}\qquad\frac{}{\Gamma\vdash\text{Unit}=\text{Unit}\Leftarrow\text{Type}} Figure 1. Unit and Dependent Pair Type Directed Equality In Figure 2 , we present an overview of key definitions from smalltt that implement judgmental equality, and the changes we made to implement type-directed equality. We have simplified the code shown here slightly to elide meta variables and unification, which are irrelevant to our purposes, but the implementation supports these. ⬇ data Tm = LocalVar Ix | App Tm Tm