Debian Codegraph @

Formal_ineqs/list/more_list.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 (* Additional list definitions and theorems *)
11 (* -------------------------------------------------------------------------- *)
12
13 module More_list = struct
14
15 (* definitions *)
16 let REVERSE_TABLE = define `(REVERSE_TABLE (f:num->A) 0 = []) /\
17 (REVERSE_TABLE f (SUC i) = CONS (f i) ( REVERSE_TABLE f i))`;;
18
19 let TABLE = new_definition `!(f:num->A) k. TABLE f k = REVERSE (REVERSE_TABLE f k)`;;
20
21 let l_seq = new_definition `l_seq n m = TABLE (\i. n + i) ((m + 1) - n)`;;
22
23 (* lemmas *)
24 let LENGTH_REVERSE_TABLE = prove(`!(f:num->A) n. LENGTH (REVERSE_TABLE f n) = n`,
25 GEN_TAC THEN INDUCT_TAC THEN ASM_REWRITE_TAC[REVERSE_TABLE; LENGTH]);;
26
27 let LENGTH_REVERSE = prove(`!(l:(A)list). LENGTH (REVERSE l) = LENGTH l`,
28 MATCH_MP_TAC list_INDUCT THEN REWRITE_TAC[REVERSE] THEN
29 REPEAT STRIP_TAC THEN
30 ASM_REWRITE_TAC[LENGTH_APPEND; LENGTH] THEN
31 ARITH_TAC);;
32
33 let LENGTH_TABLE = prove(`!(f:num->A) n. LENGTH (TABLE f n) = n`,
34 REWRITE_TAC[TABLE; LENGTH_REVERSE; LENGTH_REVERSE_TABLE]);;
35
36 let EL_TABLE = prove(`!(f:num->A) n i. i < n ==> EL i (TABLE f n) = f i`,
37 REPEAT GEN_TAC THEN SPEC_TAC (`n:num`, `n:num`) THEN
38 INDUCT_TAC THENL [ ARITH_TAC; ALL_TAC ] THEN
39 REWRITE_TAC[TABLE; REVERSE_TABLE; REVERSE; EL_APPEND] THEN
40 REWRITE_TAC[GSYM TABLE; LENGTH_TABLE] THEN
41 DISCH_TAC THEN COND_CASES_TAC THENL
42 [
43 FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[];
44 ALL_TAC
45 ] THEN
46 SUBGOAL_THEN `i = n:num` (fun th -> REWRITE_TAC[th]) THENL
47 [
48 POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN
49 ARITH_TAC;
50 ALL_TAC
51 ] THEN
52 REWRITE_TAC[ARITH_RULE `n - n = 0`; EL; HD]);;
53
54 let TABLE_0 = prove(`!(f:num->A). TABLE f 0 = []`,
55 REWRITE_TAC[TABLE; REVERSE_TABLE; REVERSE]);;
56
57 let TABLE_SUC = prove(`!(f:num->A) n. TABLE f (SUC n) = APPEND (TABLE f n) [f n]`,
58 GEN_TAC THEN INDUCT_TAC THEN REWRITE_TAC[TABLE; REVERSE_TABLE; REVERSE]);;
59
60 let LIST_EL_EQ = prove(`!ul vl:(A)list. ul = vl <=>
61 (LENGTH ul = LENGTH vl /\ (!j. j < LENGTH ul ==> EL j ul = EL j vl))`,
62 REPEAT STRIP_TAC THEN
63 EQ_TAC THEN STRIP_TAC THEN ASM_REWRITE_TAC[] THEN
64 POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN
65 SPEC_TAC (`vl:(A)list`, `vl:(A)list`) THEN SPEC_TAC (`ul:(A)list`, `ul:(A)list`) THEN
66 LIST_INDUCT_TAC THEN LIST_INDUCT_TAC THEN SIMP_TAC[LENGTH_EQ_NIL; EQ_SYM_EQ; LENGTH; ARITH_RULE `~(0 = SUC a)`] THEN
67 POP_ASSUM (fun th -> ALL_TAC) THEN
68 REWRITE_TAC[ARITH_RULE `SUC a = SUC b <=> a = b`] THEN
69 REPEAT STRIP_TAC THEN
70 FIRST_X_ASSUM (MP_TAC o SPEC `t':(A)list`) THEN
71 ASM_REWRITE_TAC[] THEN
72 ANTS_TAC THENL
73 [
74 REPEAT STRIP_TAC THEN
75 FIRST_X_ASSUM (MP_TAC o SPEC `SUC j`) THEN
76 ASM_REWRITE_TAC[ARITH_RULE `SUC a < SUC b <=> a < b`; EL; TL];
77 ALL_TAC
78 ] THEN
79 DISCH_TAC THEN
80 FIRST_X_ASSUM (MP_TAC o SPEC `0`) THEN
81 ASM_SIMP_TAC[ARITH_RULE `0 < SUC a`; EL; HD]);;
82
83
84 let LENGTH_L_SEQ = prove(`LENGTH (l_seq n m) = (m + 1) - n`, REWRITE_TAC[l_seq; LENGTH_TABLE]);;
85
86 let EL_L_SEQ = prove(`!i m n. i < (m + 1) - n ==> EL i (l_seq n m) = n + i`,
87 REWRITE_TAC[l_seq] THEN REPEAT STRIP_TAC THEN MATCH_MP_TAC EL_TABLE THEN ASM_REWRITE_TAC[]);;
88
89 let L_SEQ_NIL = prove(`!n m. l_seq n m = [] <=> (m < n)`,
90 GEN_TAC THEN GEN_TAC THEN REWRITE_TAC[GSYM LENGTH_EQ_NIL; LENGTH_L_SEQ] THEN ARITH_TAC);;
91
92 let L_SEQ_NN = prove(`!n. l_seq n n = [n]`,
93 GEN_TAC THEN REWRITE_TAC[l_seq; ARITH_RULE `(n + 1) - n = 1`; ONE; TABLE; REVERSE_TABLE; REVERSE] THEN
94 REWRITE_TAC[APPEND; ADD_0]);;
95
96 let L_SEQ_CONS = prove(`!n m. n <= m ==> l_seq n m = CONS n (l_seq (n + 1) m)`,
97 REPEAT STRIP_TAC THEN
98 REWRITE_TAC[LIST_EL_EQ; LENGTH_L_SEQ; LENGTH] THEN CONJ_TAC THENL
99 [
100 ASM_ARITH_TAC;
101 ALL_TAC
102 ] THEN
103 INDUCT_TAC THENL
104 [
105 ASM_SIMP_TAC[EL_L_SEQ] THEN ASM_REWRITE_TAC[EL; HD] THEN ARITH_TAC;
106 DISCH_TAC THEN
107 ASM_SIMP_TAC[EL_L_SEQ] THEN ASM_REWRITE_TAC[EL; TL] THEN
108 MP_TAC (SPECL [`j:num`; `m:num`; `n + 1`] EL_L_SEQ) THEN ANTS_TAC THENL
109 [
110 ASM_ARITH_TAC;
111 ALL_TAC
112 ] THEN
113 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN ARITH_TAC
114 ]);;
115
116
117 let LENGTH_BUTLAST = prove(`!l. LENGTH (BUTLAST l) = LENGTH l - 1`,
118 MATCH_MP_TAC list_INDUCT THEN REWRITE_TAC[BUTLAST; LENGTH; ARITH] THEN REPEAT STRIP_TAC THEN
119 COND_CASES_TAC THEN ASM_REWRITE_TAC[LENGTH; ARITH] THEN
120 POP_ASSUM MP_TAC THEN REWRITE_TAC[GSYM LENGTH_EQ_NIL] THEN
121 ARITH_TAC);;
122
123 let EL_BUTLAST = prove(`!(l:(A)list) i. i < LENGTH l - 1 ==> EL i (BUTLAST l) = EL i l`,
124 MATCH_MP_TAC list_INDUCT THEN REWRITE_TAC[BUTLAST; LENGTH] THEN REPEAT STRIP_TAC THEN
125 COND_CASES_TAC THENL
126 [
127 UNDISCH_TAC `i < SUC (LENGTH (a1:(A)list)) - 1` THEN
128 ASM_REWRITE_TAC[LENGTH] THEN ARITH_TAC;
129 ALL_TAC
130 ] THEN
131 REWRITE_TAC[EL_CONS] THEN COND_CASES_TAC THEN ASM_REWRITE_TAC[] THEN
132 FIRST_X_ASSUM (MP_TAC o SPEC `i - 1`) THEN
133 ANTS_TAC THENL
134 [
135 ASM_ARITH_TAC;
136 ALL_TAC
137 ] THEN
138 REWRITE_TAC[]);;
139
140 end;;