Pith. sign in

REVIEW 3 major objections 6 minor 40 references

Definitional Inversion, Without Normalisation

T0 review · 3 major / 6 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A domain-theoretic model proves definitional inversion for dependent types without any normalisation theorem, even in the presence of η laws and type-in-type.

desk verdict Promising new technique for definitional inversion without normalisation, but the central adequacy lemma is unproved in the text and the mechanisations are not yet inspectable — worth a real refereeing. read the letter →

arxiv 2607.13662 v1 pith:KSI45UPV submitted 2026-07-15 cs.LO cs.PL

Mario Carneiro , Thierry Coquand , Adrien Frabetti Mathieu , Meven Lennon-Bertrand , Paul-André Melliès , Stephanie Weirich This is my paper · ORCID
classification cs.LOcs.PL MSC 03B1568Q55
keywords definitionalinversioninjectivityoftypeconstructorsdomaintheoryfinitaryprojectorslogicalrelationsetalawstype-in-typesubjectreduction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's central claim is that definitional inversion — the principle that equal type-forming expressions have equal parts, for example Πx:A B ≡ Πx:A' B' forces A ≡ A' and B ≡ B' — can be proved by a domain-theoretic logical relation indexed by compact elements, with no appeal to normalisation. This matters because normalisation fails for type theories with type-in-type, for dependently typed languages with general recursion, and is unavailable inside a logic trying to reason about itself. The method handles η laws, which have long defeated confluence-based arguments, and scales to sums, unit, fixed points, natural numbers, identity types, and a universe of proof-irrelevant propositions. The immediate corollaries are subject reduction and progress for a minimal dependent type theory with universe-in-universe, β, and η.

What carries the argument

The key object is a recursive domain D, realised through its compact elements (a conditional upper semi-lattice) built as a colimit of finite stages. Its coalesced sum validates η by identifying λ(⊥) with ⊥. Types are finitary projectors, i.e. continuous idempotent approximations; semantic typing u : a is a stage-indexed relation on compact elements. The logical relation Γ ⊨ A ≡ A' type | a and Γ ⊨ M ≡ N : A | u:a is defined by recursion on the stage and on the compact witnesses, with a degenerate clause at ⊥; the Π-clause requires both syntaxes to head-reduce to Π-types with related parts. Adequacy (Theorems 2.35 and 2.36) is the bridge from witnesses to syntax, proved by induction on deriv

What would settle it

One concrete way to settle it: in the paper's system, search for a conversion Γ ⊢ Πx:A B ≡ Πx:A' B' with A and A' not convertible; if such a derivation exists, Corollary 2.37 is false. Short of that, inspect the mechanised proof of adequacy for a single unclosed case in the induction on conversion — one rule whose logical-relation closure fails would collapse subject reduction and progress along with injectivity.

Watch

Extended reading notes

Core claim

The paper establishes that in a dependent type theory with universe-in-universe plus β and η, equality Γ ⊢ Πx:A B ≡ Πx:A' B' : 𝒰 forces A ≡ A' and B ≡ B', and from this derives subject reduction and progress. Types are interpreted as finitary projectors on a recursive domain built from compact elements; a stage-indexed semantic typing and a logical relation indexed by compact witnesses, proved adequate by induction, turn semantic witnesses into object-level conversions. The same model yields disjointness of Π and 𝒰 and refutes definitional UIP for the identity type.

Load-bearing premise

The proof stands or falls on the fundamental lemma (Adequacy): the induction showing that every typing and conversion rule, including η, lands in the logical relation at the appropriate compact witnesses, with the listed closure laws (symmetry, transitivity, monotonicity, joins, head reduction) verified; the paper outsources the verification to the accompanying mechanisations rather than displaying the induction.

Editorial extensions

If this is right

  • In the minimal system with type-in-type and η, every equality between Π-types decomposes into equalities of domains and codomains (Corollary 2.37).
  • Subject reduction and progress follow, giving a well-behaved operational semantics for a theory that was previously out of reach of confluence- and normalisation-based tools.
  • The construction extends to Σ with surjective pairing, unit with η, a fixed-point combinator, natural numbers with large elimination, the identity type with transport, and a Prop universe with definitional proof irrelevance; it can also read off sort injectivity for universe hierarchies.
  • Because the ambient logic is weak (essentially induction on natural numbers), the method is usable in projects that formalise a type theory inside itself, where proving normalisation is impossible.
  • The model refutes the rule of definitional uniqueness of identity proofs, showing that the identity type is genuinely proof-relevant in this setting.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: the same 'add a code, add a logical-relation clause, extend soundness and adequacy' recipe should transfer to coinductive types, quotient types, or gradual dependent types, all areas where normalisation is unavailable; the paper targets this direction but does not prove it.
  • Inference: because the compact witness functions as a generalised step index, the construction suggests a way to derive a conversion-checking algorithm or completeness statement from the logical relation, which the paper leaves unexplored.
  • Inference: the model can only refute equality rules, never inhabitation (every semantic type is inhabited by ⊥), so it cannot say anything about propositional consistency; users of the technique should not expect consistency-style meta-theorems from it.
  • Inference: the paper's open problem — proving definitional inversion for neutral terms — could be attacked by combining this domain model with a separate typed confluence argument, since the two tools cover complementary parts of the conversion relation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper introduces a domain-theoretic proof technique for establishing definitional inversion principles (injectivity and no-confusion of type constructors) in dependent type theories without relying on normalization. The technique is demonstrated on MLTTη, a type theory with Π-types, a universe with type-in-type, and β/η conversion, which is both non-normalizing and has η laws—features that defeat confluence-based and normalization-based approaches. The authors build a finitary projection model of the syntax, define a stage-indexed logical relation over compact elements of a recursive domain, and claim an adequacy/fundamental lemma (Theorems 2.35–2.36) from which they derive injectivity of Π (Corollary 2.37), subject reduction (Theorem 2.38), and progress (Theorem 2.39). They then sketch extensions to Σ-types, unit type, fixed points, natural numbers, identity types, and a strict Prop universe. Three mechanized proofs (Agda, Lean, Rocq) are claimed, but only as anonymized supplementary material.

Significance. If the central adequacy theorem is correct, this is a significant advance for the metatheory of dependent type systems. It offers a route to injectivity/no-confusion in non-normalising systems with η laws, using only simple induction on natural numbers in a weak ambient logic, and with claimed machine-checked implementations in three proof assistants. The potential applications to verified kernel projects such as Lean4Lean and MetaRocq are real and well-motivated. The main weakness is that the crucial Theorem 2.35–2.36 is stated without proof in the text and the mechanized artifacts are not available for inspection in this version, so the core result is not independently verifiable from the paper alone. The extensions in Section 3 are also presented as sketches rather than full proofs.

major comments (3)
  1. [§2.7–2.8, Thms 2.35–2.36, Cor 2.37] The central claim rests on the Adequacy and Fundamental Lemma (Theorems 2.35–2.36), which are stated without proof. The text only says they are proved by induction and verified in the supplementary mechanizations. Corollary 2.37 derives injectivity of Π directly from Theorem 2.36, so any gap in this induction—particularly in the η-law or head-expansion cases—invalidates the main result. A journal version must either prove these theorems in the text/appendix or make the mechanized proofs available and inspectable. As it stands, the central derivation is not independently verifiable from the paper alone.
  2. [§2.7, closure properties (Symm–Join, Cor 2.33, Lemma 2.34)] The listed properties of the logical relation are stated without proof. The fundamental lemma proceeds by induction on conversion derivations and necessarily uses all of these closures; for example, the Head Reduction lemma (2.34) is what makes the η-rule and head-expansion cases tractable. A failure in any one of these closures would break Theorem 2.36. Please include at least proof sketches or an explicit statement of which mechanization proves which property.
  3. [§4, supplementary material / coverage table] The formalizations are anonymized and not available for inspection in this submission. Moreover, the coverage table shows non-uniform coverage (e.g., Rocq's row for the extensions is marked '0 and S only', and Lean's Id is 'transport only'), and the Rocq development relies on three axioms (funext, propext, proof irrelevance). The reader cannot check that the core MLTTη result—which all three systems are claimed to verify—is actually mechanized. Please provide the artifacts or a detailed proof, and clarify the table entries.
minor comments (6)
  1. [Throughout] The small-caps macros produce non-words: PRoof, TheoRem, CoRollaRy, PRoposition, PRop, etc. Standardize these for final publication.
  2. [§2.8, proof of Cor 2.37] The proof should justify why Π(⊥,⊥) satisfies the preconditions of Theorem 2.36: it must be shown that Π(⊥,⊥) ≤ JΠx:A B K⊥ and Π(⊥,⊥) : U. This is not explicit.
  3. [§4, Table 1] The coverage table should state explicitly what the symbols ('3', '0') mean for each cell, and which proof-assistant files correspond to which extension. This is necessary to interpret the claimed mechanization coverage.
  4. [§3] The extensions are presented as sketches; if they are meant as concrete contributions, add at least a map from each extension to the corresponding mechanization files or state clearly which results are proved versus conjectured.
  5. [§2.7] The 'grey premises' convention should be rendered robustly (e.g., with italics or brackets) so that the distinction survives black-and-white printing or ordinary PDF viewers.
  6. [References] Several references are to preprints or drafts (Felicissimo–Winterhalter 2026, Liu–Weirich 2026, Felicissimo et al. 2026). Add DOIs or stable identifiers where available, and mark those still in submission.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the Π-injectivity proof uses a standard logical-relations argument; the main text gap is that the fundamental lemma is asserted rather than proved, which is a verification risk, not a circular reduction.

full rationale

The derivation chain is: build a domain model (Thm 2.31 soundness), define a logical relation by recursion on semantic witnesses (Sec. 2.6), assert adequacy/fundamental lemmas (Thms 2.35–2.36), then read off injectivity (Cor. 2.37). The Π-clause of the logical relation literally contains the target syntactic equalities, and Cor. 2.37 obtains them 'from which the definition of the logical relation implies in particular Γ ⊢ A ≡ A′ : 𝒰 and Γ, x:A ⊢ B ≡ B′ : 𝒰.' This is not circular in the logical-relations method: the relation is a defined predicate on semantic witnesses, not an axiom that all convertible types satisfy it. The content is in the fundamental lemma, which the paper states without an in-text proof but says is 'proven by induction on the syntactic typing/conversion judgement' (Sec. 4) and checked in the Agda/Lean/Rocq mechanizations. If that induction or the closure properties of Sec. 2.7 were wrong, the result would fail; but that is an omitted-proof / reproducibility gap, not a self-definitional or fitted-input circularity. No parameter is fitted to make the conclusion hold, and the conclusions are not assumed among the inputs. Self-citations (Coquand–Huber 2018, Carneiro 2024, Sozeau et al. 2025, Liu–Weirich 2026) are used for context, motivation, and provenance of the domain-theoretic idea, not as the load-bearing justification of injectivity. The most serious issue is that Theorems 2.35–2.36 and the logical-relation closure properties are asserted rather than demonstrated in this version, with the supporting mechanizations anonymized; this is a verification concern that should be addressed, but it does not make the derivation circular.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters; no invented entities. The technique relies on standard domain theory (CUSL, step functions, ideal completion, fixed points of continuous functors), the chosen syntactic presentation of MLTTη with typed conversion and U:U, and the ambient formalisms used for the three mechanizations (with Rocq's explicit axioms).

assumptions (3)
  • standard math Standard domain theory: CUSL/Scott domain equivalence, step functions as compact maps, existence of the least fixed point of the continuous functor F(X)=(X⇒X)+↑(X×(X⇒X))+↑1.
    Used to construct C and D and to justify λ(⊥)=⊥ (coalesced sum) and the separation of Π and U in Section 2.1; presented as background, not proved in the paper.
  • domain assumption The object type theory is presented with conversion as a typed judgement (Fig. 3), with β/η rules and U:U, and with a deterministic head-reduction inside conversion.
    The technique is stated for this presentation; the paper explicitly distinguishes it from untyped/PTS presentations (footnote 3) and notes subject reduction was open for it.
  • domain assumption The formalizations' ambient systems (Agda, Lean, Rocq) provide the required inductive types/quotients (or setoids) and natural-number induction; the Rocq version additionally assumes dependent functional extensionality, propositional extensionality, and proof irrelevance.
    The paper claims the proof needs only basic natural-number induction, but the actual machine-checked proofs run in systems with additional infrastructure and axioms, acknowledged in Section 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Definitional Inversion, Without Normalisation." pith.science (2026). https://pith.science/paper/KSI45UPV

@misc{pith2026260713662,
  author       = {Pith},
  title        = {Pith review of: Definitional Inversion, Without Normalisation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KSI45UPV}},
  note         = {Machine review of arXiv:2607.13662}
}
abstract

We contribute a new proof technique, based on domain theory, to prove key meta-theoretic properties of dependent type systems: definitional inversion properties, i.e. injectivity and no-confusion of type constructors. This proof technique is independent of normalisation, and indeed applies even for the "type-in-type" rule of Martin-L\"of's original type theory. Our proof is the first to establish injectivity of type constructors for such a system in the presence of $\eta$ laws. More generally, the technique is motivated by, and intended for, the metatheory of systems such as Idris, Lean, or dependent Haskell, whose underlying type theory is known to be non-normalising, as well as projects such as MetaRocq or Lean4Lean, where G\"odel's second incompleteness theorem means we cannot show normalisation of the object logic in itself. We showcase the method on a small type theory, then explain how it extends to more ambitious extensions.

Figures

Figures reproduced from arXiv: 2607.13662 by the authors.

Figure 1
Figure 1. Representation of D The insight is that to validate η for functions we should identify ⊥ and λ 𝑥.⊥: both correspond to a function which diverges on all arguments, thus no observation can distinguish them. On the contrary, Π ⊥ ⊥ contains observable information: that the type is a Π-type. Standard results in domain theory [Scott 1981; Smyth and Plotkin 1982] allow us to construct a solution to such an equation by inte… view at source ↗
Figure 2
Figure 2. Semantic typing rules 2.2 Semantic Typing The domain D will give us a good structure in which we can interpret terms of MLTT𝜂 . However, before moving to that model we also need to explain how to interpret the typing relation. To do this, we define a semantic typing relation on elements of C𝑛 , in [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Selected typing rules of MLTT𝜂 Recall the application operator app ∈ D → D → D from Section 2.1; concretely, app(λ𝑓 , 𝑢) = 𝑓 (𝑢) and app(𝑣, 𝑢) = ⊥ otherwise. By continuity of Fp, the maps p𝑛 lift to a single p : D → Fp D, satisfying the following equations: p U U = U p U (Π(𝛼, 𝛽)) = Π(p U 𝛼, 𝑢 ↦ p U(𝛽(p 𝛼 𝑢))) p (Π(𝛼, 𝛽)) 𝑓 = 𝑢 ↦ p (𝛽 (p 𝛼 𝑢)) (app(𝑓 , p 𝛼 𝑢)) p 𝛼 𝛽 = ⊥ in all other cases. Composing the embeddings 𝑒… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Definition of the semantics of a term as a predicate on compacts, and description as a domain element [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 15 canonical work pages

  1. [1]

    Napoli: Bibliopolis. Nancy J. McCracken. 1982.A Finitary Retract Model for the Polymorphic Lambda-Calculus. Tech. rep. Syracuse University. Albert R. Meyer and Mark B. Reinhold

    1982

  2. [5]

    Remarks on the equational theory of non-normalizing pure type systems

    “Remarks on the equational theory of non-normalizing pure type systems.” Journal of Functional Programming, 16, 2, 137–155. doi:10.1017/S0956796803004726. Rafaël Bocquet, Ambrus Kaposi, and Christian Sattler

    work page doi:10.1017/s0956796803004726

  3. [10]

    Mario Carneiro

    Digital Equip- ment Corporation Systems Research Center, (May 1986). Mario Carneiro. Mar. 21, 2024.Lean4Lean: Towards a formalized metatheory for the Lean theorem prover. (Mar. 21, 2024). arXiv: 2403.14064 [cs.PL]. doi:10.48550/ARXIV.2403.14064. Mario Carneiro

    arXiv doi:10.48550/arxiv.2403.14064 1986

  4. [19]

    Implementing a Modal Dependent Type Theory

    “Implementing a Modal Dependent Type Theory.”Proc. ACM Program. Lang., 3, ICFP, Article 107, (July 2019), 29 pages. doi:10.1145/3341711. Robert Harper and Frank Pfenning. Jan

    work page doi:10.1145/3341711 2019

  5. [22]

    Iris from the ground up: A modular foundation for higher-order concurrent separation logic

    “Iris from the ground up: A modular foundation for higher-order concurrent separation logic.”Journal of Functional Programming, 28, e20. doi:10.1017/S0956796818000151. Jan Willem Klop

    doi:10.1017/s0956796818000151

  6. [23]

    Using Information Systems to Solve Recursive Domain Equations

    “Using Information Systems to Solve Recursive Domain Equations.” Information and Computation, 91, 2, 232–258. doi:https://doi.org/10.1016/0890-5401(91)90068-D. ThéoLaurent,MevenLennon-Bertrand,andKenjiMaillard.2024.“DefinitionalFunctorialityforDependent(Sub)Types.”In: 33rd European Symposium on Programming, ESOP 2024(Lecture Notes in Computer Science). Ed...

    work page doi:10.1016/0890-5401(91)90068-d 2024

  7. [26]

    Gradualizing the Calculus of In- ductive Constructions

    “Gradualizing the Calculus of In- ductive Constructions.”ACM Transactions on Programming Languages and Systems, 44, 2, Article 7, (Apr. 2022), 82 pages. doi:10.1145/3495528. Bohdan Liesnikov and Jesper Cockx

    work page doi:10.1145/3495528 2022

  8. [27]

    Algorithmic Conversion with Surjective Pairing: A Syntactic and Untyped Ap- proach

    “Algorithmic Conversion with Surjective Pairing: A Syntactic and Untyped Ap- proach.”Proceedings of the ACM on Programming Languages, 10, POPL, 865–894. doi:10.1145/3776672. Per Martin-Löf

    work page doi:10.1145/3776672

Show all 40 references
  1. [28]

    A theory of types

    “A theory of types.” Preprint. (1971). Per Martin-Löf and Giovanni Sambin. 1984.Intuitionistic Type Theory. Studies in Proof Theory

    1971

  2. [30]

    ”Type” is not a type

    “”Type” is not a type.” In:Proceedings of the 13th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL ’86). ACM, 287–295. doi:10.1145/512644.512671. Anja Petković Komel

  3. [35]

    Correct and Complete Type Checking and Certified Erasure for Coq, in Coq

    “Correct and Complete Type Checking and Certified Erasure for Coq, in Coq.”Journal of the ACM, (Jan. 2025). doi:10.1145/3706056. 28 Carneiro, Coquand, Frabetti Mathieu, Lennon-Bertrand, Melliès and Weirich Kathrin Stark, Steven Schäfer, and Jonas Kaiser. Jan

    2025 doi

  4. [36]

    Autosubst 2: reasoning with multi-sorted de Bruijn terms and vector substitutions

    “Autosubst 2: reasoning with multi-sorted de Bruijn terms and vector substitutions.” In:Proceedings of the 8th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP ’19). ACM, (Jan. 2019), 166–180. doi:10.1145/3293880.3294101. Jonathan Sterling. Nov

    2019

  5. [40]

    A Syntactic Approach to Type Soundness

    “A Syntactic Approach to Type Soundness.”Information and Computation, 115, 1, 38–94. doi:10.1006/inco.1994.1093

    1994

  6. [125]

    Luca Cardelli

    Springer, Berlin, 29–61. Luca Cardelli. May 1986.A polymorphic lambda-calculus with Type:Type.Tech. rep. SRC Research Report

    1986

  7. [260]

    TheMathematicalLanguageAUTOMATH,ItsUsage,andSomeofItsExtensions

    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 18:1–18:23. doi:10.4230/LIPICS.FSCD.2023.18. NicolaasGovertdeBruijn.1970.“TheMathematicalLanguageAUTOMATH,ItsUsage,andSomeofItsExtensions.”In: Sym- posium on Automatic Demonstration(Lecture Notes in Mathematics). Ed. by M. Lau...

    2023 doi

  8. [337]

    isbn: 978-3-95977- 374-4

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 27:1–27:23. isbn: 978-3-95977- 374-4. doi:10.4230/LIPIcs.FSCD.2025.27. Meven Lennon-Bertrand, Kenji Maillard, Nicolas Tabareau, and Éric Tanter. Apr

    2025 doi

  9. [417]

    doi:10.1007/3-540-52335-9_47

    Springer, 50–66. doi:10.1007/3-540-52335-9_47. Peter Dybjer. June

    doi

  10. [1956]

    On the Axiom of Extensionality. Part I

    “On the Axiom of Extensionality. Part I.”The Journal of Symbolic Logic, 21, 1, 36–48. doi:10.2307/226

    doi

  11. [1967]

    Intensional interpretations of functionals of finite type I

    “Intensional interpretations of functionals of finite type I.”The journal of symbolic logic, 32, 2, 198–212. The Univalent Foundations Program. 2013.Homotopy Type Theory: Univalent Foundations of Mathematics. Institute for Advanced Study.https://homotopytypetheory.org/book. St...

    2013

  12. [1971]

    Some Extensional Term Models for Combinatory Logics and Lambda-Calculi

    “Some Extensional Term Models for Combinatory Logics and Lambda-Calculi.” PhD thesis. Rijksuniversiteit Utrecht, (June 1971). Gilles Barthe and Thierry Coquand

    1971

  13. [1982]

    The Category-Theoretic Solution of Recursive Domain Equations

    “The Category-Theoretic Solution of Recursive Domain Equations.”SIAM Journal on Computing, 11, 4, 761–783. doi:10.1137/0211062. Matthieu Sozeau, Yannick Forster, Meven Lennon-Bertrand, Jakob Nielsen, Nicolas Tabareau, and Théo Winterhalter. Jan

    doi

  14. [1986]

    The System F of Variable Types, Fifteen Years Later

    “The System F of Variable Types, Fifteen Years Later.”Theoretical Computer Science, 45, 2, 159–192. doi:10.1016/0304-3975(86)90044-7. Daniel Gratzer, Jonathan Sterling, and Lars Birkedal. July

    doi

  15. [1989]

    Typechecking is Undecidable when ‘Type’ is a Type

    “Typechecking is Undecidable when ‘Type’ is a Type.” Master’s thesis. Massachusetts Institute of Technology, Cambridge, MA. Dana S. Scott. May 1981.Lectures on a Mathematical Theory of Computation. Tech. rep. PRG-19. Oxford University Comput- ing Laboratory, Programming Resear...

    1981

  16. [1991]

    First steps in synthetic domain theory

    “First steps in synthetic domain theory.” In:Category Theory. Springer Berlin Heidelberg, 131–156. isbn: 9783540464358. doi:10.1007/bfb0084217. The Idris Community. 2026.Idris 2 Reference Manual – FAQ. Does Idris have universe polymorphism? What is the type of Type? https://id...

    2026 doi

  17. [1994]

    On the Church-Rosser Property for Expressive Type Systems and its Consequences for their Metatheoretic Study

    “On the Church-Rosser Property for Expressive Type Systems and its Consequences for their Metatheoretic Study.” In:Proceedings of the Ninth Annual IEEE Symposium on Logic in Computer Science (LICS ’94). IEEE Computer Society Press, Paris, France, (July 1994), 320–329. Jean-Yve...

    1994

  18. [1998]

    Cayenne—a language with dependent types

    “Cayenne—a language with dependent types.” In:Proceedings of the Third ACM SIGPLAN Inter- national Conference on Functional Programming(ICFP ’98). Association for Computing Machinery, Baltimore, Maryland, USA, 239–250. isbn: 1581130244. doi:10.1145/289423.289451. Henk Barendregt

  19. [2000]

    A General Formulation of Simultaneous Inductive-Recursive Definitions in Type Theory

    “A General Formulation of Simultaneous Inductive-Recursive Definitions in Type Theory.”Journal of Symbolic Logic, 65, (June 2000). doi:10.2307/2586554. Joseph Eremondi, Ronald Garcia, and Éric Tanter

    doi

  20. [2004]

    The Origins of Structural Operational Semantics

    “The Origins of Structural Operational Semantics.”The Journal of Logic and Algebraic Programming, 60–61, 3–15. doi:10.1016/j.jlap.2004.03.009. Mark B. Reinhold

    2004 doi

  21. [2005]

    On equivalence and canonical forms in the LF type theory

    “On equivalence and canonical forms in the LF type theory.”ACM Trans. Comput. Logic, 6, 1, (Jan. 2005), 61–101. doi:10.1145/1042038.1042041. J. M. E. Hyland

    2005

  22. [2006]

    Pure type systems with judgemental equality

    “Pure type systems with judgemental equality.”J. Funct. Program., 16, 2, 219–246. doi:10.1017/S095679 6805005770. ArthurAdjedj,MevenLennon-Bertrand,KenjiMaillard,Pierre-MariePédrot,andLoı̈cPujet.2024.“Martin-LöfàlaCoq.”In: Proceedings of the 13th ACM SIGPLAN International Conf...

    2024

  23. [2012]

    Pure Type System conversion is always typable

    “Pure Type System conversion is always typable.”J. Funct. Program., 22, 2, 153–180. doi:10.1017/S0956796812000044. M. B. Smyth and Gordon Plotkin

    doi

  24. [2013]

    Normalization by Evaluation: Dependent Types and Impredicativity

    “Normalization by Evaluation: Dependent Types and Impredicativity.” Habilitation Thesis. Institut für Informatik, Ludwig-Maximilians-Universität München. AndreasAbel,JoakimÖhman,andAndreaVezzosi.Dec.2017.“DecidabilityofConversionforTypeTheoryinTypeTheory.” Proc. ACM Program. L...

    2017 doi

  25. [2017]

    A speci- fication for dependent types in Haskell

    “A speci- fication for dependent types in Haskell.”Proc. ACM Program. Lang., 1, ICFP, Article 31, (Aug. 2017), 29 pages. doi:10.11 45/3110275. Eric Wieser

    2017

  26. [2018]

    An Adequacy Theorem for Dependent Type Theory

    “An Adequacy Theorem for Dependent Type Theory.”Theory of Computing Systems, 63, 4, (July 2018), 647–665. doi:10.1007/s00224-018-9879-9. Thierry Coquand and Gérard Huet

    2018 doi

  27. [2019]

    Approximate Normalization for Gradual Dependent Types

    “Approximate Normalization for Gradual Dependent Types.” Proceedings of the ACM on Programming Languages, 3, ICFP, (Aug. 2019). Thiago Felicissimo, Yann Leray, Loı̈c Pujet, Nicolas Tabareau, Éric Tanter, and Théo Winterhalter

    2019

  28. [2021]

    First Steps in Synthetic Tait Computability: The Objective Metatheory of Cubical Type Theory

    “First Steps in Synthetic Tait Computability: The Objective Metatheory of Cubical Type Theory.” Ph.D. Dissertation. Carnegie Mellon University, (Nov. 2021). doi:10.5281/zenodo.6990769. Viggo Stoltenberg-Hansen, Ingrid Lindström, and Edward R. Griffor. 1994.Mathematical Theory ...

    2021 doi

  29. [2022]

    Propositional equality for gradual dependently typed program- ming

    “Propositional equality for gradual dependently typed program- ming.”Proc. ACM Program. Lang., 6, ICFP, 165–193. doi:10.1145/3547627. Joseph Eremondi, Éric Tanter, and Ronald Garcia. Aug

    doi

  30. [2023]

    For the Metatheory of Type Theory, Internal Sconing Is Enough

    “For the Metatheory of Type Theory, Internal Sconing Is Enough.” In:8th International Conference on Formal Structures for Computation and Deduction, FSCD 2023(LIPIcs). Ed. by Marco Gaboardi and Femke van Raamsdonk. Vol

    2023

  31. [2025]

    What Does It Take to Certify a Conversion Checker?

    “What Does It Take to Certify a Conversion Checker?” In:10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)(LeibnizInternationalProceedingsinInformatics(LIPIcs)). Ed. by Maribel Fernández. Vol

    2025

  32. [2026]

    Confluence Techniques for Dependent Type Theory with Typed Conver- sion

    “Confluence Techniques for Dependent Type Theory with Typed Conver- sion.” Draft. (2026).https://inria.hal.science/hal-05520710. Robin O. Gandy

    2026

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.