Reference. A Specification for Dependent Types in Haskell
Cite
Cited by (1)
Internalizing Extensions in Lattices of Type Theories chan-2025-internalizing
Many proof assistants allow the use of features and axioms that increase their expressive power. However, these extensions must be used with care, as some combinations are known to lead to logical inconsistencies. Therefore, proof assistants include mechanisms that track which extensions are used in a proof development or module, ensuring that incompatible extensions are not used simultaneously. Unfortunately, existing extension tracking mechanisms are external to the type system. This means that we cannot specify precisely which extensions a definition depends on. Having the ability to write more precise specifications means we are not picking an overapproximation of the extensions needed, which prevents reusing definitions in the presence of incompatible extensions. Furthermore, we cannot refer to definitions that use incompatible extensions even if they are never used in inconsistent ways. The reasoning principles of one extension therefore cannot be used as a metatheory to reason about the properties of an incompatible extension. In this report, I explore the use of the Dependent Calculus of Indistinguishability (DCOI) by Liu et al. for extension tracking. DCOI is a dependent type system with dependency tracking, where terms and variables are assigned dependency levels alongside their types. These dependency levels form a lattice that describes which levels are permitted to access what. To instead track extensions, each set of extensions would correspond to a dependency level, and the lattice would describe how extensions are permitted to interact.
Cites 61 works (2 here)
With notes (2)
Computational higher-dimensional type theory angiuli-2017-computational
Elimination with a Motive mcbride-2002-elimination
External (59)
- Levity polymorphism (2017)
- Visible Type Application (2016)
- The Calculus of Dependent Lambda Eliminations (2016)
- Unified Syntax with Iso-types (2016)
- Dependent Types in Haskell: Theory and Practice (PhD thesis, Eisenberg) (2016)
- A Small Scale Reflection Extension for the Coq system (INRIA RR-6455) (2016)
- Programming up to Congruence (2015)
- Injective type families for Haskell (2015)
- Safe zero-cost coercions for Haskell (2014)
- Combining proofs and programs in a dependently typed language (2014)
- System F with coercion constraints (2014)
- A Model of Type Theory in Cubical Sets (2014)
- Erasable coercions: a unified approach to type systems (PhD thesis, Cretin) (2014)
- Equational reasoning about programs with general recursion and call-by-value semantics (2013)
- Explicit convertibility proofs in pure type systems (2013)
- System FC with explicit kind equality (2013)
- Idris, a general-purpose dependently typed programming language: Design and implementation (2013)
- Type inference, Haskell and dependent types (2013)
- Giving Haskell a promotion (2012)
- OutsideIn(X) Modular type inference with local assumptions (2011)
- Re: Agda with the excluded middle is inconsistent? URL https://lists.chalmers.se/pipermail/agda/ 2010/001543.html (2010)
- Ott: Effective tool support for the working semanticist (2010)
- LNgen: Tool Support for Locally Nameless Representations (2010)
- Agda with the excluded middle is inconsistent? (Hur, Agda mailing list) (2010)
- The Implicit Calculus of Constructions as a Programming Language with Dependent Types (2008)
- Scrap Your Type Applications (2008)
- Type checking with open type functions (2008)
- FPH (2008)
- Un environnement pour la programmation avec types dépendants (PhD thesis, Sozeau) (2008)
- Practical type inference for arbitrary-rank types (2007)
- System F with type equality coercions (2007)
- Towards a practical programming language based on dependent type theory (2007)
- Simple unification-based type inference for GADTs (2006)
- Modelling general recursion in type theory (2005)
- Associated type synonyms (2005)
- Practical Implementation of a Dependently Typed Functional Programming Language (2005)
- Dependent Types (2004)
- A logical framework with explicit conversions (2004)
- The Coq proof assistant reference manual, version 8.0 (2004)
- First-Class Phantom Types (2003)
- The Implicit Calculus of Constructions Extending Pure Type Systems with an Intersection Type Binder and Subtyping (2001)
- Intensionality, extensionality, and proof irrelevance in modal type theory (2001)
- Local type inference (2000)
- A Finite Axiomatization of Inductive-Recursive Definitions (1999)
- Typability and type checking in System F are equivalent and undecidable (1999)
- Cayenne—a language with dependent types (1998)
- A Syntactic Approach to Type Soundness (1994)
- On the Undecidability of Partial Polymorphic Type Reconstruction (1993)
- Introduction to generalized type systems (1991)
- A Calculus of Constructions (1986)
- A Polymorphic Lambda Calculus with Type:Type (DEC SRC Technical Report 10) (1986)
- Intuitionistic type theory (1984)
- Principal type-schemes for functional programs (1982)
- An Intuitionistic Theory of Types: Predicative Part (1975)
- Towards a theory of type structure (1974)
- Combinatory logic: Volume II (1972)
- Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur (PhD thesis, Girard) (1972)
- Une Extension De ĽInterpretation De Gödel a ĽAnalyse, Et Son Application a ĽElimination Des Coupures Dans ĽAnalyse Et La Theorie Des Types (1971)
- A Theory of Types (Martin-Löf, unpublished manuscript) (1971)