14 In case the function has more than one argument |
15 In case the function has more than one argument |
15 \begin{quote} |
16 \begin{quote} |
16 \emph{Do induction on argument number $i$ if the function is defined by |
17 \emph{Do induction on argument number $i$ if the function is defined by |
17 recursion in argument number $i$.} |
18 recursion in argument number $i$.} |
18 \end{quote} |
19 \end{quote} |
19 When we look at the proof of @{term[source]"(xs @ ys) @ zs = xs @ (ys @ zs)"} |
20 When we look at the proof of @{text"(xs@ys) @ zs = xs @ (ys@zs)"} |
20 in \S\ref{sec:intro-proof} we find (a) @{text"@"} is recursive in |
21 in \S\ref{sec:intro-proof} we find |
21 the first argument, (b) @{term xs} occurs only as the first argument of |
22 \begin{itemize} |
22 @{text"@"}, and (c) both @{term ys} and @{term zs} occur at least once as |
23 \item @{text"@"} is recursive in |
23 the second argument of @{text"@"}. Hence it is natural to perform induction |
24 the first argument |
24 on @{term xs}. |
25 \item @{term xs} occurs only as the first argument of |
|
26 @{text"@"} |
|
27 \item both @{term ys} and @{term zs} occur at least once as |
|
28 the second argument of @{text"@"} |
|
29 \end{itemize} |
|
30 Hence it is natural to perform induction on~@{term xs}. |
25 |
31 |
26 The key heuristic, and the main point of this section, is to |
32 The key heuristic, and the main point of this section, is to |
27 generalize the goal before induction. The reason is simple: if the goal is |
33 \emph{generalize the goal before induction}. |
|
34 The reason is simple: if the goal is |
28 too specific, the induction hypothesis is too weak to allow the induction |
35 too specific, the induction hypothesis is too weak to allow the induction |
29 step to go through. Let us illustrate the idea with an example. |
36 step to go through. Let us illustrate the idea with an example. |
30 |
37 |
31 Function @{term"rev"} has quadratic worst-case running time |
38 Function \cdx{rev} has quadratic worst-case running time |
32 because it calls function @{text"@"} for each element of the list and |
39 because it calls function @{text"@"} for each element of the list and |
33 @{text"@"} is linear in its first argument. A linear time version of |
40 @{text"@"} is linear in its first argument. A linear time version of |
34 @{term"rev"} reqires an extra argument where the result is accumulated |
41 @{term"rev"} reqires an extra argument where the result is accumulated |
35 gradually, using only @{text"#"}: |
42 gradually, using only~@{text"#"}: |
36 *} |
43 *} |
37 |
44 |
38 consts itrev :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list"; |
45 consts itrev :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list"; |
39 primrec |
46 primrec |
40 "itrev [] ys = ys" |
47 "itrev [] ys = ys" |
41 "itrev (x#xs) ys = itrev xs (x#ys)"; |
48 "itrev (x#xs) ys = itrev xs (x#ys)"; |
42 |
49 |
43 text{*\noindent |
50 text{*\noindent |
44 The behaviour of @{term"itrev"} is simple: it reverses |
51 The behaviour of \cdx{itrev} is simple: it reverses |
45 its first argument by stacking its elements onto the second argument, |
52 its first argument by stacking its elements onto the second argument, |
46 and returning that second argument when the first one becomes |
53 and returning that second argument when the first one becomes |
47 empty. Note that @{term"itrev"} is tail-recursive, i.e.\ it can be |
54 empty. Note that @{term"itrev"} is tail-recursive: it can be |
48 compiled into a loop. |
55 compiled into a loop. |
49 |
56 |
50 Naturally, we would like to show that @{term"itrev"} does indeed reverse |
57 Naturally, we would like to show that @{term"itrev"} does indeed reverse |
51 its first argument provided the second one is empty: |
58 its first argument provided the second one is empty: |
52 *}; |
59 *}; |
58 *}; |
65 *}; |
59 |
66 |
60 apply(induct_tac xs, simp_all); |
67 apply(induct_tac xs, simp_all); |
61 |
68 |
62 txt{*\noindent |
69 txt{*\noindent |
63 Unfortunately, this is not a complete success: |
70 Unfortunately, this attempt does not prove |
|
71 the induction step: |
64 @{subgoals[display,indent=0,margin=70]} |
72 @{subgoals[display,indent=0,margin=70]} |
65 Just as predicted above, the overall goal, and hence the induction |
73 The induction hypothesis is too weak. The fixed |
66 hypothesis, is too weak to solve the induction step because of the fixed |
74 argument,~@{term"[]"}, prevents it from rewriting the conclusion. |
67 argument, @{term"[]"}. This suggests a heuristic: |
75 This example suggests a heuristic: |
68 \begin{quote} |
76 \begin{quote}\index{generalizing induction formulae}% |
69 \emph{Generalize goals for induction by replacing constants by variables.} |
77 \emph{Generalize goals for induction by replacing constants by variables.} |
70 \end{quote} |
78 \end{quote} |
71 Of course one cannot do this na\"{\i}vely: @{term"itrev xs ys = rev xs"} is |
79 Of course one cannot do this na\"{\i}vely: @{term"itrev xs ys = rev xs"} is |
72 just not true --- the correct generalization is |
80 just not true. The correct generalization is |
73 *}; |
81 *}; |
74 (*<*)oops;(*>*) |
82 (*<*)oops;(*>*) |
75 lemma "itrev xs ys = rev xs @ ys"; |
83 lemma "itrev xs ys = rev xs @ ys"; |
76 (*<*)apply(induct_tac xs, simp_all)(*>*) |
84 (*<*)apply(induct_tac xs, simp_all)(*>*) |
77 txt{*\noindent |
85 txt{*\noindent |
78 If @{term"ys"} is replaced by @{term"[]"}, the right-hand side simplifies to |
86 If @{term"ys"} is replaced by @{term"[]"}, the right-hand side simplifies to |
79 @{term"rev xs"}, just as required. |
87 @{term"rev xs"}, as required. |
80 |
88 |
81 In this particular instance it was easy to guess the right generalization, |
89 In this instance it was easy to guess the right generalization. |
82 but in more complex situations a good deal of creativity is needed. This is |
90 Other situations can require a good deal of creativity. |
83 the main source of complications in inductive proofs. |
|
84 |
91 |
85 Although we now have two variables, only @{term"xs"} is suitable for |
92 Although we now have two variables, only @{term"xs"} is suitable for |
86 induction, and we repeat our above proof attempt. Unfortunately, we are still |
93 induction, and we repeat our proof attempt. Unfortunately, we are still |
87 not there: |
94 not there: |
88 @{subgoals[display,indent=0,goals_limit=1]} |
95 @{subgoals[display,indent=0,goals_limit=1]} |
89 The induction hypothesis is still too weak, but this time it takes no |
96 The induction hypothesis is still too weak, but this time it takes no |
90 intuition to generalize: the problem is that @{term"ys"} is fixed throughout |
97 intuition to generalize: the problem is that @{term"ys"} is fixed throughout |
91 the subgoal, but the induction hypothesis needs to be applied with |
98 the subgoal, but the induction hypothesis needs to be applied with |
103 leads to another heuristic for generalization: |
110 leads to another heuristic for generalization: |
104 \begin{quote} |
111 \begin{quote} |
105 \emph{Generalize goals for induction by universally quantifying all free |
112 \emph{Generalize goals for induction by universally quantifying all free |
106 variables {\em(except the induction variable itself!)}.} |
113 variables {\em(except the induction variable itself!)}.} |
107 \end{quote} |
114 \end{quote} |
108 This prevents trivial failures like the above and does not change the |
115 This prevents trivial failures like the one above and does not affect the |
109 provability of the goal. Because it is not always required, and may even |
116 validity of the goal. However, this heuristic should not be applied blindly. |
110 complicate matters in some cases, this heuristic is often not |
117 It is not always required, and the additional quantifiers can complicate |
111 applied blindly. |
118 matters in some cases, The variables that should be quantified are typically |
112 The variables that require generalization are typically those that |
119 those that change in recursive calls. |
113 change in recursive calls. |
|
114 |
120 |
115 A final point worth mentioning is the orientation of the equation we just |
121 A final point worth mentioning is the orientation of the equation we just |
116 proved: the more complex notion (@{term itrev}) is on the left-hand |
122 proved: the more complex notion (@{term itrev}) is on the left-hand |
117 side, the simpler one (@{term rev}) on the right-hand side. This constitutes |
123 side, the simpler one (@{term rev}) on the right-hand side. This constitutes |
118 another, albeit weak heuristic that is not restricted to induction: |
124 another, albeit weak heuristic that is not restricted to induction: |
122 \end{quote} |
128 \end{quote} |
123 This heuristic is tricky to apply because it is not obvious that |
129 This heuristic is tricky to apply because it is not obvious that |
124 @{term"rev xs @ ys"} is simpler than @{term"itrev xs ys"}. But see what |
130 @{term"rev xs @ ys"} is simpler than @{term"itrev xs ys"}. But see what |
125 happens if you try to prove @{prop"rev xs @ ys = itrev xs ys"}! |
131 happens if you try to prove @{prop"rev xs @ ys = itrev xs ys"}! |
126 |
132 |
127 In general, if you have tried the above heuristics and still find your |
133 If you have tried these heuristics and still find your |
128 induction does not go through, and no obvious lemma suggests itself, you may |
134 induction does not go through, and no obvious lemma suggests itself, you may |
129 need to generalize your proposition even further. This requires insight into |
135 need to generalize your proposition even further. This requires insight into |
130 the problem at hand and is beyond simple rules of thumb. You |
136 the problem at hand and is beyond simple rules of thumb. |
131 will need to be creative. Additionally, you can read \S\ref{sec:advanced-ind} |
137 Additionally, you can read \S\ref{sec:advanced-ind} |
132 to learn about some advanced techniques for inductive proofs. |
138 to learn about some advanced techniques for inductive proofs.% |
|
139 \index{induction heuristics|)} |
133 *} |
140 *} |
134 (*<*) |
141 (*<*) |
135 end |
142 end |
136 (*>*) |
143 (*>*) |