2 \chapter{Generic Tools and Packages}\label{ch:gen-tools}
4 \section{Axiomatic Type Classes}\label{sec:axclass}
6 \indexisarcmd{axclass}\indexisarcmd{instance}\indexisarmeth{intro-classes}
8 \isarcmd{axclass} & : & \isartrans{theory}{theory} \\
9 \isarcmd{instance} & : & \isartrans{theory}{proof(prove)} \\
10 intro_classes & : & \isarmeth \\
13 Axiomatic type classes are provided by Isabelle/Pure as a \emph{definitional}
14 interface to type classes (cf.~\S\ref{sec:classes}). Thus any object logic
15 may make use of this light-weight mechanism of abstract theories
16 \cite{Wenzel:1997:TPHOL}. There is also a tutorial on \emph{Using Axiomatic
17 Type Classes in Isabelle} that is part of the standard Isabelle
22 'axclass' classdecl (axmdecl prop comment? +)
24 'instance' (nameref '<' nameref | nameref '::' simplearity) comment?
29 \item [$\isarkeyword{axclass}~c < \vec c~axms$] defines an axiomatic type
30 class as the intersection of existing classes, with additional axioms
31 holding. Class axioms may not contain more than one type variable. The
32 class axioms (with implicit sort constraints added) are bound to the given
33 names. Furthermore a class introduction rule is generated, which is
34 employed by method $intro_classes$ to support instantiation proofs of this
37 \item [$\isarkeyword{instance}~c@1 < c@2$ and $\isarkeyword{instance}~t ::
38 (\vec s)c$] setup a goal stating a class relation or type arity. The proof
39 would usually proceed by $intro_classes$, and then establish the
40 characteristic theorems of the type classes involved. After finishing the
41 proof, the theory will be augmented by a type signature declaration
42 corresponding to the resulting theorem.
43 \item [$intro_classes$] repeatedly expands all class introduction rules of
48 \section{Calculational proof}\label{sec:calculation}
50 \indexisarcmd{also}\indexisarcmd{finally}
51 \indexisarcmd{moreover}\indexisarcmd{ultimately}
53 \begin{matharray}{rcl}
54 \isarcmd{also} & : & \isartrans{proof(state)}{proof(state)} \\
55 \isarcmd{finally} & : & \isartrans{proof(state)}{proof(chain)} \\
56 \isarcmd{moreover} & : & \isartrans{proof(state)}{proof(state)} \\
57 \isarcmd{ultimately} & : & \isartrans{proof(state)}{proof(chain)} \\
58 trans & : & \isaratt \\
61 Calculational proof is forward reasoning with implicit application of
62 transitivity rules (such those of $=$, $\le$, $<$). Isabelle/Isar maintains
63 an auxiliary register $calculation$\indexisarthm{calculation} for accumulating
64 results obtained by transitivity composed with the current result. Command
65 $\ALSO$ updates $calculation$ involving $this$, while $\FINALLY$ exhibits the
66 final $calculation$ by forward chaining towards the next goal statement. Both
67 commands require valid current facts, i.e.\ may occur only after commands that
68 produce theorems such as $\ASSUMENAME$, $\NOTENAME$, or some finished proof of
69 $\HAVENAME$, $\SHOWNAME$ etc. The $\MOREOVER$ and $\ULTIMATELY$ commands are
70 similar to $\ALSO$ and $\FINALLY$, but only collect further results in
71 $calculation$ without applying any rules yet.
73 Also note that the automatic term abbreviation ``$\dots$'' has its canonical
74 application with calculational proofs. It refers to the argument\footnote{The
75 argument of a curried infix expression is its right-hand side.} of the
78 Isabelle/Isar calculations are implicitly subject to block structure in the
79 sense that new threads of calculational reasoning are commenced for any new
80 block (as opened by a local goal, for example). This means that, apart from
81 being able to nest calculations, there is no separate \emph{begin-calculation}
86 The Isar calculation proof commands may be defined as
87 follows:\footnote{Internal bookkeeping such as proper handling of
88 block-structure has been suppressed.}
89 \begin{matharray}{rcl}
90 \ALSO@0 & \equiv & \NOTE{calculation}{this} \\
91 \ALSO@{n+1} & \equiv & \NOTE{calculation}{trans~[OF~calculation~this]} \\
92 \FINALLY & \equiv & \ALSO~\FROM{calculation} \\
93 \MOREOVER & \equiv & \NOTE{calculation}{calculation~this} \\
94 \ULTIMATELY & \equiv & \MOREOVER~\FROM{calculation} \\
98 ('also' | 'finally') transrules? comment?
100 ('moreover' | 'ultimately') comment?
102 'trans' (() | 'add' | 'del')
105 transrules: '(' thmrefs ')' interest?
110 \item [$\ALSO~(\vec a)$] maintains the auxiliary $calculation$ register as
111 follows. The first occurrence of $\ALSO$ in some calculational thread
112 initializes $calculation$ by $this$. Any subsequent $\ALSO$ on the same
113 level of block-structure updates $calculation$ by some transitivity rule
114 applied to $calculation$ and $this$ (in that order). Transitivity rules are
115 picked from the current context plus those given as explicit arguments (the
116 latter have precedence).
118 \item [$\FINALLY~(\vec a)$] maintaining $calculation$ in the same way as
119 $\ALSO$, and concludes the current calculational thread. The final result
120 is exhibited as fact for forward chaining towards the next goal. Basically,
121 $\FINALLY$ just abbreviates $\ALSO~\FROM{calculation}$. Note that
122 ``$\FINALLY~\SHOW{}{\Var{thesis}}~\DOT$'' and
123 ``$\FINALLY~\HAVE{}{\phi}~\DOT$'' are typical idioms for concluding
124 calculational proofs.
126 \item [$\MOREOVER$ and $\ULTIMATELY$] are analogous to $\ALSO$ and $\FINALLY$,
127 but collect results only, without applying rules.
129 \item [$trans$] declares theorems as transitivity rules.
133 \section{Named local contexts (cases)}\label{sec:cases}
135 \indexisarcmd{case}\indexisarcmd{print-cases}
136 \indexisaratt{case-names}\indexisaratt{params}
137 \begin{matharray}{rcl}
138 \isarcmd{case} & : & \isartrans{proof(state)}{proof(state)} \\
139 \isarcmd{print_cases}^* & : & \isarkeep{proof} \\
140 case_names & : & \isaratt \\
141 params & : & \isaratt \\
144 Basically, Isar proof contexts are built up explicitly using commands like
145 $\FIXNAME$, $\ASSUMENAME$ etc.\ (see \S\ref{sec:proof-context}). In typical
146 verification tasks this can become hard to manage, though. In particular, a
147 large number of local contexts may emerge from case analysis or induction over
148 inductive sets and types.
152 The $\CASENAME$ command provides a shorthand to refer to certain parts of
153 logical context symbolically. Proof methods may provide an environment of
154 named ``cases'' of the form $c\colon \vec x, \vec \phi$. Then the effect of
155 $\CASE{c}$ is exactly the same as $\FIX{\vec x}~\ASSUME{c}{\vec\phi}$.
157 It is important to note that $\CASENAME$ does \emph{not} provide any means to
158 peek at the current goal state, which is treated as strictly non-observable in
159 Isar! Instead, the cases considered here usually emerge in a canonical way
160 from certain pieces of specification that appear in the theory somewhere else
161 (e.g.\ in an inductive definition, or recursive function). See also
162 \S\ref{sec:induct-method} for more details of how this works in HOL.
166 Named cases may be exhibited in the current proof context only if both the
167 proof method and the rules involved support this. Case names and parameters
168 of basic rules may be declared by hand as well, by using appropriate
169 attributes. Thus variant versions of rules that have been derived manually
170 may be used in advanced case analysis later.
172 \railalias{casenames}{case\_names}
176 'case' nameref attributes?
180 'params' ((name * ) + 'and')
186 \item [$\CASE{c}$] invokes a named local context $c\colon \vec x, \vec \phi$,
187 as provided by an appropriate proof method (such as $cases$ and $induct$ in
188 Isabelle/HOL, see \S\ref{sec:induct-method}). The command $\CASE{c}$
189 abbreviates $\FIX{\vec x}~\ASSUME{c}{\vec\phi}$.
190 \item [$\isarkeyword{print_cases}$] prints all local contexts of the current
191 state, using Isar proof language notation. This is a diagnostic command;
192 $undo$ does not apply.
193 \item [$case_names~\vec c$] declares names for the local contexts of premises
194 of some theorem; $\vec c$ refers to the \emph{suffix} of the list premises.
195 \item [$params~\vec p@1 \dots \vec p@n$] renames the innermost parameters of
196 premises $1, \dots, n$ of some theorem. An empty list of names may be given
197 to skip positions, leaving the present parameters unchanged.
201 \section{Generalized existence}
203 \indexisarcmd{obtain}
204 \begin{matharray}{rcl}
205 \isarcmd{obtain} & : & \isartrans{proof(prove)}{proof(state)} \\
208 Generalized existence reasoning means that additional elements with certain
209 properties are introduced, together with a soundness proof of that context
210 change (the rest of the main goal is left unchanged).
212 Syntactically, the $\OBTAINNAME$ language element is like an initial proof
213 method to the present goal, followed by a proof of its additional claim,
214 followed by the actual context commands (using the syntax of $\FIXNAME$ and
215 $\ASSUMENAME$, see \S\ref{sec:proof-context}).
218 'obtain' (vars + 'and') comment? \\ 'where' (assm comment? + 'and')
222 $\OBTAINNAME$ is defined as a derived Isar command as follows; here the
223 preceding goal shall be $\psi$, with (optional) facts $\vec b$ indicated for
226 \OBTAIN{\vec x}{a}{\vec \phi}~~\langle proof\rangle \equiv {} \\[0.5ex]
227 \quad \PROOF{succeed} \\
228 \qquad \DEF{}{thesis \equiv \psi} \\
229 \qquad \PRESUME{that}{\All{\vec x} \vec\phi \Imp thesis} \\
230 \qquad \FROM{\vec b}~\SHOW{}{thesis}~~\langle proof\rangle \\
232 \qquad \FIX{\vec x}~\ASSUME{a}{\vec\phi} \\
235 Typically, the soundness proof is relatively straight-forward, often just by
236 canonical automated tools such as $\BY{simp}$ (see \S\ref{sec:simp}) or
237 $\BY{blast}$ (see \S\ref{sec:classical-auto}). Note that the ``$that$''
238 presumption above is usually declared as simplification and (unsafe)
239 introduction rule, depending on the object-logic's policy,
240 though.\footnote{HOL and HOLCF do this already.}
242 The original goal statement is wrapped into a local definition in order to
243 avoid any automated tools descending into it. Usually, any statement would
244 admit the intended reduction anyway; only in very rare cases $thesis_def$ has
245 to be expanded to complete the soundness proof.
249 In a sense, $\OBTAINNAME$ represents at the level of Isar proofs what would be
250 meta-logical existential quantifiers and conjunctions. This concept has a
251 broad range of useful applications, ranging from plain elimination (or even
252 introduction) of object-level existentials and conjunctions, to elimination
253 over results of symbolic evaluation of recursive definitions, for example.
256 \section{Miscellaneous methods and attributes}
258 \indexisarmeth{unfold}\indexisarmeth{fold}
259 \indexisarmeth{erule}\indexisarmeth{drule}\indexisarmeth{frule}
260 \indexisarmeth{fail}\indexisarmeth{succeed}
261 \begin{matharray}{rcl}
262 unfold & : & \isarmeth \\
263 fold & : & \isarmeth \\[0.5ex]
264 erule^* & : & \isarmeth \\
265 drule^* & : & \isarmeth \\
266 frule^* & : & \isarmeth \\[0.5ex]
267 succeed & : & \isarmeth \\
268 fail & : & \isarmeth \\
272 ('fold' | 'unfold' | 'erule' | 'drule' | 'frule') thmrefs
277 \item [$unfold~\vec a$ and $fold~\vec a$] expand and fold back again the given
278 meta-level definitions throughout all goals; any facts provided are inserted
279 into the goal and subject to rewriting as well.
280 \item [$erule~\vec a$, $drule~\vec a$, and $frule~\vec a$] are similar to the
281 basic $rule$ method (see \S\ref{sec:pure-meth-att}), but apply rules by
282 elim-resolution, destruct-resolution, and forward-resolution, respectively
283 \cite{isabelle-ref}. These are improper method, mainly for experimentation
284 and emulating tactic scripts.
286 Different modes of basic rule application are usually expressed in Isar at
287 the proof language level, rather than via implicit proof state
288 manipulations. For example, a proper single-step elimination would be done
289 using the basic $rule$ method, with forward chaining of current facts.
290 \item [$succeed$] yields a single (unchanged) result; it is the identity of
291 the ``\texttt{,}'' method combinator (cf.\ \S\ref{sec:syn-meth}).
292 \item [$fail$] yields an empty result sequence; it is the identity of the
293 ``\texttt{|}'' method combinator (cf.\ \S\ref{sec:syn-meth}).
297 \indexisaratt{standard}
298 \indexisaratt{elimify}
300 \indexisaratt{RS}\indexisaratt{COMP}
302 \indexisaratt{tag}\indexisaratt{untag}
303 \indexisaratt{transfer}
304 \indexisaratt{export}
305 \indexisaratt{unfold}\indexisaratt{fold}
306 \begin{matharray}{rcl}
307 tag & : & \isaratt \\
308 untag & : & \isaratt \\[0.5ex]
310 COMP & : & \isaratt \\[0.5ex]
311 where & : & \isaratt \\[0.5ex]
312 unfold & : & \isaratt \\
313 fold & : & \isaratt \\[0.5ex]
314 standard & : & \isaratt \\
315 elimify & : & \isaratt \\
316 export^* & : & \isaratt \\
317 transfer & : & \isaratt \\[0.5ex]
325 ('RS' | 'COMP') nat? thmref
327 'where' (name '=' term * 'and')
329 ('unfold' | 'fold') thmrefs
334 \item [$tag~name~args$ and $untag~name$] add and remove $tags$ of some
335 theorem. Tags may be any list of strings that serve as comment for some
336 tools (e.g.\ $\LEMMANAME$ causes the tag ``$lemma$'' to be added to the
337 result). The first string is considered the tag name, the rest its
338 arguments. Note that untag removes any tags of the same name.
339 \item [$RS~n~a$ and $COMP~n~a$] compose rules. $RS$ resolves with the $n$-th
340 premise of $a$; $COMP$ is a version of $RS$ that skips the automatic lifting
341 process that is normally intended (cf.\ \texttt{RS} and \texttt{COMP} in
342 \cite[\S5]{isabelle-ref}).
343 \item [$where~\vec x = \vec t$] perform named instantiation of schematic
344 variables occurring in a theorem. Unlike instantiation tactics (such as
345 \texttt{res_inst_tac}, see \cite{isabelle-ref}), actual schematic variables
346 have to be specified (e.g.\ $\Var{x@3}$).
348 \item [$unfold~\vec a$ and $fold~\vec a$] expand and fold back again the given
349 meta-level definitions throughout a rule.
351 \item [$standard$] puts a theorem into the standard form of object-rules, just
352 as the ML function \texttt{standard} (see \cite[\S5]{isabelle-ref}).
354 \item [$elimify$] turns an destruction rule into an elimination, just as the
355 ML function \texttt{make\_elim} (see \cite{isabelle-ref}).
357 \item [$export$] lifts a local result out of the current proof context,
358 generalizing all fixed variables and discharging all assumptions. Note that
359 proper incremental export is already done as part of the basic Isar
360 machinery. This attribute is mainly for experimentation.
362 \item [$transfer$] promotes a theorem to the current theory context, which has
363 to enclose the former one. This is done automatically whenever rules are
369 \section{The Simplifier}
371 \subsection{Simplification methods}\label{sec:simp}
373 \indexisarmeth{simp}\indexisarmeth{simp-all}
374 \begin{matharray}{rcl}
375 simp & : & \isarmeth \\
376 simp_all & : & \isarmeth \\
379 \railalias{simpall}{simp\_all}
383 ('simp' | simpall) ('!' ?) (simpmod * )
386 simpmod: ('add' | 'del' | 'only' | 'split' (() | 'add' | 'del') | 'other') ':' thmrefs
391 \item [$simp$] invokes Isabelle's simplifier, after declaring additional rules
392 according to the arguments given. Note that the \railtterm{only} modifier
393 first removes all other rewrite rules, congruences, and looper tactics
394 (including splits), and then behaves like \railtterm{add}.
396 The \railtterm{split} modifiers add or delete rules for the Splitter (see
397 also \cite{isabelle-ref}), the default is to add. This works only if the
398 Simplifier method has been properly setup to include the Splitter (all major
399 object logics such HOL, HOLCF, FOL, ZF do this already).
401 The \railtterm{other} modifier ignores its arguments. Nevertheless,
402 additional kinds of rules may be declared by including appropriate
403 attributes in the specification.
404 \item [$simp_all$] is similar to $simp$, but acts on all goals.
407 Internally, the $simp$ method is based on \texttt{asm_full_simp_tac}
408 \cite[\S10]{isabelle-ref}, but is much better behaved in practice. Just the
409 local premises of the actual goal are involved by default. Additional facts
410 may be inserted via forward-chaining (using $\THEN$, $\FROMNAME$ etc.). The
411 full context of assumptions is only included in the $simp!$ version, which
412 should be used with some care, though.
414 Note that there is no separate $split$ method. The effect of
415 \texttt{split_tac} can be simulated by $(simp~only\colon~split\colon~\vec a)$.
418 \subsection{Declaring rules}
420 \indexisaratt{simp}\indexisaratt{split}\indexisaratt{cong}
421 \begin{matharray}{rcl}
422 simp & : & \isaratt \\
423 split & : & \isaratt \\
424 cong & : & \isaratt \\
428 ('simp' | 'split' | 'cong') (() | 'add' | 'del')
433 \item [$simp$] declares simplification rules.
434 \item [$split$] declares split rules.
435 \item [$cong$] declares congruence rules.
439 \subsection{Forward simplification}
441 \indexisaratt{simplify}\indexisaratt{asm-simplify}
442 \indexisaratt{full-simplify}\indexisaratt{asm-full-simplify}
443 \begin{matharray}{rcl}
444 simplify & : & \isaratt \\
445 asm_simplify & : & \isaratt \\
446 full_simplify & : & \isaratt \\
447 asm_full_simplify & : & \isaratt \\
450 These attributes provide forward rules for simplification, which should be
451 used only very rarely. There are no separate options for declaring
452 simplification rules locally.
454 See the ML functions of the same name in \cite[\S10]{isabelle-ref} for more
458 \section{The Classical Reasoner}
460 \subsection{Basic methods}\label{sec:classical-basic}
462 \indexisarmeth{rule}\indexisarmeth{intro}
463 \indexisarmeth{elim}\indexisarmeth{default}\indexisarmeth{contradiction}
464 \begin{matharray}{rcl}
465 rule & : & \isarmeth \\
466 intro & : & \isarmeth \\
467 elim & : & \isarmeth \\
468 contradiction & : & \isarmeth \\
472 ('rule' | 'intro' | 'elim') thmrefs?
477 \item [$rule$] as offered by the classical reasoner is a refinement over the
478 primitive one (see \S\ref{sec:pure-meth-att}). In case that no rules are
479 provided as arguments, it automatically determines elimination and
480 introduction rules from the context (see also \S\ref{sec:classical-mod}).
481 This is made the default method for basic proof steps, such as $\PROOFNAME$
482 and ``$\DDOT$'' (two dots), see also \S\ref{sec:proof-steps} and
483 \S\ref{sec:pure-meth-att}.
485 \item [$intro$ and $elim$] repeatedly refine some goal by intro- or
486 elim-resolution, after having inserted any facts. Omitting the arguments
487 refers to any suitable rules declared in the context, otherwise only the
488 explicitly given ones may be applied. The latter form admits better control
489 of what actually happens, thus it is very appropriate as an initial method
490 for $\PROOFNAME$ that splits up certain connectives of the goal, before
491 entering the actual sub-proof.
493 \item [$contradiction$] solves some goal by contradiction, deriving any result
494 from both $\neg A$ and $A$. Facts, which are guaranteed to participate, may
495 appear in either order.
499 \subsection{Automated methods}\label{sec:classical-auto}
501 \indexisarmeth{blast}
502 \indexisarmeth{fast}\indexisarmeth{best}\indexisarmeth{slow}\indexisarmeth{slow-best}
503 \begin{matharray}{rcl}
504 blast & : & \isarmeth \\
505 fast & : & \isarmeth \\
506 best & : & \isarmeth \\
507 slow & : & \isarmeth \\
508 slow_best & : & \isarmeth \\
511 \railalias{slowbest}{slow\_best}
515 'blast' ('!' ?) nat? (clamod * )
517 ('fast' | 'best' | 'slow' | slowbest) ('!' ?) (clamod * )
520 clamod: (('intro' | 'elim' | 'dest') (() | '?' | '??') | 'del') ':' thmrefs
525 \item [$blast$] refers to the classical tableau prover (see \texttt{blast_tac}
526 in \cite[\S11]{isabelle-ref}). The optional argument specifies a
527 user-supplied search bound (default 20).
528 \item [$fast$, $best$, $slow$, $slow_best$] refer to the generic classical
529 reasoner (see \cite[\S11]{isabelle-ref}, tactic \texttt{fast_tac} etc).
532 Any of above methods support additional modifiers of the context of classical
533 rules. Their semantics is analogous to the attributes given in
534 \S\ref{sec:classical-mod}. Facts provided by forward chaining are
535 inserted\footnote{These methods usually cannot make proper use of actual rules
536 inserted that way, though.} into the goal before doing the search. The
537 ``!''~argument causes the full context of assumptions to be included as well.
538 This is slightly less hazardous than for the Simplifier (see
542 \subsection{Combined automated methods}
544 \indexisarmeth{auto}\indexisarmeth{force}
545 \begin{matharray}{rcl}
546 force & : & \isarmeth \\
547 auto & : & \isarmeth \\
551 ('force' | 'auto') ('!' ?) (clasimpmod * )
554 clasimpmod: ('simp' (() | 'add' | 'del' | 'only') | 'other' |
555 ('split' (() | 'add' | 'del')) |
556 (('intro' | 'elim' | 'dest') (() | '?' | '??') | 'del')) ':' thmrefs
560 \item [$force$ and $auto$] provide access to Isabelle's combined
561 simplification and classical reasoning tactics. See \texttt{force_tac} and
562 \texttt{auto_tac} in \cite[\S11]{isabelle-ref} for more information. The
563 modifier arguments correspond to those given in \S\ref{sec:simp} and
564 \S\ref{sec:classical-auto}. Just note that the ones related to the
565 Simplifier are prefixed by \railtterm{simp} here.
567 Facts provided by forward chaining are inserted into the goal before doing
568 the search. The ``!''~argument causes the full context of assumptions to be
573 \subsection{Declaring rules}\label{sec:classical-mod}
575 \indexisaratt{intro}\indexisaratt{elim}\indexisaratt{dest}
576 \indexisaratt{iff}\indexisaratt{delrule}
577 \begin{matharray}{rcl}
578 intro & : & \isaratt \\
579 elim & : & \isaratt \\
580 dest & : & \isaratt \\
581 iff & : & \isaratt \\
582 delrule & : & \isaratt \\
586 ('intro' | 'elim' | 'dest') (() | '?' | '??')
588 'iff' (() | 'add' | 'del')
592 \item [$intro$, $elim$, and $dest$] declare introduction, elimination, and
593 destruct rules, respectively. By default, rules are considered as
594 \emph{safe}, while a single ``?'' classifies as \emph{unsafe}, and ``??'' as
595 \emph{extra} (i.e.\ not applied in the search-oriented automated methods,
596 but only in single-step methods such as $rule$).
598 \item [$iff$] declares equations both as rules for the Simplifier and
601 \item [$delrule$] deletes introduction or elimination rules from the context.
602 Note that destruction rules would have to be turned into elimination rules
603 first, e.g.\ by using the $elimify$ attribute.
609 %%% TeX-master: "isar-ref"