%

\begin{isabellebody}%

%

\begin{isamarkuptext}%

Once we have succeeded in proving all termination conditions, the recursion

equations become simplification rules, just as with

\isacommand{primrec}. In most cases this works fine, but there is a subtle

problem that must be mentioned: simplification may not

terminate because of automatic splitting of \isa{if}.

Let us look at an example:%

\end{isamarkuptext}%

\isacommand{consts}\ gcd\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}nat{\isacharasterisk}nat\ {\isasymRightarrow}\ nat{\isachardoublequote}\isanewline

\isacommand{recdef}\ gcd\ {\isachardoublequote}measure\ {\isacharparenleft}{\isasymlambda}{\isacharparenleft}m{\isacharcomma}n{\isacharparenright}{\isachardot}n{\isacharparenright}{\isachardoublequote}\isanewline

\ \ {\isachardoublequote}gcd\ {\isacharparenleft}m{\isacharcomma}\ n{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}if\ n{\isacharequal}\isadigit{0}\ then\ m\ else\ gcd{\isacharparenleft}n{\isacharcomma}\ m\ mod\ n{\isacharparenright}{\isacharparenright}{\isachardoublequote}%

\begin{isamarkuptext}%

\noindent

According to the measure function, the second argument should decrease with

each recursive call. The resulting termination condition

\begin{quote}

\begin{isabelle}%

\mbox{n}\ {\isasymnoteq}\ \isadigit{0}\ {\isasymLongrightarrow}\ \mbox{m}\ mod\ \mbox{n}\ {\isacharless}\ \mbox{n}

\end{isabelle}%

\end{quote}

is provded automatically because it is already present as a lemma in the

arithmetic library. Thus the recursion equation becomes a simplification

rule. Of course the equation is nonterminating if we are allowed to unfold

the recursive call inside the \isa{else} branch, which is why programming

languages and our simplifier don't do that. Unfortunately the simplifier does

something else which leads to the same problem: it splits \isa{if}s if the

condition simplifies to neither \isa{True} nor \isa{False}. For

example, simplification reduces

\begin{quote}

\begin{isabelle}%

gcd\ {\isacharparenleft}\mbox{m}{\isacharcomma}\ \mbox{n}{\isacharparenright}\ {\isacharequal}\ \mbox{k}

\end{isabelle}%

\end{quote}

in one step to

\begin{quote}

\begin{isabelle}%

{\isacharparenleft}if\ \mbox{n}\ {\isacharequal}\ \isadigit{0}\ then\ \mbox{m}\ else\ gcd\ {\isacharparenleft}\mbox{n}{\isacharcomma}\ \mbox{m}\ mod\ \mbox{n}{\isacharparenright}{\isacharparenright}\ {\isacharequal}\ \mbox{k}

\end{isabelle}%

\end{quote}

where the condition cannot be reduced further, and splitting leads to

\begin{quote}

\begin{isabelle}%

{\isacharparenleft}\mbox{n}\ {\isacharequal}\ \isadigit{0}\ {\isasymlongrightarrow}\ \mbox{m}\ {\isacharequal}\ \mbox{k}{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}\mbox{n}\ {\isasymnoteq}\ \isadigit{0}\ {\isasymlongrightarrow}\ gcd\ {\isacharparenleft}\mbox{n}{\isacharcomma}\ \mbox{m}\ mod\ \mbox{n}{\isacharparenright}\ {\isacharequal}\ \mbox{k}{\isacharparenright}

\end{isabelle}%

\end{quote}

Since the recursive call \isa{gcd\ {\isacharparenleft}\mbox{n}{\isacharcomma}\ \mbox{m}\ mod\ \mbox{n}{\isacharparenright}} is no longer protected by

an \isa{if}, it is unfolded again, which leads to an infinite chain of

simplification steps. Fortunately, this problem can be avoided in many

different ways.

The most radical solution is to disable the offending

\isa{split_if} as shown in the section on case splits in

\S\ref{sec:SimpFeatures}.

However, we do not recommend this because it means you will often have to

invoke the rule explicitly when \isa{if} is involved.

If possible, the definition should be given by pattern matching on the left

rather than \isa{if} on the right. In the case of \isa{gcd} the

following alternative definition suggests itself:%

\end{isamarkuptext}%

\isacommand{consts}\ gcd\isadigit{1}\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}nat{\isacharasterisk}nat\ {\isasymRightarrow}\ nat{\isachardoublequote}\isanewline

\isacommand{recdef}\ gcd\isadigit{1}\ {\isachardoublequote}measure\ {\isacharparenleft}{\isasymlambda}{\isacharparenleft}m{\isacharcomma}n{\isacharparenright}{\isachardot}n{\isacharparenright}{\isachardoublequote}\isanewline

\ \ {\isachardoublequote}gcd\isadigit{1}\ {\isacharparenleft}m{\isacharcomma}\ \isadigit{0}{\isacharparenright}\ {\isacharequal}\ m{\isachardoublequote}\isanewline

\ \ {\isachardoublequote}gcd\isadigit{1}\ {\isacharparenleft}m{\isacharcomma}\ n{\isacharparenright}\ {\isacharequal}\ gcd\isadigit{1}{\isacharparenleft}n{\isacharcomma}\ m\ mod\ n{\isacharparenright}{\isachardoublequote}%

\begin{isamarkuptext}%

\noindent

Note that the order of equations is important and hides the side condition

\isa{n \isasymnoteq\ 0}. Unfortunately, in general the case distinction

may not be expressible by pattern matching.

A very simple alternative is to replace \isa{if} by \isa{case}, which

is also available for \isa{bool} but is not split automatically:%

\end{isamarkuptext}%

\isacommand{consts}\ gcd\isadigit{2}\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}nat{\isacharasterisk}nat\ {\isasymRightarrow}\ nat{\isachardoublequote}\isanewline

\isacommand{recdef}\ gcd\isadigit{2}\ {\isachardoublequote}measure\ {\isacharparenleft}{\isasymlambda}{\isacharparenleft}m{\isacharcomma}n{\isacharparenright}{\isachardot}n{\isacharparenright}{\isachardoublequote}\isanewline

\ \ {\isachardoublequote}gcd\isadigit{2}{\isacharparenleft}m{\isacharcomma}n{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}case\ n{\isacharequal}\isadigit{0}\ of\ True\ {\isasymRightarrow}\ m\ {\isacharbar}\ False\ {\isasymRightarrow}\ gcd\isadigit{2}{\isacharparenleft}n{\isacharcomma}m\ mod\ n{\isacharparenright}{\isacharparenright}{\isachardoublequote}%

\begin{isamarkuptext}%

\noindent

In fact, this is probably the neatest solution next to pattern matching.

A final alternative is to replace the offending simplification rules by

derived conditional ones. For \isa{gcd} it means we have to prove%

\end{isamarkuptext}%

\isacommand{lemma}\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}gcd\ {\isacharparenleft}m{\isacharcomma}\ \isadigit{0}{\isacharparenright}\ {\isacharequal}\ m{\isachardoublequote}\isanewline

\isacommand{by}{\isacharparenleft}simp{\isacharparenright}\isanewline

\isacommand{lemma}\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}n\ {\isasymnoteq}\ \isadigit{0}\ {\isasymLongrightarrow}\ gcd{\isacharparenleft}m{\isacharcomma}\ n{\isacharparenright}\ {\isacharequal}\ gcd{\isacharparenleft}n{\isacharcomma}\ m\ mod\ n{\isacharparenright}{\isachardoublequote}\isanewline

\isacommand{by}{\isacharparenleft}simp{\isacharparenright}%

\begin{isamarkuptext}%

\noindent

after which we can disable the original simplification rule:%

\end{isamarkuptext}%

\isacommand{lemmas}\ {\isacharbrackleft}simp\ del{\isacharbrackright}\ {\isacharequal}\ gcd{\isachardot}simps\isanewline

\end{isabellebody}%

%%% Local Variables:

%%% mode: latex

%%% TeX-master: "root"

%%% End: