How does one implement Coq?

Question

If one wishes to re-implement the calculus of inductive constructions, what is the "shortest" path towards this? In particular, what actually goes on inside the kernel?

My mental model says that we need two things:

• ability to compute / reduce terms to values.
• ability to type check to ensure that proofs are correct.

However, since the language is dependently typed, the type-checker will most likely depend on the ability to compute when deciding two types are equal.

So, really, what is the operational semantics of the Coq evaluator? What are the type checking inference rules? And how difficult are they to implement?

I'd like a stable, standard reference of these two facts so I can re-implement a small CIC kernel.

Answer 1

It sounds a bit like self-advertising but it might be worth a look at the metacoq project https://metacoq.github.io/metacoq/ (or the github repo directly https://github.com/MetaCoq/metacoq). Along with the papers associated with it. We specify the type theory of Coq (minus η, template polymorphism and modules for now) and write a sound type-checker for it.

As such I agree that one key ingredient is being able to compare types (and thus terms because of dependencies). This relies on evaluation, but generally not call by value (hence I would disagree with the value part). For instance we do conversion using weak head reduction.

CIC is still quite big, so you might want to look for something simpler, in which case "How to implement type theory in an hour" by Andrej Bauer is definitely worth a look.