src/Doc/Implementation/Logic.thy
changeset 58555 7975676c08c0
parent 56579 4c94f631c595
child 58618 782f0b662cae
equal deleted inserted replaced
58554:423202f05a43 58555:7975676c08c0
     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}