How do you represent terms of the CoC in Agda?

Question

Representing, for example, the STLC in Agda can be done as:

data Type : Set where
*   : Type
_⇒_ : (S T : Type) → Type

data Context : Set where
ε   : Context
_,_ : (Γ : Context) (S : Type) → Context

data _∋_ : Context → Type → Set where
here  : ∀ {Γ S} → (Γ , S) ∋ S
there : ∀ {Γ S T} (i : Γ ∋ S) → (Γ , T) ∋ S

data Term : Context → Type → Set where
var : ∀ {Γ S} (v : Γ ∋ S) → Term Γ S
lam : ∀ {Γ S T} (t : Term (Γ , S) T) → Term Γ (S ⇒ T)
app : ∀ {Γ S T} (f : Term Γ (S ⇒ T)) (x : Term Γ S) → Term Γ T

(From here.) Trying to adapt this to the Calculus of Constructions, though, is problematic, because Type and Term are a single type. This means not only Context/Term must be mutually recursive, but also that Term must be indexed on itself. Here is an initial attempt:

data Γ : Set

data Term : Γ → Term → Set

data Γ where
  ε   : Γ
  _,_ : (ty : Term) (ctx : Γ) → Γ
infixr 5 _,_

data Term where
    -- ...

Agda, though, complains that Term isn't in scope on its initial declaration. Is it possible to represent it that way, or do we really need to have different types for Term and Type? I'd highly like to see a minimal/reference implementation of CoC in Agda.

user3237465 user3237465 · Accepted Answer · 2019-03-01T14:27:51

This is known to be a very hard problem. As far as I'm aware there is no "minimal" way to encode CoC in Agda. You have to either prove a lot of stuff or use shallow encoding or use heavy (but perfectly sensible) techniques like quotient induction or define untyped terms first and then reify them into typed ones. Here is some related literature:

Functional Program Correctness Through Types, Nils Anders Danielsson -- the last chapter of this thesis is a formalization of a dependently typed language. This is a ton-of-lemmas-style formalization and also contains some untyped terms.

Type checking and normalisation, James Chapman -- the fifth chapter of this thesis is a formalization of a dependently typed language. It is also a ton-of-lemmas-style formalization, except many lemmas are just constructors of the corresponding data types. For example, you have explicit substitutions as constructors rather than as computing functions (the previous thesis didn't have those for types, only for terms, while this thesis have explicit substitutions even for types).

Outrageous but Meaningful Coincidences. Dependent type-safe syntax and evaluation, Conor McBride -- this paper presents a deep encoding of a dependent type theory that reifies a shallow encoding of the theory. This means that instead of defining substitution and proving properties about it the author just uses the Agda's evaluation model, but also gives a full syntax for the target language.

Typed Syntactic Meta-programming, Dominique Devriese, Frank Piessens -- untyped terms reified into typed ones. IIRC there were a lot of postulates in the code when I looked into it, as this is a framework for meta-programming rather than a formalization.

Type theory eating itself?, Chuangjie Xu & Martin Escardo -- a single file formalization. As always, several data types defined mutually. Explicit substitutions with explicit transports that "mimic" the behavior of the substitution operations.

EatEval.agda -- we get this by combining the ideas from the previous two formalizations. In this file instead of defining multiple explicit transports we have just a single transport which allows to change the type of a term to a denotationally equal one. I.e. instead of explicitly specifying the behavior of substitution via constructors, we have a single constructor that says "if evaluating two types in Agda gives the same results, then you can convert a term of one type to the another one via a constructor".

Type Theory in Type Theory using Quotient Inductive Type, Thorsten Altenkirch, Ambrus Kaposi -- this is the most promising approach I'd say. It "legalizes" computation at the type level via the quotient types device. But we do not yet have quotient types in Agda, they are essentially postulated in the paper. People work a lot on quotient types (there is an entire thesis: Quotient inductive-inductive definitions -- Dijkstra, Gabe), though, so we'll probably have them at some point.

Decidability of Conversion for Type Theory in Type Theory, Andreas Abel, Joakim Öhman, Andrea Vezzosi -- untyped terms reified as typed ones. Lots of properties. Also has a lot of metatheoretical proofs and a particularly interesting device that allows to prove soundness and completeness using the same logical relation. The formalization is huge and well-commented.

A setoid model of extensional Martin-Löf type theory in Agda (zip file with the development), Erik Palmgren -- abstract:

Abstract. We present details of an Agda formalization of a setoid model of Martin-Löf type theory with Pi, Sigma, extensional identity types, natural numbers and an infinite hiearchy of universe à la Russell. A crucial ingredient is the use of Aczel's type V of iterative sets as an extensional universe of setoids, which allows for a well-behaved interpretation of type equality.

Coq in Coq, Bruno Barras and Benjamin Werner -- a formalization of CC in Coq (the code). Untyped terms reified as types ones + lots of lemmas + metatheoretical proofs.

Thanks to András Kovács and James Chapman for suggestions.

How do you represent terms of the CoC in Agda?

1 Answers