src/Doc/Implementation/Isar.thy
changeset 61416 b9a3324e4e62
parent 60754 02924903a6fd
child 61439 2bf52eec4e8a
equal deleted inserted replaced
61415:55e73b352287 61416:b9a3324e4e62
     8   @{cite \<open>\S2\<close> "isabelle-isar-ref"}) consists of three main categories of
     8   @{cite \<open>\S2\<close> "isabelle-isar-ref"}) consists of three main categories of
     9   language elements:
     9   language elements:
    10 
    10 
    11   \begin{enumerate}
    11   \begin{enumerate}
    12 
    12 
    13   \item Proof \emph{commands} define the primary language of
    13   \<^enum> Proof \emph{commands} define the primary language of
    14   transactions of the underlying Isar/VM interpreter.  Typical
    14   transactions of the underlying Isar/VM interpreter.  Typical
    15   examples are @{command "fix"}, @{command "assume"}, @{command
    15   examples are @{command "fix"}, @{command "assume"}, @{command
    16   "show"}, @{command "proof"}, and @{command "qed"}.
    16   "show"}, @{command "proof"}, and @{command "qed"}.
    17 
    17 
    18   Composing proof commands according to the rules of the Isar/VM leads
    18   Composing proof commands according to the rules of the Isar/VM leads
    19   to expressions of structured proof text, such that both the machine
    19   to expressions of structured proof text, such that both the machine
    20   and the human reader can give it a meaning as formal reasoning.
    20   and the human reader can give it a meaning as formal reasoning.
    21 
    21 
    22   \item Proof \emph{methods} define a secondary language of mixed
    22   \<^enum> Proof \emph{methods} define a secondary language of mixed
    23   forward-backward refinement steps involving facts and goals.
    23   forward-backward refinement steps involving facts and goals.
    24   Typical examples are @{method rule}, @{method unfold}, and @{method
    24   Typical examples are @{method rule}, @{method unfold}, and @{method
    25   simp}.
    25   simp}.
    26 
    26 
    27   Methods can occur in certain well-defined parts of the Isar proof
    27   Methods can occur in certain well-defined parts of the Isar proof
    28   language, say as arguments to @{command "proof"}, @{command "qed"},
    28   language, say as arguments to @{command "proof"}, @{command "qed"},
    29   or @{command "by"}.
    29   or @{command "by"}.
    30 
    30 
    31   \item \emph{Attributes} define a tertiary language of small
    31   \<^enum> \emph{Attributes} define a tertiary language of small
    32   annotations to theorems being defined or referenced.  Attributes can
    32   annotations to theorems being defined or referenced.  Attributes can
    33   modify both the context and the theorem.
    33   modify both the context and the theorem.
    34 
    34 
    35   Typical examples are @{attribute intro} (which affects the context),
    35   Typical examples are @{attribute intro} (which affects the context),
    36   and @{attribute symmetric} (which affects the theorem).
    36   and @{attribute symmetric} (which affects the theorem).
   189   tactics need to hold for methods accordingly, with the following
   189   tactics need to hold for methods accordingly, with the following
   190   additions.
   190   additions.
   191 
   191 
   192   \begin{itemize}
   192   \begin{itemize}
   193 
   193 
   194   \item Goal addressing is further limited either to operate
   194   \<^item> Goal addressing is further limited either to operate
   195   uniformly on \emph{all} subgoals, or specifically on the
   195   uniformly on \emph{all} subgoals, or specifically on the
   196   \emph{first} subgoal.
   196   \emph{first} subgoal.
   197 
   197 
   198   Exception: old-style tactic emulations that are embedded into the
   198   Exception: old-style tactic emulations that are embedded into the
   199   method space, e.g.\ @{method rule_tac}.
   199   method space, e.g.\ @{method rule_tac}.
   200 
   200 
   201   \item A non-trivial method always needs to make progress: an
   201   \<^item> A non-trivial method always needs to make progress: an
   202   identical follow-up goal state has to be avoided.\footnote{This
   202   identical follow-up goal state has to be avoided.\footnote{This
   203   enables the user to write method expressions like @{text "meth\<^sup>+"}
   203   enables the user to write method expressions like @{text "meth\<^sup>+"}
   204   without looping, while the trivial do-nothing case can be recovered
   204   without looping, while the trivial do-nothing case can be recovered
   205   via @{text "meth\<^sup>?"}.}
   205   via @{text "meth\<^sup>?"}.}
   206 
   206 
   207   Exception: trivial stuttering steps, such as ``@{method -}'' or
   207   Exception: trivial stuttering steps, such as ``@{method -}'' or
   208   @{method succeed}.
   208   @{method succeed}.
   209 
   209 
   210   \item Goal facts passed to the method must not be ignored.  If there
   210   \<^item> Goal facts passed to the method must not be ignored.  If there
   211   is no sensible use of facts outside the goal state, facts should be
   211   is no sensible use of facts outside the goal state, facts should be
   212   inserted into the subgoals that are addressed by the method.
   212   inserted into the subgoals that are addressed by the method.
   213 
   213 
   214   \end{itemize}
   214   \end{itemize}
   215 
   215 
   216   \medskip Syntactically, the language of proof methods appears as
   216   \<^medskip>
       
   217   Syntactically, the language of proof methods appears as
   217   arguments to Isar commands like @{command "by"} or @{command apply}.
   218   arguments to Isar commands like @{command "by"} or @{command apply}.
   218   User-space additions are reasonably easy by plugging suitable
   219   User-space additions are reasonably easy by plugging suitable
   219   method-valued parser functions into the framework, using the
   220   method-valued parser functions into the framework, using the
   220   @{command method_setup} command, for example.
   221   @{command method_setup} command, for example.
   221 
   222 
   222   To get a better idea about the range of possibilities, consider the
   223   To get a better idea about the range of possibilities, consider the
   223   following Isar proof schemes.  This is the general form of
   224   following Isar proof schemes.  This is the general form of
   224   structured proof text:
   225   structured proof text:
   225 
   226 
   226   \medskip
   227   \<^medskip>
   227   \begin{tabular}{l}
   228   \begin{tabular}{l}
   228   @{command from}~@{text "facts\<^sub>1"}~@{command have}~@{text "props"}~@{command using}~@{text "facts\<^sub>2"} \\
   229   @{command from}~@{text "facts\<^sub>1"}~@{command have}~@{text "props"}~@{command using}~@{text "facts\<^sub>2"} \\
   229   @{command proof}~@{text "(initial_method)"} \\
   230   @{command proof}~@{text "(initial_method)"} \\
   230   \quad@{text "body"} \\
   231   \quad@{text "body"} \\
   231   @{command qed}~@{text "(terminal_method)"} \\
   232   @{command qed}~@{text "(terminal_method)"} \\
   232   \end{tabular}
   233   \end{tabular}
   233   \medskip
   234   \<^medskip>
   234 
   235 
   235   The goal configuration consists of @{text "facts\<^sub>1"} and
   236   The goal configuration consists of @{text "facts\<^sub>1"} and
   236   @{text "facts\<^sub>2"} appended in that order, and various @{text
   237   @{text "facts\<^sub>2"} appended in that order, and various @{text
   237   "props"} being claimed.  The @{text "initial_method"} is invoked
   238   "props"} being claimed.  The @{text "initial_method"} is invoked
   238   with facts and goals together and refines the problem to something
   239   with facts and goals together and refines the problem to something
   239   that is handled recursively in the proof @{text "body"}.  The @{text
   240   that is handled recursively in the proof @{text "body"}.  The @{text
   240   "terminal_method"} has another chance to finish any remaining
   241   "terminal_method"} has another chance to finish any remaining
   241   subgoals, but it does not see the facts of the initial step.
   242   subgoals, but it does not see the facts of the initial step.
   242 
   243 
   243   \medskip This pattern illustrates unstructured proof scripts:
   244   \<^medskip>
   244 
   245   This pattern illustrates unstructured proof scripts:
   245   \medskip
   246 
       
   247   \<^medskip>
   246   \begin{tabular}{l}
   248   \begin{tabular}{l}
   247   @{command have}~@{text "props"} \\
   249   @{command have}~@{text "props"} \\
   248   \quad@{command using}~@{text "facts\<^sub>1"}~@{command apply}~@{text "method\<^sub>1"} \\
   250   \quad@{command using}~@{text "facts\<^sub>1"}~@{command apply}~@{text "method\<^sub>1"} \\
   249   \quad@{command apply}~@{text "method\<^sub>2"} \\
   251   \quad@{command apply}~@{text "method\<^sub>2"} \\
   250   \quad@{command using}~@{text "facts\<^sub>3"}~@{command apply}~@{text "method\<^sub>3"} \\
   252   \quad@{command using}~@{text "facts\<^sub>3"}~@{command apply}~@{text "method\<^sub>3"} \\
   251   \quad@{command done} \\
   253   \quad@{command done} \\
   252   \end{tabular}
   254   \end{tabular}
   253   \medskip
   255   \<^medskip>
   254 
   256 
   255   The @{text "method\<^sub>1"} operates on the original claim while
   257   The @{text "method\<^sub>1"} operates on the original claim while
   256   using @{text "facts\<^sub>1"}.  Since the @{command apply} command
   258   using @{text "facts\<^sub>1"}.  Since the @{command apply} command
   257   structurally resets the facts, the @{text "method\<^sub>2"} will
   259   structurally resets the facts, the @{text "method\<^sub>2"} will
   258   operate on the remaining goal state without facts.  The @{text
   260   operate on the remaining goal state without facts.  The @{text
   259   "method\<^sub>3"} will see again a collection of @{text
   261   "method\<^sub>3"} will see again a collection of @{text
   260   "facts\<^sub>3"} that has been inserted into the script explicitly.
   262   "facts\<^sub>3"} that has been inserted into the script explicitly.
   261 
   263 
   262   \medskip Empirically, any Isar proof method can be categorized as
   264   \<^medskip>
       
   265   Empirically, any Isar proof method can be categorized as
   263   follows.
   266   follows.
   264 
   267 
   265   \begin{enumerate}
   268   \begin{enumerate}
   266 
   269 
   267   \item \emph{Special method with cases} with named context additions
   270   \<^enum> \emph{Special method with cases} with named context additions
   268   associated with the follow-up goal state.
   271   associated with the follow-up goal state.
   269 
   272 
   270   Example: @{method "induct"}, which is also a ``raw'' method since it
   273   Example: @{method "induct"}, which is also a ``raw'' method since it
   271   operates on the internal representation of simultaneous claims as
   274   operates on the internal representation of simultaneous claims as
   272   Pure conjunction (\secref{sec:logic-aux}), instead of separate
   275   Pure conjunction (\secref{sec:logic-aux}), instead of separate
   273   subgoals (\secref{sec:tactical-goals}).
   276   subgoals (\secref{sec:tactical-goals}).
   274 
   277 
   275   \item \emph{Structured method} with strong emphasis on facts outside
   278   \<^enum> \emph{Structured method} with strong emphasis on facts outside
   276   the goal state.
   279   the goal state.
   277 
   280 
   278   Example: @{method "rule"}, which captures the key ideas behind
   281   Example: @{method "rule"}, which captures the key ideas behind
   279   structured reasoning in Isar in its purest form.
   282   structured reasoning in Isar in its purest form.
   280 
   283 
   281   \item \emph{Simple method} with weaker emphasis on facts, which are
   284   \<^enum> \emph{Simple method} with weaker emphasis on facts, which are
   282   inserted into subgoals to emulate old-style tactical ``premises''.
   285   inserted into subgoals to emulate old-style tactical ``premises''.
   283 
   286 
   284   Examples: @{method "simp"}, @{method "blast"}, @{method "auto"}.
   287   Examples: @{method "simp"}, @{method "blast"}, @{method "auto"}.
   285 
   288 
   286   \item \emph{Old-style tactic emulation} with detailed numeric goal
   289   \<^enum> \emph{Old-style tactic emulation} with detailed numeric goal
   287   addressing and explicit references to entities of the internal goal
   290   addressing and explicit references to entities of the internal goal
   288   state (which are otherwise invisible from proper Isar proof text).
   291   state (which are otherwise invisible from proper Isar proof text).
   289   The naming convention @{text "foo_tac"} makes this special
   292   The naming convention @{text "foo_tac"} makes this special
   290   non-standard status clear.
   293   non-standard status clear.
   291 
   294 
   351 \<close>
   354 \<close>
   352 
   355 
   353 text %mlex \<open>See also @{command method_setup} in
   356 text %mlex \<open>See also @{command method_setup} in
   354   @{cite "isabelle-isar-ref"} which includes some abstract examples.
   357   @{cite "isabelle-isar-ref"} which includes some abstract examples.
   355 
   358 
   356   \medskip The following toy examples illustrate how the goal facts
   359   \<^medskip>
       
   360   The following toy examples illustrate how the goal facts
   357   and state are passed to proof methods.  The predefined proof method
   361   and state are passed to proof methods.  The predefined proof method
   358   called ``@{method tactic}'' wraps ML source of type @{ML_type
   362   called ``@{method tactic}'' wraps ML source of type @{ML_type
   359   tactic} (abstracted over @{ML_text facts}).  This allows immediate
   363   tactic} (abstracted over @{ML_text facts}).  This allows immediate
   360   experimentation without parsing of concrete syntax.\<close>
   364   experimentation without parsing of concrete syntax.\<close>
   361 
   365 
   376     apply (tactic \<open>Method.insert_tac facts 1\<close>)
   380     apply (tactic \<open>Method.insert_tac facts 1\<close>)
   377     apply (tactic \<open>(resolve_tac @{context} @{thms conjI} THEN_ALL_NEW assume_tac @{context}) 1\<close>)
   381     apply (tactic \<open>(resolve_tac @{context} @{thms conjI} THEN_ALL_NEW assume_tac @{context}) 1\<close>)
   378     done
   382     done
   379 end
   383 end
   380 
   384 
   381 text \<open>\medskip The next example implements a method that simplifies
   385 text \<open>
       
   386   \<^medskip>
       
   387   The next example implements a method that simplifies
   382   the first subgoal by rewrite rules that are given as arguments.\<close>
   388   the first subgoal by rewrite rules that are given as arguments.\<close>
   383 
   389 
   384 method_setup my_simp =
   390 method_setup my_simp =
   385   \<open>Attrib.thms >> (fn thms => fn ctxt =>
   391   \<open>Attrib.thms >> (fn thms => fn ctxt =>
   386     SIMPLE_METHOD' (fn i =>
   392     SIMPLE_METHOD' (fn i =>
   402   method @{method simp} by default.  The extra wrapping by the @{ML
   408   method @{method simp} by default.  The extra wrapping by the @{ML
   403   CHANGED} tactical ensures progress of simplification: identical goal
   409   CHANGED} tactical ensures progress of simplification: identical goal
   404   states are filtered out explicitly to make the raw tactic conform to
   410   states are filtered out explicitly to make the raw tactic conform to
   405   standard Isar method behaviour.
   411   standard Isar method behaviour.
   406 
   412 
   407   \medskip Method @{method my_simp} can be used in Isar proofs like
   413   \<^medskip>
   408   this:
   414   Method @{method my_simp} can be used in Isar proofs like this:
   409 \<close>
   415 \<close>
   410 
   416 
   411 notepad
   417 notepad
   412 begin
   418 begin
   413   fix a b c :: 'a
   419   fix a b c :: 'a
   433   assume a: "a = b"
   439   assume a: "a = b"
   434   assume b: "b = c"
   440   assume b: "b = c"
   435   have "a = c" and "c = b" by (my_simp_all a b)
   441   have "a = c" and "c = b" by (my_simp_all a b)
   436 end
   442 end
   437 
   443 
   438 text \<open>\medskip Apart from explicit arguments, common proof methods
   444 text \<open>
       
   445   \<^medskip>
       
   446   Apart from explicit arguments, common proof methods
   439   typically work with a default configuration provided by the context. As a
   447   typically work with a default configuration provided by the context. As a
   440   shortcut to rule management we use a cheap solution via the @{command
   448   shortcut to rule management we use a cheap solution via the @{command
   441   named_theorems} command to declare a dynamic fact in the context.\<close>
   449   named_theorems} command to declare a dynamic fact in the context.\<close>
   442 
   450 
   443 named_theorems my_simp
   451 named_theorems my_simp
   456             addsimps (thms @ my_simps)) i))
   464             addsimps (thms @ my_simps)) i))
   457     end)\<close>
   465     end)\<close>
   458   "rewrite subgoal by given rules and my_simp rules from the context"
   466   "rewrite subgoal by given rules and my_simp rules from the context"
   459 
   467 
   460 text \<open>
   468 text \<open>
   461   \medskip Method @{method my_simp'} can be used in Isar proofs
   469   \<^medskip>
       
   470   Method @{method my_simp'} can be used in Isar proofs
   462   like this:
   471   like this:
   463 \<close>
   472 \<close>
   464 
   473 
   465 notepad
   474 notepad
   466 begin
   475 begin
   468   assume [my_simp]: "a \<equiv> b"
   477   assume [my_simp]: "a \<equiv> b"
   469   assume [my_simp]: "b \<equiv> c"
   478   assume [my_simp]: "b \<equiv> c"
   470   have "a \<equiv> c" by my_simp'
   479   have "a \<equiv> c" by my_simp'
   471 end
   480 end
   472 
   481 
   473 text \<open>\medskip The @{method my_simp} variants defined above are
   482 text \<open>
       
   483   \<^medskip>
       
   484   The @{method my_simp} variants defined above are
   474   ``simple'' methods, i.e.\ the goal facts are merely inserted as goal
   485   ``simple'' methods, i.e.\ the goal facts are merely inserted as goal
   475   premises by the @{ML SIMPLE_METHOD'} or @{ML SIMPLE_METHOD} wrapper.
   486   premises by the @{ML SIMPLE_METHOD'} or @{ML SIMPLE_METHOD} wrapper.
   476   For proof methods that are similar to the standard collection of
   487   For proof methods that are similar to the standard collection of
   477   @{method simp}, @{method blast}, @{method fast}, @{method auto}
   488   @{method simp}, @{method blast}, @{method fast}, @{method auto}
   478   there is little more that can be done.
   489   there is little more that can be done.
   483   proof methods, because rewrite rules as used above can be easily
   494   proof methods, because rewrite rules as used above can be easily
   484   ignored.  A proof text ``@{command using}~@{text "foo"}~@{command
   495   ignored.  A proof text ``@{command using}~@{text "foo"}~@{command
   485   "by"}~@{text "my_simp"}'' where @{text "foo"} is not used would
   496   "by"}~@{text "my_simp"}'' where @{text "foo"} is not used would
   486   deceive the reader.
   497   deceive the reader.
   487 
   498 
   488   \medskip The technical treatment of rules from the context requires
   499   \<^medskip>
       
   500   The technical treatment of rules from the context requires
   489   further attention.  Above we rebuild a fresh @{ML_type simpset} from
   501   further attention.  Above we rebuild a fresh @{ML_type simpset} from
   490   the arguments and \emph{all} rules retrieved from the context on
   502   the arguments and \emph{all} rules retrieved from the context on
   491   every invocation of the method.  This does not scale to really large
   503   every invocation of the method.  This does not scale to really large
   492   collections of rules, which easily emerges in the context of a big
   504   collections of rules, which easily emerges in the context of a big
   493   theory library, for example.
   505   theory library, for example.