|
1 General questions |
|
2 ================= |
|
3 |
|
4 Here is an initial list: |
|
5 clarify, clarsimp, hyp_subst_tac, rename_tac, rotate_tac, split |
|
6 single step tactics: (e/d/f)rule, insert |
|
7 with instantiation: (e/d/f)rule_tac, insert_tac |
|
8 |
|
9 Hide global names like Node. |
|
10 Why is comp needed in addition to op O? |
|
11 Explain in syntax section! |
|
12 |
|
13 Implementation |
|
14 ============== |
|
15 |
|
16 swap in classical.ML has ugly name Pa in it. Rename. |
|
17 |
|
18 list of ^*/^+ intro rules. Incl transitivity? |
|
19 |
|
20 Induction rules for int: int_le/ge_induct? |
|
21 Needed for ifak example. But is that example worth it? |
|
22 |
|
23 Add map_cong?? (upto 10% slower) |
|
24 But we should install UN_cong and INT_cong too. |
|
25 |
|
26 recdef: funny behaviour with map (see email to Konrad.Slind, Recdef/Nested1) |
|
27 |
|
28 defs with = and pattern matching |
|
29 |
|
30 Why can't I declare trev at the end of Recdef/Nested0 and define it in |
|
31 Recdef/Nested1?? |
|
32 |
|
33 use arith_tac in recdef to solve termination conditions? |
|
34 -> new example in Recdef/termination |
|
35 |
|
36 a tactic for replacing a specific occurrence: |
|
37 apply(substitute [2] thm) |
|
38 |
|
39 Minor fixes in the tutorial |
|
40 =========================== |
|
41 |
|
42 replace simp only split by split_tac. |
|
43 |
|
44 get rid of use_thy? |
|
45 |
|
46 Explain typographic conventions? |
|
47 |
|
48 how the simplifier works |
|
49 |
|
50 an example of induction: !y. A --> B --> C ?? |
|
51 |
|
52 Advanced Ind expects rulify, mp and spec. How much really? |
|
53 |
|
54 recdef: subsection Beyond Measure on lex, finite_psubset, ... |
|
55 incl Ackermann, which is now at the end of Recdef/termination.thy. |
|
56 -> Advanced. |
|
57 Sentence at the end: |
|
58 If you feel that the definition of recursive functions is overly and maybe |
|
59 unnecessarily complicated by the requirement of totality you should ponder |
|
60 the alternative, a logic of partial functions, where recursive definitions |
|
61 are always wellformed. For a start, there are many |
|
62 such logics, and no clear winner has emerged. And in all of these logics you |
|
63 are (more or less frequently) required to reason about the definedness of |
|
64 terms explicitly. Thus one shifts definedness arguments from definition to |
|
65 proof time. In HOL you may have to work hard to define a function, but proofs |
|
66 can then proceed unencumbered by worries about undefinedness. |
|
67 |
|
68 Appendix: Lexical: long ids. |
|
69 |
|
70 Warning: infixes automatically become reserved words! |
|
71 |
|
72 Forward ref from blast proof of Puzzle (AdvancedInd) to Isar proof? |
|
73 |
|
74 mention split_split in advanced pair section. |
|
75 |
|
76 Advanced: |
|
77 rule induction where premise not atomic (x1...xn) : R. |
|
78 |
|
79 recdef with nested recursion: either an example or at least a pointer to the |
|
80 literature. In Recdef/termination.thy, at the end. |
|
81 %FIXME, with one exception: nested recursion. |
|
82 |
|
83 Sets: rels and ^* |
|
84 |
|
85 |
|
86 Minor additions to the tutorial, unclear where |
|
87 ============================================== |
|
88 |
|
89 insert: lcp? |
|
90 |
|
91 Tacticals: , ? + |
|
92 |
|
93 print_simpset (-> print_simps?) |
|
94 (Another subsection Useful theorems, methods, and commands?) |
|
95 |
|
96 Mention that simp etc (big step tactics) insist on change? |
|
97 |
|
98 Explain what "by" and "." really do, and introduce "done". |
|
99 |
|
100 A list of further useful commands (rules? tricks?) |
|
101 prefer, defer |
|
102 |
|
103 An overview of the automatic methods: simp, auto, fast, blast, force, |
|
104 clarify, clarsimp (intro, elim?) |
|
105 |
|
106 explain rulify before induction section? |
|
107 |
|
108 demonstrate x : set xs in Sets. Or Tricks chapter? |
|
109 |
|
110 Table with symbols \<forall> etc. Apendix? |
|
111 Appendix with HOL keywords. Say something about other keywords. |
|
112 |
|
113 |
|
114 Possible exercises |
|
115 ================== |
|
116 |
|
117 Exercises |
|
118 %\begin{exercise} |
|
119 %Extend expressions by conditional expressions. |
|
120 braucht wfrec! |
|
121 %\end{exercise} |
|
122 |
|
123 Nested inductive datatypes: another example/exercise: |
|
124 size(t) <= size(subst s t)? |
|
125 |
|
126 Add Until to CTL. |
|
127 |
|
128 insertion sort: primrec, later recdef |
|
129 |
|
130 OTree: |
|
131 first version only for non-empty trees: |
|
132 Tip 'a | Node tree tree |
|
133 Then real version? |
|
134 First primrec, then recdef? |
|
135 |
|
136 Ind. sets: define ABC inductively and prove |
|
137 ABC = {rep A n @ rep B n @ rep C n. True} |
|
138 |
|
139 Possible examples/case studies |
|
140 ============================== |
|
141 |
|
142 Trie: Define functional version |
|
143 datatype ('a,'b)trie = Trie ('b option) ('a => ('a,'b)trie option) |
|
144 lookup t [] = value t |
|
145 lookup t (a#as) = case tries t a of None => None | Some s => lookup s as |
|
146 Maybe as an exercise? |
|
147 |
|
148 Trie: function for partial matches (prefixes). Needs sets for spec/proof. |
|
149 |
|
150 Sets via ordered list of intervals. (Isa/Interval(2)) |
|
151 |
|
152 Sets: PDL and CTL |
|
153 |
|
154 Ind. defs: Grammar (for same number of as and bs), |
|
155 propositional logic (soundness and completeness?), |
|
156 predicate logic (soundness?), |
|
157 CTL proof. |
|
158 |
|
159 Tautology checker. Based on Ifexpr or prop.logic? |
|
160 Include forward reference in relevant section. |
|
161 |
|
162 Sorting with comp-parameter and with type class (<) |
|
163 |
|
164 New book by Bird? |
|
165 |
|
166 Steps Towards Mechanizing Program Transformations Using PVS by N. Shankar, |
|
167 Science of Computer Programming, 26(1-3):33-57, 1996. |
|
168 You can get it from http://www.csl.sri.com/scp95.html |
|
169 |
|
170 J Moore article Towards a ... |
|
171 Mergesort, JVM |
|
172 |
|
173 |
|
174 Additional topics |
|
175 ================= |
|
176 |
|
177 Beef up recdef (see below). |
|
178 Nested recursion? Mutual recursion? |
|
179 |
|
180 Nested inductive datatypes: better recursion and induction |
|
181 (see below) |
|
182 |
|
183 Extensionality: applications in |
|
184 - boolean expressions: valif o bool2if = value |
|
185 - Advanced datatypes exercise subst (f o g) = subst f o subst g |
|
186 |
|
187 A look at the library? |
|
188 Functions. Relations. Lfp/Gfp. Map. |
|
189 If WF is discussed, make a link to it from AdvancedInd. |
|
190 |
|
191 Prototyping? |
|
192 |
|
193 |
|
194 Isabelle |
|
195 ======== |
|
196 |
|
197 Get rid of function name in recdef header |
|
198 |
|
199 More predefined functions for datatypes: map? |
|
200 |
|
201 1 and 2 on nat? |
|
202 |
|
203 |
|
204 ============================================================== |
|
205 Nested inductive datatypes: better recursion and induction |
|
206 |
|
207 Show how to derive simpler primrec functions using eg map. Text: |
|
208 |
|
209 Returning to the definition of \texttt{subst}, we have to admit that it does |
|
210 not really need the auxiliary \texttt{substs} function. The \texttt{App}-case |
|
211 can directly be expressed as |
|
212 \begin{ttbox} |
|
213 \input{Datatype/appmap}\end{ttbox} |
|
214 Although Isabelle insists on the more verbose version, we can easily {\em |
|
215 prove} that the \texttt{map}-equation holds: simply by induction on |
|
216 \texttt{ts} followed by \texttt{Auto_tac}. |
|
217 lemma "subst s (App f ts) = App f (map (subst s) ts)"; |
|
218 by(induct_tac ts, auto); |
|
219 |
|
220 Now explain how to remove old eqns from simpset by naming them. |
|
221 But: the new eqn only helps if the induction schema is also modified |
|
222 accordingly: |
|
223 |
|
224 val prems = |
|
225 Goal "[| !!v. P(Var v); !!f ts. (!!t. t : set ts ==> P t) ==> P(App f ts) |] \ |
|
226 \ ==> P t & (!t: set ts. P t)"; |
|
227 by(induct_tac "t ts" 1); |
|
228 brs prems 1; |
|
229 brs prems 1; |
|
230 by(Blast_tac 1); |
|
231 by(Simp_tac 1); |
|
232 by(Asm_simp_tac 1); |
|
233 |
|
234 Now the following exercise has an easy proof: |
|
235 |
|
236 \begin{exercise} |
|
237 Define a function \texttt{rev_term} of type \texttt{term -> term} that |
|
238 recursively reverses the order of arguments of all function symbols in a |
|
239 term. Prove that \texttt{rev_term(rev_term t) = t}. |
|
240 \end{exercise} |
|
241 |
|
242 ============================================================== |
|
243 Recdef: |
|
244 |
|
245 nested recursion |
|
246 more example proofs: |
|
247 if-normalization with measure function, |
|
248 nested if-normalization, |
|
249 quicksort |
|
250 Trie? |
|
251 a case study? |
|
252 |
|
253 A separate subsection on recdef beyond measure, eg <*lex*> and psubset. |
|
254 Example: some finite fixpoint computation? MC, Grammar? |
|
255 How to modify wf-prover? |
|
256 |
|
257 ---------- |
|
258 |
|
259 Partial rekursive functions / Nontermination |
|
260 |
|
261 What appears to be the problem: |
|
262 axiom f n = f n + 1 |
|
263 lemma False |
|
264 apply(cut_facts_tac axiom, simp). |
|
265 |
|
266 1. Guarded recursion |
|
267 |
|
268 Scheme: |
|
269 f x = if $x \in dom(f)$ then ... else arbitrary |
|
270 |
|
271 Example: sum/fact: int -> int (for no good reason because we have nat) |
|
272 |
|
273 Exercise: ?! f. !i. f i = if i=0 then 1 else i*f(i-1) |
|
274 (What about sum? Is there one, a unique one?) |
|
275 |
|
276 [Alternative: include argument that is counted down |
|
277 f x n = if n=0 then None else ... |
|
278 Refer to Boyer and Moore] |
|
279 |
|
280 More complex: same_fst |
|
281 |
|
282 chase(f,x) = if wf{(f x,x) . f x ~= x} |
|
283 then if f x = x then x else chase(f,f x) |
|
284 else arb |
|
285 |
|
286 Prove wf ==> f(chase(f,x)) = chase(f,x) |
|
287 |
|
288 2. While / Tail recursion |
|
289 |
|
290 chase f x = fst(while (%(x,fx). x=fx) (%(x,fx). (fx,f fx)) (x,f x)) |
|
291 |
|
292 ==> unfold eqn for chase? Prove fixpoint property? |
|
293 |
|
294 Better(?) sum i = fst(while (%(s,i). i=0) (%(s,i). (s+i,i-1)) (0,i)) |
|
295 Prove 0 <= i ==> sum i = i*(i+1) via while-rule |
|
296 |
|
297 Mention prototyping? |
|
298 ============================================================== |