source: src/ASM/CostsProof.ma @ 2657

Last change on this file since 2657 was 2657, checked in by sacerdot, 7 years ago

Cost proof fully repaired. It was broken by the definitions used in compiler.ma.

File size: 35.0 KB
Line 
1include "ASM/ASMCostsSplit.ma".
2include "ASM/WellLabeled.ma".
3include "ASM/Status.ma".
4include "common/StructuredTraces.ma".
5include "arithmetics/bigops.ma".
6
7include alias "arithmetics/nat.ma".
8include alias "basics/logic.ma".
9
10let rec compute_max_trace_label_label_cost
11  (cm: ?)
12  (cost_labels: BitVectorTrie costlabel 16)
13   (trace_ends_flag: trace_ends_with_ret)
14    (start_status: Status cm) (final_status: Status cm)
15      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
16        start_status final_status) on the_trace: nat ≝
17  match the_trace with
18  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
19      compute_max_trace_any_label_cost … given_trace
20  ]
21and compute_max_trace_any_label_cost
22  (cm: ?)
23  (cost_labels: BitVectorTrie costlabel 16)
24  (trace_ends_flag: trace_ends_with_ret)
25   (start_status: Status cm) (final_status: Status cm)
26     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag start_status final_status)
27       on the_trace: nat ≝
28  match the_trace with
29  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost cm the_status
30  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost cm the_status
31  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
32      let current_instruction_cost ≝ current_instruction_cost cm pre_fun_call in
33      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
34        call_trace_cost + current_instruction_cost
35  | tal_base_tailcall pre_fun_call start_fun_call final _ _ call_trace ⇒
36      let current_instruction_cost ≝ current_instruction_cost cm pre_fun_call in
37      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
38        call_trace_cost + current_instruction_cost
39  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
40     _ _ _ call_trace _ final_trace ⇒
41      let current_instruction_cost ≝ current_instruction_cost cm pre_fun_call in
42      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
43      let final_trace_cost ≝ compute_max_trace_any_label_cost cm cost_labels end_flag … final_trace in
44        call_trace_cost + current_instruction_cost + final_trace_cost
45  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
46      let current_instruction_cost ≝ current_instruction_cost cm status_pre in
47      let tail_trace_cost ≝
48       compute_max_trace_any_label_cost cm cost_labels end_flag
49        status_init status_end tail_trace
50      in
51        current_instruction_cost + tail_trace_cost
52  ]
53and compute_max_trace_label_return_cost
54  (cm: ?)
55  (cost_labels: BitVectorTrie costlabel 16)
56  (start_status: Status cm) (final_status: Status cm)
57    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels) start_status final_status)
58      on the_trace: nat ≝
59  match the_trace with
60  [ tlr_base before after trace_to_lift ⇒ compute_max_trace_label_label_cost … trace_to_lift
61  | tlr_step initial labelled final labelled_trace ret_trace ⇒
62      let labelled_cost ≝ compute_max_trace_label_label_cost … labelled_trace in
63      let return_cost ≝ compute_max_trace_label_return_cost … ret_trace in
64        labelled_cost + return_cost
65  ].
66
67include alias "arithmetics/nat.ma".
68
69let rec compute_max_trace_label_label_cost_is_ok
70  (cm: ?)
71  (cost_labels: BitVectorTrie costlabel 16)
72   (trace_ends_flag: trace_ends_with_ret)
73    (start_status: Status cm) (final_status: Status cm)
74      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
75        start_status final_status) on the_trace:
76          clock … cm … final_status = (compute_max_trace_label_label_cost cm cost_labels trace_ends_flag start_status final_status the_trace) + (clock … cm … start_status) ≝ ?
77and compute_max_trace_any_label_cost_is_ok
78  (cm: ?)
79  (cost_labels: BitVectorTrie costlabel 16)
80  (trace_ends_flag: trace_ends_with_ret)
81   (start_status: Status cm) (final_status: Status cm)
82     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag start_status final_status)
83       on the_trace:
84         clock … cm … final_status = (compute_max_trace_any_label_cost cm cost_labels trace_ends_flag start_status final_status the_trace) + (clock … cm … start_status) ≝ ?
85and compute_max_trace_label_return_cost_is_ok
86  (cm: ?)
87  (cost_labels: BitVectorTrie costlabel 16)
88  (start_status: Status cm) (final_status: Status cm)
89    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels) start_status final_status)
90      on the_trace:
91        clock … cm … final_status = (compute_max_trace_label_return_cost cm cost_labels start_status final_status the_trace) + clock … cm … start_status ≝ ?.
92  [1:
93    cases the_trace
94    #ends_flag #start_status #end_status #any_label_trace #is_costed
95    normalize @compute_max_trace_any_label_cost_is_ok
96  |2:
97    cases the_trace
98    [1,2:
99      #start_status #final_status #is_next #is_not_return try (#is_costed)
100      change with (current_instruction_cost cm start_status) in ⊢ (???(?%?));
101      cases(is_next) @execute_1_ok_clock
102    |3:
103      #status_pre_fun_call #status_start_fun_call #status_final #is_next
104      #classifier_assm #after_return_assm #call_trace #costed_assm
105      whd in match (compute_max_trace_any_label_cost … (tal_base_call …));
106      >(compute_max_trace_label_return_cost_is_ok … call_trace)
107      >associative_plus @eq_f cases(is_next)
108      @execute_1_ok_clock
109    |4:
110      #status_pre_fun_call #status_start_fun_call #status_final #is_next
111      #classifier_assm #call_trace
112      whd in match (compute_max_trace_any_label_cost … (tal_base_tailcall …));
113      >(compute_max_trace_label_return_cost_is_ok … call_trace)
114      >associative_plus @eq_f cases(is_next)
115      @execute_1_ok_clock
116    |5:
117      #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
118      #status_final #is_next #is_call #is_after_return #call_trace #not_costed #final_trace
119      change with (
120      let current_instruction_cost ≝ current_instruction_cost cm status_pre_fun_call in
121      let call_trace_cost ≝ compute_max_trace_label_return_cost cm … call_trace in
122      let final_trace_cost ≝ compute_max_trace_any_label_cost cm cost_labels end_flag … final_trace in
123        call_trace_cost + current_instruction_cost + final_trace_cost) in ⊢ (???(?%?));
124      normalize nodelta;
125      >(compute_max_trace_any_label_cost_is_ok … cost_labels end_flag status_after_fun_call
126          status_final final_trace)
127      >(compute_max_trace_label_return_cost_is_ok … cost_labels status_start_fun_call
128        status_after_fun_call call_trace)
129      cases(is_next) in match (clock … cm status_start_fun_call);
130      >(execute_1_ok_clock cm status_pre_fun_call)
131      <associative_plus in ⊢ (??%?);
132      <commutative_plus in match (
133        compute_max_trace_any_label_cost cm cost_labels end_flag status_after_fun_call status_final final_trace
134          + compute_max_trace_label_return_cost cm cost_labels status_start_fun_call status_after_fun_call call_trace);
135      >associative_plus in ⊢ (??%?); >associative_plus in ⊢ (???%); >associative_plus in ⊢ (???%);
136      @eq_f >commutative_plus in ⊢ (??%?); >associative_plus in ⊢ (??%?);
137      @eq_f @commutative_plus
138    |6:
139      #end_flag #status_pre #status_init #status_end #is_next
140      #trace_any_label #is_other #is_not_costed
141      change with (
142      let current_instruction_cost ≝ current_instruction_cost cm status_pre in
143      let tail_trace_cost ≝
144       compute_max_trace_any_label_cost cm cost_labels end_flag
145        status_init status_end trace_any_label
146      in
147        current_instruction_cost + tail_trace_cost) in ⊢ (???(?%?));
148      normalize nodelta;
149      >(compute_max_trace_any_label_cost_is_ok cm cost_labels end_flag
150         status_init status_end trace_any_label)
151      cases(is_next) in match (clock … cm status_init);
152      >(execute_1_ok_clock … status_pre)
153      >commutative_plus >associative_plus >associative_plus @eq_f
154      @commutative_plus
155    ]
156  |3:
157    cases the_trace
158    [1:
159      #status_before #status_after #trace_to_lift
160      normalize @compute_max_trace_label_label_cost_is_ok
161    |2:
162      #status_initial #status_labelled #status_final #labelled_trace #ret_trace
163      normalize
164      >(compute_max_trace_label_return_cost_is_ok cm cost_labels status_labelled status_final ret_trace);
165      >(compute_max_trace_label_label_cost_is_ok cm cost_labels doesnt_end_with_ret status_initial status_labelled labelled_trace);
166      <associative_plus in ⊢ (??%?);
167      >commutative_plus in match (
168        compute_max_trace_label_return_cost cm cost_labels status_labelled status_final ret_trace
169          + compute_max_trace_label_label_cost cm cost_labels doesnt_end_with_ret status_initial status_labelled labelled_trace);
170      %
171    ]
172  ]
173qed.
174
175let rec compute_trace_label_label_cost_using_paid
176  (cm: ?)
177  (cost_labels: BitVectorTrie costlabel 16)
178   (trace_ends_flag: trace_ends_with_ret)
179    (start_status: Status cm) (final_status: Status cm)
180      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
181        start_status final_status) on the_trace: nat ≝
182  match the_trace with
183  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
184      compute_paid_trace_label_label cm cost_labels … the_trace +
185      compute_trace_any_label_cost_using_paid … given_trace
186  ]
187and compute_trace_any_label_cost_using_paid
188  (cm: ?)
189  (cost_labels: BitVectorTrie costlabel 16)
190  (trace_ends_flag: trace_ends_with_ret)
191   (start_status: Status cm) (final_status: Status cm)
192     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag start_status final_status)
193       on the_trace: nat ≝
194  match the_trace with
195  [ tal_base_not_return the_status _ _ _ _ ⇒ 0
196  | tal_base_return the_status _ _ _ ⇒ 0
197  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
198      compute_trace_label_return_cost_using_paid … call_trace
199  | tal_base_tailcall pre_fun_call start_fun_call final _ _ call_trace ⇒
200      compute_trace_label_return_cost_using_paid … call_trace
201  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
202     _ _ _ call_trace _ final_trace ⇒
203      let call_trace_cost ≝ compute_trace_label_return_cost_using_paid … call_trace in
204      let final_trace_cost ≝ compute_trace_any_label_cost_using_paid cm cost_labels end_flag … final_trace in
205        call_trace_cost + final_trace_cost
206  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
207     compute_trace_any_label_cost_using_paid cm cost_labels end_flag
208      status_init status_end tail_trace
209  ]
210and compute_trace_label_return_cost_using_paid
211  (cm: ?)
212  (cost_labels: BitVectorTrie costlabel 16)
213  (start_status: Status cm) (final_status: Status cm)
214    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels) start_status final_status)
215      on the_trace: nat ≝
216  match the_trace with
217  [ tlr_base before after trace_to_lift ⇒ compute_trace_label_label_cost_using_paid … trace_to_lift
218  | tlr_step initial labelled final labelled_trace ret_trace ⇒
219      let labelled_cost ≝ compute_trace_label_label_cost_using_paid … labelled_trace in
220      let return_cost ≝ compute_trace_label_return_cost_using_paid … ret_trace in
221        labelled_cost + return_cost
222  ].
223
224let rec compute_trace_label_label_cost_using_paid_ok
225  (cm: ?)
226  (cost_labels: BitVectorTrie costlabel 16)
227   (trace_ends_flag: trace_ends_with_ret)
228    (start_status: Status cm) (final_status: Status cm)
229      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
230        start_status final_status) on the_trace:
231 compute_trace_label_label_cost_using_paid cm cost_labels … the_trace =
232 compute_max_trace_label_label_cost … the_trace ≝ ?
233and compute_trace_any_label_cost_using_paid_ok
234  (cm: ?)
235  (cost_labels: BitVectorTrie costlabel 16)
236  (trace_ends_flag: trace_ends_with_ret)
237   (start_status: Status cm) (final_status: Status cm)
238     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels)
239      trace_ends_flag start_status final_status) on the_trace:     
240  compute_paid_trace_any_label cm cost_labels trace_ends_flag … the_trace
241  +compute_trace_any_label_cost_using_paid cm cost_labels trace_ends_flag … the_trace
242  =compute_max_trace_any_label_cost cm cost_labels trace_ends_flag … the_trace ≝ ?
243and compute_trace_label_return_cost_using_paid_ok
244  (cm: ?)
245  (cost_labels: BitVectorTrie costlabel 16)
246  (start_status: Status cm) (final_status: Status cm)
247    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels)
248     start_status final_status) on the_trace:
249 compute_trace_label_return_cost_using_paid cm cost_labels … the_trace =
250 compute_max_trace_label_return_cost cm cost_labels … the_trace ≝ ?.
251[ cases the_trace #endsf #ss #es #tr #H normalize
252  @compute_trace_any_label_cost_using_paid_ok
253| cases the_trace
254  [ #ss #fs #H1 #H2 #H3 whd in ⊢ (??(?%%)%); <plus_n_O %
255  | #ss #fs #H1 #H2 whd in ⊢ (??(?%%)%); <plus_n_O %
256  | #sp #ss #sf #H1 #H2 #tr1 #tr2 #H3
257    whd in ⊢ (???%); whd in ⊢ (??(??%)?); whd in ⊢ (??(?%?)?);
258    >compute_trace_label_return_cost_using_paid_ok in ⊢ (??%?);
259    >commutative_plus in ⊢ (??%?); @eq_f %
260  | #sp #ss #sf #H1 #H2 #tr1
261    whd in ⊢ (???%); whd in ⊢ (??(??%)?); whd in ⊢ (??(?%?)?);
262    >compute_trace_label_return_cost_using_paid_ok in ⊢ (??%?);
263    >commutative_plus in ⊢ (??%?); @eq_f %
264  | #ef #spfc #ssfc #safc #sf #H1 #H2 #H3 #tr1 #H4 #tr2 whd in ⊢ (??(?%%)%);
265    <compute_trace_any_label_cost_using_paid_ok
266    <compute_trace_label_return_cost_using_paid_ok
267    -compute_trace_label_label_cost_using_paid_ok
268    -compute_trace_label_return_cost_using_paid_ok
269    -compute_trace_any_label_cost_using_paid_ok
270    >commutative_plus in ⊢ (???(?%?));
271    >commutative_plus in ⊢ (??(??%)?);
272    >associative_plus >associative_plus in ⊢ (???%); @eq_f2 try %
273    <associative_plus <commutative_plus %
274  | #ef #sp #si #se #H1 #tr #H2 #H3 whd in ⊢ (??(?%%)%); >associative_plus @eq_f2
275    [ % | @compute_trace_any_label_cost_using_paid_ok ]
276  ]
277| cases the_trace
278  [ #sb #sa #tr normalize @compute_trace_label_label_cost_using_paid_ok
279  | #si #sl #sf #tr1 #tr2 normalize @eq_f2
280    [ @compute_trace_label_label_cost_using_paid_ok
281    | @compute_trace_label_return_cost_using_paid_ok ]]]
282qed.
283
284include alias "ASM/BitVectorTrie.ma".
285
286(*
287let rec compute_cost_trace_label_label
288  (cm: BitVectorTrie Byte 16)
289  (cost_labels: BitVectorTrie costlabel 16)
290   (trace_ends_flag: trace_ends_with_ret)
291    (start_status: Status cm) (final_status: Status cm)
292      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
293        start_status final_status) on the_trace:
294         list (Σk:costlabel. ∃pc: Word. lookup_opt … pc cost_labels = Some … k) ≝
295  match the_trace with
296  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
297     let pc ≝ program_counter ? cm initial in
298     let label ≝
299      match lookup_opt … pc cost_labels return λx: option ?. x ≠ None … → costlabel with
300      [ None ⇒ λabs. ⊥
301      | Some l ⇒ λ_. l ] labelled_proof in
302      (mk_Sig ?? label ?)::compute_cost_trace_any_label cm cost_labels ends_flag initial final … given_trace
303  ]
304and compute_cost_trace_any_label
305  (cm: BitVectorTrie Byte 16)
306  (cost_labels: BitVectorTrie costlabel 16)
307  (trace_ends_flag: trace_ends_with_ret)
308   (start_status: Status cm) (final_status: Status cm)
309     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag start_status final_status)
310       on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
311  match the_trace with
312  [ tal_base_not_return the_status _ _ _ _ ⇒ [ ]
313  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
314      compute_cost_trace_label_return … call_trace
315  | tal_base_return the_status _ _ _ ⇒ [ ]
316  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
317     _ _ _ call_trace _ final_trace ⇒
318      let call_cost_trace ≝ compute_cost_trace_label_return … call_trace in
319      let final_cost_trace ≝ compute_cost_trace_any_label cm cost_labels end_flag … final_trace in
320        call_cost_trace @ final_cost_trace
321  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
322       compute_cost_trace_any_label cm cost_labels end_flag
323        status_init status_end tail_trace
324  ]
325and compute_cost_trace_label_return
326  (cm: BitVectorTrie Byte 16)
327  (cost_labels: BitVectorTrie costlabel 16)
328  (start_status: Status cm) (final_status: Status cm)
329    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels) start_status final_status)
330      on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
331  match the_trace with
332  [ tlr_base before after trace_to_lift ⇒ compute_cost_trace_label_label cm … trace_to_lift
333  | tlr_step initial labelled final labelled_trace ret_trace ⇒
334      let labelled_cost ≝ compute_cost_trace_label_label cm … labelled_trace in
335      let return_cost ≝ compute_cost_trace_label_return cm … ret_trace in
336        labelled_cost @ return_cost
337  ].
338 [1:
339  %{pc} whd in match label;  generalize in match labelled_proof; whd in ⊢ (% → ?);
340   whd in match (as_costed ??); whd in match (as_label ??); normalize nodelta
341   cases (lookup_opt costlabel … (program_counter … initial) cost_labels)
342   normalize
343  [ #abs cases abs #absurd @⊥ @absurd % | // ]
344 | cases abs #absurd @absurd % ]
345qed.
346*)
347
348include alias "arithmetics/nat.ma".
349include alias "basics/logic.ma".
350
351include alias "arithmetics/bigops.ma".
352
353(* This shoudl go in bigops! *)
354theorem bigop_sum_rev: ∀k1,k2,p,B,nil.∀op:Aop B nil.∀f:nat→B.
355 \big[op,nil]_{i<k1+k2|p i} (f i) =
356 op \big[op,nil]_{i<k2|p (i+k1)} (f (i+k1)) \big[op,nil]_{i<k1|p i} (f i).
357 #k1 #k2 #p #B #nil #op #f >bigop_sum
358 >commutative_plus @same_bigop #i @leb_elim normalize
359 [2,4: //
360 | #H1 #H2 <plus_minus_m_m //
361 | #H1 #H2 #H3 <plus_minus_m_m //]
362qed.
363
364(* This is taken by sigma_pi.ma that does not compile now *)
365definition natAop ≝ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
366   (λa,b,c.sym_eq ??? (associative_plus a b c)).
367
368definition natACop ≝ mk_ACop nat 0 natAop commutative_plus.
369
370definition natDop ≝ mk_Dop nat 0 natACop times (λn.(sym_eq ??? (times_n_O n)))
371   distributive_times_plus.
372
373unification hint  0 ≔ ;
374   S ≟ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
375   (λa,b,c.sym_eq ??? (associative_plus a b c))
376(* ---------------------------------------- *) ⊢
377   plus ≡ op ? ? S.
378
379unification hint  0 ≔ ;
380   S ≟ mk_ACop nat 0 (mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
381   (λa,b,c.sym_eq ??? (associative_plus a b c))) commutative_plus
382(* ---------------------------------------- *) ⊢
383   plus ≡ op ? ? S.
384   
385unification hint  0 ≔ ;
386   S ≟ natDop
387(* ---------------------------------------- *) ⊢
388   plus ≡ sum ? ? S.
389
390unification hint  0 ≔ ;
391   S ≟ natDop
392(* ---------------------------------------- *) ⊢
393   times ≡ prod ? ? S.
394
395notation > "Σ_{ ident i < n } f"
396  with precedence 20
397for @{'bigop $n plus 0 (λ${ident i}.true) (λ${ident i}. $f)}.
398
399notation < "Σ_{ ident i < n } f"
400  with precedence 20
401for @{'bigop $n plus 0 (λ${ident i}:$X.true) (λ${ident i}:$Y. $f)}.
402
403definition tech_cost_of_label0:
404 ∀cost_labels: BitVectorTrie costlabel 16.
405 ∀cost_map: identifier_map CostTag nat.
406 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
407 ∀ctrace:list (Σk:costlabel.∃b.lookup_opt … b cost_labels = Some ? k).
408 ∀i,p. present … cost_map (nth_safe ? i ctrace p).
409 #cost_labels #cost_map #codom_dom #ctrace #i #p
410 cases (nth_safe … i ctrace ?) normalize #id * #id_pc #K
411 lapply (codom_dom … K) #k_pres >(lookup_lookup_present … k_pres)
412 % #abs destruct (abs)
413qed.
414
415include alias "arithmetics/nat.ma".
416include alias "basics/logic.ma".
417
418lemma ltb_rect:
419 ∀P:Type[0].∀n,m. (n < m → P) → (¬ n < m → P) → P.
420 #P #n #m lapply (refl … (ltb n m)) cases (ltb n m) in ⊢ (???% → %); #E #H1 #H2
421 [ @H1 @leb_true_to_le @E | @H2 @leb_false_to_not_le @E ]
422qed.
423
424lemma same_ltb_rect:
425 ∀P,n,m,H1,H2,n',m',H1',H2'.
426  ltb n m = ltb n' m' → (∀x,y. H1 x = H1' y) → (∀x,y. H2 x = H2' y) →
427   ltb_rect P n m H1 H2 =
428   ltb_rect P n' m' H1' H2'.
429 #P #n #m #H1 #H2 #n' #m' #H1' #H2' #E #K1 #K2 whd in ⊢ (??%?);
430 cut (∀xxx,yyy,xxx',yyy'.
431   match ltb n m
432   return λx:bool.
433           eq bool (ltb n m) x
434            → (lt n m → P) → (Not (lt n m) → P) → P
435    with
436    [ true ⇒
437        λE0:eq bool (ltb n m) true.
438         λH10:lt n m → P.
439          λH20:Not (lt n m) → P. H10 (xxx E0)
440    | false ⇒
441        λE0:eq bool (ltb n m) false.
442         λH10:lt n m → P.
443          λH20:Not (lt n m) → P. H20 (yyy E0)]
444    (refl … (ltb n m)) H1 H2 =
445   match ltb n' m'
446   return λx:bool.
447           eq bool (ltb n' m') x
448            → (lt n' m' → P) → (Not (lt n' m') → P) → P
449    with
450    [ true ⇒
451        λE0:eq bool (ltb n' m') true.
452         λH10:lt n' m' → P.
453          λH20:Not (lt n' m') → P. H10 (xxx' E0)
454    | false ⇒
455        λE0:eq bool (ltb n' m') false.
456         λH10:lt n' m' → P.
457          λH20:Not (lt n' m') → P. H20 (yyy' E0)]
458    (refl … (ltb n' m')) H1' H2'
459  ) [2: #X @X]
460 >E cases (ltb n' m') #xxx #yyy #xxx' #yyy' normalize
461 [ @K1 | @K2 ]
462qed.
463
464definition tech_cost_of_label:
465 ∀cost_labels: BitVectorTrie costlabel 16.
466 ∀cost_map: identifier_map CostTag nat.
467 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
468 list (Σk:costlabel.∃b.lookup_opt … b cost_labels = Some ? k) →
469 nat → nat
470≝ λcost_labels,cost_map,codom_dom,ctrace,i.
471 ltb_rect ? i (|ctrace|)
472 (λH. lookup_present ?? cost_map (nth_safe ? i ctrace H) ?)
473 (λ_.0).
474 @tech_cost_of_label0 @codom_dom
475qed.
476
477lemma tech_cost_of_label_shift:
478 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
479  i < |l2| →
480   tech_cost_of_label cost_labels cost_map codom_dom l2 i =
481   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) (i+|l1|).
482 #cost_labels #cost_Map #codom_dom #l1 #l2 #i #H
483 whd in match tech_cost_of_label; normalize nodelta @same_ltb_rect
484 [ @(ltb_rect ? i (|l2|)) @(ltb_rect ? (i+|l1|) (|l1@l2|)) #K1 #K2
485   whd in match ltb; normalize nodelta
486   [1: >le_to_leb_true try assumption applyS le_to_leb_true / by /
487   |4: >not_le_to_leb_false try assumption applyS not_le_to_leb_false
488       change with (¬ ? ≤ ?) in K1; applyS K1
489   |2: @⊥ @(absurd (i+|l1| < |l1@l2|)) / by / >length_append
490       applyS (monotonic_lt_plus_r … (|l1|)) / by /
491   |3: @⊥ @(absurd ?? K2) >length_append in K1; #K1 /2 by lt_plus_to_lt_l/ ]
492 | #H1 #H2
493   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
494   <(shift_nth_safe … H1) #p %
495 | / by / ]
496qed.
497
498lemma tech_cost_of_label_prefix:
499 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
500  i < |l1| →
501   tech_cost_of_label cost_labels cost_map codom_dom l1 i =
502   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) i.
503 #cost_labels #cost_map #codom_dom #l1 #l2 #i #H
504 whd in match tech_cost_of_label; normalize nodelta @same_ltb_rect
505 [1:
506   whd in match ltb; normalize nodelta
507   >(le_to_leb_true … H) applyS le_to_leb_true
508   >length_append whd in H; >commutative_plus @le_plus_a assumption
509 |2:
510   #K1 #K2
511   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
512   <(shift_nth_prefix … l1 i l2 K1 K2) //
513 |3:
514   #_ #_ %
515 ]
516qed.
517   
518let rec compute_trace_label_return_using_paid_ok_with_trace
519 (cm: ?) (cost_labels: BitVectorTrie costlabel 16)
520 (cost_map: identifier_map CostTag nat)
521 (initial: Status cm) (final: Status cm)
522 (trace: trace_label_return (ASM_abstract_status cm cost_labels) initial final)
523 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
524 on trace:
525 ∀unrepeating_witness: tlr_unrepeating … trace.
526 ∀dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
527   pi1 … (block_cost cm pc cost_labels) = lookup_present … k_pres).
528  let ctrace ≝ flatten_trace_label_return (ASM_abstract_status cm cost_labels) … trace in
529  compute_trace_label_return_cost_using_paid cm … trace =
530   (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i))
531    ≝ ?
532and compute_trace_any_label_using_paid_ok_with_trace
533 (cm: ?) (cost_labels: BitVectorTrie costlabel 16)
534 (trace_ends_flag: trace_ends_with_ret)
535 (cost_map: identifier_map CostTag nat)
536 (initial: Status cm) (final: Status cm)
537 (trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag initial final)
538 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
539 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
540   pi1 … (block_cost cm pc cost_labels) = lookup_present … k_pres))
541 on trace:
542  ∀unrepeating_witness: tal_unrepeating … trace.
543  let ctrace ≝ flatten_trace_any_label (ASM_abstract_status cm cost_labels) … trace_ends_flag … trace in
544  compute_trace_any_label_cost_using_paid … trace =
545   (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i))
546    ≝ ?
547and compute_trace_label_label_using_paid_ok_with_trace
548 (cm: ?) (cost_labels: BitVectorTrie costlabel 16)
549 (trace_ends_flag: trace_ends_with_ret)
550 (cost_map: identifier_map CostTag nat)
551 (initial: Status cm) (final: Status cm)
552 (trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag initial final)
553 (unrepeating_witness: tll_unrepeating … trace)
554 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
555 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
556   pi1 … (block_cost cm pc cost_labels) = lookup_present … k_pres))
557 on trace:
558 ∀unrepeating_witness: tll_unrepeating … trace.
559  let ctrace ≝ flatten_trace_label_label (ASM_abstract_status cm cost_labels) … trace in
560  compute_trace_label_label_cost_using_paid … trace =
561   (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i))
562    ≝ ?.
563  cases trace normalize nodelta
564  [ #sb #sa #tr #unrepeating_witness #dom_codom whd in ⊢ (??%?);
565    whd in match (flatten_trace_label_return ????);
566    @compute_trace_label_label_using_paid_ok_with_trace
567    assumption
568  | #si #sl #sf #tr1 #tr2 #unrepeating_witness #dom_codom
569    whd in ⊢ (??%?);
570    whd in match (flatten_trace_label_return ????);
571    >append_length >bigop_sum_rev >commutative_plus @eq_f2
572    [ >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
573      -compute_trace_label_return_using_paid_ok_with_trace
574      [1:
575        @same_bigop [//] #i #H #_ -dom_codom @tech_cost_of_label_shift //
576      |2:
577        inversion unrepeating_witness
578        #tll_unrepeating #tlr_unrepeating #_ assumption
579      ]
580    | >(compute_trace_label_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
581      -compute_trace_label_label_using_paid_ok_with_trace
582      [1:
583        @same_bigop [//] #i #H #_ @(tech_cost_of_label_prefix … H)
584      |2,3:
585        inversion unrepeating_witness
586        #tll_unrepeating #tlr_unrepeating #_ assumption
587      ]
588    ]
589  |9:
590    #end_flag #start_status #end_status #trace_any_label #costed_assm
591    #unrepeating_witness'
592    whd in ⊢ (??%?); whd in ⊢ (??(?%?)?);
593    >(compute_trace_any_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
594    [1:
595      whd in match (flatten_trace_label_label ?????);
596      >bigop_0 in ⊢ (???%); >commutative_plus @eq_f2
597      [1:
598        @same_bigop [//] #i #H #_ -dom_codom >(plus_n_O i) >plus_n_Sm
599        <(tech_cost_of_label_shift ??? [?] ? i) try assumption <(plus_n_O i) %
600      |2:
601        change with (? = lookup_present ? ? ? ? ?)
602        generalize in match (tech_cost_of_label0 ? ? ? ? ? ?);
603        whd in ⊢ (∀p:????%.???(????%?));
604        whd in costed_assm; lapply costed_assm whd in match (as_label ??);
605        inversion (lookup_opt ? ? (program_counter … cm start_status) cost_labels)
606        [1:
607          #_ #absurd @⊥ cases absurd #absurd @absurd %
608        |2:
609          normalize nodelta #cost_label #Some_assm #_ #p
610          cases (dom_codom ? p ? Some_assm)
611          cases (block_cost ???)
612          #cost #block_cost_assm
613          cases (block_cost_assm ??? trace_any_label ??)
614          try @refl assumption
615        ]
616      ]
617    |2:
618      assumption
619    ]
620  |3:
621    #start_status #final_status #execute_assm #classifier_assm #costed_assm
622    #unrepeating_witness
623    %
624  |4:
625    #start_status #final_status #execute_assm #classifier_assm #unrepeating_witness
626    %
627  |5:
628    #status_pre_fun_call #status_start_fun_call #status_final #execute_assm
629    #classifier_assm #after_return_assm #trace_label_return #costed_assm #unrepeating_witness
630    whd in ⊢ (??%?);
631    @(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
632    assumption
633  |6:
634    #status_pre_fun_call #status_start_fun_call #status_final #execute_assm
635    #classifier_assm #trace_label_return #unrepeating_witness
636    whd in ⊢ (??%?);
637    @(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
638    assumption
639  |7:
640    #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
641    #status_final #execute_assm #classifier_assm #after_return_assm #trace_label_return
642    #costed_assm #trace_any_label #unrepeating_witness
643    whd in ⊢ (??%?);
644    >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
645    [1:
646      >(compute_trace_any_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
647      [1:
648        >length_append >bigop_sum_rev >commutative_plus @eq_f2
649        [ @same_bigop [2: #i #H #_ -dom_codom @tech_cost_of_label_shift assumption
650                      |1: #i #H % ]
651        | @same_bigop [#i #H %] #i #H #_ @(tech_cost_of_label_prefix … H)
652        ]
653      |2:
654        inversion unrepeating_witness
655        * #memb_1 #tal_unrepeating #tlr_unrepeating #_ assumption
656      ]
657    |2:
658      inversion unrepeating_witness
659      * #memb_1 #tal_unrepeating #tlr_unrepeating #_ assumption
660    ]
661  |8:
662    #end_flag #status_pre_fun_call #status_start_fun_call #status_final
663    #execute_assm #trace_any_label #classifier_assm #costed_assm #unrepeating_witness
664    whd in ⊢ (??%?);
665    @(compute_trace_any_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
666    inversion unrepeating_witness
667    #memb_1 #tal_unrepeating #_ assumption
668  ]
669qed.
670 
671lemma compute_max_trace_label_return_cost_ok_with_trace_aux:
672  ∀code_memory: BitVectorTrie Byte 16.
673  ∀cost_labels: BitVectorTrie costlabel 16.
674  ∀cost_map: identifier_map CostTag nat.
675  ∀initial: Status code_memory.
676  ∀final: Status code_memory.
677  ∀trace: trace_label_return (ASM_abstract_status code_memory cost_labels) initial final.
678  ∀unrepeating_witness: tlr_unrepeating … trace.
679  ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
680  ∀dom_codom: (∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
681      pi1 … (block_cost code_memory pc cost_labels) = lookup_present … k_pres).
682        let ctrace ≝ flatten_trace_label_return … trace in
683          clock … code_memory … final =
684            clock … code_memory … initial + (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i)).
685  #code_memory #cost_labels #cost_map
686  #initial #final #trace #unrepeating_witness #codom_dom #dom_codom normalize nodelta
687  <compute_trace_label_return_using_paid_ok_with_trace try assumption
688  >commutative_plus >compute_trace_label_return_cost_using_paid_ok //
689qed.
690
691theorem compute_max_trace_label_return_cost_ok_with_trace:
692  ∀code_memory: BitVectorTrie Byte 16.
693  ∀cost_labels: BitVectorTrie costlabel 16.
694  ∀cost_labels_injective:
695   (∀pc,pc',l.
696     lookup_opt costlabel 16 pc cost_labels=Some costlabel l
697      →lookup_opt costlabel 16 pc' cost_labels=Some costlabel l→pc=pc').
698  ∀initial: Status code_memory.
699  ∀final: Status code_memory.
700  ∀trace: trace_label_return (ASM_abstract_status code_memory cost_labels) initial final.
701  ∀unrepeating_witness: tlr_unrepeating … trace.
702    let cost_map ≝ traverse_code code_memory cost_labels cost_labels_injective in
703    let ctrace ≝ flatten_trace_label_return … trace in
704      clock … code_memory … final = clock … code_memory … initial + (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map ? ctrace i)).
705  [1:
706    #code_memory #cost_labels #cost_labels_injective #initial #final #trace #unrepeating_witness
707    @compute_max_trace_label_return_cost_ok_with_trace_aux try assumption
708  |2:
709    skip
710  ]
711  normalize nodelta
712  cases (traverse_code ???)
713  #cost_map * #dom_codom #codom_dom try assumption
714  #pc #k #lookup_opt_assm @(dom_codom … lookup_opt_assm)
715  lapply (sym_eq ? ? ? lookup_opt_assm)
716  -lookup_opt_assm #lookup_opt_assm
717  @nat_of_bitvector_lt_bound
718qed.
719 
720include "utilities/permutations.ma".
721
722definition map_of_sigma_map:
723 ∀P.
724  (Σmap:identifier_map CostTag ℕ.P map) → identifier_map CostTag ℕ
725 ≝ λP,x.x.
726
727definition costlabel_of_as_cost_labels:
728 ∀code,cost_labels.
729  as_cost_label (ASM_abstract_status (load_code_memory code) cost_labels)
730  →Σk:costlabel
731   .(∃b:BitVector 16.lookup_opt costlabel 16 b cost_labels = Some costlabel k).
732 #code #cost_labels * #l #Hl %{l} cases Hl #pc #Hl' %{pc} @Hl'
733qed.
734
735lemma costlabel_map_of_as_cost_labels_map_ok:
736 ∀ccode1,ccode2,cost_labels_injective,tl,Htl,PRF,PRF2.
737  lookup_present CostTag ℕ (compute_costs ccode1 ccode2 cost_labels_injective) tl
738  PRF
739  =
740   lookup_present CostTag ℕ (compute_costs ccode1 ccode2 cost_labels_injective)
741   (as_cost_get_label (ASM_abstract_status (load_code_memory ccode1) ccode2)
742    «tl,Htl») PRF2.
743//
744qed.
745
746lemma tech_cost_sum_eq_as_cost :
747  ∀compiled_code: (list Byte) × (BitVectorTrie costlabel 16).
748  let cost_labels ≝ \snd compiled_code in
749  ∀cost_labels_injective:
750   (∀pc,pc',l.
751     lookup_opt … pc (\snd  compiled_code) = Some … l
752     → lookup_opt … pc' (\snd  compiled_code) = Some … l → pc = pc').
753  let cost_map ≝ compute_costs (\fst compiled_code) (\snd compiled_code) cost_labels_injective in
754  ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … k).
755  ∀trace.
756  (Σ_{i < |trace|}(tech_cost_of_label cost_labels (map_of_sigma_map … cost_map) codom_dom (map ?? (costlabel_of_as_cost_labels …) trace) i)) =
757  (Σ_{l ∈ trace}(ASM_cost_map compiled_code cost_labels_injective l)).
758* #ccode1 #ccode2 #cost_labels_injective #codom_dom #trace
759@(list_elim_left … trace)
760[ %
761| #tl #hd #IH >append_length >commutative_plus
762  >(fold_permute … (hd@[tl]) (tl::hd)) [2: @perm_swap_append ]
763  whd in ⊢ (??%%); <IH <map_append
764  <(? : | map … hd | = | hd |) [1: <tech_cost_of_label_shift] [2: % | 5: // |3,4: skip]
765  cut (∀x,y,z,w.x = y → z = w → x + z = y + w) [ // ] #APP @APP -APP
766  [ cases tl -tl #tl #Htl
767    change with (lookup_present ????? = ?)
768    whd in ⊢ (???(%???)); normalize nodelta
769    generalize in ⊢ (???(?????%)); #p
770    @costlabel_map_of_as_cost_labels_map_ok
771  | @sym_eq @same_bigop /2 by tech_cost_of_label_prefix/
772  ]
773]
774qed.
Note: See TracBrowser for help on using the repository browser.