krauss@21212
|
1 |
(* Title: Doc/IsarAdvanced/Functions/Thy/Fundefs.thy
|
krauss@21212
|
2 |
ID: $Id$
|
krauss@21212
|
3 |
Author: Alexander Krauss, TU Muenchen
|
krauss@21212
|
4 |
|
krauss@21212
|
5 |
Tutorial for function definitions with the new "function" package.
|
krauss@21212
|
6 |
*)
|
krauss@21212
|
7 |
|
krauss@21212
|
8 |
theory Functions
|
krauss@21212
|
9 |
imports Main
|
krauss@21212
|
10 |
begin
|
krauss@21212
|
11 |
|
krauss@23188
|
12 |
section {* Function Definitions for Dummies *}
|
krauss@21212
|
13 |
|
krauss@21212
|
14 |
text {*
|
krauss@21212
|
15 |
In most cases, defining a recursive function is just as simple as other definitions:
|
krauss@23003
|
16 |
*}
|
krauss@21212
|
17 |
|
krauss@21212
|
18 |
fun fib :: "nat \<Rightarrow> nat"
|
krauss@21212
|
19 |
where
|
krauss@21212
|
20 |
"fib 0 = 1"
|
krauss@21212
|
21 |
| "fib (Suc 0) = 1"
|
krauss@21212
|
22 |
| "fib (Suc (Suc n)) = fib n + fib (Suc n)"
|
krauss@21212
|
23 |
|
krauss@21212
|
24 |
text {*
|
krauss@23003
|
25 |
The syntax is rather self-explanatory: We introduce a function by
|
krauss@25091
|
26 |
giving its name, its type,
|
krauss@25091
|
27 |
and a set of defining recursive equations.
|
krauss@25091
|
28 |
If we leave out the type, the most general type will be
|
krauss@25091
|
29 |
inferred, which can sometimes lead to surprises: Since both @{term
|
krauss@25278
|
30 |
"1::nat"} and @{text "+"} are overloaded, we would end up
|
krauss@25091
|
31 |
with @{text "fib :: nat \<Rightarrow> 'a::{one,plus}"}.
|
krauss@23003
|
32 |
*}
|
krauss@23003
|
33 |
|
krauss@23003
|
34 |
text {*
|
krauss@23003
|
35 |
The function always terminates, since its argument gets smaller in
|
krauss@23188
|
36 |
every recursive call.
|
krauss@23188
|
37 |
Since HOL is a logic of total functions, termination is a
|
krauss@23188
|
38 |
fundamental requirement to prevent inconsistencies\footnote{From the
|
krauss@23188
|
39 |
\qt{definition} @{text "f(n) = f(n) + 1"} we could prove
|
krauss@23188
|
40 |
@{text "0 = 1"} by subtracting @{text "f(n)"} on both sides.}.
|
krauss@23188
|
41 |
Isabelle tries to prove termination automatically when a definition
|
krauss@23188
|
42 |
is made. In \S\ref{termination}, we will look at cases where this
|
krauss@23188
|
43 |
fails and see what to do then.
|
krauss@21212
|
44 |
*}
|
krauss@21212
|
45 |
|
krauss@21212
|
46 |
subsection {* Pattern matching *}
|
krauss@21212
|
47 |
|
krauss@22065
|
48 |
text {* \label{patmatch}
|
krauss@23003
|
49 |
Like in functional programming, we can use pattern matching to
|
krauss@23003
|
50 |
define functions. At the moment we will only consider \emph{constructor
|
krauss@21212
|
51 |
patterns}, which only consist of datatype constructors and
|
krauss@23805
|
52 |
variables. Furthermore, patterns must be linear, i.e.\ all variables
|
krauss@23805
|
53 |
on the left hand side of an equation must be distinct. In
|
krauss@23805
|
54 |
\S\ref{genpats} we discuss more general pattern matching.
|
krauss@21212
|
55 |
|
krauss@21212
|
56 |
If patterns overlap, the order of the equations is taken into
|
krauss@21212
|
57 |
account. The following function inserts a fixed element between any
|
krauss@21212
|
58 |
two elements of a list:
|
krauss@21212
|
59 |
*}
|
krauss@21212
|
60 |
|
krauss@21212
|
61 |
fun sep :: "'a \<Rightarrow> 'a list \<Rightarrow> 'a list"
|
krauss@21212
|
62 |
where
|
krauss@21212
|
63 |
"sep a (x#y#xs) = x # a # sep a (y # xs)"
|
krauss@21212
|
64 |
| "sep a xs = xs"
|
krauss@21212
|
65 |
|
krauss@21212
|
66 |
text {*
|
krauss@23188
|
67 |
Overlapping patterns are interpreted as \qt{increments} to what is
|
krauss@21212
|
68 |
already there: The second equation is only meant for the cases where
|
krauss@21212
|
69 |
the first one does not match. Consequently, Isabelle replaces it
|
krauss@22065
|
70 |
internally by the remaining cases, making the patterns disjoint:
|
krauss@21212
|
71 |
*}
|
krauss@21212
|
72 |
|
krauss@22065
|
73 |
thm sep.simps
|
krauss@21212
|
74 |
|
krauss@22065
|
75 |
text {* @{thm [display] sep.simps[no_vars]} *}
|
krauss@21212
|
76 |
|
krauss@21212
|
77 |
text {*
|
krauss@23805
|
78 |
\noindent The equations from function definitions are automatically used in
|
krauss@21212
|
79 |
simplification:
|
krauss@21212
|
80 |
*}
|
krauss@21212
|
81 |
|
krauss@23188
|
82 |
lemma "sep 0 [1, 2, 3] = [1, 0, 2, 0, 3]"
|
krauss@21212
|
83 |
by simp
|
krauss@21212
|
84 |
|
krauss@21212
|
85 |
subsection {* Induction *}
|
krauss@21212
|
86 |
|
krauss@22065
|
87 |
text {*
|
krauss@21212
|
88 |
|
krauss@23805
|
89 |
Isabelle provides customized induction rules for recursive
|
krauss@23805
|
90 |
functions. These rules follow the recursive structure of the
|
krauss@23805
|
91 |
definition. Here is the rule @{text sep.induct} arising from the
|
krauss@23805
|
92 |
above definition of @{const sep}:
|
krauss@23188
|
93 |
|
krauss@23805
|
94 |
@{thm [display] sep.induct}
|
krauss@23805
|
95 |
|
krauss@23805
|
96 |
We have a step case for list with at least two elements, and two
|
krauss@23805
|
97 |
base cases for the zero- and the one-element list. Here is a simple
|
krauss@23805
|
98 |
proof about @{const sep} and @{const map}
|
krauss@23805
|
99 |
*}
|
krauss@23805
|
100 |
|
krauss@23805
|
101 |
lemma "map f (sep x ys) = sep (f x) (map f ys)"
|
krauss@23805
|
102 |
apply (induct x ys rule: sep.induct)
|
krauss@23805
|
103 |
|
krauss@23805
|
104 |
txt {*
|
krauss@23805
|
105 |
We get three cases, like in the definition.
|
krauss@23805
|
106 |
|
krauss@23805
|
107 |
@{subgoals [display]}
|
krauss@23805
|
108 |
*}
|
krauss@23805
|
109 |
|
krauss@23805
|
110 |
apply auto
|
krauss@23805
|
111 |
done
|
krauss@23805
|
112 |
text {*
|
krauss@23188
|
113 |
|
krauss@23188
|
114 |
With the \cmd{fun} command, you can define about 80\% of the
|
krauss@23188
|
115 |
functions that occur in practice. The rest of this tutorial explains
|
krauss@23188
|
116 |
the remaining 20\%.
|
krauss@22065
|
117 |
*}
|
krauss@21212
|
118 |
|
krauss@22065
|
119 |
|
krauss@23188
|
120 |
section {* fun vs.\ function *}
|
krauss@21212
|
121 |
|
krauss@21212
|
122 |
text {*
|
krauss@23188
|
123 |
The \cmd{fun} command provides a
|
krauss@21212
|
124 |
convenient shorthand notation for simple function definitions. In
|
krauss@21212
|
125 |
this mode, Isabelle tries to solve all the necessary proof obligations
|
krauss@27026
|
126 |
automatically. If any proof fails, the definition is
|
krauss@22065
|
127 |
rejected. This can either mean that the definition is indeed faulty,
|
krauss@22065
|
128 |
or that the default proof procedures are just not smart enough (or
|
krauss@22065
|
129 |
rather: not designed) to handle the definition.
|
krauss@21212
|
130 |
|
krauss@23188
|
131 |
By expanding the abbreviation to the more verbose \cmd{function} command, these proof obligations become visible and can be analyzed or
|
krauss@23188
|
132 |
solved manually. The expansion from \cmd{fun} to \cmd{function} is as follows:
|
krauss@21212
|
133 |
|
krauss@22065
|
134 |
\end{isamarkuptext}
|
krauss@21212
|
135 |
|
krauss@21212
|
136 |
|
krauss@23188
|
137 |
\[\left[\;\begin{minipage}{0.25\textwidth}\vspace{6pt}
|
krauss@23188
|
138 |
\cmd{fun} @{text "f :: \<tau>"}\\%
|
krauss@23188
|
139 |
\cmd{where}\\%
|
krauss@23188
|
140 |
\hspace*{2ex}{\it equations}\\%
|
krauss@23188
|
141 |
\hspace*{2ex}\vdots\vspace*{6pt}
|
krauss@23188
|
142 |
\end{minipage}\right]
|
krauss@23188
|
143 |
\quad\equiv\quad
|
krauss@27026
|
144 |
\left[\;\begin{minipage}{0.48\textwidth}\vspace{6pt}
|
krauss@23188
|
145 |
\cmd{function} @{text "("}\cmd{sequential}@{text ") f :: \<tau>"}\\%
|
krauss@23188
|
146 |
\cmd{where}\\%
|
krauss@23188
|
147 |
\hspace*{2ex}{\it equations}\\%
|
krauss@23188
|
148 |
\hspace*{2ex}\vdots\\%
|
krauss@22065
|
149 |
\cmd{by} @{text "pat_completeness auto"}\\%
|
krauss@23188
|
150 |
\cmd{termination by} @{text "lexicographic_order"}\vspace{6pt}
|
krauss@23188
|
151 |
\end{minipage}
|
krauss@23188
|
152 |
\right]\]
|
krauss@22065
|
153 |
|
krauss@22065
|
154 |
\begin{isamarkuptext}
|
krauss@22065
|
155 |
\vspace*{1em}
|
krauss@23188
|
156 |
\noindent Some details have now become explicit:
|
krauss@21212
|
157 |
|
krauss@21212
|
158 |
\begin{enumerate}
|
krauss@22065
|
159 |
\item The \cmd{sequential} option enables the preprocessing of
|
krauss@23805
|
160 |
pattern overlaps which we already saw. Without this option, the equations
|
krauss@21212
|
161 |
must already be disjoint and complete. The automatic completion only
|
krauss@23188
|
162 |
works with constructor patterns.
|
krauss@21212
|
163 |
|
krauss@23188
|
164 |
\item A function definition produces a proof obligation which
|
krauss@23188
|
165 |
expresses completeness and compatibility of patterns (we talk about
|
krauss@22065
|
166 |
this later). The combination of the methods @{text "pat_completeness"} and
|
krauss@22065
|
167 |
@{text "auto"} is used to solve this proof obligation.
|
krauss@21212
|
168 |
|
krauss@21212
|
169 |
\item A termination proof follows the definition, started by the
|
krauss@23188
|
170 |
\cmd{termination} command. This will be explained in \S\ref{termination}.
|
krauss@22065
|
171 |
\end{enumerate}
|
krauss@22065
|
172 |
Whenever a \cmd{fun} command fails, it is usually a good idea to
|
krauss@22065
|
173 |
expand the syntax to the more verbose \cmd{function} form, to see
|
krauss@22065
|
174 |
what is actually going on.
|
krauss@21212
|
175 |
*}
|
krauss@21212
|
176 |
|
krauss@21212
|
177 |
|
krauss@23188
|
178 |
section {* Termination *}
|
krauss@21212
|
179 |
|
krauss@23188
|
180 |
text {*\label{termination}
|
krauss@23805
|
181 |
The method @{text "lexicographic_order"} is the default method for
|
krauss@23805
|
182 |
termination proofs. It can prove termination of a
|
krauss@23188
|
183 |
certain class of functions by searching for a suitable lexicographic
|
krauss@23188
|
184 |
combination of size measures. Of course, not all functions have such
|
krauss@23805
|
185 |
a simple termination argument. For them, we can specify the termination
|
krauss@23805
|
186 |
relation manually.
|
krauss@23188
|
187 |
*}
|
krauss@23188
|
188 |
|
krauss@23188
|
189 |
subsection {* The {\tt relation} method *}
|
krauss@23188
|
190 |
text{*
|
krauss@21212
|
191 |
Consider the following function, which sums up natural numbers up to
|
krauss@22065
|
192 |
@{text "N"}, using a counter @{text "i"}:
|
krauss@21212
|
193 |
*}
|
krauss@21212
|
194 |
|
krauss@21212
|
195 |
function sum :: "nat \<Rightarrow> nat \<Rightarrow> nat"
|
krauss@21212
|
196 |
where
|
krauss@21212
|
197 |
"sum i N = (if i > N then 0 else i + sum (Suc i) N)"
|
krauss@22065
|
198 |
by pat_completeness auto
|
krauss@21212
|
199 |
|
krauss@21212
|
200 |
text {*
|
krauss@22065
|
201 |
\noindent The @{text "lexicographic_order"} method fails on this example, because none of the
|
krauss@23805
|
202 |
arguments decreases in the recursive call, with respect to the standard size ordering.
|
krauss@23805
|
203 |
To prove termination manually, we must provide a custom wellfounded relation.
|
krauss@21212
|
204 |
|
krauss@21212
|
205 |
The termination argument for @{text "sum"} is based on the fact that
|
krauss@21212
|
206 |
the \emph{difference} between @{text "i"} and @{text "N"} gets
|
krauss@21212
|
207 |
smaller in every step, and that the recursion stops when @{text "i"}
|
krauss@23805
|
208 |
is greater than @{text "N"}. Phrased differently, the expression
|
krauss@23805
|
209 |
@{text "N + 1 - i"} always decreases.
|
krauss@21212
|
210 |
|
krauss@22065
|
211 |
We can use this expression as a measure function suitable to prove termination.
|
krauss@21212
|
212 |
*}
|
krauss@21212
|
213 |
|
krauss@27026
|
214 |
termination sum
|
krauss@23188
|
215 |
apply (relation "measure (\<lambda>(i,N). N + 1 - i)")
|
krauss@21212
|
216 |
|
krauss@23188
|
217 |
txt {*
|
krauss@23003
|
218 |
The \cmd{termination} command sets up the termination goal for the
|
krauss@23188
|
219 |
specified function @{text "sum"}. If the function name is omitted, it
|
krauss@23003
|
220 |
implicitly refers to the last function definition.
|
krauss@23003
|
221 |
|
krauss@22065
|
222 |
The @{text relation} method takes a relation of
|
krauss@22065
|
223 |
type @{typ "('a \<times> 'a) set"}, where @{typ "'a"} is the argument type of
|
krauss@22065
|
224 |
the function. If the function has multiple curried arguments, then
|
krauss@22065
|
225 |
these are packed together into a tuple, as it happened in the above
|
krauss@22065
|
226 |
example.
|
krauss@21212
|
227 |
|
krauss@27026
|
228 |
The predefined function @{term[source] "measure :: ('a \<Rightarrow> nat) \<Rightarrow> ('a \<times> 'a) set"} constructs a
|
krauss@23188
|
229 |
wellfounded relation from a mapping into the natural numbers (a
|
krauss@23188
|
230 |
\emph{measure function}).
|
krauss@22065
|
231 |
|
krauss@22065
|
232 |
After the invocation of @{text "relation"}, we must prove that (a)
|
krauss@22065
|
233 |
the relation we supplied is wellfounded, and (b) that the arguments
|
krauss@22065
|
234 |
of recursive calls indeed decrease with respect to the
|
krauss@23188
|
235 |
relation:
|
krauss@22065
|
236 |
|
krauss@23188
|
237 |
@{subgoals[display,indent=0]}
|
krauss@23188
|
238 |
|
krauss@23188
|
239 |
These goals are all solved by @{text "auto"}:
|
krauss@23188
|
240 |
*}
|
krauss@23188
|
241 |
|
krauss@23188
|
242 |
apply auto
|
krauss@23188
|
243 |
done
|
krauss@23188
|
244 |
|
krauss@23188
|
245 |
text {*
|
krauss@22065
|
246 |
Let us complicate the function a little, by adding some more
|
krauss@22065
|
247 |
recursive calls:
|
krauss@21212
|
248 |
*}
|
krauss@21212
|
249 |
|
krauss@21212
|
250 |
function foo :: "nat \<Rightarrow> nat \<Rightarrow> nat"
|
krauss@21212
|
251 |
where
|
krauss@21212
|
252 |
"foo i N = (if i > N
|
krauss@21212
|
253 |
then (if N = 0 then 0 else foo 0 (N - 1))
|
krauss@21212
|
254 |
else i + foo (Suc i) N)"
|
krauss@21212
|
255 |
by pat_completeness auto
|
krauss@21212
|
256 |
|
krauss@21212
|
257 |
text {*
|
krauss@21212
|
258 |
When @{text "i"} has reached @{text "N"}, it starts at zero again
|
krauss@21212
|
259 |
and @{text "N"} is decremented.
|
krauss@21212
|
260 |
This corresponds to a nested
|
krauss@21212
|
261 |
loop where one index counts up and the other down. Termination can
|
krauss@21212
|
262 |
be proved using a lexicographic combination of two measures, namely
|
krauss@22065
|
263 |
the value of @{text "N"} and the above difference. The @{const
|
krauss@22065
|
264 |
"measures"} combinator generalizes @{text "measure"} by taking a
|
krauss@22065
|
265 |
list of measure functions.
|
krauss@21212
|
266 |
*}
|
krauss@21212
|
267 |
|
krauss@21212
|
268 |
termination
|
krauss@22065
|
269 |
by (relation "measures [\<lambda>(i, N). N, \<lambda>(i,N). N + 1 - i]") auto
|
krauss@21212
|
270 |
|
krauss@23188
|
271 |
subsection {* How @{text "lexicographic_order"} works *}
|
krauss@23188
|
272 |
|
krauss@23188
|
273 |
(*fun fails :: "nat \<Rightarrow> nat list \<Rightarrow> nat"
|
krauss@23188
|
274 |
where
|
krauss@23188
|
275 |
"fails a [] = a"
|
krauss@23188
|
276 |
| "fails a (x#xs) = fails (x + a) (x # xs)"
|
krauss@23188
|
277 |
*)
|
krauss@23003
|
278 |
|
krauss@23003
|
279 |
text {*
|
krauss@23188
|
280 |
To see how the automatic termination proofs work, let's look at an
|
krauss@23188
|
281 |
example where it fails\footnote{For a detailed discussion of the
|
krauss@23188
|
282 |
termination prover, see \cite{bulwahnKN07}}:
|
krauss@23188
|
283 |
|
krauss@23188
|
284 |
\end{isamarkuptext}
|
krauss@23188
|
285 |
\cmd{fun} @{text "fails :: \"nat \<Rightarrow> nat list \<Rightarrow> nat\""}\\%
|
krauss@23188
|
286 |
\cmd{where}\\%
|
krauss@23188
|
287 |
\hspace*{2ex}@{text "\"fails a [] = a\""}\\%
|
krauss@23188
|
288 |
|\hspace*{1.5ex}@{text "\"fails a (x#xs) = fails (x + a) (x#xs)\""}\\
|
krauss@23188
|
289 |
\begin{isamarkuptext}
|
krauss@23188
|
290 |
|
krauss@23188
|
291 |
\noindent Isabelle responds with the following error:
|
krauss@23188
|
292 |
|
krauss@23188
|
293 |
\begin{isabelle}
|
krauss@23805
|
294 |
*** Unfinished subgoals:\newline
|
krauss@23805
|
295 |
*** (a, 1, <):\newline
|
krauss@23805
|
296 |
*** \ 1.~@{text "\<And>x. x = 0"}\newline
|
krauss@23805
|
297 |
*** (a, 1, <=):\newline
|
krauss@23805
|
298 |
*** \ 1.~False\newline
|
krauss@23805
|
299 |
*** (a, 2, <):\newline
|
krauss@23805
|
300 |
*** \ 1.~False\newline
|
krauss@23188
|
301 |
*** Calls:\newline
|
krauss@23188
|
302 |
*** a) @{text "(a, x # xs) -->> (x + a, x # xs)"}\newline
|
krauss@23188
|
303 |
*** Measures:\newline
|
krauss@23188
|
304 |
*** 1) @{text "\<lambda>x. size (fst x)"}\newline
|
krauss@23188
|
305 |
*** 2) @{text "\<lambda>x. size (snd x)"}\newline
|
krauss@23805
|
306 |
*** Result matrix:\newline
|
krauss@23805
|
307 |
*** \ \ \ \ 1\ \ 2 \newline
|
krauss@23805
|
308 |
*** a: ? <= \newline
|
krauss@23805
|
309 |
*** Could not find lexicographic termination order.\newline
|
krauss@23188
|
310 |
*** At command "fun".\newline
|
krauss@23188
|
311 |
\end{isabelle}
|
krauss@23003
|
312 |
*}
|
krauss@23003
|
313 |
|
krauss@23188
|
314 |
|
krauss@23188
|
315 |
text {*
|
krauss@23188
|
316 |
|
krauss@23188
|
317 |
|
krauss@23805
|
318 |
The the key to this error message is the matrix at the bottom. The rows
|
krauss@23188
|
319 |
of that matrix correspond to the different recursive calls (In our
|
krauss@23188
|
320 |
case, there is just one). The columns are the function's arguments
|
krauss@23188
|
321 |
(expressed through different measure functions, which map the
|
krauss@23188
|
322 |
argument tuple to a natural number).
|
krauss@23188
|
323 |
|
krauss@23188
|
324 |
The contents of the matrix summarize what is known about argument
|
krauss@23188
|
325 |
descents: The second argument has a weak descent (@{text "<="}) at the
|
krauss@23188
|
326 |
recursive call, and for the first argument nothing could be proved,
|
krauss@23805
|
327 |
which is expressed by @{text "?"}. In general, there are the values
|
krauss@23805
|
328 |
@{text "<"}, @{text "<="} and @{text "?"}.
|
krauss@23188
|
329 |
|
krauss@23188
|
330 |
For the failed proof attempts, the unfinished subgoals are also
|
krauss@23805
|
331 |
printed. Looking at these will often point to a missing lemma.
|
krauss@23188
|
332 |
|
krauss@23188
|
333 |
% As a more real example, here is quicksort:
|
krauss@23188
|
334 |
*}
|
krauss@23188
|
335 |
(*
|
krauss@23188
|
336 |
function qs :: "nat list \<Rightarrow> nat list"
|
krauss@23003
|
337 |
where
|
krauss@23188
|
338 |
"qs [] = []"
|
krauss@23188
|
339 |
| "qs (x#xs) = qs [y\<in>xs. y < x] @ x # qs [y\<in>xs. y \<ge> x]"
|
krauss@23003
|
340 |
by pat_completeness auto
|
krauss@23003
|
341 |
|
krauss@23188
|
342 |
termination apply lexicographic_order
|
krauss@23003
|
343 |
|
krauss@23188
|
344 |
text {* If we try @{text "lexicographic_order"} method, we get the
|
krauss@23188
|
345 |
following error *}
|
krauss@23188
|
346 |
termination by (lexicographic_order simp:l2)
|
krauss@23003
|
347 |
|
krauss@23188
|
348 |
lemma l: "x \<le> y \<Longrightarrow> x < Suc y" by arith
|
krauss@23188
|
349 |
|
krauss@23188
|
350 |
function
|
krauss@23188
|
351 |
|
krauss@23188
|
352 |
*)
|
krauss@21212
|
353 |
|
krauss@21212
|
354 |
section {* Mutual Recursion *}
|
krauss@21212
|
355 |
|
krauss@21212
|
356 |
text {*
|
krauss@21212
|
357 |
If two or more functions call one another mutually, they have to be defined
|
krauss@23188
|
358 |
in one step. Here are @{text "even"} and @{text "odd"}:
|
krauss@21212
|
359 |
*}
|
krauss@21212
|
360 |
|
krauss@22065
|
361 |
function even :: "nat \<Rightarrow> bool"
|
krauss@22065
|
362 |
and odd :: "nat \<Rightarrow> bool"
|
krauss@21212
|
363 |
where
|
krauss@21212
|
364 |
"even 0 = True"
|
krauss@21212
|
365 |
| "odd 0 = False"
|
krauss@21212
|
366 |
| "even (Suc n) = odd n"
|
krauss@21212
|
367 |
| "odd (Suc n) = even n"
|
krauss@22065
|
368 |
by pat_completeness auto
|
krauss@21212
|
369 |
|
krauss@21212
|
370 |
text {*
|
krauss@23188
|
371 |
To eliminate the mutual dependencies, Isabelle internally
|
krauss@21212
|
372 |
creates a single function operating on the sum
|
krauss@23188
|
373 |
type @{typ "nat + nat"}. Then, @{const even} and @{const odd} are
|
krauss@23188
|
374 |
defined as projections. Consequently, termination has to be proved
|
krauss@21212
|
375 |
simultaneously for both functions, by specifying a measure on the
|
krauss@21212
|
376 |
sum type:
|
krauss@21212
|
377 |
*}
|
krauss@21212
|
378 |
|
krauss@21212
|
379 |
termination
|
krauss@23188
|
380 |
by (relation "measure (\<lambda>x. case x of Inl n \<Rightarrow> n | Inr n \<Rightarrow> n)") auto
|
krauss@23188
|
381 |
|
krauss@23188
|
382 |
text {*
|
krauss@23188
|
383 |
We could also have used @{text lexicographic_order}, which
|
krauss@23188
|
384 |
supports mutual recursive termination proofs to a certain extent.
|
krauss@23188
|
385 |
*}
|
krauss@21212
|
386 |
|
krauss@22065
|
387 |
subsection {* Induction for mutual recursion *}
|
krauss@21212
|
388 |
|
krauss@22065
|
389 |
text {*
|
krauss@21212
|
390 |
|
krauss@22065
|
391 |
When functions are mutually recursive, proving properties about them
|
krauss@23188
|
392 |
generally requires simultaneous induction. The induction rule @{text "even_odd.induct"}
|
krauss@23188
|
393 |
generated from the above definition reflects this.
|
krauss@21212
|
394 |
|
krauss@22065
|
395 |
Let us prove something about @{const even} and @{const odd}:
|
krauss@22065
|
396 |
*}
|
krauss@21212
|
397 |
|
krauss@23188
|
398 |
lemma even_odd_mod2:
|
krauss@22065
|
399 |
"even n = (n mod 2 = 0)"
|
krauss@22065
|
400 |
"odd n = (n mod 2 = 1)"
|
krauss@21212
|
401 |
|
krauss@22065
|
402 |
txt {*
|
krauss@22065
|
403 |
We apply simultaneous induction, specifying the induction variable
|
krauss@22065
|
404 |
for both goals, separated by \cmd{and}: *}
|
krauss@22065
|
405 |
|
krauss@22065
|
406 |
apply (induct n and n rule: even_odd.induct)
|
krauss@22065
|
407 |
|
krauss@22065
|
408 |
txt {*
|
krauss@22065
|
409 |
We get four subgoals, which correspond to the clauses in the
|
krauss@22065
|
410 |
definition of @{const even} and @{const odd}:
|
krauss@22065
|
411 |
@{subgoals[display,indent=0]}
|
krauss@22065
|
412 |
Simplification solves the first two goals, leaving us with two
|
krauss@22065
|
413 |
statements about the @{text "mod"} operation to prove:
|
krauss@22065
|
414 |
*}
|
krauss@22065
|
415 |
|
krauss@22065
|
416 |
apply simp_all
|
krauss@22065
|
417 |
|
krauss@22065
|
418 |
txt {*
|
krauss@22065
|
419 |
@{subgoals[display,indent=0]}
|
krauss@22065
|
420 |
|
krauss@23805
|
421 |
\noindent These can be handled by Isabelle's arithmetic decision procedures.
|
krauss@22065
|
422 |
|
krauss@22065
|
423 |
*}
|
krauss@22065
|
424 |
|
krauss@23805
|
425 |
apply arith
|
krauss@23805
|
426 |
apply arith
|
krauss@22065
|
427 |
done
|
krauss@22065
|
428 |
|
krauss@22065
|
429 |
text {*
|
krauss@23188
|
430 |
In proofs like this, the simultaneous induction is really essential:
|
krauss@23188
|
431 |
Even if we are just interested in one of the results, the other
|
krauss@23188
|
432 |
one is necessary to strengthen the induction hypothesis. If we leave
|
krauss@27026
|
433 |
out the statement about @{const odd} and just write @{term True} instead,
|
krauss@27026
|
434 |
the same proof fails:
|
krauss@22065
|
435 |
*}
|
krauss@22065
|
436 |
|
krauss@23188
|
437 |
lemma failed_attempt:
|
krauss@22065
|
438 |
"even n = (n mod 2 = 0)"
|
krauss@22065
|
439 |
"True"
|
krauss@22065
|
440 |
apply (induct n rule: even_odd.induct)
|
krauss@22065
|
441 |
|
krauss@22065
|
442 |
txt {*
|
krauss@22065
|
443 |
\noindent Now the third subgoal is a dead end, since we have no
|
krauss@23188
|
444 |
useful induction hypothesis available:
|
krauss@22065
|
445 |
|
krauss@22065
|
446 |
@{subgoals[display,indent=0]}
|
krauss@22065
|
447 |
*}
|
krauss@22065
|
448 |
|
krauss@22065
|
449 |
oops
|
krauss@22065
|
450 |
|
krauss@23188
|
451 |
section {* General pattern matching *}
|
krauss@23805
|
452 |
text{*\label{genpats} *}
|
krauss@22065
|
453 |
|
krauss@23188
|
454 |
subsection {* Avoiding automatic pattern splitting *}
|
krauss@22065
|
455 |
|
krauss@22065
|
456 |
text {*
|
krauss@22065
|
457 |
|
krauss@22065
|
458 |
Up to now, we used pattern matching only on datatypes, and the
|
krauss@22065
|
459 |
patterns were always disjoint and complete, and if they weren't,
|
krauss@22065
|
460 |
they were made disjoint automatically like in the definition of
|
krauss@22065
|
461 |
@{const "sep"} in \S\ref{patmatch}.
|
krauss@22065
|
462 |
|
krauss@23188
|
463 |
This automatic splitting can significantly increase the number of
|
krauss@23188
|
464 |
equations involved, and this is not always desirable. The following
|
krauss@23188
|
465 |
example shows the problem:
|
krauss@22065
|
466 |
|
krauss@23805
|
467 |
Suppose we are modeling incomplete knowledge about the world by a
|
krauss@23003
|
468 |
three-valued datatype, which has values @{term "T"}, @{term "F"}
|
krauss@23003
|
469 |
and @{term "X"} for true, false and uncertain propositions, respectively.
|
krauss@22065
|
470 |
*}
|
krauss@22065
|
471 |
|
krauss@22065
|
472 |
datatype P3 = T | F | X
|
krauss@22065
|
473 |
|
krauss@23188
|
474 |
text {* \noindent Then the conjunction of such values can be defined as follows: *}
|
krauss@22065
|
475 |
|
krauss@22065
|
476 |
fun And :: "P3 \<Rightarrow> P3 \<Rightarrow> P3"
|
krauss@22065
|
477 |
where
|
krauss@22065
|
478 |
"And T p = p"
|
krauss@23003
|
479 |
| "And p T = p"
|
krauss@23003
|
480 |
| "And p F = F"
|
krauss@23003
|
481 |
| "And F p = F"
|
krauss@23003
|
482 |
| "And X X = X"
|
krauss@22065
|
483 |
|
krauss@22065
|
484 |
|
krauss@22065
|
485 |
text {*
|
krauss@22065
|
486 |
This definition is useful, because the equations can directly be used
|
krauss@23805
|
487 |
as simplification rules rules. But the patterns overlap: For example,
|
krauss@23188
|
488 |
the expression @{term "And T T"} is matched by both the first and
|
krauss@23188
|
489 |
the second equation. By default, Isabelle makes the patterns disjoint by
|
krauss@22065
|
490 |
splitting them up, producing instances:
|
krauss@22065
|
491 |
*}
|
krauss@22065
|
492 |
|
krauss@22065
|
493 |
thm And.simps
|
krauss@22065
|
494 |
|
krauss@22065
|
495 |
text {*
|
krauss@22065
|
496 |
@{thm[indent=4] And.simps}
|
krauss@22065
|
497 |
|
krauss@22065
|
498 |
\vspace*{1em}
|
krauss@23003
|
499 |
\noindent There are several problems with this:
|
krauss@22065
|
500 |
|
krauss@22065
|
501 |
\begin{enumerate}
|
krauss@23188
|
502 |
\item If the datatype has many constructors, there can be an
|
krauss@22065
|
503 |
explosion of equations. For @{const "And"}, we get seven instead of
|
krauss@23003
|
504 |
five equations, which can be tolerated, but this is just a small
|
krauss@22065
|
505 |
example.
|
krauss@22065
|
506 |
|
krauss@23188
|
507 |
\item Since splitting makes the equations \qt{less general}, they
|
krauss@22065
|
508 |
do not always match in rewriting. While the term @{term "And x F"}
|
krauss@23188
|
509 |
can be simplified to @{term "F"} with the original equations, a
|
krauss@22065
|
510 |
(manual) case split on @{term "x"} is now necessary.
|
krauss@22065
|
511 |
|
krauss@22065
|
512 |
\item The splitting also concerns the induction rule @{text
|
krauss@22065
|
513 |
"And.induct"}. Instead of five premises it now has seven, which
|
krauss@22065
|
514 |
means that our induction proofs will have more cases.
|
krauss@22065
|
515 |
|
krauss@22065
|
516 |
\item In general, it increases clarity if we get the same definition
|
krauss@22065
|
517 |
back which we put in.
|
krauss@22065
|
518 |
\end{enumerate}
|
krauss@22065
|
519 |
|
krauss@23188
|
520 |
If we do not want the automatic splitting, we can switch it off by
|
krauss@23188
|
521 |
leaving out the \cmd{sequential} option. However, we will have to
|
krauss@23188
|
522 |
prove that our pattern matching is consistent\footnote{This prevents
|
krauss@23188
|
523 |
us from defining something like @{term "f x = True"} and @{term "f x
|
krauss@23188
|
524 |
= False"} simultaneously.}:
|
krauss@22065
|
525 |
*}
|
krauss@22065
|
526 |
|
krauss@22065
|
527 |
function And2 :: "P3 \<Rightarrow> P3 \<Rightarrow> P3"
|
krauss@22065
|
528 |
where
|
krauss@22065
|
529 |
"And2 T p = p"
|
krauss@23003
|
530 |
| "And2 p T = p"
|
krauss@23003
|
531 |
| "And2 p F = F"
|
krauss@23003
|
532 |
| "And2 F p = F"
|
krauss@23003
|
533 |
| "And2 X X = X"
|
krauss@22065
|
534 |
|
krauss@22065
|
535 |
txt {*
|
krauss@23188
|
536 |
\noindent Now let's look at the proof obligations generated by a
|
krauss@22065
|
537 |
function definition. In this case, they are:
|
krauss@22065
|
538 |
|
krauss@23188
|
539 |
@{subgoals[display,indent=0]}\vspace{-1.2em}\hspace{3cm}\vdots\vspace{1.2em}
|
krauss@22065
|
540 |
|
krauss@22065
|
541 |
The first subgoal expresses the completeness of the patterns. It has
|
krauss@22065
|
542 |
the form of an elimination rule and states that every @{term x} of
|
krauss@23188
|
543 |
the function's input type must match at least one of the patterns\footnote{Completeness could
|
krauss@22065
|
544 |
be equivalently stated as a disjunction of existential statements:
|
krauss@22065
|
545 |
@{term "(\<exists>p. x = (T, p)) \<or> (\<exists>p. x = (p, T)) \<or> (\<exists>p. x = (p, F)) \<or>
|
krauss@27026
|
546 |
(\<exists>p. x = (F, p)) \<or> (x = (X, X))"}, and you can use the method @{text atomize_elim} to get that form instead.}. If the patterns just involve
|
krauss@23188
|
547 |
datatypes, we can solve it with the @{text "pat_completeness"}
|
krauss@23188
|
548 |
method:
|
krauss@22065
|
549 |
*}
|
krauss@22065
|
550 |
|
krauss@22065
|
551 |
apply pat_completeness
|
krauss@22065
|
552 |
|
krauss@22065
|
553 |
txt {*
|
krauss@22065
|
554 |
The remaining subgoals express \emph{pattern compatibility}. We do
|
krauss@23188
|
555 |
allow that an input value matches multiple patterns, but in this
|
krauss@22065
|
556 |
case, the result (i.e.~the right hand sides of the equations) must
|
krauss@22065
|
557 |
also be equal. For each pair of two patterns, there is one such
|
krauss@22065
|
558 |
subgoal. Usually this needs injectivity of the constructors, which
|
krauss@22065
|
559 |
is used automatically by @{text "auto"}.
|
krauss@22065
|
560 |
*}
|
krauss@22065
|
561 |
|
krauss@22065
|
562 |
by auto
|
krauss@22065
|
563 |
|
krauss@22065
|
564 |
|
krauss@22065
|
565 |
subsection {* Non-constructor patterns *}
|
krauss@21212
|
566 |
|
krauss@23188
|
567 |
text {*
|
krauss@23805
|
568 |
Most of Isabelle's basic types take the form of inductive datatypes,
|
krauss@23805
|
569 |
and usually pattern matching works on the constructors of such types.
|
krauss@23805
|
570 |
However, this need not be always the case, and the \cmd{function}
|
krauss@23805
|
571 |
command handles other kind of patterns, too.
|
krauss@21212
|
572 |
|
krauss@23805
|
573 |
One well-known instance of non-constructor patterns are
|
krauss@23188
|
574 |
so-called \emph{$n+k$-patterns}, which are a little controversial in
|
krauss@23188
|
575 |
the functional programming world. Here is the initial fibonacci
|
krauss@23188
|
576 |
example with $n+k$-patterns:
|
krauss@23188
|
577 |
*}
|
krauss@23188
|
578 |
|
krauss@23188
|
579 |
function fib2 :: "nat \<Rightarrow> nat"
|
krauss@23188
|
580 |
where
|
krauss@23188
|
581 |
"fib2 0 = 1"
|
krauss@23188
|
582 |
| "fib2 1 = 1"
|
krauss@23188
|
583 |
| "fib2 (n + 2) = fib2 n + fib2 (Suc n)"
|
krauss@23188
|
584 |
|
krauss@26749
|
585 |
(*<*)ML_val "goals_limit := 1"(*>*)
|
krauss@23188
|
586 |
txt {*
|
krauss@23805
|
587 |
This kind of matching is again justified by the proof of pattern
|
krauss@23805
|
588 |
completeness and compatibility.
|
krauss@23188
|
589 |
The proof obligation for pattern completeness states that every natural number is
|
krauss@23188
|
590 |
either @{term "0::nat"}, @{term "1::nat"} or @{term "n +
|
krauss@23188
|
591 |
(2::nat)"}:
|
krauss@23188
|
592 |
|
krauss@23188
|
593 |
@{subgoals[display,indent=0]}
|
krauss@23188
|
594 |
|
krauss@23188
|
595 |
This is an arithmetic triviality, but unfortunately the
|
krauss@23188
|
596 |
@{text arith} method cannot handle this specific form of an
|
krauss@23805
|
597 |
elimination rule. However, we can use the method @{text
|
krauss@26580
|
598 |
"atomize_elim"} to do an ad-hoc conversion to a disjunction of
|
krauss@23805
|
599 |
existentials, which can then be soved by the arithmetic decision procedure.
|
krauss@23805
|
600 |
Pattern compatibility and termination are automatic as usual.
|
krauss@23188
|
601 |
*}
|
krauss@26749
|
602 |
(*<*)ML_val "goals_limit := 10"(*>*)
|
krauss@26580
|
603 |
apply atomize_elim
|
krauss@23805
|
604 |
apply arith
|
krauss@23188
|
605 |
apply auto
|
krauss@23188
|
606 |
done
|
krauss@23188
|
607 |
termination by lexicographic_order
|
krauss@23188
|
608 |
text {*
|
krauss@23188
|
609 |
We can stretch the notion of pattern matching even more. The
|
krauss@23188
|
610 |
following function is not a sensible functional program, but a
|
krauss@23188
|
611 |
perfectly valid mathematical definition:
|
krauss@23188
|
612 |
*}
|
krauss@23188
|
613 |
|
krauss@23188
|
614 |
function ev :: "nat \<Rightarrow> bool"
|
krauss@23188
|
615 |
where
|
krauss@23188
|
616 |
"ev (2 * n) = True"
|
krauss@23188
|
617 |
| "ev (2 * n + 1) = False"
|
krauss@26580
|
618 |
apply atomize_elim
|
krauss@23805
|
619 |
by arith+
|
krauss@23188
|
620 |
termination by (relation "{}") simp
|
krauss@23188
|
621 |
|
krauss@23188
|
622 |
text {*
|
krauss@27026
|
623 |
This general notion of pattern matching gives you a certain freedom
|
krauss@27026
|
624 |
in writing down specifications. However, as always, such freedom should
|
krauss@23188
|
625 |
be used with care:
|
krauss@23188
|
626 |
|
krauss@23188
|
627 |
If we leave the area of constructor
|
krauss@23188
|
628 |
patterns, we have effectively departed from the world of functional
|
krauss@23188
|
629 |
programming. This means that it is no longer possible to use the
|
krauss@23188
|
630 |
code generator, and expect it to generate ML code for our
|
krauss@23188
|
631 |
definitions. Also, such a specification might not work very well together with
|
krauss@23188
|
632 |
simplification. Your mileage may vary.
|
krauss@23188
|
633 |
*}
|
krauss@23188
|
634 |
|
krauss@23188
|
635 |
|
krauss@23188
|
636 |
subsection {* Conditional equations *}
|
krauss@23188
|
637 |
|
krauss@23188
|
638 |
text {*
|
krauss@23188
|
639 |
The function package also supports conditional equations, which are
|
krauss@23188
|
640 |
similar to guards in a language like Haskell. Here is Euclid's
|
krauss@23188
|
641 |
algorithm written with conditional patterns\footnote{Note that the
|
krauss@23188
|
642 |
patterns are also overlapping in the base case}:
|
krauss@23188
|
643 |
*}
|
krauss@23188
|
644 |
|
krauss@23188
|
645 |
function gcd :: "nat \<Rightarrow> nat \<Rightarrow> nat"
|
krauss@23188
|
646 |
where
|
krauss@23188
|
647 |
"gcd x 0 = x"
|
krauss@23188
|
648 |
| "gcd 0 y = y"
|
krauss@23188
|
649 |
| "x < y \<Longrightarrow> gcd (Suc x) (Suc y) = gcd (Suc x) (y - x)"
|
krauss@23188
|
650 |
| "\<not> x < y \<Longrightarrow> gcd (Suc x) (Suc y) = gcd (x - y) (Suc y)"
|
krauss@26580
|
651 |
by (atomize_elim, auto, arith)
|
krauss@23188
|
652 |
termination by lexicographic_order
|
krauss@23188
|
653 |
|
krauss@23188
|
654 |
text {*
|
krauss@23188
|
655 |
By now, you can probably guess what the proof obligations for the
|
krauss@23188
|
656 |
pattern completeness and compatibility look like.
|
krauss@23188
|
657 |
|
krauss@23188
|
658 |
Again, functions with conditional patterns are not supported by the
|
krauss@23188
|
659 |
code generator.
|
krauss@23188
|
660 |
*}
|
krauss@23188
|
661 |
|
krauss@23188
|
662 |
|
krauss@23188
|
663 |
subsection {* Pattern matching on strings *}
|
krauss@23188
|
664 |
|
krauss@23188
|
665 |
text {*
|
krauss@23805
|
666 |
As strings (as lists of characters) are normal datatypes, pattern
|
krauss@23188
|
667 |
matching on them is possible, but somewhat problematic. Consider the
|
krauss@23188
|
668 |
following definition:
|
krauss@23188
|
669 |
|
krauss@23188
|
670 |
\end{isamarkuptext}
|
krauss@23188
|
671 |
\noindent\cmd{fun} @{text "check :: \"string \<Rightarrow> bool\""}\\%
|
krauss@23188
|
672 |
\cmd{where}\\%
|
krauss@23188
|
673 |
\hspace*{2ex}@{text "\"check (''good'') = True\""}\\%
|
krauss@23188
|
674 |
@{text "| \"check s = False\""}
|
krauss@23188
|
675 |
\begin{isamarkuptext}
|
krauss@23188
|
676 |
|
krauss@23805
|
677 |
\noindent An invocation of the above \cmd{fun} command does not
|
krauss@23188
|
678 |
terminate. What is the problem? Strings are lists of characters, and
|
krauss@23805
|
679 |
characters are a datatype with a lot of constructors. Splitting the
|
krauss@23188
|
680 |
catch-all pattern thus leads to an explosion of cases, which cannot
|
krauss@23188
|
681 |
be handled by Isabelle.
|
krauss@23188
|
682 |
|
krauss@23188
|
683 |
There are two things we can do here. Either we write an explicit
|
krauss@23188
|
684 |
@{text "if"} on the right hand side, or we can use conditional patterns:
|
krauss@23188
|
685 |
*}
|
krauss@23188
|
686 |
|
krauss@23188
|
687 |
function check :: "string \<Rightarrow> bool"
|
krauss@23188
|
688 |
where
|
krauss@23188
|
689 |
"check (''good'') = True"
|
krauss@23188
|
690 |
| "s \<noteq> ''good'' \<Longrightarrow> check s = False"
|
krauss@23188
|
691 |
by auto
|
krauss@23188
|
692 |
|
krauss@23188
|
693 |
|
krauss@22065
|
694 |
section {* Partiality *}
|
krauss@22065
|
695 |
|
krauss@22065
|
696 |
text {*
|
krauss@22065
|
697 |
In HOL, all functions are total. A function @{term "f"} applied to
|
krauss@23188
|
698 |
@{term "x"} always has the value @{term "f x"}, and there is no notion
|
krauss@22065
|
699 |
of undefinedness.
|
krauss@23188
|
700 |
This is why we have to do termination
|
krauss@23188
|
701 |
proofs when defining functions: The proof justifies that the
|
krauss@23188
|
702 |
function can be defined by wellfounded recursion.
|
krauss@22065
|
703 |
|
krauss@23188
|
704 |
However, the \cmd{function} package does support partiality to a
|
krauss@23188
|
705 |
certain extent. Let's look at the following function which looks
|
krauss@23188
|
706 |
for a zero of a given function f.
|
krauss@22065
|
707 |
*}
|
krauss@22065
|
708 |
|
krauss@23003
|
709 |
function (*<*)(domintros, tailrec)(*>*)findzero :: "(nat \<Rightarrow> nat) \<Rightarrow> nat \<Rightarrow> nat"
|
krauss@23003
|
710 |
where
|
krauss@23003
|
711 |
"findzero f n = (if f n = 0 then n else findzero f (Suc n))"
|
krauss@23003
|
712 |
by pat_completeness auto
|
krauss@23003
|
713 |
(*<*)declare findzero.simps[simp del](*>*)
|
krauss@22065
|
714 |
|
krauss@23003
|
715 |
text {*
|
krauss@23805
|
716 |
\noindent Clearly, any attempt of a termination proof must fail. And without
|
krauss@23003
|
717 |
that, we do not get the usual rules @{text "findzero.simp"} and
|
krauss@23003
|
718 |
@{text "findzero.induct"}. So what was the definition good for at all?
|
krauss@23003
|
719 |
*}
|
krauss@23003
|
720 |
|
krauss@23003
|
721 |
subsection {* Domain predicates *}
|
krauss@23003
|
722 |
|
krauss@23003
|
723 |
text {*
|
krauss@23003
|
724 |
The trick is that Isabelle has not only defined the function @{const findzero}, but also
|
krauss@23003
|
725 |
a predicate @{term "findzero_dom"} that characterizes the values where the function
|
krauss@23188
|
726 |
terminates: the \emph{domain} of the function. If we treat a
|
krauss@23188
|
727 |
partial function just as a total function with an additional domain
|
krauss@23188
|
728 |
predicate, we can derive simplification and
|
krauss@23188
|
729 |
induction rules as we do for total functions. They are guarded
|
krauss@23188
|
730 |
by domain conditions and are called @{text psimps} and @{text
|
krauss@23188
|
731 |
pinduct}:
|
krauss@23003
|
732 |
*}
|
krauss@23003
|
733 |
|
krauss@23805
|
734 |
text {*
|
krauss@23805
|
735 |
\noindent\begin{minipage}{0.79\textwidth}@{thm[display,margin=85] findzero.psimps}\end{minipage}
|
krauss@23805
|
736 |
\hfill(@{text "findzero.psimps"})
|
krauss@23805
|
737 |
\vspace{1em}
|
krauss@23003
|
738 |
|
krauss@23805
|
739 |
\noindent\begin{minipage}{0.79\textwidth}@{thm[display,margin=85] findzero.pinduct}\end{minipage}
|
krauss@23805
|
740 |
\hfill(@{text "findzero.pinduct"})
|
krauss@23003
|
741 |
*}
|
krauss@23003
|
742 |
|
krauss@23003
|
743 |
text {*
|
krauss@23188
|
744 |
Remember that all we
|
krauss@23188
|
745 |
are doing here is use some tricks to make a total function appear
|
krauss@23003
|
746 |
as if it was partial. We can still write the term @{term "findzero
|
krauss@23003
|
747 |
(\<lambda>x. 1) 0"} and like any other term of type @{typ nat} it is equal
|
krauss@23003
|
748 |
to some natural number, although we might not be able to find out
|
krauss@23188
|
749 |
which one. The function is \emph{underdefined}.
|
krauss@23003
|
750 |
|
krauss@23805
|
751 |
But it is defined enough to prove something interesting about it. We
|
krauss@23188
|
752 |
can prove that if @{term "findzero f n"}
|
krauss@23805
|
753 |
terminates, it indeed returns a zero of @{term f}:
|
krauss@23003
|
754 |
*}
|
krauss@23003
|
755 |
|
krauss@23003
|
756 |
lemma findzero_zero: "findzero_dom (f, n) \<Longrightarrow> f (findzero f n) = 0"
|
krauss@23003
|
757 |
|
krauss@23805
|
758 |
txt {* \noindent We apply induction as usual, but using the partial induction
|
krauss@23003
|
759 |
rule: *}
|
krauss@23003
|
760 |
|
krauss@23003
|
761 |
apply (induct f n rule: findzero.pinduct)
|
krauss@23003
|
762 |
|
krauss@23805
|
763 |
txt {* \noindent This gives the following subgoals:
|
krauss@23003
|
764 |
|
krauss@23003
|
765 |
@{subgoals[display,indent=0]}
|
krauss@23003
|
766 |
|
krauss@23805
|
767 |
\noindent The hypothesis in our lemma was used to satisfy the first premise in
|
krauss@23188
|
768 |
the induction rule. However, we also get @{term
|
krauss@23188
|
769 |
"findzero_dom (f, n)"} as a local assumption in the induction step. This
|
krauss@23003
|
770 |
allows to unfold @{term "findzero f n"} using the @{text psimps}
|
krauss@23188
|
771 |
rule, and the rest is trivial. Since the @{text psimps} rules carry the
|
krauss@23003
|
772 |
@{text "[simp]"} attribute by default, we just need a single step:
|
krauss@23003
|
773 |
*}
|
krauss@23003
|
774 |
apply simp
|
krauss@23003
|
775 |
done
|
krauss@23003
|
776 |
|
krauss@23003
|
777 |
text {*
|
krauss@23003
|
778 |
Proofs about partial functions are often not harder than for total
|
krauss@23003
|
779 |
functions. Fig.~\ref{findzero_isar} shows a slightly more
|
krauss@23003
|
780 |
complicated proof written in Isar. It is verbose enough to show how
|
krauss@23003
|
781 |
partiality comes into play: From the partial induction, we get an
|
krauss@23003
|
782 |
additional domain condition hypothesis. Observe how this condition
|
krauss@23003
|
783 |
is applied when calls to @{term findzero} are unfolded.
|
krauss@23003
|
784 |
*}
|
krauss@23003
|
785 |
|
krauss@23003
|
786 |
text_raw {*
|
krauss@23003
|
787 |
\begin{figure}
|
krauss@23188
|
788 |
\hrule\vspace{6pt}
|
krauss@23003
|
789 |
\begin{minipage}{0.8\textwidth}
|
krauss@23003
|
790 |
\isabellestyle{it}
|
krauss@23003
|
791 |
\isastyle\isamarkuptrue
|
krauss@23003
|
792 |
*}
|
krauss@23003
|
793 |
lemma "\<lbrakk>findzero_dom (f, n); x \<in> {n ..< findzero f n}\<rbrakk> \<Longrightarrow> f x \<noteq> 0"
|
krauss@23003
|
794 |
proof (induct rule: findzero.pinduct)
|
krauss@23003
|
795 |
fix f n assume dom: "findzero_dom (f, n)"
|
krauss@23188
|
796 |
and IH: "\<lbrakk>f n \<noteq> 0; x \<in> {Suc n ..< findzero f (Suc n)}\<rbrakk> \<Longrightarrow> f x \<noteq> 0"
|
krauss@23188
|
797 |
and x_range: "x \<in> {n ..< findzero f n}"
|
krauss@23003
|
798 |
have "f n \<noteq> 0"
|
krauss@23003
|
799 |
proof
|
krauss@23003
|
800 |
assume "f n = 0"
|
krauss@23003
|
801 |
with dom have "findzero f n = n" by simp
|
krauss@23003
|
802 |
with x_range show False by auto
|
krauss@23003
|
803 |
qed
|
krauss@23003
|
804 |
|
krauss@23003
|
805 |
from x_range have "x = n \<or> x \<in> {Suc n ..< findzero f n}" by auto
|
krauss@23003
|
806 |
thus "f x \<noteq> 0"
|
krauss@23003
|
807 |
proof
|
krauss@23003
|
808 |
assume "x = n"
|
krauss@23003
|
809 |
with `f n \<noteq> 0` show ?thesis by simp
|
krauss@23003
|
810 |
next
|
krauss@23188
|
811 |
assume "x \<in> {Suc n ..< findzero f n}"
|
krauss@23805
|
812 |
with dom and `f n \<noteq> 0` have "x \<in> {Suc n ..< findzero f (Suc n)}" by simp
|
krauss@23003
|
813 |
with IH and `f n \<noteq> 0`
|
krauss@23003
|
814 |
show ?thesis by simp
|
krauss@23003
|
815 |
qed
|
krauss@23003
|
816 |
qed
|
krauss@23003
|
817 |
text_raw {*
|
krauss@23003
|
818 |
\isamarkupfalse\isabellestyle{tt}
|
krauss@23188
|
819 |
\end{minipage}\vspace{6pt}\hrule
|
krauss@23003
|
820 |
\caption{A proof about a partial function}\label{findzero_isar}
|
krauss@23003
|
821 |
\end{figure}
|
krauss@23003
|
822 |
*}
|
krauss@23003
|
823 |
|
krauss@23003
|
824 |
subsection {* Partial termination proofs *}
|
krauss@23003
|
825 |
|
krauss@23003
|
826 |
text {*
|
krauss@23003
|
827 |
Now that we have proved some interesting properties about our
|
krauss@23003
|
828 |
function, we should turn to the domain predicate and see if it is
|
krauss@23003
|
829 |
actually true for some values. Otherwise we would have just proved
|
krauss@23003
|
830 |
lemmas with @{term False} as a premise.
|
krauss@23003
|
831 |
|
krauss@23003
|
832 |
Essentially, we need some introduction rules for @{text
|
krauss@23003
|
833 |
findzero_dom}. The function package can prove such domain
|
krauss@23003
|
834 |
introduction rules automatically. But since they are not used very
|
krauss@23188
|
835 |
often (they are almost never needed if the function is total), this
|
krauss@23188
|
836 |
functionality is disabled by default for efficiency reasons. So we have to go
|
krauss@23003
|
837 |
back and ask for them explicitly by passing the @{text
|
krauss@23003
|
838 |
"(domintros)"} option to the function package:
|
krauss@23003
|
839 |
|
krauss@23188
|
840 |
\vspace{1ex}
|
krauss@23003
|
841 |
\noindent\cmd{function} @{text "(domintros) findzero :: \"(nat \<Rightarrow> nat) \<Rightarrow> nat \<Rightarrow> nat\""}\\%
|
krauss@23003
|
842 |
\cmd{where}\isanewline%
|
krauss@23003
|
843 |
\ \ \ldots\\
|
krauss@23003
|
844 |
|
krauss@23188
|
845 |
\noindent Now the package has proved an introduction rule for @{text findzero_dom}:
|
krauss@23003
|
846 |
*}
|
krauss@23003
|
847 |
|
krauss@23003
|
848 |
thm findzero.domintros
|
krauss@23003
|
849 |
|
krauss@23003
|
850 |
text {*
|
krauss@23003
|
851 |
@{thm[display] findzero.domintros}
|
krauss@23003
|
852 |
|
krauss@23003
|
853 |
Domain introduction rules allow to show that a given value lies in the
|
krauss@23003
|
854 |
domain of a function, if the arguments of all recursive calls
|
krauss@23003
|
855 |
are in the domain as well. They allow to do a \qt{single step} in a
|
krauss@23003
|
856 |
termination proof. Usually, you want to combine them with a suitable
|
krauss@23003
|
857 |
induction principle.
|
krauss@23003
|
858 |
|
krauss@23003
|
859 |
Since our function increases its argument at recursive calls, we
|
krauss@23003
|
860 |
need an induction principle which works \qt{backwards}. We will use
|
krauss@23003
|
861 |
@{text inc_induct}, which allows to do induction from a fixed number
|
krauss@23003
|
862 |
\qt{downwards}:
|
krauss@23003
|
863 |
|
krauss@23188
|
864 |
\begin{center}@{thm inc_induct}\hfill(@{text "inc_induct"})\end{center}
|
krauss@23003
|
865 |
|
krauss@23188
|
866 |
Figure \ref{findzero_term} gives a detailed Isar proof of the fact
|
krauss@23003
|
867 |
that @{text findzero} terminates if there is a zero which is greater
|
krauss@23003
|
868 |
or equal to @{term n}. First we derive two useful rules which will
|
krauss@23003
|
869 |
solve the base case and the step case of the induction. The
|
krauss@23805
|
870 |
induction is then straightforward, except for the unusual induction
|
krauss@23003
|
871 |
principle.
|
krauss@23003
|
872 |
|
krauss@23003
|
873 |
*}
|
krauss@23003
|
874 |
|
krauss@23003
|
875 |
text_raw {*
|
krauss@23003
|
876 |
\begin{figure}
|
krauss@23188
|
877 |
\hrule\vspace{6pt}
|
krauss@23003
|
878 |
\begin{minipage}{0.8\textwidth}
|
krauss@23003
|
879 |
\isabellestyle{it}
|
krauss@23003
|
880 |
\isastyle\isamarkuptrue
|
krauss@23003
|
881 |
*}
|
krauss@23003
|
882 |
lemma findzero_termination:
|
krauss@23188
|
883 |
assumes "x \<ge> n" and "f x = 0"
|
krauss@23003
|
884 |
shows "findzero_dom (f, n)"
|
krauss@23003
|
885 |
proof -
|
krauss@23003
|
886 |
have base: "findzero_dom (f, x)"
|
krauss@23003
|
887 |
by (rule findzero.domintros) (simp add:`f x = 0`)
|
krauss@23003
|
888 |
|
krauss@23003
|
889 |
have step: "\<And>i. findzero_dom (f, Suc i)
|
krauss@23003
|
890 |
\<Longrightarrow> findzero_dom (f, i)"
|
krauss@23003
|
891 |
by (rule findzero.domintros) simp
|
krauss@23003
|
892 |
|
krauss@23188
|
893 |
from `x \<ge> n` show ?thesis
|
krauss@23003
|
894 |
proof (induct rule:inc_induct)
|
krauss@23188
|
895 |
show "findzero_dom (f, x)" by (rule base)
|
krauss@23003
|
896 |
next
|
krauss@23003
|
897 |
fix i assume "findzero_dom (f, Suc i)"
|
krauss@23188
|
898 |
thus "findzero_dom (f, i)" by (rule step)
|
krauss@23003
|
899 |
qed
|
krauss@23003
|
900 |
qed
|
krauss@23003
|
901 |
text_raw {*
|
krauss@23003
|
902 |
\isamarkupfalse\isabellestyle{tt}
|
krauss@23188
|
903 |
\end{minipage}\vspace{6pt}\hrule
|
krauss@23003
|
904 |
\caption{Termination proof for @{text findzero}}\label{findzero_term}
|
krauss@23003
|
905 |
\end{figure}
|
krauss@23003
|
906 |
*}
|
krauss@23003
|
907 |
|
krauss@23003
|
908 |
text {*
|
krauss@23003
|
909 |
Again, the proof given in Fig.~\ref{findzero_term} has a lot of
|
krauss@23003
|
910 |
detail in order to explain the principles. Using more automation, we
|
krauss@23003
|
911 |
can also have a short proof:
|
krauss@23003
|
912 |
*}
|
krauss@23003
|
913 |
|
krauss@23003
|
914 |
lemma findzero_termination_short:
|
krauss@23003
|
915 |
assumes zero: "x >= n"
|
krauss@23003
|
916 |
assumes [simp]: "f x = 0"
|
krauss@23003
|
917 |
shows "findzero_dom (f, n)"
|
krauss@23805
|
918 |
using zero
|
krauss@23805
|
919 |
by (induct rule:inc_induct) (auto intro: findzero.domintros)
|
krauss@23003
|
920 |
|
krauss@23003
|
921 |
text {*
|
krauss@23188
|
922 |
\noindent It is simple to combine the partial correctness result with the
|
krauss@23003
|
923 |
termination lemma:
|
krauss@23003
|
924 |
*}
|
krauss@23003
|
925 |
|
krauss@23003
|
926 |
lemma findzero_total_correctness:
|
krauss@23003
|
927 |
"f x = 0 \<Longrightarrow> f (findzero f 0) = 0"
|
krauss@23003
|
928 |
by (blast intro: findzero_zero findzero_termination)
|
krauss@23003
|
929 |
|
krauss@23003
|
930 |
subsection {* Definition of the domain predicate *}
|
krauss@23003
|
931 |
|
krauss@23003
|
932 |
text {*
|
krauss@23003
|
933 |
Sometimes it is useful to know what the definition of the domain
|
krauss@23805
|
934 |
predicate looks like. Actually, @{text findzero_dom} is just an
|
krauss@23003
|
935 |
abbreviation:
|
krauss@23003
|
936 |
|
krauss@23003
|
937 |
@{abbrev[display] findzero_dom}
|
krauss@23003
|
938 |
|
krauss@23188
|
939 |
The domain predicate is the \emph{accessible part} of a relation @{const
|
krauss@23003
|
940 |
findzero_rel}, which was also created internally by the function
|
krauss@23003
|
941 |
package. @{const findzero_rel} is just a normal
|
krauss@23188
|
942 |
inductive predicate, so we can inspect its definition by
|
krauss@23003
|
943 |
looking at the introduction rules @{text findzero_rel.intros}.
|
krauss@23003
|
944 |
In our case there is just a single rule:
|
krauss@23003
|
945 |
|
krauss@23003
|
946 |
@{thm[display] findzero_rel.intros}
|
krauss@23003
|
947 |
|
krauss@23188
|
948 |
The predicate @{const findzero_rel}
|
krauss@23003
|
949 |
describes the \emph{recursion relation} of the function
|
krauss@23003
|
950 |
definition. The recursion relation is a binary relation on
|
krauss@23003
|
951 |
the arguments of the function that relates each argument to its
|
krauss@23003
|
952 |
recursive calls. In general, there is one introduction rule for each
|
krauss@23003
|
953 |
recursive call.
|
krauss@23003
|
954 |
|
krauss@23805
|
955 |
The predicate @{term "accp findzero_rel"} is the accessible part of
|
krauss@23003
|
956 |
that relation. An argument belongs to the accessible part, if it can
|
krauss@23188
|
957 |
be reached in a finite number of steps (cf.~its definition in @{text
|
krauss@23188
|
958 |
"Accessible_Part.thy"}).
|
krauss@23003
|
959 |
|
krauss@23003
|
960 |
Since the domain predicate is just an abbreviation, you can use
|
krauss@23805
|
961 |
lemmas for @{const accp} and @{const findzero_rel} directly. Some
|
krauss@23805
|
962 |
lemmas which are occasionally useful are @{text accpI}, @{text
|
krauss@23805
|
963 |
accp_downward}, and of course the introduction and elimination rules
|
krauss@23003
|
964 |
for the recursion relation @{text "findzero.intros"} and @{text "findzero.cases"}.
|
krauss@23003
|
965 |
*}
|
krauss@23003
|
966 |
|
krauss@23003
|
967 |
(*lemma findzero_nicer_domintros:
|
krauss@23003
|
968 |
"f x = 0 \<Longrightarrow> findzero_dom (f, x)"
|
krauss@23003
|
969 |
"findzero_dom (f, Suc x) \<Longrightarrow> findzero_dom (f, x)"
|
krauss@23805
|
970 |
by (rule accpI, erule findzero_rel.cases, auto)+
|
krauss@23003
|
971 |
*)
|
krauss@23003
|
972 |
|
krauss@23003
|
973 |
subsection {* A Useful Special Case: Tail recursion *}
|
krauss@23003
|
974 |
|
krauss@23003
|
975 |
text {*
|
krauss@23003
|
976 |
The domain predicate is our trick that allows us to model partiality
|
krauss@23003
|
977 |
in a world of total functions. The downside of this is that we have
|
krauss@23003
|
978 |
to carry it around all the time. The termination proof above allowed
|
krauss@23003
|
979 |
us to replace the abstract @{term "findzero_dom (f, n)"} by the more
|
krauss@23188
|
980 |
concrete @{term "(x \<ge> n \<and> f x = (0::nat))"}, but the condition is still
|
krauss@23188
|
981 |
there and can only be discharged for special cases.
|
krauss@23188
|
982 |
In particular, the domain predicate guards the unfolding of our
|
krauss@23003
|
983 |
function, since it is there as a condition in the @{text psimp}
|
krauss@23003
|
984 |
rules.
|
krauss@23003
|
985 |
|
krauss@23003
|
986 |
Now there is an important special case: We can actually get rid
|
krauss@23003
|
987 |
of the condition in the simplification rules, \emph{if the function
|
krauss@23003
|
988 |
is tail-recursive}. The reason is that for all tail-recursive
|
krauss@23003
|
989 |
equations there is a total function satisfying them, even if they
|
krauss@23003
|
990 |
are non-terminating.
|
krauss@23003
|
991 |
|
krauss@23188
|
992 |
% A function is tail recursive, if each call to the function is either
|
krauss@23188
|
993 |
% equal
|
krauss@23188
|
994 |
%
|
krauss@23188
|
995 |
% So the outer form of the
|
krauss@23188
|
996 |
%
|
krauss@23188
|
997 |
%if it can be written in the following
|
krauss@23188
|
998 |
% form:
|
krauss@23188
|
999 |
% {term[display] "f x = (if COND x then BASE x else f (LOOP x))"}
|
krauss@23188
|
1000 |
|
krauss@23188
|
1001 |
|
krauss@23003
|
1002 |
The function package internally does the right construction and can
|
krauss@23003
|
1003 |
derive the unconditional simp rules, if we ask it to do so. Luckily,
|
krauss@23003
|
1004 |
our @{const "findzero"} function is tail-recursive, so we can just go
|
krauss@23003
|
1005 |
back and add another option to the \cmd{function} command:
|
krauss@23003
|
1006 |
|
krauss@23188
|
1007 |
\vspace{1ex}
|
krauss@23003
|
1008 |
\noindent\cmd{function} @{text "(domintros, tailrec) findzero :: \"(nat \<Rightarrow> nat) \<Rightarrow> nat \<Rightarrow> nat\""}\\%
|
krauss@23003
|
1009 |
\cmd{where}\isanewline%
|
krauss@23003
|
1010 |
\ \ \ldots\\%
|
krauss@22065
|
1011 |
|
krauss@22065
|
1012 |
|
krauss@23188
|
1013 |
\noindent Now, we actually get unconditional simplification rules, even
|
krauss@23003
|
1014 |
though the function is partial:
|
krauss@23003
|
1015 |
*}
|
krauss@23003
|
1016 |
|
krauss@23003
|
1017 |
thm findzero.simps
|
krauss@23003
|
1018 |
|
krauss@23003
|
1019 |
text {*
|
krauss@23003
|
1020 |
@{thm[display] findzero.simps}
|
krauss@23003
|
1021 |
|
krauss@23188
|
1022 |
\noindent Of course these would make the simplifier loop, so we better remove
|
krauss@23003
|
1023 |
them from the simpset:
|
krauss@23003
|
1024 |
*}
|
krauss@23003
|
1025 |
|
krauss@23003
|
1026 |
declare findzero.simps[simp del]
|
krauss@23003
|
1027 |
|
krauss@23188
|
1028 |
text {*
|
krauss@23188
|
1029 |
Getting rid of the domain conditions in the simplification rules is
|
krauss@23188
|
1030 |
not only useful because it simplifies proofs. It is also required in
|
krauss@23188
|
1031 |
order to use Isabelle's code generator to generate ML code
|
krauss@23188
|
1032 |
from a function definition.
|
krauss@23188
|
1033 |
Since the code generator only works with equations, it cannot be
|
krauss@23188
|
1034 |
used with @{text "psimp"} rules. Thus, in order to generate code for
|
krauss@23188
|
1035 |
partial functions, they must be defined as a tail recursion.
|
krauss@23188
|
1036 |
Luckily, many functions have a relatively natural tail recursive
|
krauss@23188
|
1037 |
definition.
|
krauss@23188
|
1038 |
*}
|
krauss@23003
|
1039 |
|
krauss@22065
|
1040 |
section {* Nested recursion *}
|
krauss@22065
|
1041 |
|
krauss@22065
|
1042 |
text {*
|
krauss@23003
|
1043 |
Recursive calls which are nested in one another frequently cause
|
krauss@23003
|
1044 |
complications, since their termination proof can depend on a partial
|
krauss@23003
|
1045 |
correctness property of the function itself.
|
krauss@23003
|
1046 |
|
krauss@23003
|
1047 |
As a small example, we define the \qt{nested zero} function:
|
krauss@23003
|
1048 |
*}
|
krauss@23003
|
1049 |
|
krauss@23003
|
1050 |
function nz :: "nat \<Rightarrow> nat"
|
krauss@23003
|
1051 |
where
|
krauss@23003
|
1052 |
"nz 0 = 0"
|
krauss@23003
|
1053 |
| "nz (Suc n) = nz (nz n)"
|
krauss@23003
|
1054 |
by pat_completeness auto
|
krauss@23003
|
1055 |
|
krauss@23003
|
1056 |
text {*
|
krauss@23003
|
1057 |
If we attempt to prove termination using the identity measure on
|
krauss@23003
|
1058 |
naturals, this fails:
|
krauss@23003
|
1059 |
*}
|
krauss@23003
|
1060 |
|
krauss@23003
|
1061 |
termination
|
krauss@23003
|
1062 |
apply (relation "measure (\<lambda>n. n)")
|
krauss@23003
|
1063 |
apply auto
|
krauss@23003
|
1064 |
|
krauss@23003
|
1065 |
txt {*
|
krauss@23003
|
1066 |
We get stuck with the subgoal
|
krauss@23003
|
1067 |
|
krauss@23003
|
1068 |
@{subgoals[display]}
|
krauss@23003
|
1069 |
|
krauss@23003
|
1070 |
Of course this statement is true, since we know that @{const nz} is
|
krauss@23003
|
1071 |
the zero function. And in fact we have no problem proving this
|
krauss@23003
|
1072 |
property by induction.
|
krauss@23003
|
1073 |
*}
|
krauss@23805
|
1074 |
(*<*)oops(*>*)
|
krauss@23003
|
1075 |
lemma nz_is_zero: "nz_dom n \<Longrightarrow> nz n = 0"
|
krauss@23003
|
1076 |
by (induct rule:nz.pinduct) auto
|
krauss@23003
|
1077 |
|
krauss@23003
|
1078 |
text {*
|
krauss@23003
|
1079 |
We formulate this as a partial correctness lemma with the condition
|
krauss@23003
|
1080 |
@{term "nz_dom n"}. This allows us to prove it with the @{text
|
krauss@23003
|
1081 |
pinduct} rule before we have proved termination. With this lemma,
|
krauss@23003
|
1082 |
the termination proof works as expected:
|
krauss@23003
|
1083 |
*}
|
krauss@23003
|
1084 |
|
krauss@23003
|
1085 |
termination
|
krauss@23003
|
1086 |
by (relation "measure (\<lambda>n. n)") (auto simp: nz_is_zero)
|
krauss@23003
|
1087 |
|
krauss@23003
|
1088 |
text {*
|
krauss@23003
|
1089 |
As a general strategy, one should prove the statements needed for
|
krauss@23003
|
1090 |
termination as a partial property first. Then they can be used to do
|
krauss@23003
|
1091 |
the termination proof. This also works for less trivial
|
krauss@23188
|
1092 |
examples. Figure \ref{f91} defines the 91-function, a well-known
|
krauss@23188
|
1093 |
challenge problem due to John McCarthy, and proves its termination.
|
krauss@23003
|
1094 |
*}
|
krauss@23003
|
1095 |
|
krauss@23003
|
1096 |
text_raw {*
|
krauss@23003
|
1097 |
\begin{figure}
|
krauss@23188
|
1098 |
\hrule\vspace{6pt}
|
krauss@23003
|
1099 |
\begin{minipage}{0.8\textwidth}
|
krauss@23003
|
1100 |
\isabellestyle{it}
|
krauss@23003
|
1101 |
\isastyle\isamarkuptrue
|
krauss@23003
|
1102 |
*}
|
krauss@23003
|
1103 |
|
krauss@23188
|
1104 |
function f91 :: "nat \<Rightarrow> nat"
|
krauss@23003
|
1105 |
where
|
krauss@23003
|
1106 |
"f91 n = (if 100 < n then n - 10 else f91 (f91 (n + 11)))"
|
krauss@23003
|
1107 |
by pat_completeness auto
|
krauss@23003
|
1108 |
|
krauss@23003
|
1109 |
lemma f91_estimate:
|
krauss@23003
|
1110 |
assumes trm: "f91_dom n"
|
krauss@23003
|
1111 |
shows "n < f91 n + 11"
|
krauss@23003
|
1112 |
using trm by induct auto
|
krauss@23003
|
1113 |
|
krauss@23003
|
1114 |
termination
|
krauss@23003
|
1115 |
proof
|
krauss@23003
|
1116 |
let ?R = "measure (\<lambda>x. 101 - x)"
|
krauss@23003
|
1117 |
show "wf ?R" ..
|
krauss@23003
|
1118 |
|
krauss@23003
|
1119 |
fix n :: nat assume "\<not> 100 < n" -- "Assumptions for both calls"
|
krauss@23003
|
1120 |
|
krauss@23003
|
1121 |
thus "(n + 11, n) \<in> ?R" by simp -- "Inner call"
|
krauss@23003
|
1122 |
|
krauss@23003
|
1123 |
assume inner_trm: "f91_dom (n + 11)" -- "Outer call"
|
krauss@23003
|
1124 |
with f91_estimate have "n + 11 < f91 (n + 11) + 11" .
|
krauss@23805
|
1125 |
with `\<not> 100 < n` show "(f91 (n + 11), n) \<in> ?R" by simp
|
krauss@23003
|
1126 |
qed
|
krauss@23003
|
1127 |
|
krauss@23003
|
1128 |
text_raw {*
|
krauss@23003
|
1129 |
\isamarkupfalse\isabellestyle{tt}
|
krauss@23188
|
1130 |
\end{minipage}
|
krauss@23188
|
1131 |
\vspace{6pt}\hrule
|
krauss@23003
|
1132 |
\caption{McCarthy's 91-function}\label{f91}
|
krauss@23003
|
1133 |
\end{figure}
|
krauss@23003
|
1134 |
*}
|
krauss@23003
|
1135 |
|
krauss@23003
|
1136 |
|
krauss@23003
|
1137 |
section {* Higher-Order Recursion *}
|
krauss@23003
|
1138 |
|
krauss@23003
|
1139 |
text {*
|
krauss@23003
|
1140 |
Higher-order recursion occurs when recursive calls
|
krauss@23003
|
1141 |
are passed as arguments to higher-order combinators such as @{term
|
krauss@23003
|
1142 |
map}, @{term filter} etc.
|
krauss@23805
|
1143 |
As an example, imagine a datatype of n-ary trees:
|
krauss@23003
|
1144 |
*}
|
krauss@23003
|
1145 |
|
krauss@23003
|
1146 |
datatype 'a tree =
|
krauss@23003
|
1147 |
Leaf 'a
|
krauss@23003
|
1148 |
| Branch "'a tree list"
|
krauss@23003
|
1149 |
|
krauss@23003
|
1150 |
|
krauss@25278
|
1151 |
text {* \noindent We can define a function which swaps the left and right subtrees recursively, using the
|
krauss@25278
|
1152 |
list functions @{const rev} and @{const map}: *}
|
krauss@25688
|
1153 |
|
krauss@27026
|
1154 |
fun mirror :: "'a tree \<Rightarrow> 'a tree"
|
krauss@23003
|
1155 |
where
|
krauss@25278
|
1156 |
"mirror (Leaf n) = Leaf n"
|
krauss@25278
|
1157 |
| "mirror (Branch l) = Branch (rev (map mirror l))"
|
krauss@23003
|
1158 |
|
krauss@23003
|
1159 |
text {*
|
krauss@27026
|
1160 |
Although the definition is accepted without problems, let us look at the termination proof:
|
krauss@23003
|
1161 |
*}
|
krauss@23003
|
1162 |
|
krauss@23003
|
1163 |
termination proof
|
krauss@23003
|
1164 |
txt {*
|
krauss@23003
|
1165 |
|
krauss@23003
|
1166 |
As usual, we have to give a wellfounded relation, such that the
|
krauss@23003
|
1167 |
arguments of the recursive calls get smaller. But what exactly are
|
krauss@27026
|
1168 |
the arguments of the recursive calls when mirror is given as an
|
krauss@27026
|
1169 |
argument to map? Isabelle gives us the
|
krauss@23003
|
1170 |
subgoals
|
krauss@23003
|
1171 |
|
krauss@23003
|
1172 |
@{subgoals[display,indent=0]}
|
krauss@23003
|
1173 |
|
krauss@27026
|
1174 |
So the system seems to know that @{const map} only
|
krauss@25278
|
1175 |
applies the recursive call @{term "mirror"} to elements
|
krauss@27026
|
1176 |
of @{term "l"}, which is essential for the termination proof.
|
krauss@23003
|
1177 |
|
krauss@27026
|
1178 |
This knowledge about map is encoded in so-called congruence rules,
|
krauss@23003
|
1179 |
which are special theorems known to the \cmd{function} command. The
|
krauss@23003
|
1180 |
rule for map is
|
krauss@22065
|
1181 |
|
krauss@23003
|
1182 |
@{thm[display] map_cong}
|
krauss@22065
|
1183 |
|
krauss@23003
|
1184 |
You can read this in the following way: Two applications of @{const
|
krauss@23003
|
1185 |
map} are equal, if the list arguments are equal and the functions
|
krauss@23003
|
1186 |
coincide on the elements of the list. This means that for the value
|
krauss@23003
|
1187 |
@{term "map f l"} we only have to know how @{term f} behaves on
|
krauss@27026
|
1188 |
the elements of @{term l}.
|
krauss@23003
|
1189 |
|
krauss@23003
|
1190 |
Usually, one such congruence rule is
|
krauss@23003
|
1191 |
needed for each higher-order construct that is used when defining
|
krauss@23003
|
1192 |
new functions. In fact, even basic functions like @{const
|
krauss@23805
|
1193 |
If} and @{const Let} are handled by this mechanism. The congruence
|
krauss@23003
|
1194 |
rule for @{const If} states that the @{text then} branch is only
|
krauss@23003
|
1195 |
relevant if the condition is true, and the @{text else} branch only if it
|
krauss@23003
|
1196 |
is false:
|
krauss@23003
|
1197 |
|
krauss@23003
|
1198 |
@{thm[display] if_cong}
|
krauss@23003
|
1199 |
|
krauss@23003
|
1200 |
Congruence rules can be added to the
|
krauss@23003
|
1201 |
function package by giving them the @{term fundef_cong} attribute.
|
krauss@23003
|
1202 |
|
krauss@23805
|
1203 |
The constructs that are predefined in Isabelle, usually
|
krauss@23805
|
1204 |
come with the respective congruence rules.
|
krauss@27026
|
1205 |
But if you define your own higher-order functions, you may have to
|
krauss@27026
|
1206 |
state and prove the required congruence rules yourself, if you want to use your
|
krauss@23805
|
1207 |
functions in recursive definitions.
|
krauss@23805
|
1208 |
*}
|
krauss@27026
|
1209 |
(*<*)oops(*>*)
|
krauss@23805
|
1210 |
|
krauss@23805
|
1211 |
subsection {* Congruence Rules and Evaluation Order *}
|
krauss@23805
|
1212 |
|
krauss@23805
|
1213 |
text {*
|
krauss@23805
|
1214 |
Higher order logic differs from functional programming languages in
|
krauss@23805
|
1215 |
that it has no built-in notion of evaluation order. A program is
|
krauss@23805
|
1216 |
just a set of equations, and it is not specified how they must be
|
krauss@23805
|
1217 |
evaluated.
|
krauss@23805
|
1218 |
|
krauss@23805
|
1219 |
However for the purpose of function definition, we must talk about
|
krauss@23805
|
1220 |
evaluation order implicitly, when we reason about termination.
|
krauss@23805
|
1221 |
Congruence rules express that a certain evaluation order is
|
krauss@23805
|
1222 |
consistent with the logical definition.
|
krauss@23805
|
1223 |
|
krauss@23805
|
1224 |
Consider the following function.
|
krauss@23805
|
1225 |
*}
|
krauss@23805
|
1226 |
|
krauss@23805
|
1227 |
function f :: "nat \<Rightarrow> bool"
|
krauss@23805
|
1228 |
where
|
krauss@23805
|
1229 |
"f n = (n = 0 \<or> f (n - 1))"
|
krauss@23805
|
1230 |
(*<*)by pat_completeness auto(*>*)
|
krauss@23805
|
1231 |
|
krauss@23805
|
1232 |
text {*
|
krauss@27026
|
1233 |
For this definition, the termination proof fails. The default configuration
|
krauss@23805
|
1234 |
specifies no congruence rule for disjunction. We have to add a
|
krauss@23805
|
1235 |
congruence rule that specifies left-to-right evaluation order:
|
krauss@23805
|
1236 |
|
krauss@23805
|
1237 |
\vspace{1ex}
|
krauss@23805
|
1238 |
\noindent @{thm disj_cong}\hfill(@{text "disj_cong"})
|
krauss@23805
|
1239 |
\vspace{1ex}
|
krauss@23805
|
1240 |
|
krauss@23805
|
1241 |
Now the definition works without problems. Note how the termination
|
krauss@23805
|
1242 |
proof depends on the extra condition that we get from the congruence
|
krauss@23805
|
1243 |
rule.
|
krauss@23805
|
1244 |
|
krauss@23805
|
1245 |
However, as evaluation is not a hard-wired concept, we
|
krauss@23805
|
1246 |
could just turn everything around by declaring a different
|
krauss@23805
|
1247 |
congruence rule. Then we can make the reverse definition:
|
krauss@23805
|
1248 |
*}
|
krauss@23805
|
1249 |
|
krauss@23805
|
1250 |
lemma disj_cong2[fundef_cong]:
|
krauss@23805
|
1251 |
"(\<not> Q' \<Longrightarrow> P = P') \<Longrightarrow> (Q = Q') \<Longrightarrow> (P \<or> Q) = (P' \<or> Q')"
|
krauss@23805
|
1252 |
by blast
|
krauss@23805
|
1253 |
|
krauss@23805
|
1254 |
fun f' :: "nat \<Rightarrow> bool"
|
krauss@23805
|
1255 |
where
|
krauss@23805
|
1256 |
"f' n = (f' (n - 1) \<or> n = 0)"
|
krauss@23805
|
1257 |
|
krauss@23805
|
1258 |
text {*
|
krauss@23805
|
1259 |
\noindent These examples show that, in general, there is no \qt{best} set of
|
krauss@23805
|
1260 |
congruence rules.
|
krauss@23805
|
1261 |
|
krauss@23805
|
1262 |
However, such tweaking should rarely be necessary in
|
krauss@23805
|
1263 |
practice, as most of the time, the default set of congruence rules
|
krauss@23805
|
1264 |
works well.
|
krauss@23805
|
1265 |
*}
|
krauss@23805
|
1266 |
|
krauss@23003
|
1267 |
end
|