This repository shows how to implement a minimalist type theory of the kind that is sometimes called “spartan”. The current version is an updated version of the one presented at the School and Workshop on Univalent Mathematics which took place at the University of Birmingham in December 2017.
The dependent type theory spartan
has the following ingredients:
- A universe
Type
withType : Type
. - Dependent products, written as
forall (x : T₁), T₂
or∀ (x : T₁), T₂
or∏ (x : T₁), T₂
. - Functions, written as one of
fun (x : T) => e
orλ (x : T) ⇒ e
. The typing annotation may be omitted, i.e.,fun x => e
, and multiple abstractions may be shortened asλ x y (z u : T) (w : U) ⇒ e
. - Application
e₁ e₂
. - Type ascription written as
e : T
.
Top-level commands:
Definition x := e.
-- define a valueAxiom x : T.
-- assume a constantx
of typeT
Check e.
-- print the type ofe
Eval e.
-- evaluatee
a la call-by-valueLoad "⟨file⟩".
-- load a file
-
The OPAM packages
dune
,menhir
,menhirLib
,sedlex
andbindlib
:opam install dune menhir menihirLib sedlex bindlib
-
It is recommended that you also install the
rlwrap
orledit
command line wrapper.
You can type:
dune build
to compile thespartan.exe
executable.dune clean
to clean up.
Once you compile the program, you can run it in interactive mode as ./spartan.exe
Run ./spartan.exe --help
to see the command-line options and general usage.
The purpose of the implementation is to keep the source uncomplicated and short. The essential bits of source code can be found in the following files. It should be possible for you to just read the entire source code.
It is best to first familiarize yourself with the core:
lib/core/TT.ml
– the core type theorylib/core/context.ml
– typing contextlib/core/typecheck.ml
– type checking and elaborationlib/core/norm.ml
– normalizationlib/core/equal.ml
– equality and normalizationlib/core/toplevel.ml
– top-level commands
Continue with the infrastructure:
lib/parsing/syntax.ml
– abstract syntax of the input codelib/parsing/lexer.ml
– the lexerlib/parsing/parser.mly
– the parserlib/util
– various utilitiesbin/spartan.ml
– the main executable