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