Core of Verifier in Isabelle/HOL

Question

Question

What is the core algorithm of the Isabelle/HOL verifier?

I'm looking for something on the level of a scheme metacircular evaluator.

Clarification

I'm only interested in the Verifier , not the strategies for automated theorem proving.

Context

I want to implement a simple proof verifier from scratch (purely for education reasons, not for production use.)

I want to understand the core Verifier algorithm of Isabelle/HOL. I don't care about the strategies / code used for automated theorem proving.

I have a suspicion that the core Verifier algorithm is very simple (and elegant). However, I can't find it.

Thanks!

Answer 1

Isabelle is a member of the "LCF family" of proof checkers, which means you have a special module --- the inference kernel -- where all inferences are run through to produce values of the abstract datatype thm. This is a bit like an operating system kernel processing system calls. Everything you can produce this way is "correct by construction" relative to the correctness of the kernel implementation. Since the programming language environment of the prover (Standard ML) has very strong static type-correctness properties, the correctness-by-construction of the inference kernel carries over to the rest of the proof assistant implementation, which can be quite huge.

So in principle you have a relatively small "trusted kernel" part and a really big "application user-space". In particular, most of Isabelle/HOL is actually a big collection of library theories and add-on tools (mostly in SML) in Isabelle user-land.

In Isabelle, the kernel infrastructure is quite complex, but still very small compared to the rest of the system. The kernel is in fact layered into a "micro kernel" (the Thm module) and a "nano kernel" (the Context module). Thm produces thm values in the sense of Milner's LCF-approach, and Context takes care of theory certficates for any results you produce, as well as proof contexts for local reasoning (notably in the Isar proof language).

If you want to learn more about LCF-style provers, I recommend looking also at HOL-Light which is probably the smallest realistic system of the LCF-family, realistic in the sense that people have done big applications with it. HOL-Light has the big advantage that its implementation can be easily understood, but this minimalism also has some disdavantages: it does not fully protect the user from doing non-sense in its ML environment, which is OCaml instead of SML. For various technical reasons, OCaml is not as "safe" by default as Standard ML.

Answer 2

If you untar the Isabelle sources, e.g.

http://isabelle.in.tum.de/dist/Isabelle2013_linux.tar.gz

you will find the core definitions in

src/Pure/thm.ML

And, there is such a project already you want to tackle:

http://www.proof-technologies.com/holzero/

added later: another, more serious project is

https://team.inria.fr/parsifal/proofcert/