src/Doc/Implementation/Tactic.thy
changeset 61439 2bf52eec4e8a
parent 61416 b9a3324e4e62
child 61458 987533262fc2
equal deleted inserted replaced
61438:151f894984d8 61439:2bf52eec4e8a
    70   @{index_ML Goal.conclude: "thm -> thm"} \\
    70   @{index_ML Goal.conclude: "thm -> thm"} \\
    71   \end{mldecls}
    71   \end{mldecls}
    72 
    72 
    73   \begin{description}
    73   \begin{description}
    74 
    74 
    75   \item @{ML "Goal.init"}~@{text C} initializes a tactical goal from
    75   \<^descr> @{ML "Goal.init"}~@{text C} initializes a tactical goal from
    76   the well-formed proposition @{text C}.
    76   the well-formed proposition @{text C}.
    77 
    77 
    78   \item @{ML "Goal.finish"}~@{text "ctxt thm"} checks whether theorem
    78   \<^descr> @{ML "Goal.finish"}~@{text "ctxt thm"} checks whether theorem
    79   @{text "thm"} is a solved goal (no subgoals), and concludes the
    79   @{text "thm"} is a solved goal (no subgoals), and concludes the
    80   result by removing the goal protection.  The context is only
    80   result by removing the goal protection.  The context is only
    81   required for printing error messages.
    81   required for printing error messages.
    82 
    82 
    83   \item @{ML "Goal.protect"}~@{text "n thm"} protects the statement
    83   \<^descr> @{ML "Goal.protect"}~@{text "n thm"} protects the statement
    84   of theorem @{text "thm"}.  The parameter @{text n} indicates the
    84   of theorem @{text "thm"}.  The parameter @{text n} indicates the
    85   number of premises to be retained.
    85   number of premises to be retained.
    86 
    86 
    87   \item @{ML "Goal.conclude"}~@{text "thm"} removes the goal
    87   \<^descr> @{ML "Goal.conclude"}~@{text "thm"} removes the goal
    88   protection, even if there are pending subgoals.
    88   protection, even if there are pending subgoals.
    89 
    89 
    90   \end{description}
    90   \end{description}
    91 \<close>
    91 \<close>
    92 
    92 
   187   @{index_ML PREFER_GOAL: "tactic -> int -> tactic"} \\
   187   @{index_ML PREFER_GOAL: "tactic -> int -> tactic"} \\
   188   \end{mldecls}
   188   \end{mldecls}
   189 
   189 
   190   \begin{description}
   190   \begin{description}
   191 
   191 
   192   \item Type @{ML_type tactic} represents tactics.  The
   192   \<^descr> Type @{ML_type tactic} represents tactics.  The
   193   well-formedness conditions described above need to be observed.  See
   193   well-formedness conditions described above need to be observed.  See
   194   also @{file "~~/src/Pure/General/seq.ML"} for the underlying
   194   also @{file "~~/src/Pure/General/seq.ML"} for the underlying
   195   implementation of lazy sequences.
   195   implementation of lazy sequences.
   196 
   196 
   197   \item Type @{ML_type "int -> tactic"} represents tactics with
   197   \<^descr> Type @{ML_type "int -> tactic"} represents tactics with
   198   explicit subgoal addressing, with well-formedness conditions as
   198   explicit subgoal addressing, with well-formedness conditions as
   199   described above.
   199   described above.
   200 
   200 
   201   \item @{ML no_tac} is a tactic that always fails, returning the
   201   \<^descr> @{ML no_tac} is a tactic that always fails, returning the
   202   empty sequence.
   202   empty sequence.
   203 
   203 
   204   \item @{ML all_tac} is a tactic that always succeeds, returning a
   204   \<^descr> @{ML all_tac} is a tactic that always succeeds, returning a
   205   singleton sequence with unchanged goal state.
   205   singleton sequence with unchanged goal state.
   206 
   206 
   207   \item @{ML print_tac}~@{text "ctxt message"} is like @{ML all_tac}, but
   207   \<^descr> @{ML print_tac}~@{text "ctxt message"} is like @{ML all_tac}, but
   208   prints a message together with the goal state on the tracing
   208   prints a message together with the goal state on the tracing
   209   channel.
   209   channel.
   210 
   210 
   211   \item @{ML PRIMITIVE}~@{text rule} turns a primitive inference rule
   211   \<^descr> @{ML PRIMITIVE}~@{text rule} turns a primitive inference rule
   212   into a tactic with unique result.  Exception @{ML THM} is considered
   212   into a tactic with unique result.  Exception @{ML THM} is considered
   213   a regular tactic failure and produces an empty result; other
   213   a regular tactic failure and produces an empty result; other
   214   exceptions are passed through.
   214   exceptions are passed through.
   215 
   215 
   216   \item @{ML SUBGOAL}~@{text "(fn (subgoal, i) => tactic)"} is the
   216   \<^descr> @{ML SUBGOAL}~@{text "(fn (subgoal, i) => tactic)"} is the
   217   most basic form to produce a tactic with subgoal addressing.  The
   217   most basic form to produce a tactic with subgoal addressing.  The
   218   given abstraction over the subgoal term and subgoal number allows to
   218   given abstraction over the subgoal term and subgoal number allows to
   219   peek at the relevant information of the full goal state.  The
   219   peek at the relevant information of the full goal state.  The
   220   subgoal range is checked as required above.
   220   subgoal range is checked as required above.
   221 
   221 
   222   \item @{ML CSUBGOAL} is similar to @{ML SUBGOAL}, but passes the
   222   \<^descr> @{ML CSUBGOAL} is similar to @{ML SUBGOAL}, but passes the
   223   subgoal as @{ML_type cterm} instead of raw @{ML_type term}.  This
   223   subgoal as @{ML_type cterm} instead of raw @{ML_type term}.  This
   224   avoids expensive re-certification in situations where the subgoal is
   224   avoids expensive re-certification in situations where the subgoal is
   225   used directly for primitive inferences.
   225   used directly for primitive inferences.
   226 
   226 
   227   \item @{ML SELECT_GOAL}~@{text "tac i"} confines a tactic to the
   227   \<^descr> @{ML SELECT_GOAL}~@{text "tac i"} confines a tactic to the
   228   specified subgoal @{text "i"}.  This rearranges subgoals and the
   228   specified subgoal @{text "i"}.  This rearranges subgoals and the
   229   main goal protection (\secref{sec:tactical-goals}), while retaining
   229   main goal protection (\secref{sec:tactical-goals}), while retaining
   230   the syntactic context of the overall goal state (concerning
   230   the syntactic context of the overall goal state (concerning
   231   schematic variables etc.).
   231   schematic variables etc.).
   232 
   232 
   233   \item @{ML PREFER_GOAL}~@{text "tac i"} rearranges subgoals to put
   233   \<^descr> @{ML PREFER_GOAL}~@{text "tac i"} rearranges subgoals to put
   234   @{text "i"} in front.  This is similar to @{ML SELECT_GOAL}, but
   234   @{text "i"} in front.  This is similar to @{ML SELECT_GOAL}, but
   235   without changing the main goal protection.
   235   without changing the main goal protection.
   236 
   236 
   237   \end{description}
   237   \end{description}
   238 \<close>
   238 \<close>
   295   @{index_ML bimatch_tac: "Proof.context -> (bool * thm) list -> int -> tactic"} \\
   295   @{index_ML bimatch_tac: "Proof.context -> (bool * thm) list -> int -> tactic"} \\
   296   \end{mldecls}
   296   \end{mldecls}
   297 
   297 
   298   \begin{description}
   298   \begin{description}
   299 
   299 
   300   \item @{ML resolve_tac}~@{text "ctxt thms i"} refines the goal state
   300   \<^descr> @{ML resolve_tac}~@{text "ctxt thms i"} refines the goal state
   301   using the given theorems, which should normally be introduction
   301   using the given theorems, which should normally be introduction
   302   rules.  The tactic resolves a rule's conclusion with subgoal @{text
   302   rules.  The tactic resolves a rule's conclusion with subgoal @{text
   303   i}, replacing it by the corresponding versions of the rule's
   303   i}, replacing it by the corresponding versions of the rule's
   304   premises.
   304   premises.
   305 
   305 
   306   \item @{ML eresolve_tac}~@{text "ctxt thms i"} performs elim-resolution
   306   \<^descr> @{ML eresolve_tac}~@{text "ctxt thms i"} performs elim-resolution
   307   with the given theorems, which are normally be elimination rules.
   307   with the given theorems, which are normally be elimination rules.
   308 
   308 
   309   Note that @{ML_text "eresolve_tac ctxt [asm_rl]"} is equivalent to @{ML_text
   309   Note that @{ML_text "eresolve_tac ctxt [asm_rl]"} is equivalent to @{ML_text
   310   "assume_tac ctxt"}, which facilitates mixing of assumption steps with
   310   "assume_tac ctxt"}, which facilitates mixing of assumption steps with
   311   genuine eliminations.
   311   genuine eliminations.
   312 
   312 
   313   \item @{ML dresolve_tac}~@{text "ctxt thms i"} performs
   313   \<^descr> @{ML dresolve_tac}~@{text "ctxt thms i"} performs
   314   destruct-resolution with the given theorems, which should normally
   314   destruct-resolution with the given theorems, which should normally
   315   be destruction rules.  This replaces an assumption by the result of
   315   be destruction rules.  This replaces an assumption by the result of
   316   applying one of the rules.
   316   applying one of the rules.
   317 
   317 
   318   \item @{ML forward_tac} is like @{ML dresolve_tac} except that the
   318   \<^descr> @{ML forward_tac} is like @{ML dresolve_tac} except that the
   319   selected assumption is not deleted.  It applies a rule to an
   319   selected assumption is not deleted.  It applies a rule to an
   320   assumption, adding the result as a new assumption.
   320   assumption, adding the result as a new assumption.
   321 
   321 
   322   \item @{ML biresolve_tac}~@{text "ctxt brls i"} refines the proof state
   322   \<^descr> @{ML biresolve_tac}~@{text "ctxt brls i"} refines the proof state
   323   by resolution or elim-resolution on each rule, as indicated by its
   323   by resolution or elim-resolution on each rule, as indicated by its
   324   flag.  It affects subgoal @{text "i"} of the proof state.
   324   flag.  It affects subgoal @{text "i"} of the proof state.
   325 
   325 
   326   For each pair @{text "(flag, rule)"}, it applies resolution if the
   326   For each pair @{text "(flag, rule)"}, it applies resolution if the
   327   flag is @{text "false"} and elim-resolution if the flag is @{text
   327   flag is @{text "false"} and elim-resolution if the flag is @{text
   328   "true"}.  A single tactic call handles a mixture of introduction and
   328   "true"}.  A single tactic call handles a mixture of introduction and
   329   elimination rules, which is useful to organize the search process
   329   elimination rules, which is useful to organize the search process
   330   systematically in proof tools.
   330   systematically in proof tools.
   331 
   331 
   332   \item @{ML assume_tac}~@{text "ctxt i"} attempts to solve subgoal @{text i}
   332   \<^descr> @{ML assume_tac}~@{text "ctxt i"} attempts to solve subgoal @{text i}
   333   by assumption (modulo higher-order unification).
   333   by assumption (modulo higher-order unification).
   334 
   334 
   335   \item @{ML eq_assume_tac} is similar to @{ML assume_tac}, but checks
   335   \<^descr> @{ML eq_assume_tac} is similar to @{ML assume_tac}, but checks
   336   only for immediate @{text "\<alpha>"}-convertibility instead of using
   336   only for immediate @{text "\<alpha>"}-convertibility instead of using
   337   unification.  It succeeds (with a unique next state) if one of the
   337   unification.  It succeeds (with a unique next state) if one of the
   338   assumptions is equal to the subgoal's conclusion.  Since it does not
   338   assumptions is equal to the subgoal's conclusion.  Since it does not
   339   instantiate variables, it cannot make other subgoals unprovable.
   339   instantiate variables, it cannot make other subgoals unprovable.
   340 
   340 
   341   \item @{ML match_tac}, @{ML ematch_tac}, @{ML dmatch_tac}, and @{ML
   341   \<^descr> @{ML match_tac}, @{ML ematch_tac}, @{ML dmatch_tac}, and @{ML
   342   bimatch_tac} are similar to @{ML resolve_tac}, @{ML eresolve_tac},
   342   bimatch_tac} are similar to @{ML resolve_tac}, @{ML eresolve_tac},
   343   @{ML dresolve_tac}, and @{ML biresolve_tac}, respectively, but do
   343   @{ML dresolve_tac}, and @{ML biresolve_tac}, respectively, but do
   344   not instantiate schematic variables in the goal state.%
   344   not instantiate schematic variables in the goal state.%
   345 \footnote{Strictly speaking, matching means to treat the unknowns in the goal
   345 \footnote{Strictly speaking, matching means to treat the unknowns in the goal
   346   state as constants, but these tactics merely discard unifiers that would
   346   state as constants, but these tactics merely discard unifiers that would
   419   @{index_ML rename_tac: "string list -> int -> tactic"} \\
   419   @{index_ML rename_tac: "string list -> int -> tactic"} \\
   420   \end{mldecls}
   420   \end{mldecls}
   421 
   421 
   422   \begin{description}
   422   \begin{description}
   423 
   423 
   424   \item @{ML Rule_Insts.res_inst_tac}~@{text "ctxt insts thm i"} instantiates the
   424   \<^descr> @{ML Rule_Insts.res_inst_tac}~@{text "ctxt insts thm i"} instantiates the
   425   rule @{text thm} with the instantiations @{text insts}, as described
   425   rule @{text thm} with the instantiations @{text insts}, as described
   426   above, and then performs resolution on subgoal @{text i}.
   426   above, and then performs resolution on subgoal @{text i}.
   427   
   427   
   428   \item @{ML Rule_Insts.eres_inst_tac} is like @{ML Rule_Insts.res_inst_tac},
   428   \<^descr> @{ML Rule_Insts.eres_inst_tac} is like @{ML Rule_Insts.res_inst_tac},
   429   but performs elim-resolution.
   429   but performs elim-resolution.
   430 
   430 
   431   \item @{ML Rule_Insts.dres_inst_tac} is like @{ML Rule_Insts.res_inst_tac},
   431   \<^descr> @{ML Rule_Insts.dres_inst_tac} is like @{ML Rule_Insts.res_inst_tac},
   432   but performs destruct-resolution.
   432   but performs destruct-resolution.
   433 
   433 
   434   \item @{ML Rule_Insts.forw_inst_tac} is like @{ML Rule_Insts.dres_inst_tac}
   434   \<^descr> @{ML Rule_Insts.forw_inst_tac} is like @{ML Rule_Insts.dres_inst_tac}
   435   except that the selected assumption is not deleted.
   435   except that the selected assumption is not deleted.
   436 
   436 
   437   \item @{ML Rule_Insts.subgoal_tac}~@{text "ctxt \<phi> i"} adds the proposition
   437   \<^descr> @{ML Rule_Insts.subgoal_tac}~@{text "ctxt \<phi> i"} adds the proposition
   438   @{text "\<phi>"} as local premise to subgoal @{text "i"}, and poses the
   438   @{text "\<phi>"} as local premise to subgoal @{text "i"}, and poses the
   439   same as a new subgoal @{text "i + 1"} (in the original context).
   439   same as a new subgoal @{text "i + 1"} (in the original context).
   440 
   440 
   441   \item @{ML Rule_Insts.thin_tac}~@{text "ctxt \<phi> i"} deletes the specified
   441   \<^descr> @{ML Rule_Insts.thin_tac}~@{text "ctxt \<phi> i"} deletes the specified
   442   premise from subgoal @{text i}.  Note that @{text \<phi>} may contain
   442   premise from subgoal @{text i}.  Note that @{text \<phi>} may contain
   443   schematic variables, to abbreviate the intended proposition; the
   443   schematic variables, to abbreviate the intended proposition; the
   444   first matching subgoal premise will be deleted.  Removing useless
   444   first matching subgoal premise will be deleted.  Removing useless
   445   premises from a subgoal increases its readability and can make
   445   premises from a subgoal increases its readability and can make
   446   search tactics run faster.
   446   search tactics run faster.
   447 
   447 
   448   \item @{ML rename_tac}~@{text "names i"} renames the innermost
   448   \<^descr> @{ML rename_tac}~@{text "names i"} renames the innermost
   449   parameters of subgoal @{text i} according to the provided @{text
   449   parameters of subgoal @{text i} according to the provided @{text
   450   names} (which need to be distinct identifiers).
   450   names} (which need to be distinct identifiers).
   451 
   451 
   452   \end{description}
   452   \end{description}
   453 
   453 
   473   @{index_ML flexflex_tac: "Proof.context -> tactic"} \\
   473   @{index_ML flexflex_tac: "Proof.context -> tactic"} \\
   474   \end{mldecls}
   474   \end{mldecls}
   475 
   475 
   476   \begin{description}
   476   \begin{description}
   477 
   477 
   478   \item @{ML rotate_tac}~@{text "n i"} rotates the premises of subgoal
   478   \<^descr> @{ML rotate_tac}~@{text "n i"} rotates the premises of subgoal
   479   @{text i} by @{text n} positions: from right to left if @{text n} is
   479   @{text i} by @{text n} positions: from right to left if @{text n} is
   480   positive, and from left to right if @{text n} is negative.
   480   positive, and from left to right if @{text n} is negative.
   481 
   481 
   482   \item @{ML distinct_subgoals_tac} removes duplicate subgoals from a
   482   \<^descr> @{ML distinct_subgoals_tac} removes duplicate subgoals from a
   483   proof state.  This is potentially inefficient.
   483   proof state.  This is potentially inefficient.
   484 
   484 
   485   \item @{ML flexflex_tac} removes all flex-flex pairs from the proof
   485   \<^descr> @{ML flexflex_tac} removes all flex-flex pairs from the proof
   486   state by applying the trivial unifier.  This drastic step loses
   486   state by applying the trivial unifier.  This drastic step loses
   487   information.  It is already part of the Isar infrastructure for
   487   information.  It is already part of the Isar infrastructure for
   488   facts resulting from goals, and rarely needs to be invoked manually.
   488   facts resulting from goals, and rarely needs to be invoked manually.
   489 
   489 
   490   Flex-flex constraints arise from difficult cases of higher-order
   490   Flex-flex constraints arise from difficult cases of higher-order
   513   @{index_ML_op COMP: "thm * thm -> thm"} \\
   513   @{index_ML_op COMP: "thm * thm -> thm"} \\
   514   \end{mldecls}
   514   \end{mldecls}
   515 
   515 
   516   \begin{description}
   516   \begin{description}
   517 
   517 
   518   \item @{ML compose_tac}~@{text "ctxt (flag, rule, m) i"} refines subgoal
   518   \<^descr> @{ML compose_tac}~@{text "ctxt (flag, rule, m) i"} refines subgoal
   519   @{text "i"} using @{text "rule"}, without lifting.  The @{text
   519   @{text "i"} using @{text "rule"}, without lifting.  The @{text
   520   "rule"} is taken to have the form @{text "\<psi>\<^sub>1 \<Longrightarrow> \<dots> \<psi>\<^sub>m \<Longrightarrow> \<psi>"}, where
   520   "rule"} is taken to have the form @{text "\<psi>\<^sub>1 \<Longrightarrow> \<dots> \<psi>\<^sub>m \<Longrightarrow> \<psi>"}, where
   521   @{text "\<psi>"} need not be atomic; thus @{text "m"} determines the
   521   @{text "\<psi>"} need not be atomic; thus @{text "m"} determines the
   522   number of new subgoals.  If @{text "flag"} is @{text "true"} then it
   522   number of new subgoals.  If @{text "flag"} is @{text "true"} then it
   523   performs elim-resolution --- it solves the first premise of @{text
   523   performs elim-resolution --- it solves the first premise of @{text
   524   "rule"} by assumption and deletes that assumption.
   524   "rule"} by assumption and deletes that assumption.
   525 
   525 
   526   \item @{ML Drule.compose}~@{text "(thm\<^sub>1, i, thm\<^sub>2)"} uses @{text "thm\<^sub>1"},
   526   \<^descr> @{ML Drule.compose}~@{text "(thm\<^sub>1, i, thm\<^sub>2)"} uses @{text "thm\<^sub>1"},
   527   regarded as an atomic formula, to solve premise @{text "i"} of
   527   regarded as an atomic formula, to solve premise @{text "i"} of
   528   @{text "thm\<^sub>2"}.  Let @{text "thm\<^sub>1"} and @{text "thm\<^sub>2"} be @{text
   528   @{text "thm\<^sub>2"}.  Let @{text "thm\<^sub>1"} and @{text "thm\<^sub>2"} be @{text
   529   "\<psi>"} and @{text "\<phi>\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> \<phi>"}.  The unique @{text "s"} that
   529   "\<psi>"} and @{text "\<phi>\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> \<phi>"}.  The unique @{text "s"} that
   530   unifies @{text "\<psi>"} and @{text "\<phi>\<^sub>i"} yields the theorem @{text "(\<phi>\<^sub>1 \<Longrightarrow>
   530   unifies @{text "\<psi>"} and @{text "\<phi>\<^sub>i"} yields the theorem @{text "(\<phi>\<^sub>1 \<Longrightarrow>
   531   \<dots> \<phi>\<^sub>i\<^sub>-\<^sub>1 \<Longrightarrow> \<phi>\<^sub>i\<^sub>+\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> \<phi>)s"}.  Multiple results are considered as
   531   \<dots> \<phi>\<^sub>i\<^sub>-\<^sub>1 \<Longrightarrow> \<phi>\<^sub>i\<^sub>+\<^sub>1 \<Longrightarrow> \<dots> \<phi>\<^sub>n \<Longrightarrow> \<phi>)s"}.  Multiple results are considered as
   532   error (exception @{ML THM}).
   532   error (exception @{ML THM}).
   533 
   533 
   534   \item @{text "thm\<^sub>1 COMP thm\<^sub>2"} is the same as @{text "Drule.compose
   534   \<^descr> @{text "thm\<^sub>1 COMP thm\<^sub>2"} is the same as @{text "Drule.compose
   535   (thm\<^sub>1, 1, thm\<^sub>2)"}.
   535   (thm\<^sub>1, 1, thm\<^sub>2)"}.
   536 
   536 
   537   \end{description}
   537   \end{description}
   538 
   538 
   539   \begin{warn}
   539   \begin{warn}
   581   @{index_ML "FIRST'": "('a -> tactic) list -> 'a -> tactic"} \\
   581   @{index_ML "FIRST'": "('a -> tactic) list -> 'a -> tactic"} \\
   582   \end{mldecls}
   582   \end{mldecls}
   583 
   583 
   584   \begin{description}
   584   \begin{description}
   585 
   585 
   586   \item @{text "tac\<^sub>1"}~@{ML_op THEN}~@{text "tac\<^sub>2"} is the sequential
   586   \<^descr> @{text "tac\<^sub>1"}~@{ML_op THEN}~@{text "tac\<^sub>2"} is the sequential
   587   composition of @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"}.  Applied to a goal
   587   composition of @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"}.  Applied to a goal
   588   state, it returns all states reachable in two steps by applying
   588   state, it returns all states reachable in two steps by applying
   589   @{text "tac\<^sub>1"} followed by @{text "tac\<^sub>2"}.  First, it applies @{text
   589   @{text "tac\<^sub>1"} followed by @{text "tac\<^sub>2"}.  First, it applies @{text
   590   "tac\<^sub>1"} to the goal state, getting a sequence of possible next
   590   "tac\<^sub>1"} to the goal state, getting a sequence of possible next
   591   states; then, it applies @{text "tac\<^sub>2"} to each of these and
   591   states; then, it applies @{text "tac\<^sub>2"} to each of these and
   592   concatenates the results to produce again one flat sequence of
   592   concatenates the results to produce again one flat sequence of
   593   states.
   593   states.
   594 
   594 
   595   \item @{text "tac\<^sub>1"}~@{ML_op ORELSE}~@{text "tac\<^sub>2"} makes a choice
   595   \<^descr> @{text "tac\<^sub>1"}~@{ML_op ORELSE}~@{text "tac\<^sub>2"} makes a choice
   596   between @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"}.  Applied to a state, it
   596   between @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"}.  Applied to a state, it
   597   tries @{text "tac\<^sub>1"} and returns the result if non-empty; if @{text
   597   tries @{text "tac\<^sub>1"} and returns the result if non-empty; if @{text
   598   "tac\<^sub>1"} fails then it uses @{text "tac\<^sub>2"}.  This is a deterministic
   598   "tac\<^sub>1"} fails then it uses @{text "tac\<^sub>2"}.  This is a deterministic
   599   choice: if @{text "tac\<^sub>1"} succeeds then @{text "tac\<^sub>2"} is excluded
   599   choice: if @{text "tac\<^sub>1"} succeeds then @{text "tac\<^sub>2"} is excluded
   600   from the result.
   600   from the result.
   601 
   601 
   602   \item @{text "tac\<^sub>1"}~@{ML_op APPEND}~@{text "tac\<^sub>2"} concatenates the
   602   \<^descr> @{text "tac\<^sub>1"}~@{ML_op APPEND}~@{text "tac\<^sub>2"} concatenates the
   603   possible results of @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"}.  Unlike
   603   possible results of @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"}.  Unlike
   604   @{ML_op "ORELSE"} there is \emph{no commitment} to either tactic, so
   604   @{ML_op "ORELSE"} there is \emph{no commitment} to either tactic, so
   605   @{ML_op "APPEND"} helps to avoid incompleteness during search, at
   605   @{ML_op "APPEND"} helps to avoid incompleteness during search, at
   606   the cost of potential inefficiencies.
   606   the cost of potential inefficiencies.
   607 
   607 
   608   \item @{ML EVERY}~@{text "[tac\<^sub>1, \<dots>, tac\<^sub>n]"} abbreviates @{text
   608   \<^descr> @{ML EVERY}~@{text "[tac\<^sub>1, \<dots>, tac\<^sub>n]"} abbreviates @{text
   609   "tac\<^sub>1"}~@{ML_op THEN}~@{text "\<dots>"}~@{ML_op THEN}~@{text "tac\<^sub>n"}.
   609   "tac\<^sub>1"}~@{ML_op THEN}~@{text "\<dots>"}~@{ML_op THEN}~@{text "tac\<^sub>n"}.
   610   Note that @{ML "EVERY []"} is the same as @{ML all_tac}: it always
   610   Note that @{ML "EVERY []"} is the same as @{ML all_tac}: it always
   611   succeeds.
   611   succeeds.
   612 
   612 
   613   \item @{ML FIRST}~@{text "[tac\<^sub>1, \<dots>, tac\<^sub>n]"} abbreviates @{text
   613   \<^descr> @{ML FIRST}~@{text "[tac\<^sub>1, \<dots>, tac\<^sub>n]"} abbreviates @{text
   614   "tac\<^sub>1"}~@{ML_op ORELSE}~@{text "\<dots>"}~@{ML_op "ORELSE"}~@{text
   614   "tac\<^sub>1"}~@{ML_op ORELSE}~@{text "\<dots>"}~@{ML_op "ORELSE"}~@{text
   615   "tac\<^sub>n"}.  Note that @{ML "FIRST []"} is the same as @{ML no_tac}: it
   615   "tac\<^sub>n"}.  Note that @{ML "FIRST []"} is the same as @{ML no_tac}: it
   616   always fails.
   616   always fails.
   617 
   617 
   618   \item @{ML_op "THEN'"} is the lifted version of @{ML_op "THEN"}, for
   618   \<^descr> @{ML_op "THEN'"} is the lifted version of @{ML_op "THEN"}, for
   619   tactics with explicit subgoal addressing.  So @{text
   619   tactics with explicit subgoal addressing.  So @{text
   620   "(tac\<^sub>1"}~@{ML_op THEN'}~@{text "tac\<^sub>2) i"} is the same as @{text
   620   "(tac\<^sub>1"}~@{ML_op THEN'}~@{text "tac\<^sub>2) i"} is the same as @{text
   621   "(tac\<^sub>1 i"}~@{ML_op THEN}~@{text "tac\<^sub>2 i)"}.
   621   "(tac\<^sub>1 i"}~@{ML_op THEN}~@{text "tac\<^sub>2 i)"}.
   622 
   622 
   623   The other primed tacticals work analogously.
   623   The other primed tacticals work analogously.
   641   @{index_ML "REPEAT_DETERM_N": "int -> tactic -> tactic"} \\
   641   @{index_ML "REPEAT_DETERM_N": "int -> tactic -> tactic"} \\
   642   \end{mldecls}
   642   \end{mldecls}
   643 
   643 
   644   \begin{description}
   644   \begin{description}
   645 
   645 
   646   \item @{ML TRY}~@{text "tac"} applies @{text "tac"} to the goal
   646   \<^descr> @{ML TRY}~@{text "tac"} applies @{text "tac"} to the goal
   647   state and returns the resulting sequence, if non-empty; otherwise it
   647   state and returns the resulting sequence, if non-empty; otherwise it
   648   returns the original state.  Thus, it applies @{text "tac"} at most
   648   returns the original state.  Thus, it applies @{text "tac"} at most
   649   once.
   649   once.
   650 
   650 
   651   Note that for tactics with subgoal addressing, the combinator can be
   651   Note that for tactics with subgoal addressing, the combinator can be
   652   applied via functional composition: @{ML "TRY"}~@{ML_op o}~@{text
   652   applied via functional composition: @{ML "TRY"}~@{ML_op o}~@{text
   653   "tac"}.  There is no need for @{verbatim TRY'}.
   653   "tac"}.  There is no need for @{verbatim TRY'}.
   654 
   654 
   655   \item @{ML REPEAT}~@{text "tac"} applies @{text "tac"} to the goal
   655   \<^descr> @{ML REPEAT}~@{text "tac"} applies @{text "tac"} to the goal
   656   state and, recursively, to each element of the resulting sequence.
   656   state and, recursively, to each element of the resulting sequence.
   657   The resulting sequence consists of those states that make @{text
   657   The resulting sequence consists of those states that make @{text
   658   "tac"} fail.  Thus, it applies @{text "tac"} as many times as
   658   "tac"} fail.  Thus, it applies @{text "tac"} as many times as
   659   possible (including zero times), and allows backtracking over each
   659   possible (including zero times), and allows backtracking over each
   660   invocation of @{text "tac"}.  @{ML REPEAT} is more general than @{ML
   660   invocation of @{text "tac"}.  @{ML REPEAT} is more general than @{ML
   661   REPEAT_DETERM}, but requires more space.
   661   REPEAT_DETERM}, but requires more space.
   662 
   662 
   663   \item @{ML REPEAT1}~@{text "tac"} is like @{ML REPEAT}~@{text "tac"}
   663   \<^descr> @{ML REPEAT1}~@{text "tac"} is like @{ML REPEAT}~@{text "tac"}
   664   but it always applies @{text "tac"} at least once, failing if this
   664   but it always applies @{text "tac"} at least once, failing if this
   665   is impossible.
   665   is impossible.
   666 
   666 
   667   \item @{ML REPEAT_DETERM}~@{text "tac"} applies @{text "tac"} to the
   667   \<^descr> @{ML REPEAT_DETERM}~@{text "tac"} applies @{text "tac"} to the
   668   goal state and, recursively, to the head of the resulting sequence.
   668   goal state and, recursively, to the head of the resulting sequence.
   669   It returns the first state to make @{text "tac"} fail.  It is
   669   It returns the first state to make @{text "tac"} fail.  It is
   670   deterministic, discarding alternative outcomes.
   670   deterministic, discarding alternative outcomes.
   671 
   671 
   672   \item @{ML REPEAT_DETERM_N}~@{text "n tac"} is like @{ML
   672   \<^descr> @{ML REPEAT_DETERM_N}~@{text "n tac"} is like @{ML
   673   REPEAT_DETERM}~@{text "tac"} but the number of repetitions is bound
   673   REPEAT_DETERM}~@{text "tac"} but the number of repetitions is bound
   674   by @{text "n"} (where @{ML "~1"} means @{text "\<infinity>"}).
   674   by @{text "n"} (where @{ML "~1"} means @{text "\<infinity>"}).
   675 
   675 
   676   \end{description}
   676   \end{description}
   677 \<close>
   677 \<close>
   747   @{index_ML RANGE: "(int -> tactic) list -> int -> tactic"} \\
   747   @{index_ML RANGE: "(int -> tactic) list -> int -> tactic"} \\
   748   \end{mldecls}
   748   \end{mldecls}
   749 
   749 
   750   \begin{description}
   750   \begin{description}
   751 
   751 
   752   \item @{ML ALLGOALS}~@{text "tac"} is equivalent to @{text "tac
   752   \<^descr> @{ML ALLGOALS}~@{text "tac"} is equivalent to @{text "tac
   753   n"}~@{ML_op THEN}~@{text "\<dots>"}~@{ML_op THEN}~@{text "tac 1"}.  It
   753   n"}~@{ML_op THEN}~@{text "\<dots>"}~@{ML_op THEN}~@{text "tac 1"}.  It
   754   applies the @{text tac} to all the subgoals, counting downwards.
   754   applies the @{text tac} to all the subgoals, counting downwards.
   755 
   755 
   756   \item @{ML SOMEGOAL}~@{text "tac"} is equivalent to @{text "tac
   756   \<^descr> @{ML SOMEGOAL}~@{text "tac"} is equivalent to @{text "tac
   757   n"}~@{ML_op ORELSE}~@{text "\<dots>"}~@{ML_op ORELSE}~@{text "tac 1"}.  It
   757   n"}~@{ML_op ORELSE}~@{text "\<dots>"}~@{ML_op ORELSE}~@{text "tac 1"}.  It
   758   applies @{text "tac"} to one subgoal, counting downwards.
   758   applies @{text "tac"} to one subgoal, counting downwards.
   759 
   759 
   760   \item @{ML FIRSTGOAL}~@{text "tac"} is equivalent to @{text "tac
   760   \<^descr> @{ML FIRSTGOAL}~@{text "tac"} is equivalent to @{text "tac
   761   1"}~@{ML_op ORELSE}~@{text "\<dots>"}~@{ML_op ORELSE}~@{text "tac n"}.  It
   761   1"}~@{ML_op ORELSE}~@{text "\<dots>"}~@{ML_op ORELSE}~@{text "tac n"}.  It
   762   applies @{text "tac"} to one subgoal, counting upwards.
   762   applies @{text "tac"} to one subgoal, counting upwards.
   763 
   763 
   764   \item @{ML HEADGOAL}~@{text "tac"} is equivalent to @{text "tac 1"}.
   764   \<^descr> @{ML HEADGOAL}~@{text "tac"} is equivalent to @{text "tac 1"}.
   765   It applies @{text "tac"} unconditionally to the first subgoal.
   765   It applies @{text "tac"} unconditionally to the first subgoal.
   766 
   766 
   767   \item @{ML REPEAT_SOME}~@{text "tac"} applies @{text "tac"} once or
   767   \<^descr> @{ML REPEAT_SOME}~@{text "tac"} applies @{text "tac"} once or
   768   more to a subgoal, counting downwards.
   768   more to a subgoal, counting downwards.
   769 
   769 
   770   \item @{ML REPEAT_FIRST}~@{text "tac"} applies @{text "tac"} once or
   770   \<^descr> @{ML REPEAT_FIRST}~@{text "tac"} applies @{text "tac"} once or
   771   more to a subgoal, counting upwards.
   771   more to a subgoal, counting upwards.
   772 
   772 
   773   \item @{ML RANGE}~@{text "[tac\<^sub>1, \<dots>, tac\<^sub>k] i"} is equivalent to
   773   \<^descr> @{ML RANGE}~@{text "[tac\<^sub>1, \<dots>, tac\<^sub>k] i"} is equivalent to
   774   @{text "tac\<^sub>k (i + k - 1)"}~@{ML_op THEN}~@{text "\<dots>"}~@{ML_op
   774   @{text "tac\<^sub>k (i + k - 1)"}~@{ML_op THEN}~@{text "\<dots>"}~@{ML_op
   775   THEN}~@{text "tac\<^sub>1 i"}.  It applies the given list of tactics to the
   775   THEN}~@{text "tac\<^sub>1 i"}.  It applies the given list of tactics to the
   776   corresponding range of subgoals, counting downwards.
   776   corresponding range of subgoals, counting downwards.
   777 
   777 
   778   \end{description}
   778   \end{description}
   800   @{index_ML CHANGED: "tactic -> tactic"} \\
   800   @{index_ML CHANGED: "tactic -> tactic"} \\
   801   \end{mldecls}
   801   \end{mldecls}
   802 
   802 
   803   \begin{description}
   803   \begin{description}
   804 
   804 
   805   \item @{ML FILTER}~@{text "sat tac"} applies @{text "tac"} to the
   805   \<^descr> @{ML FILTER}~@{text "sat tac"} applies @{text "tac"} to the
   806   goal state and returns a sequence consisting of those result goal
   806   goal state and returns a sequence consisting of those result goal
   807   states that are satisfactory in the sense of @{text "sat"}.
   807   states that are satisfactory in the sense of @{text "sat"}.
   808 
   808 
   809   \item @{ML CHANGED}~@{text "tac"} applies @{text "tac"} to the goal
   809   \<^descr> @{ML CHANGED}~@{text "tac"} applies @{text "tac"} to the goal
   810   state and returns precisely those states that differ from the
   810   state and returns precisely those states that differ from the
   811   original state (according to @{ML Thm.eq_thm}).  Thus @{ML
   811   original state (according to @{ML Thm.eq_thm}).  Thus @{ML
   812   CHANGED}~@{text "tac"} always has some effect on the state.
   812   CHANGED}~@{text "tac"} always has some effect on the state.
   813 
   813 
   814   \end{description}
   814   \end{description}
   824   @{index_ML DEPTH_SOLVE_1: "tactic -> tactic"} \\
   824   @{index_ML DEPTH_SOLVE_1: "tactic -> tactic"} \\
   825   \end{mldecls}
   825   \end{mldecls}
   826 
   826 
   827   \begin{description}
   827   \begin{description}
   828 
   828 
   829   \item @{ML DEPTH_FIRST}~@{text "sat tac"} returns the goal state if
   829   \<^descr> @{ML DEPTH_FIRST}~@{text "sat tac"} returns the goal state if
   830   @{text "sat"} returns true.  Otherwise it applies @{text "tac"},
   830   @{text "sat"} returns true.  Otherwise it applies @{text "tac"},
   831   then recursively searches from each element of the resulting
   831   then recursively searches from each element of the resulting
   832   sequence.  The code uses a stack for efficiency, in effect applying
   832   sequence.  The code uses a stack for efficiency, in effect applying
   833   @{text "tac"}~@{ML_op THEN}~@{ML DEPTH_FIRST}~@{text "sat tac"} to
   833   @{text "tac"}~@{ML_op THEN}~@{ML DEPTH_FIRST}~@{text "sat tac"} to
   834   the state.
   834   the state.
   835 
   835 
   836   \item @{ML DEPTH_SOLVE}@{text "tac"} uses @{ML DEPTH_FIRST} to
   836   \<^descr> @{ML DEPTH_SOLVE}@{text "tac"} uses @{ML DEPTH_FIRST} to
   837   search for states having no subgoals.
   837   search for states having no subgoals.
   838 
   838 
   839   \item @{ML DEPTH_SOLVE_1}~@{text "tac"} uses @{ML DEPTH_FIRST} to
   839   \<^descr> @{ML DEPTH_SOLVE_1}~@{text "tac"} uses @{ML DEPTH_FIRST} to
   840   search for states having fewer subgoals than the given state.  Thus,
   840   search for states having fewer subgoals than the given state.  Thus,
   841   it insists upon solving at least one subgoal.
   841   it insists upon solving at least one subgoal.
   842 
   842 
   843   \end{description}
   843   \end{description}
   844 \<close>
   844 \<close>
   857   However, they do not enumerate all solutions; they terminate after
   857   However, they do not enumerate all solutions; they terminate after
   858   the first satisfactory result from @{text "tac"}.
   858   the first satisfactory result from @{text "tac"}.
   859 
   859 
   860   \begin{description}
   860   \begin{description}
   861 
   861 
   862   \item @{ML BREADTH_FIRST}~@{text "sat tac"} uses breadth-first
   862   \<^descr> @{ML BREADTH_FIRST}~@{text "sat tac"} uses breadth-first
   863   search to find states for which @{text "sat"} is true.  For most
   863   search to find states for which @{text "sat"} is true.  For most
   864   applications, it is too slow.
   864   applications, it is too slow.
   865 
   865 
   866   \item @{ML BEST_FIRST}~@{text "(sat, dist) tac"} does a heuristic
   866   \<^descr> @{ML BEST_FIRST}~@{text "(sat, dist) tac"} does a heuristic
   867   search, using @{text "dist"} to estimate the distance from a
   867   search, using @{text "dist"} to estimate the distance from a
   868   satisfactory state (in the sense of @{text "sat"}).  It maintains a
   868   satisfactory state (in the sense of @{text "sat"}).  It maintains a
   869   list of states ordered by distance.  It applies @{text "tac"} to the
   869   list of states ordered by distance.  It applies @{text "tac"} to the
   870   head of this list; if the result contains any satisfactory states,
   870   head of this list; if the result contains any satisfactory states,
   871   then it returns them.  Otherwise, @{ML BEST_FIRST} adds the new
   871   then it returns them.  Otherwise, @{ML BEST_FIRST} adds the new
   873 
   873 
   874   The distance function is typically @{ML size_of_thm}, which computes
   874   The distance function is typically @{ML size_of_thm}, which computes
   875   the size of the state.  The smaller the state, the fewer and simpler
   875   the size of the state.  The smaller the state, the fewer and simpler
   876   subgoals it has.
   876   subgoals it has.
   877 
   877 
   878   \item @{ML THEN_BEST_FIRST}~@{text "tac\<^sub>0 (sat, dist) tac"} is like
   878   \<^descr> @{ML THEN_BEST_FIRST}~@{text "tac\<^sub>0 (sat, dist) tac"} is like
   879   @{ML BEST_FIRST}, except that the priority queue initially contains
   879   @{ML BEST_FIRST}, except that the priority queue initially contains
   880   the result of applying @{text "tac\<^sub>0"} to the goal state.  This
   880   the result of applying @{text "tac\<^sub>0"} to the goal state.  This
   881   tactical permits separate tactics for starting the search and
   881   tactical permits separate tactics for starting the search and
   882   continuing the search.
   882   continuing the search.
   883 
   883 
   895   @{index_ML DETERM: "tactic -> tactic"} \\
   895   @{index_ML DETERM: "tactic -> tactic"} \\
   896   \end{mldecls}
   896   \end{mldecls}
   897 
   897 
   898   \begin{description}
   898   \begin{description}
   899 
   899 
   900   \item @{ML COND}~@{text "sat tac\<^sub>1 tac\<^sub>2"} applies @{text "tac\<^sub>1"} to
   900   \<^descr> @{ML COND}~@{text "sat tac\<^sub>1 tac\<^sub>2"} applies @{text "tac\<^sub>1"} to
   901   the goal state if it satisfies predicate @{text "sat"}, and applies
   901   the goal state if it satisfies predicate @{text "sat"}, and applies
   902   @{text "tac\<^sub>2"}.  It is a conditional tactical in that only one of
   902   @{text "tac\<^sub>2"}.  It is a conditional tactical in that only one of
   903   @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"} is applied to a goal state.
   903   @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"} is applied to a goal state.
   904   However, both @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"} are evaluated
   904   However, both @{text "tac\<^sub>1"} and @{text "tac\<^sub>2"} are evaluated
   905   because ML uses eager evaluation.
   905   because ML uses eager evaluation.
   906 
   906 
   907   \item @{ML IF_UNSOLVED}~@{text "tac"} applies @{text "tac"} to the
   907   \<^descr> @{ML IF_UNSOLVED}~@{text "tac"} applies @{text "tac"} to the
   908   goal state if it has any subgoals, and simply returns the goal state
   908   goal state if it has any subgoals, and simply returns the goal state
   909   otherwise.  Many common tactics, such as @{ML resolve_tac}, fail if
   909   otherwise.  Many common tactics, such as @{ML resolve_tac}, fail if
   910   applied to a goal state that has no subgoals.
   910   applied to a goal state that has no subgoals.
   911 
   911 
   912   \item @{ML SOLVE}~@{text "tac"} applies @{text "tac"} to the goal
   912   \<^descr> @{ML SOLVE}~@{text "tac"} applies @{text "tac"} to the goal
   913   state and then fails iff there are subgoals left.
   913   state and then fails iff there are subgoals left.
   914 
   914 
   915   \item @{ML DETERM}~@{text "tac"} applies @{text "tac"} to the goal
   915   \<^descr> @{ML DETERM}~@{text "tac"} applies @{text "tac"} to the goal
   916   state and returns the head of the resulting sequence.  @{ML DETERM}
   916   state and returns the head of the resulting sequence.  @{ML DETERM}
   917   limits the search space by making its argument deterministic.
   917   limits the search space by making its argument deterministic.
   918 
   918 
   919   \end{description}
   919   \end{description}
   920 \<close>
   920 \<close>
   930   @{index_ML size_of_thm: "thm -> int"} \\
   930   @{index_ML size_of_thm: "thm -> int"} \\
   931   \end{mldecls}
   931   \end{mldecls}
   932 
   932 
   933   \begin{description}
   933   \begin{description}
   934 
   934 
   935   \item @{ML has_fewer_prems}~@{text "n thm"} reports whether @{text
   935   \<^descr> @{ML has_fewer_prems}~@{text "n thm"} reports whether @{text
   936   "thm"} has fewer than @{text "n"} premises.
   936   "thm"} has fewer than @{text "n"} premises.
   937 
   937 
   938   \item @{ML Thm.eq_thm}~@{text "(thm\<^sub>1, thm\<^sub>2)"} reports whether @{text
   938   \<^descr> @{ML Thm.eq_thm}~@{text "(thm\<^sub>1, thm\<^sub>2)"} reports whether @{text
   939   "thm\<^sub>1"} and @{text "thm\<^sub>2"} are equal.  Both theorems must have the
   939   "thm\<^sub>1"} and @{text "thm\<^sub>2"} are equal.  Both theorems must have the
   940   same conclusions, the same set of hypotheses, and the same set of sort
   940   same conclusions, the same set of hypotheses, and the same set of sort
   941   hypotheses.  Names of bound variables are ignored as usual.
   941   hypotheses.  Names of bound variables are ignored as usual.
   942 
   942 
   943   \item @{ML Thm.eq_thm_prop}~@{text "(thm\<^sub>1, thm\<^sub>2)"} reports whether
   943   \<^descr> @{ML Thm.eq_thm_prop}~@{text "(thm\<^sub>1, thm\<^sub>2)"} reports whether
   944   the propositions of @{text "thm\<^sub>1"} and @{text "thm\<^sub>2"} are equal.
   944   the propositions of @{text "thm\<^sub>1"} and @{text "thm\<^sub>2"} are equal.
   945   Names of bound variables are ignored.
   945   Names of bound variables are ignored.
   946 
   946 
   947   \item @{ML size_of_thm}~@{text "thm"} computes the size of @{text
   947   \<^descr> @{ML size_of_thm}~@{text "thm"} computes the size of @{text
   948   "thm"}, namely the number of variables, constants and abstractions
   948   "thm"}, namely the number of variables, constants and abstractions
   949   in its conclusion.  It may serve as a distance function for
   949   in its conclusion.  It may serve as a distance function for
   950   @{ML BEST_FIRST}.
   950   @{ML BEST_FIRST}.
   951 
   951 
   952   \end{description}
   952   \end{description}