3 files changed, 419 insertions, 0 deletions
diff --git a/mltt/lib/List.thy b/mltt/lib/List.thy
new file mode 100644
index 0000000..4beb9b6
--- /dev/null
+++ b/mltt/lib/List.thy
@@ -0,0 +1,191 @@
+chapter \<open>Lists\<close>
+
+theory List
+imports Maybe
+
+begin
+
+(*TODO: Inductive type and recursive function definitions. The ad-hoc
+  axiomatization below should be subsumed once general inductive types are
+  properly implemented.*)
+
+axiomatization
+  List    :: \<open>o \<Rightarrow> o\<close> and
+  nil     :: \<open>o \<Rightarrow> o\<close> and
+  cons    :: \<open>o \<Rightarrow> o \<Rightarrow> o \<Rightarrow> o\<close> and
+  ListInd :: \<open>o \<Rightarrow> (o \<Rightarrow> o) \<Rightarrow> o \<Rightarrow> (o \<Rightarrow> o \<Rightarrow> o \<Rightarrow> o) \<Rightarrow> o \<Rightarrow> o\<close>
+where
+  ListF: "A: U i \<Longrightarrow> List A: U i" and
+
+  List_nil: "A: U i \<Longrightarrow> nil A: List A" and
+
+  List_cons: "\<lbrakk>x: A; xs: List A\<rbrakk> \<Longrightarrow> cons A x xs: List A" and
+
+  ListE: "\<lbrakk>
+    xs: List A;
+    c\<^sub>0: C (nil A);
+    \<And>x xs rec. \<lbrakk>x: A; xs: List A; rec: C xs\<rbrakk> \<Longrightarrow> f x xs rec: C (cons A x xs);
+    \<And>xs. xs: List A \<Longrightarrow> C xs: U i
+    \<rbrakk> \<Longrightarrow> ListInd A (fn xs. C xs) c\<^sub>0 (fn x xs rec. f x xs rec) xs: C xs" and
+
+  List_comp_nil: "\<lbrakk>
+    c\<^sub>0: C (nil A);
+    \<And>x xs rec. \<lbrakk>x: A; xs: List A; rec: C xs\<rbrakk> \<Longrightarrow> f x xs rec: C (cons A x xs);
+    \<And>xs. xs: List A \<Longrightarrow> C xs: U i
+    \<rbrakk> \<Longrightarrow> ListInd A (fn xs. C xs) c\<^sub>0 (fn x xs rec. f x xs rec) (nil A) \<equiv> c\<^sub>0" and
+
+  List_comp_cons: "\<lbrakk>
+    xs: List A;
+    c\<^sub>0: C (nil A);
+    \<And>x xs rec. \<lbrakk>x: A; xs: List A; rec: C xs\<rbrakk> \<Longrightarrow> f x xs rec: C (cons A x xs);
+    \<And>xs. xs: List A \<Longrightarrow> C xs: U i
+    \<rbrakk> \<Longrightarrow>
+      ListInd A (fn xs. C xs) c\<^sub>0 (fn x xs rec. f x xs rec) (cons A x xs) \<equiv>
+        f x xs (ListInd A (fn xs. C xs) c\<^sub>0 (fn x xs rec. f x xs rec) xs)"
+
+lemmas
+  [form] = ListF and
+  [intr, intro] = List_nil List_cons and
+  [elim "?xs"] = ListE and
+  [comp] = List_comp_nil List_comp_cons
+
+abbreviation "ListRec A C \<equiv> ListInd A (fn _. C)"
+
+Lemma list_cases [cases]:
+  assumes
+    "xs: List A" and
+    nil_case: "c\<^sub>0: C (nil A)" and
+    cons_case: "\<And>x xs. \<lbrakk>x: A; xs: List A\<rbrakk> \<Longrightarrow> f x xs: C (cons A x xs)" and
+    "\<And>xs. xs: List A \<Longrightarrow> C xs: U i"
+  shows "C xs"
+  by (elim xs) (fact nil_case, rule cons_case)
+
+
+section \<open>Notation\<close>
+
+definition nil_i ("[]")
+  where [implicit]: "[] \<equiv> nil {}"
+
+definition cons_i (infixr "#" 120)
+  where [implicit]: "x # xs \<equiv> cons {} x xs"
+
+translations
+  "[]" \<leftharpoondown> "CONST List.nil A"
+  "x # xs" \<leftharpoondown> "CONST List.cons A x xs"
+syntax
+  "_list" :: \<open>args \<Rightarrow> o\<close> ("[_]")
+translations
+  "[x, xs]" \<rightleftharpoons> "x # [xs]"
+  "[x]" \<rightleftharpoons> "x # []"
+
+
+section \<open>Standard functions\<close>
+
+subsection \<open>Head and tail\<close>
+
+Definition head:
+  assumes "A: U i" "xs: List A"
+  shows "Maybe A"
+proof (cases xs)
+  show "none: Maybe A" by intro
+  show "\<And>x. x: A \<Longrightarrow> some x: Maybe A" by intro
+qed
+
+Definition tail:
+  assumes "A: U i" "xs: List A"
+  shows "List A"
+proof (cases xs)
+  show "[]: List A" by intro
+  show "\<And>xs. xs: List A \<Longrightarrow> xs: List A" .
+qed
+
+definition head_i ("head") where [implicit]: "head xs \<equiv> List.head {} xs"
+definition tail_i ("tail") where [implicit]: "tail xs \<equiv> List.tail {} xs"
+
+translations
+  "head" \<leftharpoondown> "CONST List.head A"
+  "tail" \<leftharpoondown> "CONST List.tail A"
+
+Lemma head_type [type]:
+  assumes "A: U i" "xs: List A"
+  shows "head xs: Maybe A"
+  unfolding head_def by typechk
+
+Lemma head_of_cons [comp]:
+  assumes "A: U i" "x: A" "xs: List A"
+  shows "head (x # xs) \<equiv> some x"
+  unfolding head_def by compute
+
+Lemma tail_type [type]:
+  assumes "A: U i" "xs: List A"
+  shows "tail xs: List A"
+  unfolding tail_def by typechk
+
+Lemma tail_of_cons [comp]:
+  assumes "A: U i" "x: A" "xs: List A"
+  shows "tail (x # xs) \<equiv> xs"
+  unfolding tail_def by compute
+
+subsection \<open>Append\<close>
+
+Definition app:
+  assumes "A: U i" "xs: List A" "ys: List A"
+  shows "List A"
+  apply (elim xs)
+    \<^item> by (fact \<open>ys:_\<close>)
+    \<^item> vars x _ rec
+      proof - show "x # rec: List A" by typechk qed
+  done
+
+definition app_i ("app") where [implicit]: "app xs ys \<equiv> List.app {} xs ys"
+
+translations "app" \<leftharpoondown> "CONST List.app A"
+
+subsection \<open>Map\<close>
+
+Definition map:
+  assumes "A: U i" "B: U i" "f: A \<rightarrow> B" "xs: List A"
+  shows "List B"
+proof (elim xs)
+  show "[]: List B" by intro
+  next fix x ys
+  assuming "x: A" "ys: List B"
+  show "f x # ys: List B" by typechk
+qed
+
+definition map_i ("map") where [implicit]: "map \<equiv> List.map {} {}"
+
+translations "map" \<leftharpoondown> "CONST List.map A B"
+
+Lemma map_type [type]:
+  assumes "A: U i" "B: U i" "f: A \<rightarrow> B" "xs: List A"
+  shows "map f xs: List B"
+  unfolding map_def by typechk
+
+
+subsection \<open>Reverse\<close>
+
+Definition rev:
+  assumes "A: U i" "xs: List A"
+  shows "List A"
+  apply (elim xs)
+    \<^item> by (rule List_nil)
+    \<^item> vars x _ rec proof - show "app rec [x]: List A" by typechk qed
+  done
+
+definition rev_i ("rev") where [implicit]: "rev \<equiv> List.rev {}"
+
+translations "rev" \<leftharpoondown> "CONST List.rev A"
+
+Lemma rev_type [type]:
+  assumes "A: U i" "xs: List A"
+  shows "rev xs: List A"
+  unfolding rev_def by typechk
+
+Lemma rev_nil [comp]:
+  assumes "A: U i"
+  shows "rev (nil A) \<equiv> nil A"
+  unfolding rev_def by compute
+
+
+end
diff --git a/mltt/lib/Maybe.thy b/mltt/lib/Maybe.thy
new file mode 100644
index 0000000..452acc2
--- /dev/null
+++ b/mltt/lib/Maybe.thy
@@ -0,0 +1,75 @@
+chapter \<open>Maybe type\<close>
+
+theory Maybe
+imports Prelude
+
+begin
+
+text \<open>Defined as a sum.\<close>
+
+definition "Maybe A \<equiv> A \<or> \<top>"
+definition "none A \<equiv> inr A \<top> tt"
+definition "some A a \<equiv> inl A \<top> a"
+
+lemma
+  MaybeF: "A: U i \<Longrightarrow> Maybe A: U i" and
+  Maybe_none: "A: U i \<Longrightarrow> none A: Maybe A" and
+  Maybe_some: "a: A \<Longrightarrow> some A a: Maybe A"
+  unfolding Maybe_def none_def some_def by typechk+
+
+Definition MaybeInd:
+  assumes
+    "A: U i"
+    "\<And>m. m: Maybe A \<Longrightarrow> C m: U i"
+    "c\<^sub>0: C (none A)"
+    "\<And>a. a: A \<Longrightarrow> f a: C (some A a)"
+    "m: Maybe A"
+  shows "C m"
+  using assms[unfolded Maybe_def none_def some_def, type]
+  apply (elim m)
+    apply fact
+    apply (elim, fact)
+  done
+
+Lemma Maybe_comp_none:
+  assumes
+    "A: U i"
+    "c\<^sub>0: C (none A)"
+    "\<And>a. a: A \<Longrightarrow> f a: C (some A a)"
+    "\<And>m. m: Maybe A \<Longrightarrow> C m: U i"
+  shows "MaybeInd A C c\<^sub>0 f (none A) \<equiv> c\<^sub>0"
+  using assms
+  unfolding Maybe_def MaybeInd_def none_def some_def
+  by compute
+
+Lemma Maybe_comp_some:
+  assumes
+    "A: U i"
+    "a: A"
+    "c\<^sub>0: C (none A)"
+    "\<And>a. a: A \<Longrightarrow> f a: C (some A a)"
+    "\<And>m. m: Maybe A \<Longrightarrow> C m: U i"
+  shows "MaybeInd A C c\<^sub>0 f (some A a) \<equiv> f a"
+  using assms
+  unfolding Maybe_def MaybeInd_def none_def some_def
+  by compute
+
+lemmas
+  [form] = MaybeF and
+  [intr, intro] = Maybe_none Maybe_some and
+  [comp] = Maybe_comp_none Maybe_comp_some and
+  MaybeE [elim "?m"] = MaybeInd[rotated 4]
+lemmas
+  Maybe_cases [cases] = MaybeE
+
+abbreviation "MaybeRec A C \<equiv> MaybeInd A (K C)"
+
+definition none_i ("none") where [implicit]: "none \<equiv> Maybe.none {}"
+definition some_i ("some") where [implicit]: "some a \<equiv> Maybe.some {} a"
+
+translations
+  "none" \<leftharpoondown> "CONST Maybe.none A"
+  "some a" \<leftharpoondown> "CONST Maybe.some A a"
+
+
+end
diff --git a/mltt/lib/Prelude.thy b/mltt/lib/Prelude.thy
new file mode 100644
index 0000000..0393968
--- /dev/null
+++ b/mltt/lib/Prelude.thy
@@ -0,0 +1,153 @@
+theory Prelude
+imports MLTT
+
+begin
+
+section \<open>Sum type\<close>
+
+axiomatization
+  Sum    :: \<open>o \<Rightarrow> o \<Rightarrow> o\<close> and
+  inl    :: \<open>o \<Rightarrow> o \<Rightarrow> o \<Rightarrow> o\<close> and
+  inr    :: \<open>o \<Rightarrow> o \<Rightarrow> o \<Rightarrow> o\<close> and
+  SumInd :: \<open>o \<Rightarrow> o \<Rightarrow> (o \<Rightarrow> o) \<Rightarrow> (o \<Rightarrow> o) \<Rightarrow> (o \<Rightarrow> o) \<Rightarrow> o \<Rightarrow> o\<close>
+
+notation Sum (infixl "\<or>" 50)
+
+axiomatization where
+  SumF: "\<lbrakk>A: U i; B: U i\<rbrakk> \<Longrightarrow> A \<or> B: U i" and
+
+  Sum_inl: "\<lbrakk>B: U i; a: A\<rbrakk> \<Longrightarrow> inl A B a: A \<or> B" and
+
+  Sum_inr: "\<lbrakk>A: U i; b: B\<rbrakk> \<Longrightarrow> inr A B b: A \<or> B" and
+
+  SumE: "\<lbrakk>
+    s: A \<or> B;
+    \<And>s. s: A \<or> B \<Longrightarrow> C s: U i;
+    \<And>a. a: A \<Longrightarrow> c a: C (inl A B a);
+    \<And>b. b: B \<Longrightarrow> d b: C (inr A B b)
+    \<rbrakk> \<Longrightarrow> SumInd A B (fn s. C s) (fn a. c a) (fn b. d b) s: C s" and
+
+  Sum_comp_inl: "\<lbrakk>
+    a: A;
+    \<And>s. s: A \<or> B \<Longrightarrow> C s: U i;
+    \<And>a. a: A \<Longrightarrow> c a: C (inl A B a);
+    \<And>b. b: B \<Longrightarrow> d b: C (inr A B b)
+    \<rbrakk> \<Longrightarrow> SumInd A B (fn s. C s) (fn a. c a) (fn b. d b) (inl A B a) \<equiv> c a" and
+
+  Sum_comp_inr: "\<lbrakk>
+    b: B;
+    \<And>s. s: A \<or> B \<Longrightarrow> C s: U i;
+    \<And>a. a: A \<Longrightarrow> c a: C (inl A B a);
+    \<And>b. b: B \<Longrightarrow> d b: C (inr A B b)
+    \<rbrakk> \<Longrightarrow> SumInd A B (fn s. C s) (fn a. c a) (fn b. d b) (inr A B b) \<equiv> d b"
+
+lemmas
+  [form] = SumF and
+  [intr] = Sum_inl Sum_inr and
+  [intro] = Sum_inl[rotated] Sum_inr[rotated] and
+  [elim ?s] = SumE and
+  [comp] = Sum_comp_inl Sum_comp_inr
+
+method left = rule Sum_inl
+method right = rule Sum_inr
+
+
+section \<open>Empty and unit types\<close>
+
+axiomatization
+  Top    :: \<open>o\<close> and
+  tt     :: \<open>o\<close> and
+  TopInd :: \<open>(o \<Rightarrow> o) \<Rightarrow> o \<Rightarrow> o \<Rightarrow> o\<close>
+and
+  Bot    :: \<open>o\<close> and
+  BotInd :: \<open>(o \<Rightarrow> o) \<Rightarrow> o \<Rightarrow> o\<close>
+
+notation Top ("\<top>") and Bot ("\<bottom>")
+
+axiomatization where
+  TopF: "\<top>: U i" and
+
+  TopI: "tt: \<top>" and
+
+  TopE: "\<lbrakk>a: \<top>; \<And>x. x: \<top> \<Longrightarrow> C x: U i; c: C tt\<rbrakk> \<Longrightarrow> TopInd (fn x. C x) c a: C a" and
+
+  Top_comp: "\<lbrakk>\<And>x. x: \<top> \<Longrightarrow> C x: U i; c: C tt\<rbrakk> \<Longrightarrow> TopInd (fn x. C x) c tt \<equiv> c"
+and
+  BotF: "\<bottom>: U i" and
+
+  BotE: "\<lbrakk>x: \<bottom>; \<And>x. x: \<bottom> \<Longrightarrow> C x: U i\<rbrakk> \<Longrightarrow> BotInd (fn x. C x) x: C x"
+
+lemmas
+  [form] = TopF BotF and
+  [intr, intro] = TopI and
+  [elim ?a] = TopE and
+  [elim ?x] = BotE and
+  [comp] = Top_comp
+
+abbreviation (input) Not ("\<not>_" [1000] 1000) where "\<not>A \<equiv> A \<rightarrow> \<bottom>"
+
+
+section \<open>Booleans\<close>
+
+definition "Bool \<equiv> \<top> \<or> \<top>"
+definition "true \<equiv> inl \<top> \<top> tt"
+definition "false \<equiv> inr \<top> \<top> tt"
+
+Lemma
+  BoolF: "Bool: U i" and
+  Bool_true: "true: Bool" and
+  Bool_false: "false: Bool"
+  unfolding Bool_def true_def false_def by typechk+
+
+\<comment> \<open>Definitions like these should be handled by a future function package\<close>
+Definition ifelse [rotated 1]:
+  assumes *[unfolded Bool_def true_def false_def]:
+    "\<And>x. x: Bool \<Longrightarrow> C x: U i"
+    "x: Bool"
+    "a: C true"
+    "b: C false"
+  shows "C x"
+  using assms[unfolded Bool_def true_def false_def, type]
+  by (elim x) (elim, fact)+
+
+Lemma if_true:
+  assumes
+    "\<And>x. x: Bool \<Longrightarrow> C x: U i"
+    "a: C true"
+    "b: C false"
+  shows "ifelse C true a b \<equiv> a"
+  unfolding ifelse_def true_def
+  using assms unfolding Bool_def true_def false_def
+  by compute
+
+Lemma if_false:
+  assumes
+    "\<And>x. x: Bool \<Longrightarrow> C x: U i"
+    "a: C true"
+    "b: C false"
+  shows "ifelse C false a b \<equiv> b"
+  unfolding ifelse_def false_def
+  using assms unfolding Bool_def true_def false_def
+  by compute
+
+lemmas
+  [form] = BoolF and
+  [intr, intro] = Bool_true Bool_false and
+  [comp] = if_true if_false and
+  [elim ?x] = ifelse
+lemmas
+  BoolE = ifelse
+
+subsection \<open>Notation\<close>
+
+definition ifelse_i ("if _ then _ else _")
+  where [implicit]: "if x then a else b \<equiv> ifelse {} x a b"
+
+translations "if x then a else b" \<leftharpoondown> "CONST ifelse C x a b"
+
+subsection \<open>Logical connectives\<close>
+
+definition not ("!_") where "!x \<equiv> ifelse (K Bool) x false true"
+
+
+end