source: src/ASM/AssemblyProof.ma @ 866

Last change on this file since 866 was 866, checked in by sacerdot, 9 years ago

Significant improvement in the proof.

File size: 31.3 KB
Line 
1include "ASM/Assembly.ma".
2include "ASM/Interpret.ma".
3
4(* RUSSEL **)
5
6include "basics/jmeq.ma".
7
8notation > "hvbox(a break ≃ b)"
9  non associative with precedence 45
10for @{ 'jmeq ? $a ? $b }.
11
12notation < "hvbox(term 46 a break maction (≃) (≃\sub(t,u)) term 46 b)"
13  non associative with precedence 45
14for @{ 'jmeq $t $a $u $b }.
15
16interpretation "john major's equality" 'jmeq t x u y = (jmeq t x u y).
17
18lemma eq_to_jmeq:
19  ∀A: Type[0].
20  ∀x, y: A.
21    x = y → x ≃ y.
22  //
23qed.
24
25definition inject : ∀A.∀P:A → Prop.∀a.∀p:P a.Σx:A.P x ≝ λA,P,a,p. dp … a p.
26definition eject : ∀A.∀P: A → Prop.(Σx:A.P x) → A ≝ λA,P,c.match c with [ dp w p ⇒ w].
27
28coercion inject nocomposites: ∀A.∀P:A → Prop.∀a.∀p:P a.Σx:A.P x ≝ inject on a:? to Σx:?.?.
29coercion eject nocomposites: ∀A.∀P:A → Prop.∀c:Σx:A.P x.A ≝ eject on _c:Σx:?.? to ?.
30
31axiom VOID: Type[0].
32axiom assert_false: VOID.
33definition bigbang: ∀A:Type[0].False → VOID → A.
34 #A #abs cases abs
35qed.
36
37coercion bigbang nocomposites: ∀A:Type[0].False → ∀v:VOID.A ≝ bigbang on _v:VOID to ?.
38
39lemma sig2: ∀A.∀P:A → Prop. ∀p:Σx:A.P x. P (eject … p).
40 #A #P #p cases p #w #q @q
41qed.
42
43lemma jmeq_to_eq: ∀A:Type[0]. ∀x,y:A. x≃y → x=y.
44 #A #x #y #JMEQ @(jmeq_elim ? x … JMEQ) %
45qed.
46
47coercion jmeq_to_eq: ∀A:Type[0]. ∀x,y:A. ∀p:x≃y.x=y ≝ jmeq_to_eq on _p:?≃? to ?=?.
48
49(* END RUSSELL **)
50
51let rec foldl_strong_internal
52  (A: Type[0]) (P: list A → Type[0]) (l: list A)
53  (H: ∀prefix. ∀hd. ∀tl. l = prefix @ [hd] @ tl → P prefix → P (prefix @ [hd]))
54  (prefix: list A) (suffix: list A) (acc: P prefix) on suffix:
55    l = prefix @ suffix → P(prefix @ suffix) ≝
56  match suffix return λl'. l = prefix @ l' → P (prefix @ l') with
57  [ nil ⇒ λprf. ?
58  | cons hd tl ⇒ λprf. ?
59  ].
60  [ > (append_nil ?)
61    @ acc
62  | applyS (foldl_strong_internal A P l H (prefix @ [hd]) tl ? ?)
63    [ @ (H prefix hd tl prf acc)
64    | applyS prf
65    ]
66  ]
67qed.
68
69definition foldl_strong ≝
70  λA: Type[0].
71  λP: list A → Type[0].
72  λl: list A.
73  λH: ∀prefix. ∀hd. ∀tl. l = prefix @ [hd] @ tl → P prefix → P (prefix @ [hd]).
74  λacc: P [ ].
75    foldl_strong_internal A P l H [ ] l acc (refl …).
76
77definition bit_elim: ∀P: bool → bool. bool ≝
78  λP.
79    P true ∧ P false.
80
81let rec bitvector_elim_internal
82  (n: nat) (P: BitVector n → bool) (m: nat) on m: m ≤ n → BitVector (n - m) → bool ≝
83  match m return λm. m ≤ n → BitVector (n - m) → bool with
84  [ O    ⇒ λprf1. λprefix. P ?
85  | S n' ⇒ λprf2. λprefix. bit_elim (λbit. bitvector_elim_internal n P n' ? ?)
86  ].
87  [ applyS prefix
88  | letin res ≝ (bit ::: prefix)
89    < (minus_S_S ? ?)
90    > (minus_Sn_m ? ?)
91    [ @ res
92    | @ prf2
93    ]
94  | /2/
95  ].
96qed.
97
98definition bitvector_elim ≝
99  λn: nat.
100  λP: BitVector n → bool.
101    bitvector_elim_internal n P n ? ?.
102  [ @ (le_n ?)
103  | < (minus_n_n ?)
104    @ [[ ]]
105  ]
106qed.
107
108axiom vector_associativity_of_append:
109  ∀A: Type[0].
110  ∀n, m, o:  nat.
111  ∀v: Vector A n.
112  ∀q: Vector A m.
113  ∀r: Vector A o.
114    ((v @@ q) @@ r)
115    ≃
116    (v @@ (q @@ r)).
117       
118axiom vector_cons_append:
119  ∀A: Type[0].
120  ∀n: nat.
121  ∀a: A.
122  ∀v: Vector A n.
123    a ::: v = [[ a ]] @@ v.
124
125lemma super_rewrite2:
126 ∀A:Type[0].∀n,m.∀v1: Vector A n.∀v2: Vector A m.
127  ∀P: ∀m. Vector A m → Prop.
128   n=m → v1 ≃ v2 → P n v1 → P m v2.
129 #A #n #m #v1 #v2 #P #EQ <EQ in v2; #V #JMEQ >JMEQ //
130qed.
131
132lemma mem_middle_vector:
133  ∀A: Type[0].
134  ∀m, o: nat.
135  ∀eq: A → A → bool.
136  ∀reflex: ∀a. eq a a = true.
137  ∀p: Vector A m.
138  ∀a: A.
139  ∀r: Vector A o.
140    mem A eq ? (p@@(a:::r)) a = true.
141  # A # M # O # EQ # REFLEX # P # A
142  elim P
143  [ normalize
144    > (REFLEX A)
145    normalize
146    # H
147    %
148  | # NN # AA # PP # IH
149    normalize
150    cases (EQ A AA) //
151     @ IH
152  ]
153qed.
154
155lemma mem_monotonic_wrt_append:
156  ∀A: Type[0].
157  ∀m, o: nat.
158  ∀eq: A → A → bool.
159  ∀reflex: ∀a. eq a a = true.
160  ∀p: Vector A m.
161  ∀a: A.
162  ∀r: Vector A o.
163    mem A eq ? r a = true → mem A eq ? (p @@ r) a = true.
164  # A # M # O # EQ # REFLEX # P # A
165  elim P
166  [ #R #H @H
167  | #NN #AA # PP # IH #R #H
168    normalize
169    cases (EQ A AA)
170    [ normalize %
171    | @ IH @ H
172    ]
173  ]
174qed.
175
176lemma subvector_multiple_append:
177  ∀A: Type[0].
178  ∀o, n: nat.
179  ∀eq: A → A → bool.
180  ∀refl: ∀a. eq a a = true.
181  ∀h: Vector A o.
182  ∀v: Vector A n.
183  ∀m: nat.
184  ∀q: Vector A m.
185    bool_to_Prop (subvector_with A ? ? eq v (h @@ q @@ v)).
186  # A # O # N # EQ # REFLEX # H # V
187  elim V
188  [ normalize
189    # M # V %
190  | # NN # AA # VV # IH # MM # QQ
191    change with (bool_to_Prop (andb ??))
192    cut ((mem A EQ (O + (MM + S NN)) (H@@QQ@@AA:::VV) AA) = true)
193    [
194    | # HH > HH
195      > (vector_cons_append ? ? AA VV)
196      change with (bool_to_Prop (subvector_with ??????))
197      @(super_rewrite2 A ((MM + 1)+ NN) (MM+S NN) ??
198        (λSS.λVS.bool_to_Prop (subvector_with ?? (O+SS) ?? (H@@VS)))
199        ?
200        (vector_associativity_of_append A ? ? ? QQ [[AA]] VV))
201      [ >associative_plus //
202      | @IH ]
203    ]
204    @(mem_monotonic_wrt_append)
205    [ @ REFLEX
206    | @(mem_monotonic_wrt_append)
207      [ @ REFLEX
208      | normalize
209        > REFLEX
210        normalize
211        %
212      ]
213    ]
214qed.
215
216(*
217lemma subvector_hd_tl:
218  ∀A: Type[0].
219  ∀o: nat.
220  ∀eq: A → A → bool.
221  ∀refl: ∀a. eq a a = true.
222  ∀h: A.
223  ∀v: Vector A o.
224    bool_to_Prop (subvector_with A ? ? eq v (h ::: v)).
225
226axiom eq_a_reflexive:
227  ∀a. eq_a a a = true.
228
229let rec list_addressing_mode_tags_elim
230  (n: nat) (l: Vector addressing_mode_tag (S n)) on l: (l → bool) → bool ≝
231  match l return λx.match x with [O ⇒ λl: Vector … O. bool | S x' ⇒ λl: Vector addressing_mode_tag (S x').
232   (l → bool) → bool ] with
233  [ VEmpty      ⇒  true 
234  | VCons len hd tl ⇒ λP.
235    let process_hd ≝
236      match hd return λhd. ∀P: hd:::tl → bool. bool with
237      [ direct ⇒ λP.bitvector_elim 8 (λx. P (DIRECT x))
238      | indirect ⇒ λP.bit_elim (λx. P (INDIRECT x))
239      | ext_indirect ⇒ λP.bit_elim (λx. P (EXT_INDIRECT x))
240      | registr ⇒ λP.bitvector_elim 3 (λx. P (REGISTER x))
241      | acc_a ⇒ λP.P ACC_A
242      | acc_b ⇒ λP.P ACC_B
243      | dptr ⇒ λP.P DPTR
244      | data ⇒ λP.bitvector_elim 8 (λx. P (DATA x))
245      | data16 ⇒ λP.bitvector_elim 16 (λx. P (DATA16 x))
246      | acc_dptr ⇒ λP.P ACC_DPTR
247      | acc_pc ⇒ λP.P ACC_PC
248      | ext_indirect_dptr ⇒ λP.P EXT_INDIRECT_DPTR
249      | indirect_dptr ⇒ λP.P INDIRECT_DPTR
250      | carry ⇒ λP.P CARRY
251      | bit_addr ⇒ λP.bitvector_elim 8 (λx. P (BIT_ADDR x))
252      | n_bit_addr ⇒ λP.bitvector_elim 8 (λx. P (N_BIT_ADDR x))
253      | relative ⇒ λP.bitvector_elim 8 (λx. P (RELATIVE x))
254      | addr11 ⇒ λP.bitvector_elim 11 (λx. P (ADDR11 x))
255      | addr16 ⇒ λP.bitvector_elim 16 (λx. P (ADDR16 x))
256      ]
257    in
258      andb (process_hd P)
259       (match len return λlen. Vector addressing_mode_tag len → bool with
260         [ O ⇒ λ_.true
261         | S y ⇒ λtl.list_addressing_mode_tags_elim y tl (λaddr.P addr) ] tl)
262  ].
263  [1: @ (execute_1_technical ? ? tl)
264      [ //
265      | @ (subvector_hd_tl addressing_mode_tag (S y) (S len) eq_a eq_a_reflexive)
266      ]
267  ].
268
269definition preinstruction_elim: ∀P: preinstruction [[ relative ]] → bool. bool ≝
270 λP.
271   P (ADD … ACC_A
272   P (DA … ACC_A).lemma jmeq_to_eq: ∀A:Type[0]. ∀x,y:A. x≃y → x=y.
273 #A #x #y #JMEQ @(jmeq_elim ? x … JMEQ) %
274qed.
275 %
276qed.
277 
278
279definition instruction_elim: ∀P: instruction → bool. bool.
280 
281 
282lemma instruction_elim_correct:
283  ∀i: instruction.
284  ∀P: instruction → bool.
285    instruction_elim P = true → ∀j. P j = true.
286 
287lemma test:
288  ∀i: instruction.
289  ∃pc.
290  let assembled ≝ assembly1 i in
291  let code_memory ≝ load_code_memory assembled in
292  let fetched ≝ fetch code_memory pc in
293  let 〈instr_pc, ticks〉 ≝ fetched in
294    \fst instr_pc = i.
295  # INSTR
296  @ (ex_intro ?)
297  [ @ (zero 16)
298  | @ (instruction_elim INSTR)
299  ].
300*)
301 
302(* This establishes the correspondence between pseudo program counters and
303   program counters. It is at the heart of the proof. *)
304(*CSC: code taken from build_maps *)
305definition sigma0: pseudo_assembly_program → option (nat × (nat × (BitVectorTrie Word 16))) ≝
306 λinstr_list.
307  foldl ??
308    (λt. λi.
309       match t with
310       [ None ⇒ None ?
311       | Some ppc_pc_map ⇒
312         let 〈ppc,pc_map〉 ≝ ppc_pc_map in
313         let 〈program_counter, sigma_map〉 ≝ pc_map in
314         let 〈label, i〉 ≝ i in
315          match construct_costs instr_list program_counter (λx. zero ?) (λx. zero ?) (Stub …) i with
316           [ None ⇒ None ?
317           | Some pc_ignore ⇒
318              let 〈pc,ignore〉 ≝ pc_ignore in
319              Some … 〈S ppc,〈pc, insert ? ? (bitvector_of_nat ? ppc) (bitvector_of_nat ? pc) sigma_map〉〉 ]
320       ]) (Some ? 〈0, 〈0, (Stub ? ?)〉〉) (\snd instr_list).
321       
322definition tech_pc_sigma0: pseudo_assembly_program → option (nat × (BitVectorTrie Word 16)) ≝
323 λinstr_list.
324  match sigma0 instr_list with
325   [ None ⇒ None …
326   | Some result ⇒
327      let 〈ppc,pc_sigma_map〉 ≝ result in
328       Some … pc_sigma_map ].
329
330definition sigma_safe: pseudo_assembly_program → option (Word → Word) ≝       
331 λinstr_list.
332  match sigma0 instr_list with
333  [ None ⇒ None ?
334  | Some result ⇒
335    let 〈ppc,pc_sigma_map〉 ≝ result in
336    let 〈pc, sigma_map〉 ≝ pc_sigma_map in
337      if gtb pc (2^16) then
338        None ?
339      else
340        Some ? (λx.lookup ?? x sigma_map (zero …)) ].
341
342axiom policy_ok: ∀p. sigma_safe p ≠ None ….
343
344definition sigma: pseudo_assembly_program → Word → Word ≝
345 λp.
346  match sigma_safe p return λr:option (Word → Word). r ≠ None … → Word → Word with
347   [ None ⇒ λabs. ⊥
348   | Some r ⇒ λ_.r] (policy_ok p).
349 cases abs //
350qed.
351
352lemma length_append:
353 ∀A.∀l1,l2:list A.
354  |l1 @ l2| = |l1| + |l2|.
355 #A #l1 elim l1
356  [ //
357  | #hd #tl #IH #l2 normalize <IH //]
358qed.
359
360let rec does_not_occur (id:Identifier) (l:list labelled_instruction) on l: bool ≝
361 match l with
362  [ nil ⇒ true
363  | cons hd tl ⇒ notb (instruction_matches_identifier id hd) ∧ does_not_occur id tl].
364
365lemma does_not_occur_None:
366 ∀id,i,list_instr.
367  does_not_occur id (list_instr@[〈None …,i〉]) =
368  does_not_occur id list_instr.
369 #id #i #list_instr elim list_instr
370  [ % | #hd #tl #IH whd in ⊢ (??%%) >IH %]
371qed.
372
373let rec occurs_exactly_once (id:Identifier) (l:list labelled_instruction) on l : bool ≝
374 match l with
375  [ nil ⇒ false
376  | cons hd tl ⇒
377     if instruction_matches_identifier id hd then
378      does_not_occur id tl
379     else
380      occurs_exactly_once id tl ].
381
382lemma occurs_exactly_once_None:
383 ∀id,i,list_instr.
384  occurs_exactly_once id (list_instr@[〈None …,i〉]) =
385  occurs_exactly_once id list_instr.
386 #id #i #list_instr elim list_instr
387  [ % | #hd #tl #IH whd in ⊢ (??%%) >IH >does_not_occur_None %]
388qed.
389
390coercion bool_to_Prop: ∀b:bool. Prop ≝ bool_to_Prop on _b:bool to Type[0].
391
392lemma index_of_internal_None: ∀i,id,instr_list,n.
393 occurs_exactly_once id (instr_list@[〈None …,i〉]) →
394  index_of_internal ? (instruction_matches_identifier id) instr_list n =
395   index_of_internal ? (instruction_matches_identifier id) (instr_list@[〈None …,i〉]) n.
396 #i #id #instr_list elim instr_list
397  [ #n #abs whd in abs; cases abs
398  | #hd #tl #IH #n whd in ⊢ (% → ??%%); whd in ⊢ (match % with [_ ⇒ ? | _ ⇒ ?] → ?)
399    cases (instruction_matches_identifier id hd) whd in ⊢ (match % with [_ ⇒ ? | _ ⇒ ?] → ??%%)
400    [ #H %
401    | #H @IH whd in H; cases (occurs_exactly_once ??) in H ⊢ %
402      [ #_ % | #abs cases abs ]]]
403qed.
404
405lemma address_of_word_labels_code_mem_None: ∀i,id,instr_list.
406 occurs_exactly_once id (instr_list@[〈None …,i〉]) →
407  address_of_word_labels_code_mem instr_list id =
408  address_of_word_labels_code_mem (instr_list@[〈None …,i〉]) id.
409 #i #id #instr_list #H whd in ⊢ (??%%) whd in ⊢ (??(??%?)(??%?))
410 >(index_of_internal_None … H) %
411qed.
412
413axiom tech_pc_sigma0_append:
414 ∀preamble,instr_list,prefix,label,i,pc',code,pc,costs,costs'.
415  Some … 〈pc,costs〉 = tech_pc_sigma0 〈preamble,prefix〉 →
416   construct_costs 〈preamble,instr_list〉 … pc (λx.zero 16) (λx. zero 16) costs i = Some … 〈pc',code〉 →
417    tech_pc_sigma0 〈preamble,prefix@[〈label,i〉]〉 = Some … 〈pc',costs'〉.
418
419axiom tech_pc_sigma0_append_None:
420 ∀preamble,instr_list,prefix,i,pc,costs.
421  Some … 〈pc,costs〉 = tech_pc_sigma0 〈preamble,prefix〉 →
422   construct_costs 〈preamble,instr_list〉 … pc (λx.zero 16) (λx. zero 16) costs i = None …
423    → False.
424
425definition build_maps' ≝
426  λpseudo_program.
427  let 〈preamble,instr_list〉 ≝ pseudo_program in
428  let result ≝
429   foldl_strong
430    (option Identifier × pseudo_instruction)
431    (λpre. Σres:((BitVectorTrie Word 16) × (nat × (BitVectorTrie Word 16))).
432      let pre' ≝ 〈preamble,pre〉 in
433      let 〈labels,pc_costs〉 ≝ res in
434       tech_pc_sigma0 pre' = Some … pc_costs ∧
435       ∀id. occurs_exactly_once id pre →
436        lookup ?? id labels (zero …) = sigma pre' (address_of_word_labels_code_mem pre id))
437    instr_list
438    (λprefix,i,tl,prf,t.
439      let 〈labels, pc_costs〉 ≝ t in
440      let 〈program_counter, costs〉 ≝ pc_costs in
441       let 〈label, i'〉 ≝ i in
442       let labels ≝
443         match label with
444         [ None ⇒ labels
445         | Some label ⇒
446           let program_counter_bv ≝ bitvector_of_nat ? program_counter in
447             insert ? ? label program_counter_bv labels
448         ]
449       in
450         match construct_costs 〈preamble,instr_list〉 program_counter (λx. zero ?) (λx. zero ?) costs i' with
451         [ None ⇒
452            let dummy ≝ 〈labels,pc_costs〉 in
453             dummy
454         | Some construct ⇒ 〈labels, construct〉
455         ]
456    ) 〈(Stub ? ?), 〈0, (Stub ? ?)〉〉
457  in
458   let 〈labels, pc_costs〉 ≝ result in
459   let 〈pc, costs〉 ≝ pc_costs in
460    〈labels, costs〉.
461 [3: whd % // #id normalize in ⊢ (% → ?) #abs @⊥ //
462 | whd cases construct in p3 #PC #CODE #JMEQ %
463    [ @(tech_pc_sigma0_append ??????????? (jmeq_to_eq ??? JMEQ)) | #id #Hid ]
464 | (* dummy case *) @⊥
465   @(tech_pc_sigma0_append_None ?? prefix ???? (jmeq_to_eq ??? p3)) ]
466 [*: generalize in match (sig2 … t) whd in ⊢ (% → ?)
467     >p whd in ⊢ (% → ?) >p1 * #IH0 #IH1 >IH0 // ]
468 whd in ⊢ (??(????%?)?) -labels1;
469 cases label in Hid
470  [ #Hid whd in ⊢ (??(????%?)?) >IH1 -IH1
471     [ >(address_of_word_labels_code_mem_None … Hid)
472       (* MANCA LEMMA: INDIRIZZO TROVATO NEL PROGRAMMA! *)
473     | whd in Hid >occurs_exactly_once_None in Hid // ]
474  | -label #label #Hid whd in ⊢ (??(????%?)?)
475   
476  ]
477qed.
478
479(*
480(*
481notation < "hvbox('let' 〈ident x,ident y〉 ≝ t 'in' s)"
482 with precedence 10
483for @{ match $t with [ pair ${ident x} ${ident y} ⇒ $s ] }.
484*)
485
486lemma build_maps_ok:
487 ∀p:pseudo_assembly_program.
488  let 〈labels,costs〉 ≝ build_maps' p in
489   ∀pc.
490    (nat_of_bitvector … pc) < length … (\snd p) →
491     lookup ?? pc labels (zero …) = sigma p (\snd (fetch_pseudo_instruction (\snd p) pc)).
492 #p cases p #preamble #instr_list
493  elim instr_list
494   [ whd #pc #abs normalize in abs; cases (not_le_Sn_O ?) [#H cases (H abs) ]
495   | #hd #tl #IH
496    whd in ⊢ (match % with [ _ ⇒ ?])
497   ]
498qed.
499*)
500
501(*
502lemma list_elim_rev:
503 ∀A:Type[0].∀P:list A → Prop.
504  P [ ] → (∀n,l. length l = n → P l → 
505  P [ ] → (∀l,a. P l → P (l@[a])) →
506   ∀l. P l.
507 #A #P
508qed.*)
509
510lemma rev_preserves_length:
511 ∀A.∀l. length … (rev A l) = length … l.
512  #A #l elim l
513   [ %
514   | #hd #tl #IH normalize >length_append normalize /2/ ]
515qed.
516
517lemma rev_append:
518 ∀A.∀l1,l2.
519  rev A (l1@l2) = rev A l2 @ rev A l1.
520 #A #l1 elim l1 normalize //
521qed.
522 
523lemma rev_rev: ∀A.∀l. rev … (rev A l) = l.
524 #A #l elim l
525  [ //
526  | #hd #tl #IH normalize >rev_append normalize // ]
527qed.
528
529lemma split_len_Sn:
530 ∀A:Type[0].∀l:list A.∀len.
531  length … l = S len →
532   Σl'.Σa. l = l'@[a] ∧ length … l' = len.
533 #A #l elim l
534  [ normalize #len #abs destruct
535  | #hd #tl #IH #len
536    generalize in match (rev_rev … tl)
537    cases (rev A tl) in ⊢ (??%? → ?)
538     [ #H <H normalize #EQ % [@[ ]] % [@hd] normalize /2/ 
539     | #a #l' #H <H normalize #EQ
540      %[@(hd::rev … l')] %[@a] % //
541      >length_append in EQ #EQ normalize in EQ; normalize;
542      generalize in match (injective_S … EQ) #EQ2 /2/ ]]
543qed.
544
545lemma list_elim_rev:
546 ∀A:Type[0].∀P:list A → Type[0].
547  P [ ] → (∀l,a. P l → P (l@[a])) →
548   ∀l. P l.
549 #A #P #H1 #H2 #l
550 generalize in match (refl … (length … l))
551 generalize in ⊢ (???% → ?) #n generalize in match l
552 elim n
553  [ #L cases L [ // | #x #w #abs (normalize in abs) @⊥ // ]
554  | #m #IH #L #EQ
555    cases (split_len_Sn … EQ) #l' * #a * /3/ ]
556qed.
557
558axiom is_prefix: ∀A:Type[0]. list A → list A → Prop.
559axiom prefix_of_append:
560 ∀A:Type[0].∀l,l1,l2:list A.
561  is_prefix … l l1 → is_prefix … l (l1@l2).
562axiom prefix_reflexive: ∀A,l. is_prefix A l l.
563axiom nil_prefix: ∀A,l. is_prefix A [ ] l.
564
565record Propify (A:Type[0]) : Type[0] (*Prop*) ≝ { in_propify: A }.
566
567definition Propify_elim: ∀A. ∀P:Prop. (A → P) → (Propify A → P) ≝
568 λA,P,H,x. match x with [ mk_Propify p ⇒ H p ].
569
570definition app ≝
571 λA:Type[0].λl1:Propify (list A).λl2:list A.
572  match l1 with
573   [ mk_Propify l1 ⇒ mk_Propify … (l1@l2) ].
574
575lemma app_nil: ∀A,l1. app A l1 [ ] = l1.
576 #A * /3/
577qed.
578
579lemma app_assoc: ∀A,l1,l2,l3. app A (app A l1 l2) l3 = app A l1 (l2@l3).
580 #A * #l1 normalize //
581qed.
582
583let rec foldli (A: Type[0]) (B: Propify (list A) → Type[0])
584 (f: ∀prefix. B prefix → ∀x.B (app … prefix [x]))
585 (prefix: Propify (list A)) (b: B prefix) (l: list A) on l :
586 B (app … prefix l) ≝
587  match l with
588  [ nil ⇒ ? (* b *)
589  | cons hd tl ⇒ ? (*foldli A B f (prefix@[hd]) (f prefix b hd) tl*)
590  ].
591 [ applyS b
592 | <(app_assoc ?? [hd]) @(foldli A B f (app … prefix [hd]) (f prefix b hd) tl) ]
593qed.
594
595(*
596let rec foldli (A: Type[0]) (B: list A → Type[0]) (f: ∀prefix. B prefix → ∀x. B (prefix@[x]))
597 (prefix: list A) (b: B prefix) (l: list A) on l : B (prefix@l) ≝
598  match l with
599  [ nil ⇒ ? (* b *)
600  | cons hd tl ⇒
601     ? (*foldli A B f (prefix@[hd]) (f prefix b hd) tl*)
602  ].
603 [ applyS b
604 | applyS (foldli A B f (prefix@[hd]) (f prefix b hd) tl) ]
605qed.
606*)
607
608definition foldll:
609 ∀A:Type[0].∀B: Propify (list A) → Type[0].
610  (∀prefix. B prefix → ∀x. B (app … prefix [x])) →
611   B (mk_Propify … []) → ∀l: list A. B (mk_Propify … l)
612 ≝ λA,B,f. foldli A B f (mk_Propify … [ ]).
613
614axiom is_pprefix: ∀A:Type[0]. Propify (list A) → list A → Prop.
615axiom pprefix_of_append:
616 ∀A:Type[0].∀l,l1,l2.
617  is_pprefix A l l1 → is_pprefix A l (l1@l2).
618axiom pprefix_reflexive: ∀A,l. is_pprefix A (mk_Propify … l) l.
619axiom nil_pprefix: ∀A,l. is_pprefix A (mk_Propify … [ ]) l.
620
621
622axiom foldll':
623 ∀A:Type[0].∀l: list A.
624  ∀B: ∀prefix:Propify (list A). is_pprefix ? prefix l → Type[0].
625  (∀prefix,proof. B prefix proof → ∀x,proof'. B (app … prefix [x]) proof') →
626   B (mk_Propify … [ ]) (nil_pprefix …) → B (mk_Propify … l) (pprefix_reflexive … l).
627 #A #l #B
628 generalize in match (foldll A (λprefix. is_pprefix ? prefix l)) #HH
629 
630 
631  #H #acc
632 @foldll
633  [
634  |
635  ]
636 
637 ≝ λA,B,f. foldli A B f (mk_Propify … [ ]).
638
639
640(*
641record subset (A:Type[0]) (P: A → Prop): Type[0] ≝
642 { subset_wit:> A;
643   subset_proof: P subset_wit
644 }.
645*)
646
647definition build_maps' ≝
648  λpseudo_program.
649  let 〈preamble,instr_list〉 ≝ pseudo_program in
650  let result ≝
651   foldll
652    (option Identifier × pseudo_instruction)
653    (λprefix.
654      Σt:((BitVectorTrie Word 16) × (nat × (BitVectorTrie Word 16))).
655       match prefix return λ_.Prop with [mk_Propify prefix ⇒ tech_pc_sigma0 〈preamble,prefix〉 ≠ None ?])
656    (λprefix,t,i.
657      let 〈labels, pc_costs〉 ≝ t in
658      let 〈program_counter, costs〉 ≝ pc_costs in
659       let 〈label, i'〉 ≝ i in
660       let labels ≝
661         match label with
662         [ None ⇒ labels
663         | Some label ⇒
664           let program_counter_bv ≝ bitvector_of_nat ? program_counter in
665             insert ? ? label program_counter_bv labels
666         ]
667       in
668         match construct_costs pseudo_program program_counter (λx. zero ?) (λx. zero ?) costs i' with
669         [ None ⇒
670            let dummy ≝ 〈labels,pc_costs〉 in
671              dummy
672         | Some construct ⇒ 〈labels, construct〉
673         ]
674    ) 〈(Stub ? ?), 〈0, (Stub ? ?)〉〉 instr_list
675  in
676   let 〈labels, pc_costs〉 ≝ result in
677   let 〈pc, costs〉 ≝ pc_costs in
678    〈labels, costs〉.
679 [
680 | @⊥
681 | normalize % //
682 ]
683qed.
684
685definition build_maps' ≝
686  λpseudo_program.
687  let 〈preamble,instr_list〉 ≝ pseudo_program in
688  let result ≝
689   foldl
690    (Σt:((BitVectorTrie Word 16) × (nat × (BitVectorTrie Word 16))).
691          ∃instr_list_prefix. is_prefix ? instr_list_prefix instr_list ∧
692           tech_pc_sigma0 〈preamble,instr_list_prefix〉 = Some ? (\fst (\snd t)))
693    (Σi:option Identifier × pseudo_instruction. ∀instr_list_prefix.
694          let instr_list_prefix' ≝ instr_list_prefix @ [i] in
695           is_prefix ? instr_list_prefix' instr_list →
696           tech_pc_sigma0 〈preamble,instr_list_prefix'〉 ≠ None ?)
697    (λt: Σt:((BitVectorTrie Word 16) × (nat × (BitVectorTrie Word 16))).
698          ∃instr_list_prefix. is_prefix ? instr_list_prefix instr_list ∧
699           tech_pc_sigma0 〈preamble,instr_list_prefix〉 = Some ? (\fst (\snd t)).
700     λi: Σi:option Identifier × pseudo_instruction. ∀instr_list_prefix.
701          let instr_list_prefix' ≝ instr_list_prefix @ [i] in
702           is_prefix ? instr_list_prefix' instr_list →
703           tech_pc_sigma0 〈preamble,instr_list_prefix'〉 ≠ None ? .
704      let 〈labels, pc_costs〉 ≝ t in
705      let 〈program_counter, costs〉 ≝ pc_costs in
706       let 〈label, i'〉 ≝ i in
707       let labels ≝
708         match label with
709         [ None ⇒ labels
710         | Some label ⇒
711           let program_counter_bv ≝ bitvector_of_nat ? program_counter in
712             insert ? ? label program_counter_bv labels
713         ]
714       in
715         match construct_costs pseudo_program program_counter (λx. zero ?) (λx. zero ?) costs i' with
716         [ None ⇒
717            let dummy ≝ 〈labels,pc_costs〉 in
718              dummy
719         | Some construct ⇒ 〈labels, construct〉
720         ]
721    ) 〈(Stub ? ?), 〈0, (Stub ? ?)〉〉 ?(*instr_list*)
722  in
723   let 〈labels, pc_costs〉 ≝ result in
724   let 〈pc, costs〉 ≝ pc_costs in
725    〈labels, costs〉.
726 [4: @(list_elim_rev ?
727       (λinstr_list. list (
728        (Σi:option Identifier × pseudo_instruction. ∀instr_list_prefix.
729          let instr_list_prefix' ≝ instr_list_prefix @ [i] in
730           is_prefix ? instr_list_prefix' instr_list →
731           tech_pc_sigma0 〈preamble,instr_list_prefix'〉 ≠ None ?)))
732       ?? instr_list) (* CSC: BAD ORDER FOR CODE EXTRACTION *)
733      [ @[ ]
734      | #l' #a #limage %2
735        [ %[@a] #PREFIX #PREFIX_OK
736        | (* CSC: EVEN WORST CODE FOR EXTRACTION: WE SHOULD STRENGTHEN
737             THE INDUCTION HYPOTHESIS INSTEAD *)
738          elim limage
739           [ %1
740           | #HD #TL #IH @(?::IH) cases HD #ELEM #K1 %[@ELEM] #K2 #K3
741             @K1 @(prefix_of_append ???? K3)
742           ] 
743        ]
744       
745       
746     
747 
748  cases t in c2 ⊢ % #t' * #LIST_PREFIX * #H1t' #H2t' #HJMt'
749     % [@ (LIST_PREFIX @ [i])] %
750      [ cases (sig2 … i LIST_PREFIX) #K1 #K2 @K1
751      | (* DOABLE IN PRINCIPLE *)
752      ]
753 | (* assert false case *)
754 |3: % [@ ([ ])] % [2: % | (* DOABLE *)]
755 |   
756
757let rec encoding_check (code_memory: BitVectorTrie Byte 16) (pc: Word) (final_pc: Word)
758                       (encoding: list Byte) on encoding: Prop ≝
759  match encoding with
760  [ nil ⇒ final_pc = pc
761  | cons hd tl ⇒
762    let 〈new_pc, byte〉 ≝ next code_memory pc in
763      hd = byte ∧ encoding_check code_memory new_pc final_pc tl
764  ].
765
766definition assembly_specification:
767  ∀assembly_program: pseudo_assembly_program.
768  ∀code_mem: BitVectorTrie Byte 16. Prop ≝
769  λpseudo_assembly_program.
770  λcode_mem.
771    ∀pc: Word.
772      let 〈preamble, instr_list〉 ≝ pseudo_assembly_program in
773      let 〈pre_instr, pre_new_pc〉 ≝ fetch_pseudo_instruction instr_list pc in
774      let labels ≝ λx. sigma' pseudo_assembly_program (address_of_word_labels_code_mem instr_list x) in
775      let datalabels ≝ λx. sigma' pseudo_assembly_program (lookup ? ? x (construct_datalabels preamble) (zero ?)) in
776      let pre_assembled ≝ assembly_1_pseudoinstruction pseudo_assembly_program
777       (sigma' pseudo_assembly_program pc) labels datalabels pre_instr in
778      match pre_assembled with
779       [ None ⇒ True
780       | Some pc_code ⇒
781          let 〈new_pc,code〉 ≝ pc_code in
782           encoding_check code_mem pc (sigma' pseudo_assembly_program pre_new_pc) code ].
783
784axiom assembly_meets_specification:
785  ∀pseudo_assembly_program.
786    match assembly pseudo_assembly_program with
787    [ None ⇒ True
788    | Some code_mem_cost ⇒
789      let 〈code_mem, cost〉 ≝ code_mem_cost in
790        assembly_specification pseudo_assembly_program (load_code_memory code_mem)
791    ].
792(*
793  # PROGRAM
794  [ cases PROGRAM
795    # PREAMBLE
796    # INSTR_LIST
797    elim INSTR_LIST
798    [ whd
799      whd in ⊢ (∀_. %)
800      # PC
801      whd
802    | # INSTR
803      # INSTR_LIST_TL
804      # H
805      whd
806      whd in ⊢ (match % with [ _ ⇒ ? | _ ⇒ ?])
807    ]
808  | cases not_implemented
809  ] *)
810
811definition status_of_pseudo_status: PseudoStatus → option Status ≝
812 λps.
813  let pap ≝ code_memory … ps in
814   match assembly pap with
815    [ None ⇒ None …
816    | Some p ⇒
817       let cm ≝ load_code_memory (\fst p) in
818       let pc ≝ sigma' pap (program_counter ? ps) in
819        Some …
820         (mk_PreStatus (BitVectorTrie Byte 16)
821           cm
822           (low_internal_ram … ps)
823           (high_internal_ram … ps)
824           (external_ram … ps)
825           pc
826           (special_function_registers_8051 … ps)
827           (special_function_registers_8052 … ps)
828           (p1_latch … ps)
829           (p3_latch … ps)
830           (clock … ps)) ].
831
832definition write_at_stack_pointer':
833 ∀M. ∀ps: PreStatus M. Byte → Σps':PreStatus M.(code_memory … ps = code_memory … ps') ≝
834  λM: Type[0].
835  λs: PreStatus M.
836  λv: Byte.
837    let 〈 nu, nl 〉 ≝ split … 4 4 (get_8051_sfr ? s SFR_SP) in
838    let bit_zero ≝ get_index_v… nu O ? in
839    let bit_1 ≝ get_index_v… nu 1 ? in
840    let bit_2 ≝ get_index_v… nu 2 ? in
841    let bit_3 ≝ get_index_v… nu 3 ? in
842      if bit_zero then
843        let memory ≝ insert … ([[ bit_1 ; bit_2 ; bit_3 ]] @@ nl)
844                              v (low_internal_ram ? s) in
845          set_low_internal_ram ? s memory
846      else
847        let memory ≝ insert … ([[ bit_1 ; bit_2 ; bit_3 ]] @@ nl)
848                              v (high_internal_ram ? s) in
849          set_high_internal_ram ? s memory.
850  [ cases l0 %
851  |2,3,4,5: normalize repeat (@ le_S_S) @ le_O_n ]
852qed.
853
854definition execute_1_pseudo_instruction': (Word → nat) → ∀ps:PseudoStatus.
855 Σps':PseudoStatus.(code_memory … ps = code_memory … ps')
856
857  λticks_of.
858  λs.
859  let 〈instr, pc〉 ≝ fetch_pseudo_instruction (\snd (code_memory ? s)) (program_counter ? s) in
860  let ticks ≝ ticks_of (program_counter ? s) in
861  let s ≝ set_clock ? s (clock ? s + ticks) in
862  let s ≝ set_program_counter ? s pc in
863    match instr with
864    [ Instruction instr ⇒
865       execute_1_preinstruction … (λx, y. address_of_word_labels y x) instr s
866    | Comment cmt ⇒ s
867    | Cost cst ⇒ s
868    | Jmp jmp ⇒ set_program_counter ? s (address_of_word_labels s jmp)
869    | Call call ⇒
870      let a ≝ address_of_word_labels s call in
871      let 〈carry, new_sp〉 ≝ half_add ? (get_8051_sfr ? s SFR_SP) (bitvector_of_nat 8 1) in
872      let s ≝ set_8051_sfr ? s SFR_SP new_sp in
873      let 〈pc_bu, pc_bl〉 ≝ split ? 8 8 (program_counter ? s) in
874      let s ≝ write_at_stack_pointer' ? s pc_bl in
875      let 〈carry, new_sp〉 ≝ half_add ? (get_8051_sfr ? s SFR_SP) (bitvector_of_nat 8 1) in
876      let s ≝ set_8051_sfr ? s SFR_SP new_sp in
877      let s ≝ write_at_stack_pointer' ? s pc_bu in
878        set_program_counter ? s a
879    | Mov dptr ident ⇒
880       set_arg_16 ? s (get_arg_16 ? s (DATA16 (address_of_word_labels s ident))) dptr
881    ].
882 [
883 |2,3,4: %
884 | <(sig2 … l7) whd in ⊢ (??? (??%)) <(sig2 … l5) %
885 |
886 | %
887 ]
888 cases not_implemented
889qed.
890
891(*
892lemma execute_code_memory_unchanged:
893 ∀ticks_of,ps. code_memory ? ps = code_memory ? (execute_1_pseudo_instruction ticks_of ps).
894 #ticks #ps whd in ⊢ (??? (??%))
895 cases (fetch_pseudo_instruction (\snd (code_memory pseudo_assembly_program ps))
896  (program_counter pseudo_assembly_program ps)) #instr #pc
897 whd in ⊢ (??? (??%)) cases instr
898  [ #pre cases pre
899     [ #a1 #a2 whd in ⊢ (??? (??%)) cases (add_8_with_carry ???) #y1 #y2 whd in ⊢ (??? (??%))
900       cases (split ????) #z1 #z2 %
901     | #a1 #a2 whd in ⊢ (??? (??%)) cases (add_8_with_carry ???) #y1 #y2 whd in ⊢ (??? (??%))
902       cases (split ????) #z1 #z2 %
903     | #a1 #a2 whd in ⊢ (??? (??%)) cases (sub_8_with_carry ???) #y1 #y2 whd in ⊢ (??? (??%))
904       cases (split ????) #z1 #z2 %
905     | #a1 whd in ⊢ (??? (??%)) cases a1 #x #H whd in ⊢ (??? (??%)) cases x
906       [ #x1 whd in ⊢ (??? (??%))
907     | *: cases not_implemented
908     ]
909  | #comment %
910  | #cost %
911  | #label %
912  | #label whd in ⊢ (??? (??%)) cases (half_add ???) #x1 #x2 whd in ⊢ (??? (??%))
913    cases (split ????) #y1 #y2 whd in ⊢ (??? (??%)) cases (half_add ???) #z1 #z2
914    whd in ⊢ (??? (??%)) whd in ⊢ (??? (??%)) cases (split ????) #w1 #w2
915    whd in ⊢ (??? (??%)) cases (get_index_v bool ????) whd in ⊢ (??? (??%))
916    (* CSC: ??? *)
917  | #dptr #label (* CSC: ??? *)
918  ]
919  cases not_implemented
920qed.
921*)
922
923lemma status_of_pseudo_status_failure_depends_only_on_code_memory:
924 ∀ps,ps': PseudoStatus.
925  code_memory … ps = code_memory … ps' →
926   match status_of_pseudo_status ps with
927    [ None ⇒ status_of_pseudo_status ps' = None …
928    | Some _ ⇒ ∃w. status_of_pseudo_status ps' = Some … w
929    ].
930 #ps #ps' #H whd in ⊢ (mat
931 ch % with [ _ ⇒ ? | _ ⇒ ? ])
932 generalize in match (refl … (assembly (code_memory … ps)))
933 cases (assembly ?) in ⊢ (???% → %)
934  [ #K whd whd in ⊢ (??%?) <H >K %
935  | #x #K whd whd in ⊢ (?? (λ_.??%?)) <H >K % [2: % ] ]
936qed.*)
937
938let rec encoding_check' (code_memory: BitVectorTrie Byte 16) (pc: Word) (encoding: list Byte) on encoding: Prop ≝
939  match encoding with
940  [ nil ⇒ True
941  | cons hd tl ⇒
942    let 〈new_pc, byte〉 ≝ next code_memory pc in
943      hd = byte ∧ encoding_check' code_memory new_pc tl
944  ].
945
946(* prove later *)
947axiom test:
948  ∀pc: Word.
949  ∀code_memory: BitVectorTrie Byte 16.
950  ∀i: instruction.
951    let assembled ≝ assembly1 i in
952      encoding_check' code_memory pc assembled →
953        let 〈instr_pc, ignore〉 ≝ fetch code_memory pc in
954        let 〈instr, pc〉 ≝ instr_pc in
955          instr = i.
956 
957lemma main_thm:
958 ∀ticks_of.
959 ∀ps: PseudoStatus.
960  match status_of_pseudo_status ps with [ None ⇒ True | Some s ⇒
961  let ps' ≝ execute_1_pseudo_instruction ticks_of ps in
962  match status_of_pseudo_status ps' with [ None ⇒ True | Some s'' ⇒
963  let s' ≝ execute_1 s in
964   s = s'']].
965 #ticks_of #ps
966 whd in ⊢ (match % with [ _ ⇒ ? | _ ⇒ ? ])
967 cases (assembly (code_memory pseudo_assembly_program ps)) [%] * #cm #costs whd
968 whd in ⊢ (match % with [ _ ⇒ ? | _ ⇒ ? ])
969 generalize in match (sig2 … (execute_1_pseudo_instruction' ticks_of ps))
970 
971 cases (status_of_pseudo_status (execute_1_pseudo_instruction ticks_of ps)) [%] #s'' whd
Note: See TracBrowser for help on using the repository browser.