doc-src/HOL/HOL.tex
changeset 8628 b3d9d8446473
parent 8604 c99e0024050c
child 9212 4afe62073b41
equal deleted inserted replaced
8627:44ec33bb5c5b 8628:b3d9d8446473
  2701   left-hand side must have the form $f\,t$, where $f$ is the function and $t$
  2701   left-hand side must have the form $f\,t$, where $f$ is the function and $t$
  2702   is a tuple of distinct variables.  If more than one equation is present then
  2702   is a tuple of distinct variables.  If more than one equation is present then
  2703   $f$ is defined by pattern-matching on components of its argument whose type
  2703   $f$ is defined by pattern-matching on components of its argument whose type
  2704   is a \texttt{datatype}.  
  2704   is a \texttt{datatype}.  
  2705 
  2705 
  2706   Unlike with \texttt{primrec}, the reduction rules are not added to the
  2706   The \ML\ identifier $f$\texttt{.simps} contains the reduction rules as
  2707   default simpset, and individual rules may not be labelled with identifiers.
  2707   a list of theorems.
  2708   However, the identifier $f$\texttt{.rules} is visible at the \ML\ level
       
  2709   as a list of theorems.
       
  2710 \end{itemize}
  2708 \end{itemize}
  2711 
  2709 
  2712 With the definition of \texttt{gcd} shown above, Isabelle/HOL is unable to
  2710 With the definition of \texttt{gcd} shown above, Isabelle/HOL is unable to
  2713 prove one termination condition.  It remains as a precondition of the
  2711 prove one termination condition.  It remains as a precondition of the
  2714 recursion theorems.
  2712 recursion theorems:
  2715 \begin{ttbox}
  2713 \begin{ttbox}
  2716 gcd.rules;
  2714 gcd.simps;
  2717 {\out ["! m n. n ~= 0 --> m mod n < n}
  2715 {\out ["! m n. n ~= 0 --> m mod n < n}
  2718 {\out   ==> gcd (?m, ?n) = (if ?n = 0 then ?m else gcd (?n, ?m mod ?n))"] }
  2716 {\out   ==> gcd (?m, ?n) = (if ?n = 0 then ?m else gcd (?n, ?m mod ?n))"] }
  2719 {\out : thm list}
  2717 {\out : thm list}
  2720 \end{ttbox}
  2718 \end{ttbox}
  2721 The theory \texttt{HOL/ex/Primes} illustrates how to prove termination
  2719 The theory \texttt{HOL/ex/Primes} illustrates how to prove termination
  2722 conditions afterwards.  The function \texttt{Tfl.tgoalw} is like the standard
  2720 conditions afterwards.  The function \texttt{Tfl.tgoalw} is like the standard
  2723 function \texttt{goalw}, which sets up a goal to prove, but its argument
  2721 function \texttt{goalw}, which sets up a goal to prove, but its argument
  2724 should be the identifier $f$\texttt{.rules} and its effect is to set up a
  2722 should be the identifier $f$\texttt{.simps} and its effect is to set up a
  2725 proof of the termination conditions:
  2723 proof of the termination conditions:
  2726 \begin{ttbox}
  2724 \begin{ttbox}
  2727 Tfl.tgoalw thy [] gcd.rules;
  2725 Tfl.tgoalw thy [] gcd.simps;
  2728 {\out Level 0}
  2726 {\out Level 0}
  2729 {\out ! m n. n ~= 0 --> m mod n < n}
  2727 {\out ! m n. n ~= 0 --> m mod n < n}
  2730 {\out  1. ! m n. n ~= 0 --> m mod n < n}
  2728 {\out  1. ! m n. n ~= 0 --> m mod n < n}
  2731 \end{ttbox}
  2729 \end{ttbox}
  2732 This subgoal has a one-step proof using \texttt{simp_tac}.  Once the theorem
  2730 This subgoal has a one-step proof using \texttt{simp_tac}.  Once the theorem
  2733 is proved, it can be used to eliminate the termination conditions from
  2731 is proved, it can be used to eliminate the termination conditions from
  2734 elements of \texttt{gcd.rules}.  Theory \texttt{HOL/Subst/Unify} is a much
  2732 elements of \texttt{gcd.simps}.  Theory \texttt{HOL/Subst/Unify} is a much
  2735 more complicated example of this process, where the termination conditions can
  2733 more complicated example of this process, where the termination conditions can
  2736 only be proved by complicated reasoning involving the recursive function
  2734 only be proved by complicated reasoning involving the recursive function
  2737 itself.
  2735 itself.
  2738 
  2736 
  2739 Isabelle/HOL can prove the \texttt{gcd} function's termination condition
  2737 Isabelle/HOL can prove the \texttt{gcd} function's termination condition
  2741 \begin{ttbox}
  2739 \begin{ttbox}
  2742 recdef gcd "measure ((\%(m,n). n) ::nat*nat=>nat)"
  2740 recdef gcd "measure ((\%(m,n). n) ::nat*nat=>nat)"
  2743   simpset "simpset() addsimps [mod_less_divisor, zero_less_eq]"
  2741   simpset "simpset() addsimps [mod_less_divisor, zero_less_eq]"
  2744     "gcd (m, n) = (if n=0 then m else gcd(n, m mod n))"
  2742     "gcd (m, n) = (if n=0 then m else gcd(n, m mod n))"
  2745 \end{ttbox}
  2743 \end{ttbox}
       
  2744 
       
  2745 If all termination conditions were proved automatically, $f$\texttt{.simps}
       
  2746 is added to the simpset automatically, just as in \texttt{primrec}. 
       
  2747 The simplification rules corresponding to clause $i$ (where counting starts
       
  2748 at 0) are called $f$\texttt{.}$i$ and can be accessed as \texttt{thms
       
  2749   "$f$.$i$"},
       
  2750 which returns a list of theorems. Thus you can, for example, remove specific
       
  2751 clauses from the simpset. Note that a single clause may give rise to a set of
       
  2752 simplification rules in order to capture the fact that if clauses overlap,
       
  2753 their order disambiguates them.
  2746 
  2754 
  2747 A \texttt{recdef} definition also returns an induction rule specialised for
  2755 A \texttt{recdef} definition also returns an induction rule specialised for
  2748 the recursive function.  For the \texttt{gcd} function above, the induction
  2756 the recursive function.  For the \texttt{gcd} function above, the induction
  2749 rule is
  2757 rule is
  2750 \begin{ttbox}
  2758 \begin{ttbox}