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} |
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 |
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} |