diff options
| -rw-r--r-- | spartan/data/List.thy | 192 | ||||
| -rw-r--r-- | spartan/data/Maybe.thy | 76 | ||||
| -rw-r--r-- | spartan/data/More_Types.thy | 104 |
3 files changed, 0 insertions, 372 deletions
diff --git a/spartan/data/List.thy b/spartan/data/List.thy deleted file mode 100644 index 1798a23..0000000 --- a/spartan/data/List.thy +++ /dev/null @@ -1,192 +0,0 @@ -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 (\<lambda>xs. C xs) c\<^sub>0 (\<lambda>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 (\<lambda>xs. C xs) c\<^sub>0 (\<lambda>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 (\<lambda>xs. C xs) c\<^sub>0 (\<lambda>x xs rec. f x xs rec) (cons A x xs) \<equiv> - f x xs (ListInd A (\<lambda>xs. C xs) c\<^sub>0 (\<lambda>x xs rec. f x xs rec) xs)" - -lemmas - [intros] = ListF List_nil List_cons and - [elims "?xs"] = ListE and - [comps] = List_comp_nil List_comp_cons - -abbreviation "ListRec A C \<equiv> ListInd A (\<lambda>_. C)" - -Lemma (derive) ListCase: - 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 "?List_cases A (\<lambda>xs. C xs) c\<^sub>0 (\<lambda>x xs. f x xs) xs: C xs" - by (elim xs) (fact nil_case, rule cons_case) - -lemmas List_cases [cases] = ListCase[unfolded ListCase_def] - - -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> - -Lemma (derive) 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 - -Lemma (derive) 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 [typechk]: - assumes "A: U i" "xs: List A" - shows "head xs: Maybe A" - unfolding head_def by typechk - -Lemma head_of_cons [comps]: - assumes "A: U i" "x: A" "xs: List A" - shows "head (x # xs) \<equiv> some x" - unfolding head_def ListCase_def by reduce - -Lemma tail_type [typechk]: - assumes "A: U i" "xs: List A" - shows "tail xs: List A" - unfolding tail_def by typechk - -Lemma tail_of_cons [comps]: - assumes "A: U i" "x: A" "xs: List A" - shows "tail (x # xs) \<equiv> xs" - unfolding tail_def ListCase_def by reduce - -subsection \<open>Append\<close> - -Lemma (derive) app: - assumes "A: U i" "xs: List A" "ys: List A" - shows "List A" - apply (elim xs) - \<guillemotright> by (fact \<open>ys:_\<close>) - \<guillemotright> prems 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> - -Lemma (derive) 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 - assume "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 [typechk]: - 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> - -Lemma (derive) rev: - assumes "A: U i" "xs: List A" - shows "List A" - apply (elim xs) - \<guillemotright> by (rule List_nil) - \<guillemotright> prems 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 [typechk]: - assumes "A: U i" "xs: List A" - shows "rev xs: List A" - unfolding rev_def by typechk - -Lemma rev_nil [comps]: - assumes "A: U i" - shows "rev (nil A) \<equiv> nil A" - unfolding rev_def by reduce - - -end diff --git a/spartan/data/Maybe.thy b/spartan/data/Maybe.thy deleted file mode 100644 index 1efbb95..0000000 --- a/spartan/data/Maybe.thy +++ /dev/null @@ -1,76 +0,0 @@ -chapter \<open>Maybe type\<close> - -theory Maybe -imports More_Types - -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+ - -Lemma (derive) 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 "?MaybeInd A (\<lambda>m. C m) c\<^sub>0 (\<lambda>a. f a) m: C m" - supply assms[unfolded Maybe_def none_def some_def] - apply (elim m) - \<guillemotright> unfolding Maybe_def . - \<guillemotright> by (rule \<open>_ \<Longrightarrow> _: C (inl _ _ _)\<close>) - \<guillemotright> by elim (rule \<open>_: C (inr _ _ _)\<close>) - 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 (\<lambda>m. C m) c\<^sub>0 (\<lambda>a. f a) (none A) \<equiv> c\<^sub>0" - supply assms[unfolded Maybe_def some_def none_def] - unfolding MaybeInd_def none_def by reduce - -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 (\<lambda>m. C m) c\<^sub>0 (\<lambda>a. f a) (some A a) \<equiv> f a" - supply assms[unfolded Maybe_def some_def none_def] - unfolding MaybeInd_def some_def by (reduce add: Maybe_def) - -lemmas - [intros] = MaybeF Maybe_none Maybe_some and - [comps] = Maybe_comp_none Maybe_comp_some and - MaybeE [elims "?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/spartan/data/More_Types.thy b/spartan/data/More_Types.thy deleted file mode 100644 index 1d7abb9..0000000 --- a/spartan/data/More_Types.thy +++ /dev/null @@ -1,104 +0,0 @@ -chapter \<open>Some standard types\<close> - -theory More_Types -imports Spartan - -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>a: A; B: U i\<rbrakk> \<Longrightarrow> inl A B a: A \<or> B" and - - Sum_inr: "\<lbrakk>b: B; A: U i\<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 (\<lambda>s. C s) (\<lambda>a. c a) (\<lambda>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 (\<lambda>s. C s) (\<lambda>a. c a) (\<lambda>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 (\<lambda>s. C s) (\<lambda>a. c a) (\<lambda>b. d b) (inr A B b) \<equiv> d b" - -lemmas - [intros] = SumF Sum_inl Sum_inr and - [elims ?s] = SumE and - [comps] = 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 (\<lambda>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 (\<lambda>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 (\<lambda>x. C x) x: C x" - -lemmas - [intros] = TopF TopI BotF and - [elims ?a] = TopE and - [elims ?x] = BotE and - [comps] = Top_comp - - -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+ - -lemmas [intros] = BoolF Bool_true Bool_false - -\<comment> \<open>Can define if-then-else etc.\<close> - - -end |