doc-src/IsarRef/generic.tex
author wenzelm
Sat Oct 30 20:13:16 1999 +0200 (1999-10-30)
changeset 7981 5120a2a15d06
parent 7974 34245feb6e82
child 7987 d9aef93c0e32
permissions -rw-r--r--
tuned;
     1 
     2 \chapter{Generic Tools and Packages}\label{ch:gen-tools}
     3 
     4 \section{Basic proof methods}\label{sec:pure-meth}
     5 
     6 \indexisarmeth{fail}\indexisarmeth{succeed}\indexisarmeth{$-$}\indexisarmeth{assumption}
     7 \indexisarmeth{fold}\indexisarmeth{unfold}
     8 \indexisarmeth{rule}\indexisarmeth{erule}
     9 \begin{matharray}{rcl}
    10   - & : & \isarmeth \\
    11   assumption & : & \isarmeth \\
    12   rule & : & \isarmeth \\
    13   erule^* & : & \isarmeth \\[0.5ex]
    14   fold & : & \isarmeth \\
    15   unfold & : & \isarmeth \\[0.5ex]
    16   succeed & : & \isarmeth \\
    17   fail & : & \isarmeth \\
    18 \end{matharray}
    19 
    20 \begin{rail}
    21   ('fold' | 'unfold' | 'rule' | 'erule') thmrefs
    22   ;
    23 \end{rail}
    24 
    25 \begin{descr}
    26 \item [``$-$''] does nothing but insert the forward chaining facts as premises
    27   into the goal.  Note that command $\PROOFNAME$ without any method actually
    28   performs a single reduction step using the $rule$ method (see below); thus a
    29   plain \emph{do-nothing} proof step would be $\PROOF{-}$ rather than
    30   $\PROOFNAME$ alone.
    31 \item [$assumption$] solves some goal by assumption.  Any facts given are
    32   guaranteed to participate in the refinement.  Note that ``$\DOT$'' (dot)
    33   abbreviates $\BY{assumption}$.
    34 \item [$rule~thms$] applies some rule given as argument in backward manner;
    35   facts are used to reduce the rule before applying it to the goal.  Thus
    36   $rule$ without facts is plain \emph{introduction}, while with facts it
    37   becomes a (generalized) \emph{elimination}.
    38   
    39   Note that the classical reasoner introduces another version of $rule$ that
    40   is able to pick appropriate rules automatically, whenever explicit $thms$
    41   are omitted (see \S\ref{sec:classical-basic}); that method is the default
    42   for $\PROOFNAME$ steps.  Note that ``$\DDOT$'' (double-dot) abbreviates
    43   $\BY{default}$.
    44 \item [$erule~thms$] is similar to $rule$, but applies rules by
    45   elim-resolution.  This is an improper method, mainly for experimentation and
    46   porting of old scripts.  Actual elimination proofs are usually done with
    47   $rule$ (single step, involving facts) or $elim$ (repeated steps, see
    48   \S\ref{sec:classical-basic}).
    49 \item [$unfold~thms$ and $fold~thms$] expand and fold back again the given
    50   meta-level definitions throughout all goals; any facts provided are
    51   \emph{ignored}.
    52 \item [$succeed$] yields a single (unchanged) result; it is the identify of
    53   the ``\texttt{,}'' method combinator (cf.\ \S\ref{sec:syn-meth}).
    54 \item [$fail$] yields an empty result sequence; it is the identify of the
    55   ``\texttt{|}'' method combinator (cf.\ \S\ref{sec:syn-meth}).
    56 \end{descr}
    57 
    58 
    59 \section{Miscellaneous attributes}
    60 
    61 \indexisaratt{tag}\indexisaratt{untag}\indexisaratt{COMP}\indexisaratt{RS}
    62 \indexisaratt{OF}\indexisaratt{where}\indexisaratt{of}\indexisaratt{standard}
    63 \indexisaratt{elimify}\indexisaratt{transfer}\indexisaratt{export}
    64 \begin{matharray}{rcl}
    65   tag & : & \isaratt \\
    66   untag & : & \isaratt \\[0.5ex]
    67   OF & : & \isaratt \\
    68   RS & : & \isaratt \\
    69   COMP & : & \isaratt \\[0.5ex]
    70   of & : & \isaratt \\
    71   where & : & \isaratt \\[0.5ex]
    72   standard & : & \isaratt \\
    73   elimify & : & \isaratt \\
    74   export^* & : & \isaratt \\
    75   transfer & : & \isaratt \\
    76 \end{matharray}
    77 
    78 \begin{rail}
    79   ('tag' | 'untag') (nameref+)
    80   ;
    81   'OF' thmrefs
    82   ;
    83   ('RS' | 'COMP') nat? thmref
    84   ;
    85   'of' (inst * ) ('concl' ':' (inst * ))?
    86   ;
    87   'where' (name '=' term * 'and')
    88   ;
    89 
    90   inst: underscore | term
    91   ;
    92 \end{rail}
    93 
    94 \begin{descr}
    95 \item [$tag~tags$ and $untag~tags$] add and remove $tags$ of the theorem,
    96   respectively.  Tags may be any list of strings that serve as comment for
    97   some tools (e.g.\ $\LEMMANAME$ causes the tag ``$lemma$'' to be added to the
    98   result).
    99 \item [$OF~thms$, $RS~n~thm$, and $COMP~n~thm$] compose rules.  $OF$ applies
   100   $thms$ in parallel (cf.\ \texttt{MRS} in \cite[\S5]{isabelle-ref}, but note
   101   the reversed order).  Note that premises may be skipped by including $\_$
   102   (underscore) as argument.
   103   
   104   $RS$ resolves with the $n$-th premise of $thm$; $COMP$ is a version of $RS$
   105   that does not include the automatic lifting process that is normally
   106   intended (cf.\ \texttt{RS} and \texttt{COMP} in \cite[\S5]{isabelle-ref}).
   107   
   108 \item [$of~\vec t$ and $where~\vec x = \vec t$] perform positional and named
   109   instantiation, respectively.  The terms given in $of$ are substituted for
   110   any schematic variables occurring in a theorem from left to right;
   111   ``\texttt{_}'' (underscore) indicates to skip a position.
   112  
   113 \item [$standard$] puts a theorem into the standard form of object-rules, just
   114   as the ML function \texttt{standard} (see \cite[\S5]{isabelle-ref}).
   115   
   116 \item [$elimify$] turns an destruction rule into an elimination, just as the
   117   ML function \texttt{make\_elim} (see \cite{isabelle-ref}).
   118   
   119 \item [$export$] lifts a local result out of the current proof context,
   120   generalizing all fixed variables and discharging all assumptions.  Note that
   121   (partial) export is usually done automatically behind the scenes.  This
   122   attribute is mainly for experimentation.
   123   
   124 \item [$transfer$] promotes a theorem to the current theory context, which has
   125   to enclose the former one.  Normally, this is done automatically when rules
   126   are joined by inference.
   127 
   128 \end{descr}
   129 
   130 
   131 \section{Calculational proof}\label{sec:calculation}
   132 
   133 \indexisarcmd{also}\indexisarcmd{finally}\indexisaratt{trans}
   134 \begin{matharray}{rcl}
   135   \isarcmd{also} & : & \isartrans{proof(state)}{proof(state)} \\
   136   \isarcmd{finally} & : & \isartrans{proof(state)}{proof(chain)} \\
   137   trans & : & \isaratt \\
   138 \end{matharray}
   139 
   140 Calculational proof is forward reasoning with implicit application of
   141 transitivity rules (such those of $=$, $\le$, $<$).  Isabelle/Isar maintains
   142 an auxiliary register $calculation$\indexisarthm{calculation} for accumulating
   143 results obtained by transitivity composed with the current result.  Command
   144 $\ALSO$ updates $calculation$ involving $this$, while $\FINALLY$ exhibits the
   145 final $calculation$ by forward chaining towards the next goal statement.  Both
   146 commands require valid current facts, i.e.\ may occur only after commands that
   147 produce theorems such as $\ASSUMENAME$, $\NOTENAME$, or some finished proof of
   148 $\HAVENAME$, $\SHOWNAME$ etc.
   149 
   150 Also note that the automatic term abbreviation ``$\dots$'' has its canonical
   151 application with calculational proofs.  It automatically refers to the
   152 argument\footnote{The argument of a curried infix expression is its right-hand
   153   side.} of the preceding statement.
   154 
   155 Isabelle/Isar calculations are implicitly subject to block structure in the
   156 sense that new threads of calculational reasoning are commenced for any new
   157 block (as opened by a local goal, for example).  This means that, apart from
   158 being able to nest calculations, there is no separate \emph{begin-calculation}
   159 command required.
   160 
   161 \begin{rail}
   162   ('also' | 'finally') transrules? comment?
   163   ;
   164   'trans' (() | 'add' ':' | 'del' ':') thmrefs
   165   ;
   166 
   167   transrules: '(' thmrefs ')' interest?
   168   ;
   169 \end{rail}
   170 
   171 \begin{descr}
   172 \item [$\ALSO~(thms)$] maintains the auxiliary $calculation$ register as
   173   follows.  The first occurrence of $\ALSO$ in some calculational thread
   174   initializes $calculation$ by $this$. Any subsequent $\ALSO$ on the same
   175   level of block-structure updates $calculation$ by some transitivity rule
   176   applied to $calculation$ and $this$ (in that order).  Transitivity rules are
   177   picked from the current context plus those given as $thms$ (the latter have
   178   precedence).
   179   
   180 \item [$\FINALLY~(thms)$] maintaining $calculation$ in the same way as
   181   $\ALSO$, and concludes the current calculational thread.  The final result
   182   is exhibited as fact for forward chaining towards the next goal. Basically,
   183   $\FINALLY$ just abbreviates $\ALSO~\FROM{calculation}$.  Typical proof
   184   idioms are``$\FINALLY~\SHOW{}{\Var{thesis}}~\DOT$'' and
   185   ``$\FINALLY~\HAVE{}{\phi}~\DOT$''.
   186   
   187 \item [$trans$] maintains the set of transitivity rules of the theory or proof
   188   context, by adding or deleting theorems (the default is to add).
   189 \end{descr}
   190 
   191 %FIXME
   192 %See theory \texttt{HOL/Isar_examples/Group} for a simple application of
   193 %calculations for basic equational reasoning.
   194 %\texttt{HOL/Isar_examples/KnasterTarski} involves a few more advanced
   195 %calculational steps in combination with natural deduction.
   196 
   197 
   198 \section{Axiomatic Type Classes}\label{sec:axclass}
   199 
   200 \indexisarcmd{axclass}\indexisarcmd{instance}\indexisarmeth{intro-classes}
   201 \begin{matharray}{rcl}
   202   \isarcmd{axclass} & : & \isartrans{theory}{theory} \\
   203   \isarcmd{instance} & : & \isartrans{theory}{proof(prove)} \\
   204   intro_classes & : & \isarmeth \\
   205 \end{matharray}
   206 
   207 Axiomatic type classes are provided by Isabelle/Pure as a purely
   208 \emph{definitional} interface to type classes (cf.~\S\ref{sec:classes}).  Thus
   209 any object logic may make use of this light-weight mechanism for abstract
   210 theories.  See \cite{Wenzel:1997:TPHOL} for more information.  There is also a
   211 tutorial on \emph{Using Axiomatic Type Classes in Isabelle} that is part of
   212 the standard Isabelle documentation.
   213 %FIXME cite
   214 
   215 \begin{rail}
   216   'axclass' classdecl (axmdecl prop comment? +)
   217   ;
   218   'instance' (nameref '<' nameref | nameref '::' simplearity) comment?
   219   ;
   220 \end{rail}
   221 
   222 \begin{descr}
   223 \item [$\isarkeyword{axclass}~c < \vec c~axms$] defines an axiomatic type
   224   class as the intersection of existing classes, with additional axioms
   225   holding.  Class axioms may not contain more than one type variable.  The
   226   class axioms (with implicit sort constraints added) are bound to the given
   227   names.  Furthermore a class introduction rule is generated, which is
   228   employed by method $intro_classes$ in support instantiation proofs of this
   229   class.
   230   
   231 \item [$\isarkeyword{instance}~c@1 < c@2$ and $\isarkeyword{instance}~t ::
   232   (\vec s)c$] setup up a goal stating the class relation or type arity.  The
   233   proof would usually proceed by the $intro_classes$ method, and then
   234   establish the characteristic theorems of the type classes involved.  After
   235   finishing the proof the theory will be augmented by a type signature
   236   declaration corresponding to the resulting theorem.
   237 \item [$intro_classes$] repeatedly expands the class introduction rules of
   238   this theory.
   239 \end{descr}
   240 
   241 See theory \texttt{HOL/Isar_examples/Group} for a simple example of using
   242 axiomatic type classes, including instantiation proofs.
   243 
   244 
   245 \section{The Simplifier}
   246 
   247 \subsection{Simplification methods}\label{sec:simp}
   248 
   249 \indexisarmeth{simp}
   250 \begin{matharray}{rcl}
   251   simp & : & \isarmeth \\
   252 \end{matharray}
   253 
   254 \begin{rail}
   255   'simp' ('!' ?) (simpmod * )
   256   ;
   257 
   258   simpmod: ('add' | 'del' | 'only' | 'other') ':' thmrefs
   259   ;
   260 \end{rail}
   261 
   262 \begin{descr}
   263 \item [$simp$] invokes Isabelle's simplifier, after modifying the context by
   264   adding or deleting rules as specified.  The \railtoken{only} modifier first
   265   removes all other rewrite rules and congruences, and then is like
   266   \railtoken{add}.  In contrast, \railtoken{other} ignores its arguments;
   267   nevertheless there may be side-effects on the context via
   268   attributes.\footnote{This provides a back door for arbitrary context
   269     manipulation.}
   270   
   271   The $simp$ method is based on \texttt{asm_full_simp_tac}
   272   \cite[\S10]{isabelle-ref}, but is much better behaved in practice.  Just the
   273   local premises of the actual goal are involved by default.  Additional facts
   274   may be inserted via forward-chaining (using $\THEN$, $\FROMNAME$ etc.).  The
   275   full context of assumptions is only included in the $simp!$ version, which
   276   should be used with care.
   277 \end{descr}
   278 
   279 \subsection{Modifying the context}
   280 
   281 \indexisaratt{simp}
   282 \begin{matharray}{rcl}
   283   simp & : & \isaratt \\
   284 \end{matharray}
   285 
   286 \begin{rail}
   287   'simp' (() | 'add' | 'del')
   288   ;
   289 \end{rail}
   290 
   291 \begin{descr}
   292 \item [$simp$] adds or deletes rules from the theory or proof context (the
   293   default is to add).
   294 \end{descr}
   295 
   296 
   297 \subsection{Forward simplification}
   298 
   299 \indexisaratt{simplify}\indexisaratt{asm-simplify}
   300 \indexisaratt{full-simplify}\indexisaratt{asm-full-simplify}
   301 \begin{matharray}{rcl}
   302   simplify & : & \isaratt \\
   303   asm_simplify & : & \isaratt \\
   304   full_simplify & : & \isaratt \\
   305   asm_full_simplify & : & \isaratt \\
   306 \end{matharray}
   307 
   308 These attributes provide forward rules for simplification, which should be
   309 used only very rarely.  There are no separate options for adding or deleting
   310 simplification rules locally.
   311 
   312 See the ML functions of the same name in \cite[\S10]{isabelle-ref} for more
   313 information.
   314 
   315 
   316 \section{The Classical Reasoner}
   317 
   318 \subsection{Basic methods}\label{sec:classical-basic}
   319 
   320 \indexisarmeth{rule}\indexisarmeth{intro}
   321 \indexisarmeth{elim}\indexisarmeth{default}\indexisarmeth{contradiction}
   322 \begin{matharray}{rcl}
   323   rule & : & \isarmeth \\
   324   intro & : & \isarmeth \\
   325   elim & : & \isarmeth \\
   326   contradiction & : & \isarmeth \\
   327 \end{matharray}
   328 
   329 \begin{rail}
   330   ('rule' | 'intro' | 'elim') thmrefs
   331   ;
   332 \end{rail}
   333 
   334 \begin{descr}
   335 \item [$rule$] as offered by the classical reasoner is a refinement over the
   336   primitive one (see \S\ref{sec:pure-meth}).  In case that no rules are
   337   provided as arguments, it automatically determines elimination and
   338   introduction rules from the context (see also \S\ref{sec:classical-mod}).
   339   In that form it is the default method for basic proof steps, such as
   340   $\PROOFNAME$ and ``$\DDOT$'' (two dots).
   341   
   342 \item [$intro$ and $elim$] repeatedly refine some goal by intro- or
   343   elim-resolution, after having inserted any facts.  Omitting the arguments
   344   refers to any suitable rules from the context, otherwise only the explicitly
   345   given ones may be applied.  The latter form admits better control of what
   346   actually happens, thus it is very appropriate as an initial method for
   347   $\PROOFNAME$ that splits up certain connectives of the goal, before entering
   348   the actual proof.
   349   
   350 \item [$contradiction$] solves some goal by contradiction, deriving any result
   351   from both $\neg A$ and $A$.  Facts, which are guaranteed to participate, may
   352   appear in either order.
   353 \end{descr}
   354 
   355 
   356 \subsection{Automated methods}\label{sec:classical-auto}
   357 
   358 \indexisarmeth{blast}
   359 \indexisarmeth{fast}\indexisarmeth{best}\indexisarmeth{slow}\indexisarmeth{slow-best}
   360 \begin{matharray}{rcl}
   361  blast & : & \isarmeth \\
   362  fast & : & \isarmeth \\
   363  best & : & \isarmeth \\
   364  slow & : & \isarmeth \\
   365  slow_best & : & \isarmeth \\
   366 \end{matharray}
   367 
   368 \railalias{slowbest}{slow\_best}
   369 \railterm{slowbest}
   370 
   371 \begin{rail}
   372   'blast' ('!' ?) nat? (clamod * )
   373   ;
   374   ('fast' | 'best' | 'slow' | slowbest) ('!' ?) (clamod * )
   375   ;
   376 
   377   clamod: (('intro' | 'elim' | 'dest') (() | '!' | '!!') | 'del') ':' thmrefs
   378   ;
   379 \end{rail}
   380 
   381 \begin{descr}
   382 \item [$blast$] refers to the classical tableau prover (see \texttt{blast_tac}
   383   in \cite[\S11]{isabelle-ref}).  The optional argument specifies a
   384   user-supplied search bound (default 20).
   385 \item [$fast$, $best$, $slow$, $slow_best$] refer to the generic classical
   386   reasoner (see \cite[\S11]{isabelle-ref}, tactic \texttt{fast_tac} etc).
   387 \end{descr}
   388 
   389 Any of above methods support additional modifiers of the context of classical
   390 rules.  There semantics is analogous to the attributes given in
   391 \S\ref{sec:classical-mod}.
   392 
   393 
   394 \subsection{Combined automated methods}
   395 
   396 \indexisarmeth{auto}\indexisarmeth{force}
   397 \begin{matharray}{rcl}
   398   force & : & \isarmeth \\
   399   auto & : & \isarmeth \\
   400 \end{matharray}
   401 
   402 \begin{rail}
   403   ('force' | 'auto') ('!' ?) (clasimpmod * )
   404   ;
   405 
   406   clasimpmod: ('simp' ('add' | 'del' | 'only') | other |
   407     (('intro' | 'elim' | 'dest') (() | '!' | '!!') | 'del')) ':' thmrefs
   408 \end{rail}
   409 
   410 \begin{descr}
   411 \item [$force$ and $auto$] provide access to Isabelle's combined
   412   simplification and classical reasoning tactics.  See \texttt{force_tac} and
   413   \texttt{auto_tac} in \cite[\S11]{isabelle-ref} for more information.  The
   414   modifier arguments correspond to those given in \S\ref{sec:simp} and
   415   \S\ref{sec:classical-auto}.  Just note that the ones related to the
   416   Simplifier are prefixed by \railtoken{simp} here.
   417 \end{descr}
   418 
   419 \subsection{Modifying the context}\label{sec:classical-mod}
   420 
   421 \indexisaratt{intro}\indexisaratt{elim}\indexisaratt{dest}
   422 \indexisaratt{iff}\indexisaratt{delrule}
   423 \begin{matharray}{rcl}
   424   intro & : & \isaratt \\
   425   elim & : & \isaratt \\
   426   dest & : & \isaratt \\
   427   iff & : & \isaratt \\
   428   delrule & : & \isaratt \\
   429 \end{matharray}
   430 
   431 \begin{rail}
   432   ('intro' | 'elim' | 'dest') (() | '!' | '!!')
   433   ;
   434 \end{rail}
   435 
   436 \begin{descr}
   437 \item [$intro$, $elim$, $dest$] add introduction, elimination, destruct rules,
   438   respectively.  By default, rules are considered as \emph{safe}, while a
   439   single ``!'' classifies as \emph{unsafe}, and ``!!'' as \emph{extra} (i.e.\ 
   440   not applied in the search-oriented automated methods, but only $rule$).
   441   
   442 \item [$iff$] declares equations both as rewrite rules for the simplifier and
   443   classical reasoning rules.
   444 
   445 \item [$delrule$] deletes introduction or elimination rules from the context.
   446   Note that destruction rules would have to be turned into elimination rules
   447   first, e.g.\ by using the $elimify$ attribute.
   448 \end{descr}
   449 
   450 %%% Local Variables: 
   451 %%% mode: latex
   452 %%% TeX-master: "isar-ref"
   453 %%% End: