Debian Codegraph @

Formal_ineqs/arith/arith_num.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2012 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Formal natural arithmetic with an arbitrary base *)
11 (* -------------------------------------------------------------------------- *)
12
13 module type Arith_num_sig =
14 sig
15 val arith_base : int
16 val num_def : thm
17 val NUM_THM : thm
18 val num_const : term
19 val const_array : term array
20 val def_array: thm array
21 val def_thm_array: thm array
22 val mk_numeral_hash : num -> term
23 val mk_numeral_array : num -> term
24 val mk_small_numeral_array : int -> term
25 val raw_dest_hash : term -> num
26 val dest_numeral_hash : term -> num
27 val NUMERAL_TO_NUM_CONV : term -> thm
28 val NUM_TO_NUMERAL_CONV : term -> thm
29 (* SUC *)
30 val raw_suc_conv_hash : term -> thm
31 val NUM_SUC_HASH_CONV : term -> thm
32 (* eq0 *)
33 val raw_eq0_hash_conv : term -> thm
34 val NUM_EQ0_HASH_CONV : term -> thm
35 (* PRE *)
36 val raw_pre_hash_conv : term -> thm
37 val NUM_PRE_HASH_CONV : term -> thm
38 (* gt0 *)
39 val raw_gt0_hash_conv : term -> thm
40 val NUM_GT0_HASH_CONV : term -> thm
41 (* eq *)
42 val raw_eq_hash_conv : term -> thm
43 val NUM_EQ_HASH_CONV : term -> thm
44 (* lt, le *)
45 val raw_lt_hash_conv : term -> thm
46 val raw_le_hash_conv : term -> thm
47 val NUM_LT_HASH_CONV : term -> thm
48 val NUM_LE_HASH_CONV : term -> thm
49 (* add *)
50 val raw_add_conv_hash : term -> thm
51 val NUM_ADD_HASH_CONV : term -> thm
52 (* sub *)
53 val raw_sub_hash_conv : term -> thm
54 val raw_sub_and_le_hash_conv : term -> term -> thm * thm
55 val NUM_SUB_HASH_CONV : term -> thm
56 (* mul *)
57 val raw_mul_conv_hash : term -> thm
58 val NUM_MULT_HASH_CONV : term -> thm
59 (* DIV *)
60 val raw_div_hash_conv : term -> thm
61 val NUM_DIV_HASH_CONV : term -> thm
62 (* EVEN, ODD *)
63 val raw_even_hash_conv : term -> thm
64 val raw_odd_hash_conv : term -> thm
65 val NUM_EVEN_HASH_CONV : term -> thm
66 val NUM_ODD_HASH_CONV : term -> thm
67 end;;
68
69 (* Dependencies *)
70 needs "Formal_ineqs/misc/misc_functions.hl";;
71 needs "Formal_ineqs/misc/misc_vars.hl";;
72 needs "Formal_ineqs/arith_options.hl";;
73
74 module Arith_num : Arith_num_sig = struct
75
76 open Misc_functions;;
77 open Misc_vars;;
78
79 let arith_base = !Arith_options.base;;
80 let maximum = arith_base;;
81
82 (******************)
83
84 (* Generate definitions and constants *)
85
86 let fnum_type = `:num->num` and
87 numeral_const = `NUMERAL` and
88 bit0_const = `BIT0` and
89 bit1_const = `BIT1`;;
90
91 (* Names of constants which define "digits" *)
92 let names_array = Array.init maximum (fun i -> "D"^(string_of_int i));;
93
94 (* Definitions *)
95 let num_name = "NUM"^(string_of_int arith_base);;
96 let num_def = new_basic_definition (mk_eq(mk_var(num_name, fnum_type), numeral_const));;
97 let num_const = mk_const(num_name, []);;
98 let num_def_sym = SYM num_def;;
99
100 (* |- NUM n = n *)
101 let NUM_THM = prove(mk_eq(mk_comb(num_const, n_var_num), n_var_num),
102 REWRITE_TAC[num_def; NUMERAL]);;
103
104 (* |- D_i(n) = i + D_0(n) *)
105 let mk_bit_definition i =
106 let lhs = mk_var (names_array.(i), fnum_type) in
107 let tm1 = mk_binop mul_op_num (mk_small_numeral arith_base) n_var_num in
108 let tm2 = mk_binop add_op_num tm1 (mk_small_numeral i) in
109 let rhs = mk_abs (n_var_num, tm2) in
110 new_basic_definition (mk_eq (lhs, rhs));;
111
112 let def_basic_array = Array.init maximum mk_bit_definition;;
113 let def_array = Array.init maximum (fun i ->
114 let basic = def_basic_array.(i) in
115 let th1 = AP_THM basic n_var_num in
116 TRANS th1 (BETA (rand (concl th1))));;
117 let def_table = Hashtbl.create maximum;;
118 let def_basic_table = Hashtbl.create maximum;;
119
120 for i = 0 to maximum - 1 do
121 let _ = Hashtbl.add def_table names_array.(i) def_array.(i) in
122 Hashtbl.add def_basic_table names_array.(i) def_basic_array.(i)
123 done;;
124
125
126 (* Constants *)
127 let const_array = Array.init maximum (fun i -> mk_const(names_array.(i),[]));;
128
129 let b0_def = def_array.(0);;
130 let b0_const = const_array.(0);;
131 let b0_name = names_array.(0);;
132
133 let max_const = mk_small_numeral maximum;;
134
135
136 (* Alternative definition of D_i *)
137 let ADD_0_n = prove(`_0 + n = n`,
138 ONCE_REWRITE_TAC[GSYM NUMERAL] THEN
139 REWRITE_TAC[GSYM ARITH_ADD; ADD_CLAUSES]);;
140 let ADD_n_0 = prove(`n + _0 = n`,
141 ONCE_REWRITE_TAC[GSYM NUMERAL] THEN
142 REWRITE_TAC[GSYM ARITH_ADD; ADD_CLAUSES]);;
143
144 let MUL_n_0 = prove(`n * _0 = 0`,
145 REWRITE_TAC[NUMERAL] THEN
146 SUBGOAL_THEN `_0 = 0` MP_TAC THENL [ REWRITE_TAC[NUMERAL]; ALL_TAC ] THEN
147 DISCH_THEN (fun th -> ONCE_REWRITE_TAC[th]) THEN
148 ARITH_TAC);;
149
150 (* D_i(n) = i + D_0(n) *)
151 let def_thm i =
152 let bin = mk_comb(const_array.(i), n_var_num) in
153 let bi0 = mk_comb(const_array.(i), zero_const) in
154 let b0n = mk_comb(const_array.(0), n_var_num) in
155 let rhs = mk_binop add_op_num bi0 b0n in
156 prove(mk_eq(bin, rhs), REWRITE_TAC[def_array.(i); def_array.(0)] THEN
157 REWRITE_TAC[MUL_n_0; ADD_CLAUSES] THEN ARITH_TAC);;
158
159 let def_thm_array = Array.init maximum def_thm;;
160
161 let B0_0 = prove(mk_eq(mk_comb(b0_const, zero_const), zero_const),
162 REWRITE_TAC[b0_def; MUL_n_0; ADD_CLAUSES; NUMERAL]);;
163
164 let B0_EXPLICIT = prove(mk_eq(mk_comb(b0_const, n_var_num),
165 mk_binop mul_op_num max_const n_var_num),
166 REWRITE_TAC[b0_def; ADD_CLAUSES]);;
167
168 (******************************)
169 (* mk_numeral and dest_numeral *)
170
171 (* mk_table *)
172
173 let mk_table = Hashtbl.create maximum;;
174
175 for i = 0 to maximum - 1 do
176 Hashtbl.add mk_table (Num.num_of_int i) const_array.(i)
177 done;;
178
179 (* mk_numeral *)
180 let max_num = Num.num_of_int maximum;;
181
182 let mk_numeral_hash =
183 let rec mk_num n =
184 if (n =/ num_0) then
185 zero_const
186 else
187 let m = mod_num n max_num in
188 let bit = Hashtbl.find mk_table m in
189 mk_comb(bit, mk_num(quo_num n max_num)) in
190 fun n -> if n </ num_0 then failwith "mk_numeral_hash: negative argument"
191 else mk_comb(num_const, mk_num n);;
192
193 let mk_numeral_array =
194 let rec mk_num n =
195 if (n =/ num_0) then
196 zero_const
197 else
198 let m = Num.int_of_num (mod_num n max_num) in
199 let bit = const_array.(m) in
200 mk_comb(bit, mk_num(quo_num n max_num)) in
201 fun n -> if n </ num_0 then failwith "mk_numeral_array: negative argument"
202 else mk_comb(num_const, mk_num n);;
203
204 let mk_small_numeral_array =
205 let rec mk_num n =
206 if (n = 0) then zero_const
207 else
208 let m = n mod maximum in
209 let bit = const_array.(m) in
210 mk_comb(bit, mk_num(n / maximum)) in
211 fun n -> if n < 0 then failwith "mk_small_numeral_array: negative argument"
212 else mk_comb (num_const, mk_num n);;
213
214 (* dest_table *)
215 let dest_table_num = Hashtbl.create maximum;;
216
217 for i = 0 to maximum - 1 do
218 Hashtbl.add dest_table_num names_array.(i) (Num.num_of_int i)
219 done;;
220
221
222 (* dest_numeral *)
223 let max_num = Num.num_of_int maximum;;
224
225 let rec raw_dest_hash tm =
226 if tm = zero_const then
227 num_0
228 else
229 let l, r = dest_comb tm in
230 let n = max_num */ raw_dest_hash r in
231 let cn = fst(dest_const l) in
232 n +/ (Hashtbl.find dest_table_num cn);;
233
234
235 let dest_numeral_hash tm = raw_dest_hash (rand tm);;
236
237
238 (******************************)
239 (* NUMERAL_TO_NUM_CONV: coverts usual HOL numerals into k-bit numerals *)
240
241 let th_num_conv = Array.init maximum (fun i -> (SYM o SPEC_ALL) def_array.(i));;
242 let mod_op_num = `MOD`;;
243
244 let DIV_BASE =
245 let h1 = mk_eq(mk_binop div_op_num m_var_num max_const, q_var_num) in
246 let h2 = mk_eq(mk_binop mod_op_num m_var_num max_const, r_var_num) in
247 let c = mk_eq(m_var_num, mk_binop add_op_num (mk_binop mul_op_num max_const q_var_num) r_var_num) in
248 (UNDISCH_ALL o ARITH_RULE) (mk_imp(h1, mk_imp(h2, c)));;
249
250 let ZERO_EQ_ZERO = (EQT_ELIM o REWRITE_CONV[NUMERAL]) `0 = _0`;;
251 let SYM_ZERO_EQ_ZERO = SYM ZERO_EQ_ZERO;;
252 let SYM_NUM_THM = SYM NUM_THM;;
253
254 let NUMERAL_TO_NUM_CONV tm =
255 let rec raw_conv tm =
256 if (rand tm = zero_const) then
257 ZERO_EQ_ZERO
258 else
259 let th_div = NUM_DIV_CONV (mk_binop div_op_num tm max_const) in
260 let th_mod = NUM_MOD_CONV (mk_binop mod_op_num tm max_const) in
261 let q_tm = rand(concl th_div) in
262 let r_tm = rand(concl th_mod) in
263 let th0 = INST[tm, m_var_num; q_tm, q_var_num; r_tm, r_var_num] DIV_BASE in
264 let th1 = MY_PROVE_HYP th_mod (MY_PROVE_HYP th_div th0) in
265 let r = dest_small_numeral r_tm in
266 let th2 = INST[q_tm, n_var_num] th_num_conv.(r) in
267 let th = TRANS th1 th2 in
268 let ltm, rtm = dest_comb(rand(concl th)) in
269 let r_th = raw_conv rtm in
270 TRANS th (AP_TERM ltm r_th) in
271
272 if (fst o dest_const o rator) tm <> "NUMERAL" then
273 failwith "NUMERAL_TO_NUM_CONV"
274 else
275 let th0 = raw_conv tm in
276 let n_tm = rand(concl th0) in
277 TRANS th0 (INST[n_tm, n_var_num] SYM_NUM_THM);;
278
279 let replace_numerals = rand o concl o DEPTH_CONV NUMERAL_TO_NUM_CONV;;
280 let REPLACE_NUMERALS = CONV_RULE (DEPTH_CONV NUMERAL_TO_NUM_CONV);;
281
282 (* NUM_TO_NUMERAL_CONV *)
283 let NUM_TO_NUMERAL_CONV tm =
284 let rec raw_conv tm =
285 if tm = zero_const then
286 SYM_ZERO_EQ_ZERO
287 else
288 let b_tm, n_tm = dest_comb tm in
289 let n_th = raw_conv n_tm in
290 let n_tm' = rand(concl n_th) in
291 let cb = (fst o dest_const) b_tm in
292 let th0 = Hashtbl.find def_table cb in
293 let th1 = AP_TERM b_tm n_th in
294 let th2 = TRANS th1 (INST[n_tm', n_var_num] th0) in
295 let ltm, rtm = dest_comb(rand(concl th2)) in
296 let mul_th = NUM_MULT_CONV (rand ltm) in
297 let add_th0 = AP_THM (AP_TERM add_op_num mul_th) rtm in
298 let add_th = TRANS add_th0 (NUM_ADD_CONV (rand(concl add_th0))) in
299 TRANS th2 add_th in
300 let ltm, rtm = dest_comb tm in
301 if (fst o dest_const) ltm <> num_name then
302 failwith "NUM_TO_NUMERAL_CONV"
303 else
304 let num_th = INST[rtm, n_var_num] NUM_THM in
305 let th0 = raw_conv rtm in
306 TRANS num_th th0;;
307
308 (*************************)
309 (* SUC_CONV *)
310
311 (* Theorems *)
312 let SUC_NUM = prove(mk_eq(mk_comb(suc_op_num, mk_comb (num_const, n_var_num)),
313 mk_comb(num_const, mk_comb (suc_op_num, n_var_num))),
314 REWRITE_TAC[num_def; NUMERAL]);;
315
316 let SUC_0 = prove(mk_eq(`SUC _0`, mk_comb (const_array.(1), zero_const)),
317 REWRITE_TAC[def_array.(1); MUL_n_0; ARITH_SUC; NUMERAL; ARITH_ADD]);;
318
319 let suc_th i =
320 let cflag = (i + 1 >= maximum) in
321 let suc = if (cflag) then 0 else i + 1 in
322 let lhs = mk_comb(suc_op_num, (mk_comb (const_array.(i), n_var_num))) in
323 let rhs = mk_comb(const_array.(suc),
324 if (cflag) then mk_comb(suc_op_num, n_var_num) else n_var_num) in
325 let proof = REWRITE_TAC [def_array.(i); def_array.(suc)] THEN ARITH_TAC in
326 prove(mk_eq(lhs, rhs), proof);;
327
328 let th_suc_array = Array.init maximum suc_th;;
329 let th_suc_table = Hashtbl.create maximum;;
330
331 for i = 0 to maximum - 1 do
332 Hashtbl.add th_suc_table names_array.(i) th_suc_array.(i)
333 done;;
334
335 let SUC_MAX = th_suc_array.(maximum - 1);;
336 let bit_max_name = names_array.(maximum - 1);;
337
338 (* Conversion *)
339 let rec raw_suc_conv_hash tm =
340 let otm = rand tm in
341 if (otm = zero_const) then
342 SUC_0
343 else
344 let btm, ntm = dest_comb otm in
345 let cn = fst(dest_const btm) in
346 if (cn = bit_max_name) then
347 let th = INST [ntm, n_var_num] SUC_MAX in
348 let ltm, rtm = dest_comb(rand(concl th)) in
349 TRANS th (AP_TERM ltm (raw_suc_conv_hash rtm))
350 else
351 INST [ntm, n_var_num] (Hashtbl.find th_suc_table cn);;
352
353 let NUM_SUC_HASH_CONV tm =
354 let ntm = rand (rand tm) in
355 let th = INST [ntm, n_var_num] SUC_NUM in
356 let lhs, rhs = dest_eq(concl th) in
357 if (lhs <> tm) then failwith("NUM_SUC_HASH_CONV")
358 else
359 let ltm, rtm = dest_comb rhs in
360 TRANS th (AP_TERM ltm (raw_suc_conv_hash rtm));;
361
362
363 (**************************************)
364 (* EQ_0_CONV *)
365 let EQ_0_NUM = prove(mk_eq(mk_eq(mk_comb(num_const, n_var_num), `_0`), `n = _0`),
366 REWRITE_TAC[num_def; NUMERAL]);;
367
368 let EQ_B0_0 = prove(mk_eq(mk_eq(mk_comb(b0_const, n_var_num), `_0`), `n = _0`),
369 REWRITE_TAC[b0_def; ADD_CLAUSES; NUMERAL; REWRITE_RULE[NUMERAL] MULT_EQ_0; ARITH_EQ]);;
370
371 let EQ_0_0 = prove(`_0 = _0 <=> T`, REWRITE_TAC[ARITH_EQ]);;
372
373 let eq_0_lemma = REWRITE_RULE[NUMERAL] (ARITH_RULE `a + b = 0 <=> a = 0 /\ b = 0`);;
374
375 let eq_0_i i =
376 let concl = mk_eq(mk_eq(mk_comb(const_array.(i), n_var_num), zero_const), f_const) in
377 prove(concl, REWRITE_TAC[def_array.(i); eq_0_lemma; NUMERAL; ARITH_EQ]);;
378
379 let th_eq0_array = Array.init maximum (fun i -> if (i = 0) then EQ_0_0 else eq_0_i i);;
380
381 let th_eq0_table = Hashtbl.create maximum;;
382
383 for i = 0 to maximum - 1 do
384 Hashtbl.add th_eq0_table names_array.(i) th_eq0_array.(i)
385 done;;
386
387 let rec raw_eq0_hash_conv rtm =
388 if (rtm = zero_const) then
389 EQ_0_0
390 else
391 let b_tm, n_tm = dest_comb rtm in
392 let cn = (fst o dest_const) b_tm in
393 if (cn = b0_name) then
394 let th0 = INST[n_tm, n_var_num] EQ_B0_0 in
395 let th1 = raw_eq0_hash_conv n_tm in
396 TRANS th0 th1
397 else
398 INST[n_tm, n_var_num] (Hashtbl.find th_eq0_table cn);;
399
400 let NUM_EQ0_HASH_CONV rtm =
401 let n_tm = rand rtm in
402 let th = INST [n_tm, n_var_num] EQ_0_NUM in
403 TRANS th (raw_eq0_hash_conv n_tm);;
404
405 (**************************************)
406 (* PRE_CONV *)
407
408 (* Theorems *)
409 let PRE_NUM = prove(mk_eq(mk_comb(pre_op_num, mk_comb (num_const, n_var_num)),
410 mk_comb(num_const, mk_comb (pre_op_num, n_var_num))),
411 REWRITE_TAC[num_def; NUMERAL]);;
412
413 let PRE_0 = prove(`PRE _0 = _0`,
414 MP_TAC (CONJUNCT1 PRE) THEN SIMP_TAC[NUMERAL]);;
415
416 let PRE_B1_0 = prove(mk_eq(mk_comb(`PRE`, mk_comb(const_array.(1), `_0`)), `_0`),
417 REWRITE_TAC[def_array.(1); MUL_n_0; ARITH_ADD; NUMERAL; ARITH_PRE; ARITH_EQ]);;
418
419
420 let PRE_B0_n0 = (UNDISCH_ALL o prove)(mk_imp(`n = _0 <=> T`,
421 mk_eq(mk_comb(`PRE`, mk_comb(b0_const, `n:num`)), `_0`)),
422 REWRITE_TAC[B0_EXPLICIT] THEN
423 DISCH_THEN (fun th -> REWRITE_TAC[th; MUL_n_0]) THEN
424 REWRITE_TAC[NUMERAL; ARITH_PRE]);;
425
426 let PRE_B0_n1 = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o prove)(mk_imp(`n = 0 <=> F`,
427 mk_eq(mk_comb(`PRE`, mk_comb(b0_const, `n:num`)),
428 mk_comb(const_array.(maximum - 1), `PRE n`))),
429 REWRITE_TAC[B0_EXPLICIT; def_array.(maximum - 1)] THEN ARITH_TAC);;
430
431 let PRE_lemma = (UNDISCH_ALL o PURE_REWRITE_RULE[NUMERAL] o ARITH_RULE) `((n = 0) <=> F) ==> (SUC m = n <=> PRE n = m)`;;
432
433 let pre_th i =
434 let pre = i - 1 in
435 let pre_tm = mk_comb(const_array.(pre), n_var_num) in
436 let suc_tm = mk_comb(suc_op_num, pre_tm) in
437 let suc_th = raw_suc_conv_hash suc_tm in
438 let n_tm = rand(concl suc_th) in
439 let n0_th = raw_eq0_hash_conv n_tm in
440 let th0 = INST[pre_tm, m_var_num; n_tm, n_var_num] PRE_lemma in
441 MY_PROVE_HYP n0_th (EQ_MP th0 suc_th);;
442
443
444 let th_pre_array = Array.init maximum (fun i -> if i = 0 then REFL `_0` else pre_th i);;
445
446 let th_pre_table = Hashtbl.create maximum;;
447
448 for i = 0 to maximum - 1 do
449 Hashtbl.add th_pre_table names_array.(i) th_pre_array.(i)
450 done;;
451
452 (* Conversion *)
453 let b1_name = names_array.(1);;
454 let b1_pre_thm = th_pre_array.(1);;
455
456 let rec raw_pre_hash_conv tm =
457 let otm = rand tm in
458 if (otm = zero_const) then
459 PRE_0
460 else
461 let btm, ntm = dest_comb otm in
462 let cn = fst(dest_const btm) in
463 if (cn = b0_name) then
464 let n_th = raw_eq0_hash_conv ntm in
465 if (rand(concl n_th) = f_const) then
466 let th0 = INST[ntm, n_var_num] PRE_B0_n1 in
467 let th1 = MY_PROVE_HYP n_th th0 in
468 let ltm, rtm = dest_comb(rand(concl th1)) in
469 let th2 = raw_pre_hash_conv rtm in
470 TRANS th1 (AP_TERM ltm th2)
471 else
472 let th = INST[ntm, n_var_num] PRE_B0_n0 in
473 MY_PROVE_HYP n_th th
474 else
475 if (cn = b1_name) then
476 if (ntm = zero_const) then
477 PRE_B1_0
478 else
479 INST[ntm, n_var_num] b1_pre_thm
480 else
481 INST [ntm, n_var_num] (Hashtbl.find th_pre_table cn);;
482
483 let NUM_PRE_HASH_CONV tm =
484 let ntm = rand (rand tm) in
485 let th = INST [ntm, n_var_num] PRE_NUM in
486 let lhs, rhs = dest_eq(concl th) in
487 if (lhs <> tm) then failwith("NUM_PRE_HASH_CONV")
488 else
489 let ltm, rtm = dest_comb rhs in
490 TRANS th (AP_TERM ltm (raw_pre_hash_conv rtm));;
491
492 (**************************************)
493 (* GT0_CONV *)
494
495 let gt0_table = Hashtbl.create maximum;;
496
497 let GT0_NUM = (REWRITE_RULE[GSYM num_def] o prove)(`0 < NUMERAL n <=> _0 < n`, REWRITE_TAC[NUMERAL]);;
498
499 let gt0_0 = prove(`_0 < _0 <=> F`, REWRITE_TAC[ARITH_LT]);;
500 let gt0_b0 = (REWRITE_RULE[NUMERAL] o prove)(mk_eq (mk_binop lt_op_num `0` (mk_comb(b0_const, n_var_num)), `0 < n`),
501 REWRITE_TAC[b0_def] THEN ARITH_TAC);;
502
503 let gt0_th i =
504 let bi = const_array.(i) in
505 let concl = mk_eq (mk_binop lt_op_num zero_num (mk_comb(bi, n_var_num)), t_const) in
506 let proof = REWRITE_TAC[def_array.(i)] THEN ARITH_TAC in
507 (PURE_REWRITE_RULE[NUMERAL] o prove)(concl, proof);;
508
509 for i = 1 to maximum - 1 do
510 Hashtbl.add gt0_table names_array.(i) (gt0_th i)
511 done;;
512
513 let rec raw_gt0_hash_conv rtm =
514 if (rtm = zero_const) then
515 gt0_0
516 else
517 let b_tm, n_tm = dest_comb rtm in
518 let cn = (fst o dest_const) b_tm in
519 if (cn = b0_name) then
520 let th0 = INST[n_tm, n_var_num] gt0_b0 in
521 let th1 = raw_gt0_hash_conv n_tm in
522 TRANS th0 th1
523 else
524 INST[n_tm, n_var_num] (Hashtbl.find gt0_table cn);;
525
526 let NUM_GT0_HASH_CONV rtm =
527 let n_tm = rand rtm in
528 let th = INST [n_tm, n_var_num] GT0_NUM in
529 TRANS th (raw_gt0_hash_conv n_tm);;
530
531 (*************************************)
532 (* EQ *)
533
534 let EQ_NUM = (REWRITE_RULE[SYM num_def] o prove)(`NUMERAL m = NUMERAL n <=> m = n`, REWRITE_TAC[NUMERAL]);;
535
536
537 (* EQ tables *)
538
539 (* Generates the theorem |- D_i(m) = D_j(n) <=> F if i <> j and D_i(m) = D_i(n) <=> m = n *)
540 let gen_bi_eq_bj =
541 let aux_th = prove(`i < b /\ j < b /\ ~(i = j) ==> ~(b * m + i = b * n + j:num)`,
542 ONCE_REWRITE_TAC[ARITH_RULE `b * m + i = b * n + j <=> m * b + i = n * b + j:num`] THEN
543 STRIP_TAC THEN POP_ASSUM MP_TAC THEN
544 SUBGOAL_THEN `~(b = 0)` ASSUME_TAC THENL [POP_ASSUM MP_TAC THEN ARITH_TAC; ALL_TAC] THEN
545 REWRITE_TAC[CONTRAPOS_THM] THEN
546 DISCH_TAC THEN FIRST_ASSUM (MP_TAC o AP_TERM `\x. x DIV b`) THEN REWRITE_TAC[] THEN
547 FIRST_ASSUM (MP_TAC o MATCH_MP (CONJUNCT1 DIV_MULT_ADD)) THEN
548 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
549 SUBGOAL_THEN `i DIV b = 0 /\ j DIV b = 0` (fun th -> REWRITE_TAC[th]) THENL
550 [
551 FIRST_ASSUM (ASSUME_TAC o MATCH_MP DIV_EQ_0) THEN ASM_REWRITE_TAC[];
552 ALL_TAC
553 ] THEN
554 REWRITE_TAC[ADD_0] THEN DISCH_TAC THEN
555 UNDISCH_TAC `m * b + i = n * b + j:num` THEN
556 ASM_REWRITE_TAC[] THEN ARITH_TAC) in
557 fun i j ->
558 let bi_m = mk_comb (const_array.(i), m_var_num) in
559 let bj_n = mk_comb (const_array.(j), n_var_num) in
560 let eq_tm = mk_binop eq_op_num bi_m bj_n in
561 if i = j then
562 prove (mk_eq (eq_tm, mk_binop eq_op_num m_var_num n_var_num), REWRITE_TAC[def_array.(i)] THEN ARITH_TAC)
563 else
564 prove (mk_eq (eq_tm, f_const), REWRITE_TAC[def_array.(i); def_array.(j)] THEN
565 MATCH_MP_TAC aux_th THEN CONV_TAC NUM_REDUCE_CONV);;
566
567
568 let gen_next_eq_thm =
569 let suc_eq_th = ARITH_RULE `SUC m = SUC n <=> m = n` in
570 fun th ->
571 let ltm, n_tm = (dest_comb o lhand o concl) th in
572 let m_tm = rand ltm in
573 let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] suc_eq_th in
574 let suc_m = raw_suc_conv_hash (mk_comb (suc_op_num, m_tm)) in
575 let suc_n = raw_suc_conv_hash (mk_comb (suc_op_num, n_tm)) in
576 let th1 = SYM (MK_COMB ((AP_TERM eq_op_num suc_m), suc_n)) in
577 TRANS (TRANS th1 th0) th;;
578
579
580 let th_eq_table = Hashtbl.create (maximum * maximum);;
581
582
583 for i = 0 to maximum - 1 do
584 let sym = INST[n_var_num, m_var_num; m_var_num, n_var_num] o CONV_RULE (LAND_CONV SYM_CONV) in
585 let th = ref (gen_bi_eq_bj 0 i) in
586 let name_left = names_array.(0) and
587 name_right = names_array.(i) in
588 let _ = Hashtbl.add th_eq_table (name_left ^ name_right) !th in
589 let _ = if i > 0 then
590 Hashtbl.add th_eq_table (name_right ^ name_left) (sym !th)
591 else () in
592 for k = 1 to maximum - i - 1 do
593 let x = k and y = i + k in
594 let name_left = names_array.(x) and
595 name_right = names_array.(y) in
596 let _ = th := gen_next_eq_thm (!th) in
597 let _ = Hashtbl.add th_eq_table (name_left ^ name_right) !th in
598 if y > x then
599 Hashtbl.add th_eq_table (name_right ^ name_left) (sym !th)
600 else
601 ()
602 done;
603 done;;
604
605
606 (* Conversion *)
607
608 let eq_0_sym = (REWRITE_RULE[NUMERAL] o prove)(`0 = n <=> n = 0`, REWRITE_TAC[EQ_SYM_EQ]);;
609
610 let rec raw_eq_hash_conv tm =
611 let ltm, rtm = dest_comb tm in
612 let ltm = rand ltm in
613 if is_const rtm then
614 (* n = _0 *)
615 raw_eq0_hash_conv ltm
616 else
617 (* n <> _0 *)
618 if is_const ltm then
619 (* m = _0 *)
620 let th0 = raw_eq0_hash_conv rtm in
621 let th1 = INST[rtm, n_var_num] eq_0_sym in
622 TRANS th1 th0
623 else
624 (* m <> _0 *)
625 let bm_tm, m_tm = dest_comb ltm in
626 let bn_tm, n_tm = dest_comb rtm in
627 let cbm = (fst o dest_const) bm_tm in
628 let cbn = (fst o dest_const) bn_tm in
629 let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] (Hashtbl.find th_eq_table (cbm^cbn)) in
630 if cbm <> cbn then
631 th0
632 else
633 let th1 = raw_eq_hash_conv (rand (concl th0)) in
634 TRANS th0 th1;;
635
636
637 let NUM_EQ_HASH_CONV tm =
638 let atm, rtm = dest_comb tm in
639 let ltm = rand atm in
640 let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] EQ_NUM in
641 let rtm = rand(concl th) in
642 TRANS th (raw_eq_hash_conv rtm);;
643
644
645
646 (*************************************)
647 (* LT and LE *)
648
649 let LT_NUM = (REWRITE_RULE[SYM num_def] o prove)(`NUMERAL m < NUMERAL n <=> m < n`, REWRITE_TAC[NUMERAL]);;
650 let LE_NUM = (REWRITE_RULE[SYM num_def] o prove)(`NUMERAL m <= NUMERAL n <=> m <= n`, REWRITE_TAC[NUMERAL]);;
651
652 let LT_n_0 = prove(`n < _0 <=> F`,
653 SUBGOAL_THEN `_0 = 0` MP_TAC THENL [ REWRITE_TAC[NUMERAL]; ALL_TAC ] THEN
654 DISCH_THEN (fun th -> PURE_ONCE_REWRITE_TAC[th]) THEN
655 ARITH_TAC);;
656
657 let LE_0_n = prove(`_0 <= n <=> T`,
658 SUBGOAL_THEN `_0 = 0` MP_TAC THENL [ REWRITE_TAC[NUMERAL]; ALL_TAC ] THEN
659 DISCH_THEN (fun th -> PURE_ONCE_REWRITE_TAC[th]) THEN
660 ARITH_TAC);;
661
662 let SUC_LT_THM = ARITH_RULE `SUC m < SUC n <=> m < n`;;
663 let SUC_LE_THM = ARITH_RULE `SUC m <= SUC n <=> m <= n`;;
664
665 (* LT tables *)
666
667 (* Generates the theorem |- _0 < bi(n) <=> T (or |- _0 < b0(n) <=> _0 < n) *)
668 let gen_0_lt_bi i =
669 let bin = mk_comb (const_array.(i), n_var_num) in
670 let lt_tm = mk_binop lt_op_num zero_num bin in
671 if i > 0 then
672 (PURE_REWRITE_RULE[NUMERAL] o EQT_INTRO o prove)(lt_tm, REWRITE_TAC[def_array.(i)] THEN ARITH_TAC)
673 else
674 (PURE_REWRITE_RULE[NUMERAL] o prove)(mk_eq(lt_tm, `0 < n`), REWRITE_TAC[B0_EXPLICIT] THEN ARITH_TAC);;
675
676 let th_lt0_table = Hashtbl.create maximum;;
677 for i = 0 to maximum - 1 do
678 let th = gen_0_lt_bi i in
679 let name = names_array.(i) in
680 Hashtbl.add th_lt0_table name th
681 done;;
682
683
684 (* Generates the theorem |- bi(m) < bj(n) <=> m <= n (or m < n) *)
685 let gen_bi_lt_bj i j =
686 let bim = mk_comb (const_array.(i), m_var_num) in
687 let bjn = mk_comb (const_array.(j), n_var_num) in
688 let lt_tm = mk_binop lt_op_num bim bjn in
689 let rhs =
690 if i >= j then
691 mk_binop lt_op_num m_var_num n_var_num
692 else
693 mk_binop le_op_num m_var_num n_var_num in
694 prove(mk_eq(lt_tm, rhs), REWRITE_TAC[def_array.(i); def_array.(j)] THEN ARITH_TAC);;
695
696 (* Given a theorem |- bi(m) < bj(n) <=> P m n, generates the theorem
697 |- SUC(bi(m)) < SUC(bj(n)) <=> P m n *)
698 let gen_next_lt_thm th =
699 let ltm, n_tm = (dest_comb o lhand o concl) th in
700 let m_tm = rand ltm in
701 let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] SUC_LT_THM in
702 let suc_m = raw_suc_conv_hash (mk_comb (suc_op_num, m_tm)) in
703 let suc_n = raw_suc_conv_hash (mk_comb (suc_op_num, n_tm)) in
704 let th1 = SYM (MK_COMB ((AP_TERM lt_op_num suc_m), suc_n)) in
705 TRANS (TRANS th1 th0) th;;
706
707 let th_lt_table = Hashtbl.create (maximum * maximum);;
708
709 for i = 0 to maximum - 1 do
710 let th = ref (gen_bi_lt_bj 0 i) in
711 let name_left = names_array.(0) and
712 name_right = names_array.(i) in
713 let _ = Hashtbl.add th_lt_table (name_left ^ name_right) !th in
714
715 for k = 1 to maximum - i - 1 do
716 let x = k and y = i + k in
717 let name_left = names_array.(x) and
718 name_right = names_array.(y) in
719 th := gen_next_lt_thm (!th);
720 Hashtbl.add th_lt_table (name_left ^ name_right) !th
721 done;
722 done;;
723
724 for i = 1 to maximum - 1 do
725 let th = ref (gen_bi_lt_bj i 0) in
726 let name_left = names_array.(i) and
727 name_right = names_array.(0) in
728 let _ = Hashtbl.add th_lt_table (name_left ^ name_right) !th in
729
730 for k = 1 to maximum - i - 1 do
731 let x = i + k and y = k in
732 let name_left = names_array.(x) and
733 name_right = names_array.(y) in
734 th := gen_next_lt_thm (!th);
735 Hashtbl.add th_lt_table (name_left ^ name_right) !th
736 done;
737 done;;
738
739 (* LE tables *)
740
741 (* Generates the theorem |- bi(n) <= _0 <=> F (or |- b0(n) <= _0 <=> n <= _0) *)
742 let gen_bi_le_0 i =
743 let bin = mk_comb (const_array.(i), n_var_num) in
744 let lt_tm = mk_binop le_op_num bin zero_num in
745 if i > 0 then
746 (PURE_REWRITE_RULE[NUMERAL] o prove)(mk_eq(lt_tm, f_const), REWRITE_TAC[def_array.(i)] THEN ARITH_TAC)
747 else
748 (PURE_REWRITE_RULE[NUMERAL] o prove)(mk_eq(lt_tm, `n <= 0`), REWRITE_TAC[B0_EXPLICIT] THEN ARITH_TAC);;
749
750 let th_le0_table = Hashtbl.create maximum;;
751 for i = 0 to maximum - 1 do
752 let th = gen_bi_le_0 i in
753 let name = names_array.(i) in
754 Hashtbl.add th_le0_table name th
755 done;;
756
757
758 (* Generates the theorem |- bi(m) <= bj(n) <=> m <= n (or m < n) *)
759 let gen_bi_le_bj i j =
760 let bim = mk_comb (const_array.(i), m_var_num) in
761 let bjn = mk_comb (const_array.(j), n_var_num) in
762 let lt_tm = mk_binop le_op_num bim bjn in
763 let rhs =
764 if i > j then
765 mk_binop lt_op_num m_var_num n_var_num
766 else
767 mk_binop le_op_num m_var_num n_var_num in
768 prove(mk_eq(lt_tm, rhs), REWRITE_TAC[def_array.(i); def_array.(j)] THEN ARITH_TAC);;
769
770 (* Given the theorem |- bi(m) <= bj(n) <=> P m n, generates the theorem
771 |- SUC(bi(m)) <= SUC(bj(n)) <=> P m n *)
772 let gen_next_le_thm th =
773 let ltm, n_tm = (dest_comb o lhand o concl) th in
774 let m_tm = rand ltm in
775 let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] SUC_LE_THM in
776 let suc_m = raw_suc_conv_hash (mk_comb (suc_op_num, m_tm)) in
777 let suc_n = raw_suc_conv_hash (mk_comb (suc_op_num, n_tm)) in
778 let th1 = SYM (MK_COMB ((AP_TERM le_op_num suc_m), suc_n)) in
779 TRANS (TRANS th1 th0) th;;
780
781 let th_le_table = Hashtbl.create (maximum * maximum);;
782
783 for i = 0 to maximum - 1 do
784 let th = ref (gen_bi_le_bj 0 i) in
785 let name_left = names_array.(0) and
786 name_right = names_array.(i) in
787 let _ = Hashtbl.add th_le_table (name_left ^ name_right) !th in
788
789 for k = 1 to maximum - i - 1 do
790 let x = k and y = i + k in
791 let name_left = names_array.(x) and
792 name_right = names_array.(y) in
793 th := gen_next_le_thm (!th);
794 Hashtbl.add th_le_table (name_left ^ name_right) !th
795 done;
796 done;;
797
798 for i = 1 to maximum - 1 do
799 let th = ref (gen_bi_le_bj i 0) in
800 let name_left = names_array.(i) and
801 name_right = names_array.(0) in
802 let _ = Hashtbl.add th_le_table (name_left ^ name_right) !th in
803
804 for k = 1 to maximum - i - 1 do
805 let x = i + k and y = k in
806 let name_left = names_array.(x) and
807 name_right = names_array.(y) in
808 th := gen_next_le_thm (!th);
809 Hashtbl.add th_le_table (name_left ^ name_right) !th
810 done;
811 done;;
812
813 (* Conversions *)
814
815 let rec raw_lt_hash_conv tm =
816 let ltm, rtm = dest_comb tm in
817 let ltm = rand ltm in
818 if is_const rtm then
819 (* n < _0 <=> F *)
820 INST[ltm, n_var_num] LT_n_0
821 else
822 if is_const ltm then
823 (* _0 < Bi(n) *)
824 let bn_tm, n_tm = dest_comb rtm in
825 let cbn = (fst o dest_const) bn_tm in
826 let th0 = INST[n_tm, n_var_num] (Hashtbl.find th_lt0_table cbn) in
827 if cbn = b0_name then
828 let th1 = raw_lt_hash_conv (rand (concl th0)) in
829 TRANS th0 th1
830 else
831 th0
832 else
833 (* Bi(n) < Bj(m) *)
834 let bm_tm, m_tm = dest_comb ltm in
835 let bn_tm, n_tm = dest_comb rtm in
836 let cbm = (fst o dest_const) bm_tm in
837 let cbn = (fst o dest_const) bn_tm in
838 let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] (Hashtbl.find th_lt_table (cbm^cbn)) in
839 let op = (fst o dest_const o rator o rator o rand o concl) th0 in
840 let th1 =
841 if op = "<" then
842 raw_lt_hash_conv (rand (concl th0))
843 else
844 raw_le_hash_conv (rand (concl th0)) in
845 TRANS th0 th1 and
846
847 raw_le_hash_conv tm =
848 let ltm, rtm = dest_comb tm in
849 let ltm = rand ltm in
850 if is_const ltm then
851 (* _0 <= n <=> T *)
852 INST[rtm, n_var_num] LE_0_n
853 else
854 if is_const rtm then
855 (* Bi(n) <= _0 *)
856 let bn_tm, n_tm = dest_comb ltm in
857 let cbn = (fst o dest_const) bn_tm in
858 let th0 = INST[n_tm, n_var_num] (Hashtbl.find th_le0_table cbn) in
859 if cbn = b0_name then
860 let th1 = raw_le_hash_conv (rand (concl th0)) in
861 TRANS th0 th1
862 else
863 th0
864 else
865 (* Bi(n) <= Bj(m) *)
866 let bm_tm, m_tm = dest_comb ltm in
867 let bn_tm, n_tm = dest_comb rtm in
868 let cbm = (fst o dest_const) bm_tm in
869 let cbn = (fst o dest_const) bn_tm in
870 let th0 = INST[m_tm, m_var_num; n_tm, n_var_num] (Hashtbl.find th_le_table (cbm^cbn)) in
871 let op = (fst o dest_const o rator o rator o rand o concl) th0 in
872 let th1 =
873 if op = "<" then
874 raw_lt_hash_conv (rand (concl th0))
875 else
876 raw_le_hash_conv (rand (concl th0)) in
877 TRANS th0 th1;;
878
879 let NUM_LT_HASH_CONV tm =
880 let atm, rtm = dest_comb tm in
881 let ltm = rand atm in
882 let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] LT_NUM in
883 let rtm = rand(concl th) in
884 TRANS th (raw_lt_hash_conv rtm);;
885
886 let NUM_LE_HASH_CONV tm =
887 let atm, rtm = dest_comb tm in
888 let ltm = rand atm in
889 let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] LE_NUM in
890 let rtm = rand(concl th) in
891 TRANS th (raw_le_hash_conv rtm);;
892
893
894 (**************************************)
895 (* ADD_CONV *)
896
897 (* ADD theorems *)
898
899 let ADD_NUM = (REWRITE_RULE[GSYM num_def] o prove)
900 (`NUMERAL m + NUMERAL n = NUMERAL (m + n)`, REWRITE_TAC[NUMERAL]);;
901
902
903 let CADD_0_n = prove(`SUC (_0 + n) = SUC n`, REWRITE_TAC[ADD_0_n]);;
904 let CADD_n_0 = prove(`SUC (n + _0) = SUC n`, REWRITE_TAC[ADD_n_0]);;
905
906 (* B0 (SUC n) = B0 n + maximum *)
907 let B0_SUC = prove(mk_eq(mk_comb(b0_const, mk_comb(suc_op_num, n_var_num)),
908 mk_binop add_op_num max_const (mk_comb(b0_const, n_var_num))),
909 REWRITE_TAC [B0_EXPLICIT] THEN ARITH_TAC);;
910
911 let B0_ADD = prove(mk_eq(mk_binop add_op_num (mk_comb(b0_const, m_var_num)) (mk_comb(b0_const, n_var_num)),
912 mk_comb(b0_const, mk_binop add_op_num m_var_num n_var_num)),
913 REWRITE_TAC[B0_EXPLICIT] THEN ARITH_TAC);;
914
915 let SUC_ADD_RIGHT = prove(`SUC(m + n) = m + SUC n`, ARITH_TAC);;
916
917
918 (* Generate all theorems iteratively *)
919 let th_add_right_next th =
920 let lhs, rhs = dest_eq(concl th) in
921 let ltm, rtm = dest_comb rhs in
922 let cn = fst(dest_const ltm) in
923 let suc_th = AP_TERM suc_op_num th in
924 let th_rhs = INST[rtm, n_var_num] (Hashtbl.find th_suc_table cn) in
925 let ltm, rarg = dest_comb lhs in
926 let larg = rand ltm in
927 let th1 = INST[larg, m_var_num; rarg, n_var_num] SUC_ADD_RIGHT in
928 let cn = fst(dest_const(rator rarg)) in
929 let th2 = Hashtbl.find th_suc_table cn in
930 let th_lhs = TRANS th1 (AP_TERM ltm th2) in
931 TRANS (TRANS (SYM th_lhs) suc_th) th_rhs;;
932
933 let th_add_array = Array.make (maximum * maximum) (REFL zero_const);;
934
935 for i = 0 to maximum - 1 do
936 let th0 =
937 if i = 0 then
938 B0_ADD
939 else
940 INST[n_var_num, m_var_num; m_var_num, n_var_num]
941 (ONCE_REWRITE_RULE[ADD_AC] th_add_array.(i)) in
942 let _ = th_add_array.(i * maximum) <- th0 in
943
944 for j = 1 to maximum - 1 do
945 th_add_array.(i * maximum + j) <- th_add_right_next th_add_array.(i * maximum + j - 1)
946 done;
947 done;;
948
949 (* SUC (B_i(m) + B_j(n)) = B_p(...) *)
950 let th_cadd i j =
951 let add_th = th_add_array.(i * maximum + j) in
952 let th0 = AP_TERM suc_op_num add_th in
953 let ltm, rtm = dest_comb(rand(concl th0)) in
954 let ltm, rtm = dest_comb rtm in
955 let cn = fst(dest_const ltm) in
956 let suc_th = INST[rtm, n_var_num] (Hashtbl.find th_suc_table cn) in
957 TRANS th0 suc_th;;
958
959 let th_cadd_array = Array.make (maximum * maximum) (REFL zero_const);;
960
961 for i = 0 to maximum - 1 do
962 for j = 0 to maximum - 1 do
963 th_cadd_array.(i * maximum + j) <- th_cadd i j
964 done;
965 done;;
966
967 let th_add_table = Hashtbl.create (maximum * maximum);;
968
969 for i = 0 to maximum - 1 do
970 for j = 0 to maximum - 1 do
971 let name = names_array.(i) ^ names_array.(j) in
972 let th = th_add_array.(i * maximum + j) in
973 let cflag = (i + j >= maximum) in
974 Hashtbl.add th_add_table name (th, cflag)
975 done;
976 done;;
977
978 let th_cadd_table = Hashtbl.create (maximum * maximum);;
979
980 for i = 0 to maximum - 1 do
981 for j = 0 to maximum - 1 do
982 let name = names_array.(i) ^ names_array.(j) in
983 let th = th_cadd_array.(i * maximum + j) in
984 let cflag = (i + j + 1 >= maximum) in
985 Hashtbl.add th_cadd_table name (th, cflag)
986 done;
987 done;;
988
989 (* ADD conversion *)
990 let rec raw_add_conv_hash tm =
991 let atm,rtm = dest_comb tm in
992 let ltm = rand atm in
993 if ltm = zero_const then
994 INST [rtm,n_var_num] ADD_0_n
995 else if rtm = zero_const then
996 INST [ltm,n_var_num] ADD_n_0
997 else
998 let lbit,larg = dest_comb ltm
999 and rbit,rarg = dest_comb rtm in
1000 let name = fst(dest_const lbit) ^ fst(dest_const rbit) in
1001 let th0, cflag = Hashtbl.find th_add_table name in
1002 let th = INST [larg, m_var_num; rarg, n_var_num] th0 in
1003 let ltm, rtm = dest_comb(rand(concl th)) in
1004 if cflag then
1005 TRANS th (AP_TERM ltm (raw_adc_conv_hash rtm))
1006 else
1007 TRANS th (AP_TERM ltm (raw_add_conv_hash rtm))
1008 and raw_adc_conv_hash tm =
1009 let atm,rtm = dest_comb (rand tm) in
1010 let ltm = rand atm in
1011 if ltm = zero_const then
1012 let th = INST [rtm,n_var_num] CADD_0_n in
1013 TRANS th (raw_suc_conv_hash (rand(concl th)))
1014 else if rtm = zero_const then
1015 let th = INST [ltm,n_var_num] CADD_n_0 in
1016 TRANS th (raw_suc_conv_hash (rand(concl th)))
1017 else
1018 let lbit,larg = dest_comb ltm
1019 and rbit,rarg = dest_comb rtm in
1020 let name = fst(dest_const lbit) ^ fst(dest_const rbit) in
1021 let th0, cflag = Hashtbl.find th_cadd_table name in
1022 let th = INST [larg, m_var_num; rarg, n_var_num] th0 in
1023 let ltm, rtm = dest_comb(rand(concl th)) in
1024 if cflag then
1025 TRANS th (AP_TERM ltm (raw_adc_conv_hash rtm))
1026 else
1027 TRANS th (AP_TERM ltm (raw_add_conv_hash rtm));;
1028
1029 let NUM_ADD_HASH_CONV tm =
1030 let atm, rtm = dest_comb tm in
1031 let ltm = rand atm in
1032 let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] ADD_NUM in
1033 let ltm, rtm = dest_comb(rand(concl th)) in
1034 TRANS th (AP_TERM ltm (raw_add_conv_hash rtm));;
1035
1036 (********************************)
1037 (* Subtraction *)
1038
1039 let SUB_NUM = prove(mk_eq(mk_binop sub_op_num (mk_comb (num_const, m_var_num)) (mk_comb (num_const, n_var_num)),
1040 mk_comb(num_const, mk_binop sub_op_num m_var_num n_var_num)),
1041 REWRITE_TAC[num_def; NUMERAL]);;
1042
1043 let SUB_lemma1 = (UNDISCH_ALL o ARITH_RULE) `n + t = m ==> m - n = t:num`;;
1044 let SUB_lemma2 = (UNDISCH_ALL o REWRITE_RULE[NUMERAL] o ARITH_RULE) `m + t = n ==> m - n = 0`;;
1045 let LE_lemma = (UNDISCH_ALL o ARITH_RULE) `n + t = m ==> n <= m:num`;;
1046
1047 let raw_sub_hash_conv tm =
1048 let ltm, n_tm = dest_comb tm in
1049 let m_tm = rand ltm in
1050 let m = raw_dest_hash m_tm in
1051 let n = raw_dest_hash n_tm in
1052 let t = m -/ n in
1053 if t >=/ num_0 then
1054 let t_tm = rand (mk_numeral_array t) in
1055 let th0 = INST[n_tm, n_var_num; t_tm, t_var_num; m_tm, m_var_num] SUB_lemma1 in
1056 let th_add = raw_add_conv_hash (mk_binop add_op_num n_tm t_tm) in
1057 MY_PROVE_HYP th_add th0
1058 else
1059 let t_tm = rand (mk_numeral_array (Num.abs_num t)) in
1060 let th0 = INST[m_tm, m_var_num; t_tm, t_var_num; n_tm, n_var_num] SUB_lemma2 in
1061 let th_add = raw_add_conv_hash (mk_binop add_op_num m_tm t_tm) in
1062 MY_PROVE_HYP th_add th0;;
1063
1064 (* Returns either (tm1 - tm2, tm2 <= tm1) or (tm2 - tm1, tm1 <= tm2) *)
1065 let raw_sub_and_le_hash_conv tm1 tm2 =
1066 let m = raw_dest_hash tm1 in
1067 let n = raw_dest_hash tm2 in
1068 let t = m -/ n in
1069 if t >=/ num_0 then
1070 let t_tm = rand (mk_numeral_array t) in
1071 let inst = INST[tm2, n_var_num; t_tm, t_var_num; tm1, m_var_num] in
1072 let th_sub = inst SUB_lemma1 in
1073 let th_le = inst LE_lemma in
1074 let th_add = raw_add_conv_hash (mk_binop add_op_num tm2 t_tm) in
1075 (MY_PROVE_HYP th_add th_sub, MY_PROVE_HYP th_add th_le)
1076 else
1077 let t_tm = rand (mk_numeral_array (Num.abs_num t)) in
1078 let inst = INST[tm2, m_var_num; t_tm, t_var_num; tm1, n_var_num] in
1079 let th_sub = inst SUB_lemma1 in
1080 let th_le = inst LE_lemma in
1081 let th_add = raw_add_conv_hash (mk_binop add_op_num tm1 t_tm) in
1082 (MY_PROVE_HYP th_add th_sub, MY_PROVE_HYP th_add th_le);;
1083
1084 let NUM_SUB_HASH_CONV tm =
1085 let atm, rtm = dest_comb tm in
1086 let ltm = rand atm in
1087 let th = INST [rand ltm, m_var_num; rand rtm, n_var_num] SUB_NUM in
1088 let ltm, rtm = dest_comb(rand(concl th)) in
1089 TRANS th (AP_TERM ltm (raw_sub_hash_conv rtm));;
1090
1091
1092 (********************************)
1093 (* Multiplication *)
1094
1095 let MUL_NUM = prove(mk_eq(mk_binop mul_op_num (mk_comb(num_const, m_var_num)) (mk_comb(num_const, n_var_num)),
1096 mk_comb(num_const, mk_binop mul_op_num m_var_num n_var_num)),
1097 REWRITE_TAC[num_def; NUMERAL]);;
1098
1099 let MUL_0_n = prove(`_0 * n = _0`, ONCE_REWRITE_TAC[GSYM NUM_THM] THEN
1100 ONCE_REWRITE_TAC[GSYM MUL_NUM] THEN REWRITE_TAC[num_def] THEN
1101 REWRITE_TAC[MULT_CLAUSES]);;
1102
1103 let MUL_n_0 = ONCE_REWRITE_RULE[MULT_AC] MUL_0_n;;
1104
1105 let MUL_1_n, MUL_n_1 =
1106 let one_const = mk_comb (const_array.(1), zero_num) in
1107 let cond = mk_eq(mk_binop mul_op_num one_const n_var_num, n_var_num) in
1108 let th = (REWRITE_RULE[NUMERAL] o prove)(cond, REWRITE_TAC[def_array.(1)] THEN ARITH_TAC) in
1109 th, ONCE_REWRITE_RULE[MULT_AC] th;;
1110
1111 let MUL_B0_t = prove(mk_eq(mk_binop mul_op_num (mk_comb(b0_const, n_var_num)) t_var_num,
1112 mk_comb(b0_const, mk_binop mul_op_num n_var_num t_var_num)),
1113 REWRITE_TAC[def_array.(0)] THEN ARITH_TAC);;
1114
1115 let MUL_t_B0 = ONCE_REWRITE_RULE[MULT_AC] MUL_B0_t;;
1116
1117 let MUL_SUC_RIGHT = prove(`m * SUC(n) = m * n + m`, ARITH_TAC);;
1118
1119 (* Multiplication table *)
1120 let mul_th_next_right th =
1121 let ltm, rtm = dest_comb(rand(rator(concl th))) in
1122 let mtm = rand ltm in
1123 let th0 = INST[mtm, m_var_num; rtm, n_var_num] MUL_SUC_RIGHT in
1124 let th1 = AP_THM (AP_TERM add_op_num th) mtm in
1125 let sum_th = raw_add_conv_hash (rand(concl th1)) in
1126 let th2 = TRANS (TRANS th0 th1) sum_th in
1127 let cn = fst(dest_const (rator rtm)) in
1128 let th_suc = INST[zero_const, n_var_num] (Hashtbl.find th_suc_table cn) in
1129 let th3 = AP_TERM (mk_comb (mul_op_num, mtm)) th_suc in
1130 TRANS (SYM th3) th2;;
1131
1132 let mul_array = Array.make (maximum * maximum) (REFL zero_const);;
1133 for i = 1 to maximum - 1 do
1134 let th1 = INST[mk_comb(const_array.(i), zero_const), n_var_num] MUL_n_1 in
1135 let _ = mul_array.(i * maximum + 1) <- th1 in
1136
1137 for j = 2 to maximum - 1 do
1138 mul_array.(i * maximum + j) <- mul_th_next_right mul_array.(i * maximum + j - 1)
1139 done;
1140 done;;
1141
1142 let mul_table = Hashtbl.create (maximum * maximum);;
1143 for i = 1 to maximum - 1 do
1144 for j = 1 to maximum - 1 do
1145 Hashtbl.add mul_table (names_array.(i) ^ names_array.(j)) mul_array.(i * maximum + j)
1146 done;
1147 done;;
1148
1149 (* General multiplication theorem *)
1150 let prod_lemma =
1151 let mul (a,b) = mk_binop mul_op_num a b and
1152 add (a,b) = mk_binop add_op_num a b in
1153 let lhs = mul(add(t_var_num, mk_comb(b0_const, m_var_num)),
1154 add(r_var_num, mk_comb(b0_const, n_var_num))) in
1155 let rhs = add(mul(t_var_num, r_var_num),
1156 mk_comb(b0_const, add(mk_comb(b0_const, mul(m_var_num, n_var_num)),
1157 add(mul(m_var_num, r_var_num),
1158 mul(n_var_num, t_var_num))))) in
1159 prove(mk_eq(lhs, rhs),
1160 REWRITE_TAC[LEFT_ADD_DISTRIB; RIGHT_ADD_DISTRIB] THEN
1161 REWRITE_TAC[MUL_B0_t; MUL_t_B0] THEN
1162 ONCE_REWRITE_TAC[GSYM ADD_ASSOC] THEN
1163 REWRITE_TAC[th_add_array.(0)] THEN
1164 REWRITE_TAC[ADD_AC; MULT_AC]);;
1165
1166 let ADD_ASSOC' = SPEC_ALL ADD_ASSOC;;
1167
1168 let dest_op tm =
1169 let ltm, rtm = dest_comb tm in
1170 rand ltm, rtm;;
1171
1172 (* B_i(m) * B_j(n) = B_p(B_q(m * n) + m * B_j(0) + n * B_i(0))
1173 where B_p(B_q(0)) = i * j *)
1174 let gen_mul_thm i j =
1175 let bi0 = mk_comb(const_array.(i), zero_const) and
1176 bj0 = mk_comb(const_array.(j), zero_const) in
1177 let def_i = INST[m_var_num, n_var_num] def_thm_array.(i) in
1178 let def_j = def_thm_array.(j) in
1179 let th0 = MK_COMB(AP_TERM mul_op_num def_i, def_j) in
1180 let th1 = TRANS th0 (INST[bi0, t_var_num; bj0, r_var_num] prod_lemma) in
1181 let mul_th = mul_array.(i * maximum + j) in
1182 let larg, rarg = dest_op (rand (concl th1)) in
1183 let th2 = TRANS th1 (AP_THM (AP_TERM add_op_num mul_th) rarg) in
1184 let larg = rand(concl mul_th) in
1185 let b_low, b_high = dest_comb larg in
1186 let rtm = rand(rarg) in
1187 let th_add = INST[b_high, m_var_num; rtm, n_var_num]
1188 (fst(Hashtbl.find th_add_table (fst(dest_const b_low)^b0_name))) in
1189 if i * j < maximum then
1190 let ltm, rtm = dest_op(rand(rand(concl th_add))) in
1191 let add_0 = AP_TERM b_low (INST[rtm, n_var_num] ADD_0_n) in
1192 TRANS th2 (TRANS th_add add_0)
1193 else
1194 let larg, rtm = dest_op (rand(rand(concl th_add))) in
1195 let rarg, rtm = dest_op rtm in
1196 let th_assoc = INST[larg, m_var_num; rarg, n_var_num; rtm, p_var_num] ADD_ASSOC' in
1197 let mn = rand(rarg) in
1198 let b_high = rator b_high in
1199 let th_add2' = INST[zero_const, m_var_num; mn, n_var_num]
1200 (fst(Hashtbl.find th_add_table (fst(dest_const b_high)^b0_name))) in
1201 let add_0 = AP_TERM b_high (INST[mn, n_var_num] ADD_0_n) in
1202 let th_add2 = TRANS th_add2' add_0 in
1203 let th3 = TRANS th_assoc (AP_THM (AP_TERM add_op_num th_add2) rtm) in
1204 let th4 = TRANS th_add (AP_TERM b_low th3) in
1205 TRANS th2 th4;;
1206
1207 let gen_mul_table = Hashtbl.create (maximum * maximum);;
1208
1209 for i = 1 to maximum - 1 do
1210 for j = 1 to maximum - 1 do
1211 let name = names_array.(i) ^ names_array.(j) in
1212 Hashtbl.add gen_mul_table name (gen_mul_thm i j)
1213 done;
1214 done;;
1215
1216 (* B_i(m) * B_j(0) = B_p(B_q(0) + m * B_j(0))
1217 where i * j = B_p(B_q(0)) *)
1218 let mul1_right_th i j =
1219 let th0 = INST[zero_const, n_var_num]
1220 (Hashtbl.find gen_mul_table (names_array.(i)^names_array.(j))) in
1221 let b_low, rtm = dest_comb(rand(concl th0)) in
1222 let tm1, tm23 = dest_op rtm in
1223 let tm2p, tm3 = dest_comb tm23 in
1224 let tm3_th = INST[rand tm3, n_var_num] MUL_0_n in
1225 let tm2_th = INST[rand(tm2p), n_var_num] ADD_n_0 in
1226 let tm23_th = TRANS (AP_TERM tm2p tm3_th) tm2_th in
1227 let ltm, rtm = dest_comb tm1 in
1228 if (i * j < maximum) then
1229 let tm1_th = TRANS (AP_TERM ltm (INST[m_var_num, n_var_num] MUL_n_0)) B0_0 in
1230 let tm123_th' = TRANS (INST[tm23, n_var_num] ADD_0_n) tm23_th in
1231 let tm123_th = TRANS (AP_THM (AP_TERM add_op_num tm1_th) tm23) tm123_th' in
1232 TRANS th0 (AP_TERM b_low tm123_th)
1233 else
1234 let tm1_th = AP_TERM ltm (INST[m_var_num, n_var_num] MUL_n_0) in
1235 let tm123_th = MK_COMB(AP_TERM add_op_num tm1_th, tm23_th) in
1236 TRANS th0 (AP_TERM b_low tm123_th);;
1237
1238 (* B_j(0) * B_i(m) = B_p(B_q(0) + B_j(0) * B_i(m) *)
1239 let MULT_AC' = CONJUNCT1 MULT_AC;;
1240
1241 let mul1_left_th th =
1242 let lhs, rhs = dest_eq(concl th) in
1243 let ltm, rtm = dest_op lhs in
1244 let th_lhs = INST[ltm, n_var_num; rtm, m_var_num] MULT_AC' in
1245 let btm, rtm = dest_comb rhs in
1246 let larg, rarg = dest_op rtm in
1247 if (is_comb larg) then
1248 let ltm, rtm = dest_op rarg in
1249 let th_rhs' = INST[ltm, m_var_num; rtm, n_var_num] MULT_AC' in
1250 let th_rhs = AP_TERM (mk_comb(add_op_num, larg)) th_rhs' in
1251 TRANS th_lhs (TRANS th (AP_TERM btm th_rhs))
1252 else
1253 let th_rhs = INST[larg, m_var_num; rarg, n_var_num] MULT_AC' in
1254 TRANS th_lhs (TRANS th (AP_TERM btm th_rhs));;
1255
1256 let mul1_right_th_table = Hashtbl.create (maximum * maximum);;
1257 let mul1_left_th_table = Hashtbl.create (maximum * maximum);;
1258
1259 for i = 1 to maximum - 1 do
1260 for j = 1 to maximum - 1 do
1261 let name_right = names_array.(i) ^ names_array.(j) in
1262 let name_left = names_array.(j) ^ names_array.(i) in
1263 let th = mul1_right_th i j in
1264 let add_flag = (i * j >= maximum) in
1265 let _ = Hashtbl.add mul1_right_th_table name_right (add_flag, th) in
1266 Hashtbl.add mul1_left_th_table name_left (add_flag, mul1_left_th th)
1267 done;
1268 done;;
1269
1270
1271 (******************************************************)
1272 (* Conversions *)
1273
1274 (* Multiplies arg and (tm = tmname(_0)) *)
1275 let rec raw_mul1_right_hash arg tm tmname =
1276 if arg = zero_const then
1277 INST [tm, n_var_num] MUL_0_n
1278 else
1279 let btm, mtm = dest_comb arg in
1280 let cn = fst(dest_const btm) in
1281 if (cn = b0_name) then
1282 let th = INST[mtm, n_var_num; tm, t_var_num] MUL_B0_t in
1283 TRANS th (AP_TERM b0_const (raw_mul1_right_hash mtm tm tmname))
1284 else
1285 let name = cn ^ tmname in
1286 if (mtm = zero_const) then
1287 Hashtbl.find mul_table name
1288 else
1289 let add_flag, th' = Hashtbl.find mul1_right_th_table name in
1290 let th = INST[mtm, m_var_num] th' in
1291 if add_flag then
1292 let ltm, rtm = dest_comb(rand(concl th)) in
1293 let lplus, rarg = dest_comb rtm in
1294 let th2 = AP_TERM lplus (raw_mul1_right_hash mtm tm tmname) in
1295 let th_add = raw_add_conv_hash (rand(concl th2)) in
1296 TRANS th (AP_TERM ltm (TRANS th2 th_add))
1297 else
1298 let ltm = rator(rand(concl th)) in
1299 let th2 = AP_TERM ltm (raw_mul1_right_hash mtm tm tmname) in
1300 TRANS th th2;;
1301
1302 (* Multiplies (tm = tmname(_0)) and arg *)
1303 let rec raw_mul1_left_hash tm tmname arg =
1304 if arg = zero_const then
1305 INST [tm, n_var_num] MUL_n_0
1306 else
1307 let btm, mtm = dest_comb arg in
1308 let cn = fst(dest_const btm) in
1309 if (cn = b0_name) then
1310 let th = INST[mtm, n_var_num; tm, t_var_num] MUL_t_B0 in
1311 TRANS th (AP_TERM b0_const (raw_mul1_left_hash tm tmname mtm))
1312 else
1313 let name = tmname ^ cn in
1314 if (mtm = zero_const) then
1315 Hashtbl.find mul_table name
1316 else
1317 let add_flag, th' = Hashtbl.find mul1_left_th_table name in
1318 let th = INST[mtm, m_var_num] th' in
1319 if add_flag then
1320 let ltm, rtm = dest_comb(rand(concl th)) in
1321 let lplus, rarg = dest_comb rtm in
1322 let th2 = AP_TERM lplus (raw_mul1_left_hash tm tmname mtm) in
1323 let th_add = raw_add_conv_hash (rand(concl th2)) in
1324 TRANS th (AP_TERM ltm (TRANS th2 th_add))
1325 else
1326 let ltm = rator(rand(concl th)) in
1327 let th2 = AP_TERM ltm (raw_mul1_left_hash tm tmname mtm) in
1328 TRANS th th2;;
1329
1330 (* Computes B_i(m) * B_j(n) *)
1331 let rec raw_mul_conv_hash tm =
1332 let larg, rarg = dest_comb tm in
1333 let larg = rand larg in
1334 if larg = zero_const then
1335 INST [rarg, n_var_num] MUL_0_n
1336 else if rarg = zero_const then
1337 INST [larg, n_var_num] MUL_n_0
1338 else
1339
1340 let lbtm, mtm = dest_comb larg in
1341 let lcn = fst(dest_const lbtm) in
1342 if (lcn = b0_name) then
1343 let th = INST[rarg, t_var_num; mtm, n_var_num] MUL_B0_t in
1344 let ltm, rtm = dest_comb(rand(concl th)) in
1345 TRANS th (AP_TERM ltm (raw_mul_conv_hash rtm))
1346 else
1347 let rbtm, ntm = dest_comb rarg in
1348 let rcn = fst(dest_const rbtm) in
1349 if (rcn = b0_name) then
1350 let th = INST[larg, t_var_num; ntm, n_var_num] MUL_t_B0 in
1351 let ltm, rtm = dest_comb(rand(concl th)) in
1352 TRANS th (AP_TERM ltm (raw_mul_conv_hash rtm))
1353 else
1354
1355 if (ntm = zero_const) then
1356 if (mtm = zero_const) then
1357 Hashtbl.find mul_table (lcn ^ rcn)
1358 else
1359 raw_mul1_right_hash larg (mk_comb(rbtm, zero_const)) rcn
1360 else if (mtm = zero_const) then
1361 raw_mul1_left_hash (mk_comb(lbtm, zero_const)) lcn rarg
1362 else
1363
1364 let th0 = INST[mtm, m_var_num; ntm, n_var_num]
1365 (Hashtbl.find gen_mul_table (lcn ^ rcn)) in
1366 let b_low, expr = dest_comb(rand(concl th0)) in
1367 let ltm, rsum = dest_comb expr in
1368 let b_high, mul0 = dest_comb (rand ltm) in
1369 let th_mul0 = raw_mul_conv_hash mul0 in
1370 let th_mul1 = raw_mul1_right_hash mtm (mk_comb(rbtm, zero_const)) rcn in
1371 let th_mul2 = raw_mul1_right_hash ntm (mk_comb(lbtm, zero_const)) lcn in
1372 let th_larg = AP_TERM add_op_num (AP_TERM b_high th_mul0) in
1373 let th_rarg = MK_COMB(AP_TERM add_op_num th_mul1, th_mul2) in
1374
1375 let add_rarg = TRANS th_rarg (raw_add_conv_hash (rand(concl th_rarg))) in
1376 let add_th = MK_COMB (th_larg, add_rarg) in
1377 let add = TRANS add_th (raw_add_conv_hash (rand(concl add_th))) in
1378
1379 TRANS th0 (AP_TERM b_low add);;
1380
1381 (* The main multiplication conversion *)
1382 let NUM_MULT_HASH_CONV tm =
1383 let ltm, rtm = dest_comb tm in
1384 let larg, rarg = rand (rand ltm), rand rtm in
1385 let th0 = INST[larg, m_var_num; rarg, n_var_num] MUL_NUM in
1386 if (rand(rator(concl th0)) <> tm) then
1387 failwith "NUM_MULT_HASH_CONV"
1388 else
1389 let rtm = rand(rand(concl th0)) in
1390 let th = raw_mul_conv_hash rtm in
1391 TRANS th0 (AP_TERM num_const th);;
1392
1393
1394 (************************************)
1395 (* DIV *)
1396
1397 let DIV_NUM = prove(mk_eq(mk_binop div_op_num (mk_comb(num_const, m_var_num)) (mk_comb(num_const, n_var_num)),
1398 mk_comb(num_const, mk_binop div_op_num m_var_num n_var_num)),
1399 REWRITE_TAC[num_def; NUMERAL]);;
1400
1401 let DIV_UNIQ' = (UNDISCH_ALL o
1402 PURE_ONCE_REWRITE_RULE[ARITH_RULE `a < b <=> (a < b:num <=> T)`] o
1403 ONCE_REWRITE_RULE[ARITH_RULE `m = q * n + r <=> q * n + r = m:num`] o
1404 REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL) DIV_UNIQ;;
1405
1406 (* Computes m DIV n *)
1407 let raw_div_hash_conv tm =
1408 let ltm, n_tm = dest_comb tm in
1409 let m_tm = rand ltm in
1410 let m = raw_dest_hash m_tm in
1411 let n = raw_dest_hash n_tm in
1412 let q = Num.quo_num m n and
1413 r = Num.mod_num m n in
1414 let q_tm = rand (mk_numeral_array q) and
1415 r_tm = rand (mk_numeral_array r) in
1416
1417 let qn_th = raw_mul_conv_hash (mk_binop mul_op_num q_tm n_tm) in
1418 let qn_tm = rand (concl qn_th) in
1419 let qnr_th = raw_add_conv_hash (mk_binop add_op_num qn_tm r_tm) in
1420 let th1 = TRANS (AP_THM (AP_TERM add_op_num qn_th) r_tm) qnr_th in
1421 let th2 = raw_lt_hash_conv (mk_binop lt_op_num r_tm n_tm) in
1422 let th0 = INST[r_tm, r_var_num; n_tm, n_var_num; m_tm, m_var_num; q_tm, q_var_num] DIV_UNIQ' in
1423 MY_PROVE_HYP th1 (MY_PROVE_HYP th2 th0);;
1424
1425 (* The main division conversion *)
1426 let NUM_DIV_HASH_CONV tm =
1427 let ltm, rtm = dest_comb tm in
1428 let larg, rarg = rand (rand ltm), rand rtm in
1429 let th0 = INST[larg, m_var_num; rarg, n_var_num] DIV_NUM in
1430 if (rand(rator(concl th0)) <> tm) then
1431 failwith "NUM_DIV_HASH_CONV"
1432 else
1433 let rtm = rand(rand(concl th0)) in
1434 let th = raw_div_hash_conv rtm in
1435 TRANS th0 (AP_TERM num_const th);;
1436
1437
1438 (*********************************************)
1439 (* EVEN_CONV, ODD_CONV *)
1440
1441 let even_const = `EVEN` and
1442 odd_const = `ODD` and
1443 eq_const = `<=>`;;
1444
1445 let EVEN_NUM = (REWRITE_RULE[GSYM num_def] o prove)
1446 (`EVEN (NUMERAL n) <=> EVEN n`, REWRITE_TAC[NUMERAL]);;
1447
1448 let ODD_NUM = (REWRITE_RULE[GSYM num_def] o prove)
1449 (`ODD (NUMERAL n) <=> ODD n`, REWRITE_TAC[NUMERAL]);;
1450
1451 let EVEN_ZERO = prove(`EVEN _0 <=> T`, REWRITE_TAC[ARITH_EVEN]);;
1452 let ODD_ZERO = prove(`ODD _0 <=> F`, REWRITE_TAC[ARITH_ODD]);;
1453
1454
1455 let EVEN_B0 = prove(mk_eq(mk_comb(`EVEN`, mk_comb(b0_const, `n:num`)), `T`),
1456 REWRITE_TAC[B0_EXPLICIT; EVEN_MULT] THEN
1457 DISJ1_TAC THEN CONV_TAC NUM_EVEN_CONV);;
1458
1459
1460 let ODD_B0 = prove(mk_eq(mk_comb(`ODD`, mk_comb(b0_const, `n:num`)), `F`),
1461 REWRITE_TAC[NOT_ODD; EVEN_B0]);;
1462
1463 let EVEN_SUC_T = prove(`(EVEN (SUC n) <=> T) <=> (EVEN n <=> F)`, REWRITE_TAC[EVEN]);;
1464 let EVEN_SUC_F = prove(`(EVEN (SUC n) <=> F) <=> (EVEN n <=> T)`, REWRITE_TAC[EVEN]);;
1465
1466 let ODD_SUC_T = prove(`(ODD (SUC n) <=> T) <=> (ODD n <=> F)`, REWRITE_TAC[ODD]);;
1467 let ODD_SUC_F = prove(`(ODD (SUC n) <=> F) <=> (ODD n <=> T)`, REWRITE_TAC[ODD]);;
1468
1469 let next_even_th th =
1470 let ltm, rtm = dest_comb(concl th) in
1471 let b_tm = rand(rand ltm) in
1472 let suc_b = raw_suc_conv_hash (mk_comb (suc_op_num, b_tm)) in
1473 let flag = (fst o dest_const) rtm = "T" in
1474 let th0 = SYM (AP_TERM even_const suc_b) in
1475 let th1 = AP_THM (AP_TERM eq_const th0) (if flag then f_const else t_const) in
1476 let th2 = INST[b_tm, n_var_num] (if flag then EVEN_SUC_F else EVEN_SUC_T) in
1477 EQ_MP (SYM (TRANS th1 th2)) th;;
1478
1479 let next_odd_th th =
1480 let ltm, rtm = dest_comb(concl th) in
1481 let b_tm = rand(rand ltm) in
1482 let suc_b = raw_suc_conv_hash (mk_comb (suc_op_num, b_tm)) in
1483 let flag = (fst o dest_const) rtm = "T" in
1484 let th0 = SYM (AP_TERM odd_const suc_b) in
1485 let th1 = AP_THM (AP_TERM eq_const th0) (if flag then f_const else t_const) in
1486 let th2 = INST[b_tm, n_var_num] (if flag then ODD_SUC_F else ODD_SUC_T) in
1487 EQ_MP (SYM (TRANS th1 th2)) th;;
1488
1489 let even_thm_table = Hashtbl.create maximum;;
1490
1491 Hashtbl.add even_thm_table names_array.(0) EVEN_B0;;
1492
1493 for i = 1 to maximum - 1 do
1494 let th0 = next_even_th (Hashtbl.find even_thm_table names_array.(i - 1)) in
1495 Hashtbl.add even_thm_table names_array.(i) th0
1496 done;;
1497
1498 let odd_thm_table = Hashtbl.create maximum;;
1499 Hashtbl.add odd_thm_table names_array.(0) ODD_B0;;
1500
1501 for i = 1 to maximum - 1 do
1502 let th0 = next_odd_th (Hashtbl.find odd_thm_table names_array.(i - 1)) in
1503 Hashtbl.add odd_thm_table names_array.(i) th0
1504 done;;
1505
1506 let raw_even_hash_conv tm =
1507 let ltm, rtm = dest_comb tm in
1508 if ((fst o dest_const) ltm <> "EVEN") then
1509 failwith "raw_even_hash_conv: no EVEN"
1510 else
1511 if (is_const rtm) then
1512 EVEN_ZERO
1513 else
1514 let b_tm, n_tm = dest_comb rtm in
1515 let th0 = Hashtbl.find even_thm_table ((fst o dest_const) b_tm) in
1516 INST[n_tm, n_var_num] th0;;
1517
1518 let raw_odd_hash_conv tm =
1519 let ltm, rtm = dest_comb tm in
1520 if ((fst o dest_const) ltm <> "ODD") then
1521 failwith "raw_odd_hash_conv: no ODD"
1522 else
1523 if (is_const rtm) then
1524 ODD_ZERO
1525 else
1526 let b_tm, n_tm = dest_comb rtm in
1527 let th0 = Hashtbl.find odd_thm_table ((fst o dest_const) b_tm) in
1528 INST[n_tm, n_var_num] th0;;
1529
1530 let NUM_EVEN_HASH_CONV tm =
1531 let ltm, rtm = dest_comb tm in
1532 let th0 = INST[rand rtm, n_var_num] EVEN_NUM in
1533 let ltm, rtm = dest_comb(concl th0) in
1534 if (rand ltm <> tm) then
1535 failwith "NUM_EVEN_HASH_CONV"
1536 else
1537 let th1 = raw_even_hash_conv rtm in
1538 TRANS th0 th1;;
1539
1540 let NUM_ODD_HASH_CONV tm =
1541 let ltm, rtm = dest_comb tm in
1542 let th0 = INST[rand rtm, n_var_num] ODD_NUM in
1543 let ltm, rtm = dest_comb(concl th0) in
1544 if (rand ltm <> tm) then
1545 failwith "NUM_ODD_HASH_CONV"
1546 else
1547 let th1 = raw_odd_hash_conv rtm in
1548 TRANS th0 th1;;
1549
1550 end;;