source: src/ASM/CostsProof.ma @ 1928

Last change on this file since 1928 was 1928, checked in by mulligan, 8 years ago

Moved code from in ASM/ASMCosts*.ma and ASM/CostsProof.ma that should rightfully be in another file. Added a new file, ASM/UtilBranch.ma for code that should rightfully be in ASM/Util.ma but is incomplete (i.e. daemons).

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