5 chapter {* Primitive logic \label{ch:logic} *} |
5 chapter {* Primitive logic \label{ch:logic} *} |
6 |
6 |
7 text {* |
7 text {* |
8 The logical foundations of Isabelle/Isar are that of the Pure logic, |
8 The logical foundations of Isabelle/Isar are that of the Pure logic, |
9 which has been introduced as a Natural Deduction framework in |
9 which has been introduced as a Natural Deduction framework in |
10 \cite{paulson700}. This is essentially the same logic as ``@{text |
10 @{cite paulson700}. This is essentially the same logic as ``@{text |
11 "\<lambda>HOL"}'' in the more abstract setting of Pure Type Systems (PTS) |
11 "\<lambda>HOL"}'' in the more abstract setting of Pure Type Systems (PTS) |
12 \cite{Barendregt-Geuvers:2001}, although there are some key |
12 @{cite "Barendregt-Geuvers:2001"}, although there are some key |
13 differences in the specific treatment of simple types in |
13 differences in the specific treatment of simple types in |
14 Isabelle/Pure. |
14 Isabelle/Pure. |
15 |
15 |
16 Following type-theoretic parlance, the Pure logic consists of three |
16 Following type-theoretic parlance, the Pure logic consists of three |
17 levels of @{text "\<lambda>"}-calculus with corresponding arrows, @{text |
17 levels of @{text "\<lambda>"}-calculus with corresponding arrows, @{text |
110 vector of argument sorts @{text "(s\<^sub>1, \<dots>, s\<^sub>k)"} such |
110 vector of argument sorts @{text "(s\<^sub>1, \<dots>, s\<^sub>k)"} such |
111 that a type scheme @{text "(\<alpha>\<^bsub>s\<^sub>1\<^esub>, \<dots>, |
111 that a type scheme @{text "(\<alpha>\<^bsub>s\<^sub>1\<^esub>, \<dots>, |
112 \<alpha>\<^bsub>s\<^sub>k\<^esub>)\<kappa>"} is of sort @{text "s"}. |
112 \<alpha>\<^bsub>s\<^sub>k\<^esub>)\<kappa>"} is of sort @{text "s"}. |
113 Consequently, type unification has most general solutions (modulo |
113 Consequently, type unification has most general solutions (modulo |
114 equivalence of sorts), so type-inference produces primary types as |
114 equivalence of sorts), so type-inference produces primary types as |
115 expected \cite{nipkow-prehofer}. |
115 expected @{cite "nipkow-prehofer"}. |
116 *} |
116 *} |
117 |
117 |
118 text %mlref {* |
118 text %mlref {* |
119 \begin{mldecls} |
119 \begin{mldecls} |
120 @{index_ML_type class: string} \\ |
120 @{index_ML_type class: string} \\ |
235 |
235 |
236 section {* Terms \label{sec:terms} *} |
236 section {* Terms \label{sec:terms} *} |
237 |
237 |
238 text {* |
238 text {* |
239 The language of terms is that of simply-typed @{text "\<lambda>"}-calculus |
239 The language of terms is that of simply-typed @{text "\<lambda>"}-calculus |
240 with de-Bruijn indices for bound variables (cf.\ \cite{debruijn72} |
240 with de-Bruijn indices for bound variables (cf.\ @{cite debruijn72} |
241 or \cite{paulson-ml2}), with the types being determined by the |
241 or @{cite "paulson-ml2"}), with the types being determined by the |
242 corresponding binders. In contrast, free variables and constants |
242 corresponding binders. In contrast, free variables and constants |
243 have an explicit name and type in each occurrence. |
243 have an explicit name and type in each occurrence. |
244 |
244 |
245 \medskip A \emph{bound variable} is a natural number @{text "b"}, |
245 \medskip A \emph{bound variable} is a natural number @{text "b"}, |
246 which accounts for the number of intermediate binders between the |
246 which accounts for the number of intermediate binders between the |
556 are irrelevant in the Pure logic, though; they cannot occur within |
556 are irrelevant in the Pure logic, though; they cannot occur within |
557 propositions. The system provides a runtime option to record |
557 propositions. The system provides a runtime option to record |
558 explicit proof terms for primitive inferences, see also |
558 explicit proof terms for primitive inferences, see also |
559 \secref{sec:proof-terms}. Thus all three levels of @{text |
559 \secref{sec:proof-terms}. Thus all three levels of @{text |
560 "\<lambda>"}-calculus become explicit: @{text "\<Rightarrow>"} for terms, and @{text |
560 "\<lambda>"}-calculus become explicit: @{text "\<Rightarrow>"} for terms, and @{text |
561 "\<And>/\<Longrightarrow>"} for proofs (cf.\ \cite{Berghofer-Nipkow:2000:TPHOL}). |
561 "\<And>/\<Longrightarrow>"} for proofs (cf.\ @{cite "Berghofer-Nipkow:2000:TPHOL"}). |
562 |
562 |
563 Observe that locally fixed parameters (as in @{text |
563 Observe that locally fixed parameters (as in @{text |
564 "\<And>\<hyphen>intro"}) need not be recorded in the hypotheses, because |
564 "\<And>\<hyphen>intro"}) need not be recorded in the hypotheses, because |
565 the simple syntactic types of Pure are always inhabitable. |
565 the simple syntactic types of Pure are always inhabitable. |
566 ``Assumptions'' @{text "x :: \<tau>"} for type-membership are only |
566 ``Assumptions'' @{text "x :: \<tau>"} for type-membership are only |
567 present as long as some @{text "x\<^sub>\<tau>"} occurs in the statement |
567 present as long as some @{text "x\<^sub>\<tau>"} occurs in the statement |
568 body.\footnote{This is the key difference to ``@{text "\<lambda>HOL"}'' in |
568 body.\footnote{This is the key difference to ``@{text "\<lambda>HOL"}'' in |
569 the PTS framework \cite{Barendregt-Geuvers:2001}, where hypotheses |
569 the PTS framework @{cite "Barendregt-Geuvers:2001"}, where hypotheses |
570 @{text "x : A"} are treated uniformly for propositions and types.} |
570 @{text "x : A"} are treated uniformly for propositions and types.} |
571 |
571 |
572 \medskip The axiomatization of a theory is implicitly closed by |
572 \medskip The axiomatization of a theory is implicitly closed by |
573 forming all instances of type and term variables: @{text "\<turnstile> |
573 forming all instances of type and term variables: @{text "\<turnstile> |
574 A\<vartheta>"} holds for any substitution instance of an axiom |
574 A\<vartheta>"} holds for any substitution instance of an axiom |
626 distinct variables @{text "\<^vec>\<alpha>"}). The RHS may mention |
626 distinct variables @{text "\<^vec>\<alpha>"}). The RHS may mention |
627 previously defined constants as above, or arbitrary constants @{text |
627 previously defined constants as above, or arbitrary constants @{text |
628 "d(\<alpha>\<^sub>i)"} for some @{text "\<alpha>\<^sub>i"} projected from @{text |
628 "d(\<alpha>\<^sub>i)"} for some @{text "\<alpha>\<^sub>i"} projected from @{text |
629 "\<^vec>\<alpha>"}. Thus overloaded definitions essentially work by |
629 "\<^vec>\<alpha>"}. Thus overloaded definitions essentially work by |
630 primitive recursion over the syntactic structure of a single type |
630 primitive recursion over the syntactic structure of a single type |
631 argument. See also \cite[\S4.3]{Haftmann-Wenzel:2006:classes}. |
631 argument. See also @{cite \<open>\S4.3\<close> "Haftmann-Wenzel:2006:classes"}. |
632 *} |
632 *} |
633 |
633 |
634 text %mlref {* |
634 text %mlref {* |
635 \begin{mldecls} |
635 \begin{mldecls} |
636 @{index_ML Logic.all: "term -> term -> term"} \\ |
636 @{index_ML Logic.all: "term -> term -> term"} \\ |
1007 |
1007 |
1008 subsection {* Hereditary Harrop Formulae *} |
1008 subsection {* Hereditary Harrop Formulae *} |
1009 |
1009 |
1010 text {* |
1010 text {* |
1011 The idea of object-level rules is to model Natural Deduction |
1011 The idea of object-level rules is to model Natural Deduction |
1012 inferences in the style of Gentzen \cite{Gentzen:1935}, but we allow |
1012 inferences in the style of Gentzen @{cite "Gentzen:1935"}, but we allow |
1013 arbitrary nesting similar to \cite{extensions91}. The most basic |
1013 arbitrary nesting similar to @{cite extensions91}. The most basic |
1014 rule format is that of a \emph{Horn Clause}: |
1014 rule format is that of a \emph{Horn Clause}: |
1015 \[ |
1015 \[ |
1016 \infer{@{text "A"}}{@{text "A\<^sub>1"} & @{text "\<dots>"} & @{text "A\<^sub>n"}} |
1016 \infer{@{text "A"}}{@{text "A\<^sub>1"} & @{text "\<dots>"} & @{text "A\<^sub>n"}} |
1017 \] |
1017 \] |
1018 where @{text "A, A\<^sub>1, \<dots>, A\<^sub>n"} are atomic propositions |
1018 where @{text "A, A\<^sub>1, \<dots>, A\<^sub>n"} are atomic propositions |
1031 \] |
1031 \] |
1032 |
1032 |
1033 Nesting of rules means that the positions of @{text "A\<^sub>i"} may |
1033 Nesting of rules means that the positions of @{text "A\<^sub>i"} may |
1034 again hold compound rules, not just atomic propositions. |
1034 again hold compound rules, not just atomic propositions. |
1035 Propositions of this format are called \emph{Hereditary Harrop |
1035 Propositions of this format are called \emph{Hereditary Harrop |
1036 Formulae} in the literature \cite{Miller:1991}. Here we give an |
1036 Formulae} in the literature @{cite "Miller:1991"}. Here we give an |
1037 inductive characterization as follows: |
1037 inductive characterization as follows: |
1038 |
1038 |
1039 \medskip |
1039 \medskip |
1040 \begin{tabular}{ll} |
1040 \begin{tabular}{ll} |
1041 @{text "\<^bold>x"} & set of variables \\ |
1041 @{text "\<^bold>x"} & set of variables \\ |
1220 syntactic terms, two more layers of @{text "\<lambda>"}-calculus are added, |
1220 syntactic terms, two more layers of @{text "\<lambda>"}-calculus are added, |
1221 which correspond to @{text "\<And>x :: \<alpha>. B x"} and @{text "A \<Longrightarrow> B"} |
1221 which correspond to @{text "\<And>x :: \<alpha>. B x"} and @{text "A \<Longrightarrow> B"} |
1222 according to the propositions-as-types principle. The resulting |
1222 according to the propositions-as-types principle. The resulting |
1223 3-level @{text "\<lambda>"}-calculus resembles ``@{text "\<lambda>HOL"}'' in the |
1223 3-level @{text "\<lambda>"}-calculus resembles ``@{text "\<lambda>HOL"}'' in the |
1224 more abstract setting of Pure Type Systems (PTS) |
1224 more abstract setting of Pure Type Systems (PTS) |
1225 \cite{Barendregt-Geuvers:2001}, if some fine points like schematic |
1225 @{cite "Barendregt-Geuvers:2001"}, if some fine points like schematic |
1226 polymorphism and type classes are ignored. |
1226 polymorphism and type classes are ignored. |
1227 |
1227 |
1228 \medskip\emph{Proof abstractions} of the form @{text "\<^bold>\<lambda>x :: \<alpha>. prf"} |
1228 \medskip\emph{Proof abstractions} of the form @{text "\<^bold>\<lambda>x :: \<alpha>. prf"} |
1229 or @{text "\<^bold>\<lambda>p : A. prf"} correspond to introduction of @{text |
1229 or @{text "\<^bold>\<lambda>p : A. prf"} correspond to introduction of @{text |
1230 "\<And>"}/@{text "\<Longrightarrow>"}, and \emph{proof applications} of the form @{text |
1230 "\<And>"}/@{text "\<Longrightarrow>"}, and \emph{proof applications} of the form @{text |
1282 terms, all term and type labels of proof abstractions, and some |
1282 terms, all term and type labels of proof abstractions, and some |
1283 argument terms of applications @{text "p \<cdot> t"} (if possible). |
1283 argument terms of applications @{text "p \<cdot> t"} (if possible). |
1284 |
1284 |
1285 There are separate operations to reconstruct the full proof term |
1285 There are separate operations to reconstruct the full proof term |
1286 later on, using \emph{higher-order pattern unification} |
1286 later on, using \emph{higher-order pattern unification} |
1287 \cite{nipkow-patterns,Berghofer-Nipkow:2000:TPHOL}. |
1287 @{cite "nipkow-patterns" and "Berghofer-Nipkow:2000:TPHOL"}. |
1288 |
1288 |
1289 The \emph{proof checker} expects a fully reconstructed proof term, |
1289 The \emph{proof checker} expects a fully reconstructed proof term, |
1290 and can turn it into a theorem by replaying its primitive inferences |
1290 and can turn it into a theorem by replaying its primitive inferences |
1291 within the kernel. *} |
1291 within the kernel. *} |
1292 |
1292 |
1293 |
1293 |
1294 subsection {* Concrete syntax of proof terms *} |
1294 subsection {* Concrete syntax of proof terms *} |
1295 |
1295 |
1296 text {* The concrete syntax of proof terms is a slight extension of |
1296 text {* The concrete syntax of proof terms is a slight extension of |
1297 the regular inner syntax of Isabelle/Pure \cite{isabelle-isar-ref}. |
1297 the regular inner syntax of Isabelle/Pure @{cite "isabelle-isar-ref"}. |
1298 Its main syntactic category @{syntax (inner) proof} is defined as |
1298 Its main syntactic category @{syntax (inner) proof} is defined as |
1299 follows: |
1299 follows: |
1300 |
1300 |
1301 \begin{center} |
1301 \begin{center} |
1302 \begin{supertabular}{rclr} |
1302 \begin{supertabular}{rclr} |