source: src/ASM/CostsProof.ma @ 2760

Last change on this file since 2760 was 2760, checked in by sacerdot, 7 years ago
  1. Many files repaired.
  2. 3 new daemons: 2 in Assembly.ma, 1 in StructuredTraces?.ma
File size: 32.3 KB
RevLine 
[1898]1include "ASM/ASMCostsSplit.ma".
[1499]2include "ASM/WellLabeled.ma".
3include "ASM/Status.ma".
[1544]4include "common/StructuredTraces.ma".
[1619]5include "arithmetics/bigops.ma".
[1898]6
[1619]7include alias "arithmetics/nat.ma".
8include alias "basics/logic.ma".
[1498]9
[1506]10let rec compute_max_trace_label_label_cost
[1692]11  (cm: ?)
[2516]12  (cost_labels: BitVectorTrie costlabel 16)
[1544]13   (trace_ends_flag: trace_ends_with_ret)
[1692]14    (start_status: Status cm) (final_status: Status cm)
15      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
[1544]16        start_status final_status) on the_trace: nat ≝
[1506]17  match the_trace with
18  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
[1544]19      compute_max_trace_any_label_cost … given_trace
[1506]20  ]
[1544]21and compute_max_trace_any_label_cost
[1692]22  (cm: ?)
[2516]23  (cost_labels: BitVectorTrie costlabel 16)
[1544]24  (trace_ends_flag: trace_ends_with_ret)
[1692]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)
[1544]27       on the_trace: nat ≝
[1506]28  match the_trace with
[1693]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
[1692]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
[2656]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
[1544]39  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
[1692]40     _ _ _ call_trace _ final_trace ⇒
41      let current_instruction_cost ≝ current_instruction_cost cm pre_fun_call in
[1544]42      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
[1693]43      let final_trace_cost ≝ compute_max_trace_any_label_cost cm cost_labels end_flag … final_trace in
[1506]44        call_trace_cost + current_instruction_cost + final_trace_cost
[1544]45  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
[1692]46      let current_instruction_cost ≝ current_instruction_cost cm status_pre in
[1544]47      let tail_trace_cost ≝
[1693]48       compute_max_trace_any_label_cost cm cost_labels end_flag
[1544]49        status_init status_end tail_trace
50      in
[1506]51        current_instruction_cost + tail_trace_cost
52  ]
53and compute_max_trace_label_return_cost
[1692]54  (cm: ?)
[2516]55  (cost_labels: BitVectorTrie costlabel 16)
[1692]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)
[1506]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  ].
[1500]66
[1544]67include alias "arithmetics/nat.ma".
68
[1579]69let rec compute_max_trace_label_label_cost_is_ok
[1693]70  (cm: ?)
[2516]71  (cost_labels: BitVectorTrie costlabel 16)
[1579]72   (trace_ends_flag: trace_ends_with_ret)
[1693]73    (start_status: Status cm) (final_status: Status cm)
74      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
[1579]75        start_status final_status) on the_trace:
[1693]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) ≝ ?
[1579]77and compute_max_trace_any_label_cost_is_ok
[1693]78  (cm: ?)
[2516]79  (cost_labels: BitVectorTrie costlabel 16)
[1579]80  (trace_ends_flag: trace_ends_with_ret)
[1693]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)
[1579]83       on the_trace:
[1693]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) ≝ ?
[1579]85and compute_max_trace_label_return_cost_is_ok
[1693]86  (cm: ?)
[2516]87  (cost_labels: BitVectorTrie costlabel 16)
[1693]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)
[1579]90      on the_trace:
[1693]91        clock … cm … final_status = (compute_max_trace_label_return_cost cm cost_labels start_status final_status the_trace) + clock … cm … start_status ≝ ?.
[1579]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)
[1693]100      change with (current_instruction_cost cm start_status) in ⊢ (???(?%?));
[1898]101      cases(is_next) @execute_1_ok_clock
[1579]102    |3:
[1693]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)
[1898]108      @execute_1_ok_clock
[1693]109    |4:
[2656]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:
[1579]117      #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
[1693]118      #status_final #is_next #is_call #is_after_return #call_trace #not_costed #final_trace
[1579]119      change with (
[1693]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
[1579]123        call_trace_cost + current_instruction_cost + final_trace_cost) in ⊢ (???(?%?));
124      normalize nodelta;
[1693]125      >(compute_max_trace_any_label_cost_is_ok … cost_labels end_flag status_after_fun_call
[1579]126          status_final final_trace)
[1693]127      >(compute_max_trace_label_return_cost_is_ok … cost_labels status_start_fun_call
[1579]128        status_after_fun_call call_trace)
[1693]129      cases(is_next) in match (clock … cm status_start_fun_call);
[1898]130      >(execute_1_ok_clock cm status_pre_fun_call)
[1579]131      <associative_plus in ⊢ (??%?);
132      <commutative_plus in match (
[1693]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
[2656]138    |6:
[1579]139      #end_flag #status_pre #status_init #status_end #is_next
140      #trace_any_label #is_other #is_not_costed
141      change with (
[1693]142      let current_instruction_cost ≝ current_instruction_cost cm status_pre in
[1579]143      let tail_trace_cost ≝
[1693]144       compute_max_trace_any_label_cost cm cost_labels end_flag
[1579]145        status_init status_end trace_any_label
146      in
147        current_instruction_cost + tail_trace_cost) in ⊢ (???(?%?));
148      normalize nodelta;
[1693]149      >(compute_max_trace_any_label_cost_is_ok cm cost_labels end_flag
[1579]150         status_init status_end trace_any_label)
[1693]151      cases(is_next) in match (clock … cm status_init);
[1898]152      >(execute_1_ok_clock … status_pre)
[1619]153      >commutative_plus >associative_plus >associative_plus @eq_f
154      @commutative_plus
[1579]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
[1693]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);
[1579]166      <associative_plus in ⊢ (??%?);
167      >commutative_plus in match (
[1693]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);
[1579]170      %
171    ]
[1693]172  ]
[1579]173qed.
[1549]174
[1554]175let rec compute_trace_label_label_cost_using_paid
[1693]176  (cm: ?)
[2516]177  (cost_labels: BitVectorTrie costlabel 16)
[1554]178   (trace_ends_flag: trace_ends_with_ret)
[1693]179    (start_status: Status cm) (final_status: Status cm)
180      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
[1554]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 ⇒
[1693]184      compute_paid_trace_label_label cm cost_labels … the_trace +
[1554]185      compute_trace_any_label_cost_using_paid … given_trace
186  ]
187and compute_trace_any_label_cost_using_paid
[1693]188  (cm: ?)
[2516]189  (cost_labels: BitVectorTrie costlabel 16)
[1554]190  (trace_ends_flag: trace_ends_with_ret)
[1693]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)
[1554]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
[1693]197  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
198      compute_trace_label_return_cost_using_paid … call_trace
[2656]199  | tal_base_tailcall pre_fun_call start_fun_call final _ _ call_trace ⇒
200      compute_trace_label_return_cost_using_paid … call_trace
[1554]201  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
[1693]202     _ _ _ call_trace _ final_trace ⇒
[1554]203      let call_trace_cost ≝ compute_trace_label_return_cost_using_paid … call_trace in
[1693]204      let final_trace_cost ≝ compute_trace_any_label_cost_using_paid cm cost_labels end_flag … final_trace in
[1554]205        call_trace_cost + final_trace_cost
206  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
[1693]207     compute_trace_any_label_cost_using_paid cm cost_labels end_flag
[1554]208      status_init status_end tail_trace
209  ]
210and compute_trace_label_return_cost_using_paid
[1693]211  (cm: ?)
[2516]212  (cost_labels: BitVectorTrie costlabel 16)
[1693]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)
[1554]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
[1693]225  (cm: ?)
[2516]226  (cost_labels: BitVectorTrie costlabel 16)
[1554]227   (trace_ends_flag: trace_ends_with_ret)
[1693]228    (start_status: Status cm) (final_status: Status cm)
229      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
[1554]230        start_status final_status) on the_trace:
[1693]231 compute_trace_label_label_cost_using_paid cm cost_labels … the_trace =
[1554]232 compute_max_trace_label_label_cost … the_trace ≝ ?
233and compute_trace_any_label_cost_using_paid_ok
[1693]234  (cm: ?)
[2516]235  (cost_labels: BitVectorTrie costlabel 16)
[1554]236  (trace_ends_flag: trace_ends_with_ret)
[1693]237   (start_status: Status cm) (final_status: Status cm)
238     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels)
[1554]239      trace_ends_flag start_status final_status) on the_trace:     
[1693]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 ≝ ?
[1554]243and compute_trace_label_return_cost_using_paid_ok
[1693]244  (cm: ?)
[2516]245  (cost_labels: BitVectorTrie costlabel 16)
[1693]246  (start_status: Status cm) (final_status: Status cm)
247    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels)
[1554]248     start_status final_status) on the_trace:
[1693]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 ≝ ?.
[1554]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 %
[2656]256  | #sp #ss #sf #H1 #H2 #tr1 #tr2 #H3
[1693]257    whd in ⊢ (???%); whd in ⊢ (??(??%)?); whd in ⊢ (??(?%?)?);
258    >compute_trace_label_return_cost_using_paid_ok in ⊢ (??%?);
259    >commutative_plus in ⊢ (??%?); @eq_f %
[2656]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 %
[1693]264  | #ef #spfc #ssfc #safc #sf #H1 #H2 #H3 #tr1 #H4 #tr2 whd in ⊢ (??(?%%)%);
[1554]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 ]
[1506]276  ]
[1554]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.
[1506]283
[1693]284include alias "ASM/BitVectorTrie.ma".
[1650]285include alias "arithmetics/nat.ma".
286include alias "basics/logic.ma".
[1693]287include alias "arithmetics/bigops.ma".
288
[1570]289(* This shoudl go in bigops! *)
290theorem bigop_sum_rev: ∀k1,k2,p,B,nil.∀op:Aop B nil.∀f:nat→B.
291 \big[op,nil]_{i<k1+k2|p i} (f i) =
292 op \big[op,nil]_{i<k2|p (i+k1)} (f (i+k1)) \big[op,nil]_{i<k1|p i} (f i).
[1693]293 #k1 #k2 #p #B #nil #op #f >bigop_sum
294 >commutative_plus @same_bigop #i @leb_elim normalize
[1570]295 [2,4: //
296 | #H1 #H2 <plus_minus_m_m //
297 | #H1 #H2 #H3 <plus_minus_m_m //]
[1561]298qed.
299
[1570]300(* This is taken by sigma_pi.ma that does not compile now *)
301definition natAop ≝ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
302   (λa,b,c.sym_eq ??? (associative_plus a b c)).
303
304definition natACop ≝ mk_ACop nat 0 natAop commutative_plus.
305
306definition natDop ≝ mk_Dop nat 0 natACop times (λn.(sym_eq ??? (times_n_O n)))
307   distributive_times_plus.
308
309unification hint  0 ≔ ;
310   S ≟ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
311   (λa,b,c.sym_eq ??? (associative_plus a b c))
312(* ---------------------------------------- *) ⊢
313   plus ≡ op ? ? S.
314
315unification hint  0 ≔ ;
316   S ≟ mk_ACop nat 0 (mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n))
317   (λa,b,c.sym_eq ??? (associative_plus a b c))) commutative_plus
318(* ---------------------------------------- *) ⊢
319   plus ≡ op ? ? S.
320   
321unification hint  0 ≔ ;
322   S ≟ natDop
323(* ---------------------------------------- *) ⊢
324   plus ≡ sum ? ? S.
325
326unification hint  0 ≔ ;
327   S ≟ natDop
328(* ---------------------------------------- *) ⊢
329   times ≡ prod ? ? S.
330
[1619]331notation > "Σ_{ ident i < n } f"
[1570]332  with precedence 20
333for @{'bigop $n plus 0 (λ${ident i}.true) (λ${ident i}. $f)}.
334
[1619]335notation < "Σ_{ ident i < n } f"
336  with precedence 20
337for @{'bigop $n plus 0 (λ${ident i}:$X.true) (λ${ident i}:$Y. $f)}.
338
[1570]339definition tech_cost_of_label0:
[2516]340 ∀cost_labels: BitVectorTrie costlabel 16.
[1570]341 ∀cost_map: identifier_map CostTag nat.
342 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
[1964]343 ∀ctrace:list (Σk:costlabel.∃b.lookup_opt … b cost_labels = Some ? k).
[1570]344 ∀i,p. present … cost_map (nth_safe ? i ctrace p).
[1964]345 #cost_labels #cost_map #codom_dom #ctrace #i #p
[1570]346 cases (nth_safe … i ctrace ?) normalize #id * #id_pc #K
347 lapply (codom_dom … K) #k_pres >(lookup_lookup_present … k_pres)
348 % #abs destruct (abs)
[1564]349qed.
350
[1619]351include alias "arithmetics/nat.ma".
352include alias "basics/logic.ma".
353
[1570]354lemma ltb_rect:
355 ∀P:Type[0].∀n,m. (n < m → P) → (¬ n < m → P) → P.
356 #P #n #m lapply (refl … (ltb n m)) cases (ltb n m) in ⊢ (???% → %); #E #H1 #H2
357 [ @H1 @leb_true_to_le @E | @H2 @leb_false_to_not_le @E ]
[1564]358qed.
359
[1570]360lemma same_ltb_rect:
361 ∀P,n,m,H1,H2,n',m',H1',H2'.
362  ltb n m = ltb n' m' → (∀x,y. H1 x = H1' y) → (∀x,y. H2 x = H2' y) →
363   ltb_rect P n m H1 H2 =
364   ltb_rect P n' m' H1' H2'.
365 #P #n #m #H1 #H2 #n' #m' #H1' #H2' #E #K1 #K2 whd in ⊢ (??%?);
366 cut (∀xxx,yyy,xxx',yyy'.
367   match ltb n m
368   return λx:bool.
369           eq bool (ltb n m) x
370            → (lt n m → P) → (Not (lt n m) → P) → P
371    with
372    [ true ⇒
373        λE0:eq bool (ltb n m) true.
374         λH10:lt n m → P.
375          λH20:Not (lt n m) → P. H10 (xxx E0)
376    | false ⇒
377        λE0:eq bool (ltb n m) false.
378         λH10:lt n m → P.
379          λH20:Not (lt n m) → P. H20 (yyy E0)]
380    (refl … (ltb n m)) H1 H2 =
381   match ltb n' m'
382   return λx:bool.
383           eq bool (ltb n' m') x
384            → (lt n' m' → P) → (Not (lt n' m') → P) → P
385    with
386    [ true ⇒
387        λE0:eq bool (ltb n' m') true.
388         λH10:lt n' m' → P.
389          λH20:Not (lt n' m') → P. H10 (xxx' E0)
390    | false ⇒
391        λE0:eq bool (ltb n' m') false.
392         λH10:lt n' m' → P.
393          λH20:Not (lt n' m') → P. H20 (yyy' E0)]
394    (refl … (ltb n' m')) H1' H2'
395  ) [2: #X @X]
396 >E cases (ltb n' m') #xxx #yyy #xxx' #yyy' normalize
397 [ @K1 | @K2 ]
[1564]398qed.
399
[1570]400definition tech_cost_of_label:
[2516]401 ∀cost_labels: BitVectorTrie costlabel 16.
[1570]402 ∀cost_map: identifier_map CostTag nat.
403 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
[1964]404 list (Σk:costlabel.∃b.lookup_opt … b cost_labels = Some ? k) →
[1570]405 nat → nat
[1964]406≝ λcost_labels,cost_map,codom_dom,ctrace,i.
[1570]407 ltb_rect ? i (|ctrace|)
408 (λH. lookup_present ?? cost_map (nth_safe ? i ctrace H) ?)
409 (λ_.0).
410 @tech_cost_of_label0 @codom_dom
[1564]411qed.
412
[1570]413lemma tech_cost_of_label_shift:
[1964]414 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
[1620]415  i < |l2| →
[1964]416   tech_cost_of_label cost_labels cost_map codom_dom l2 i =
417   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) (i+|l1|).
418 #cost_labels #cost_Map #codom_dom #l1 #l2 #i #H
[1619]419 whd in match tech_cost_of_label; normalize nodelta @same_ltb_rect
420 [ @(ltb_rect ? i (|l2|)) @(ltb_rect ? (i+|l1|) (|l1@l2|)) #K1 #K2
421   whd in match ltb; normalize nodelta
[1964]422   [1: >le_to_leb_true try assumption applyS le_to_leb_true / by /
[1619]423   |4: >not_le_to_leb_false try assumption applyS not_le_to_leb_false
424       change with (¬ ? ≤ ?) in K1; applyS K1
[1964]425   |2: @⊥ @(absurd (i+|l1| < |l1@l2|)) / by / >length_append
426       applyS (monotonic_lt_plus_r … (|l1|)) / by /
[1619]427   |3: @⊥ @(absurd ?? K2) >length_append in K1; #K1 /2 by lt_plus_to_lt_l/ ]
428 | #H1 #H2
[1964]429   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
[1619]430   <(shift_nth_safe … H1) #p %
[1964]431 | / by / ]
[1619]432qed.
[1570]433
[1695]434lemma tech_cost_of_label_prefix:
[1964]435 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
[1695]436  i < |l1| →
[1964]437   tech_cost_of_label cost_labels cost_map codom_dom l1 i =
438   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) i.
439 #cost_labels #cost_map #codom_dom #l1 #l2 #i #H
[1695]440 whd in match tech_cost_of_label; normalize nodelta @same_ltb_rect
441 [1:
442   whd in match ltb; normalize nodelta
443   >(le_to_leb_true … H) applyS le_to_leb_true
444   >length_append whd in H; >commutative_plus @le_plus_a assumption
445 |2:
446   #K1 #K2
[1964]447   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
[1695]448   <(shift_nth_prefix … l1 i l2 K1 K2) //
449 |3:
450   #_ #_ %
451 ]
452qed.
[2760]453
[1695]454let rec compute_trace_label_return_using_paid_ok_with_trace
[2516]455 (cm: ?) (cost_labels: BitVectorTrie costlabel 16)
[1570]456 (cost_map: identifier_map CostTag nat)
[1693]457 (initial: Status cm) (final: Status cm)
458 (trace: trace_label_return (ASM_abstract_status cm cost_labels) initial final)
[1570]459 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
460 on trace:
[1921]461 ∀unrepeating_witness: tlr_unrepeating … trace.
[1900]462 ∀dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
[1929]463   pi1 … (block_cost cm pc cost_labels) = lookup_present … k_pres).
[1964]464  let ctrace ≝ flatten_trace_label_return (ASM_abstract_status cm cost_labels) … trace in
[1695]465  compute_trace_label_return_cost_using_paid cm … trace =
[1964]466   (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i))
[1620]467    ≝ ?
[1695]468and compute_trace_any_label_using_paid_ok_with_trace
[2516]469 (cm: ?) (cost_labels: BitVectorTrie costlabel 16)
[1620]470 (trace_ends_flag: trace_ends_with_ret)
471 (cost_map: identifier_map CostTag nat)
[1693]472 (initial: Status cm) (final: Status cm)
[1695]473 (trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag initial final)
474 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
[1900]475 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
[1929]476   pi1 … (block_cost cm pc cost_labels) = lookup_present … k_pres))
[1695]477 on trace:
[1921]478  ∀unrepeating_witness: tal_unrepeating … trace.
[1964]479  let ctrace ≝ flatten_trace_any_label (ASM_abstract_status cm cost_labels) … trace_ends_flag … trace in
[1695]480  compute_trace_any_label_cost_using_paid … trace =
[1964]481   (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i))
[1695]482    ≝ ?
483and compute_trace_label_label_using_paid_ok_with_trace
[2516]484 (cm: ?) (cost_labels: BitVectorTrie costlabel 16)
[1695]485 (trace_ends_flag: trace_ends_with_ret)
486 (cost_map: identifier_map CostTag nat)
487 (initial: Status cm) (final: Status cm)
[1693]488 (trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag initial final)
[1921]489 (unrepeating_witness: tll_unrepeating … trace)
[1620]490 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
[1900]491 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
[1929]492   pi1 … (block_cost cm pc cost_labels) = lookup_present … k_pres))
[1620]493 on trace:
[1921]494 ∀unrepeating_witness: tll_unrepeating … trace.
[1964]495  let ctrace ≝ flatten_trace_label_label (ASM_abstract_status cm cost_labels) … trace in
[1695]496  compute_trace_label_label_cost_using_paid … trace =
[1964]497   (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i))
[1570]498    ≝ ?.
[1695]499  cases trace normalize nodelta
[1921]500  [ #sb #sa #tr #unrepeating_witness #dom_codom whd in ⊢ (??%?);
[1964]501    whd in match (flatten_trace_label_return ????);
[1929]502    @compute_trace_label_label_using_paid_ok_with_trace
[1921]503    assumption
504  | #si #sl #sf #tr1 #tr2 #unrepeating_witness #dom_codom
[1695]505    whd in ⊢ (??%?);
[2760]506    whd in match flatten_trace_label_return; normalize nodelta
507    whd in match (observables_trace_label_return ?????);
508    >costlabels_of_observables_append
[1695]509    >append_length >bigop_sum_rev >commutative_plus @eq_f2
[1929]510    [ >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
[1695]511      -compute_trace_label_return_using_paid_ok_with_trace
[1921]512      [1:
513        @same_bigop [//] #i #H #_ -dom_codom @tech_cost_of_label_shift //
514      |2:
515        inversion unrepeating_witness
516        #tll_unrepeating #tlr_unrepeating #_ assumption
517      ]
[1929]518    | >(compute_trace_label_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
[1695]519      -compute_trace_label_label_using_paid_ok_with_trace
[1921]520      [1:
521        @same_bigop [//] #i #H #_ @(tech_cost_of_label_prefix … H)
522      |2,3:
523        inversion unrepeating_witness
524        #tll_unrepeating #tlr_unrepeating #_ assumption
525      ]
[1695]526    ]
[2656]527  |9:
[1695]528    #end_flag #start_status #end_status #trace_any_label #costed_assm
[1923]529    #unrepeating_witness'
[1695]530    whd in ⊢ (??%?); whd in ⊢ (??(?%?)?);
[1929]531    >(compute_trace_any_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
[1695]532    [1:
[1964]533      whd in match (flatten_trace_label_label ?????);
[1921]534      >bigop_0 in ⊢ (???%); >commutative_plus @eq_f2
[1900]535      [1:
[1921]536        @same_bigop [//] #i #H #_ -dom_codom >(plus_n_O i) >plus_n_Sm
[1964]537        <(tech_cost_of_label_shift ??? [?] ? i) try assumption <(plus_n_O i) %
[1900]538      |2:
[1921]539        change with (? = lookup_present ? ? ? ? ?)
[1964]540        generalize in match (tech_cost_of_label0 ? ? ? ? ? ?);
[2656]541        whd in ⊢ (∀p:????%.???(????%?));
[1927]542        whd in costed_assm; lapply costed_assm whd in match (as_label ??);
[1921]543        inversion (lookup_opt ? ? (program_counter … cm start_status) cost_labels)
544        [1:
[1927]545          #_ #absurd @⊥ cases absurd #absurd @absurd %
[1921]546        |2:
547          normalize nodelta #cost_label #Some_assm #_ #p
548          cases (dom_codom ? p ? Some_assm)
[1929]549          cases (block_cost ???)
550          #cost #block_cost_assm
551          cases (block_cost_assm ??? trace_any_label ??)
[1923]552          try @refl assumption
[1921]553        ]
[1900]554      ]
[1921]555    |2:
556      assumption
[1695]557    ]
558  |3:
559    #start_status #final_status #execute_assm #classifier_assm #costed_assm
[1921]560    #unrepeating_witness
[1695]561    %
562  |4:
[1921]563    #start_status #final_status #execute_assm #classifier_assm #unrepeating_witness
564    %
[1695]565  |5:
566    #status_pre_fun_call #status_start_fun_call #status_final #execute_assm
[1921]567    #classifier_assm #after_return_assm #trace_label_return #costed_assm #unrepeating_witness
[1695]568    whd in ⊢ (??%?);
[2760]569    >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
570    //
571    whd in match flatten_trace_any_label; normalize nodelta
572    whd in match (observables_trace_any_label ??????);
573    >(costlabels_of_observables_append … [?]) [2: normalize /2/]
574    >length_append whd in match (? + ?);
575    whd in match flatten_trace_label_return; normalize nodelta
576    >costlabels_of_observables_trace_label_return_id_irrelevant //
[1695]577  |6:
[2656]578    #status_pre_fun_call #status_start_fun_call #status_final #execute_assm
579    #classifier_assm #trace_label_return #unrepeating_witness
580    whd in ⊢ (??%?);
[2760]581    >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
582    //
583    whd in match flatten_trace_any_label; normalize nodelta
584    whd in match (observables_trace_any_label ??????);
585    >(costlabels_of_observables_append … [?]) [2: normalize /2/]
586    >length_append whd in match (? + ?);
587    whd in match flatten_trace_label_return; normalize nodelta
588    >costlabels_of_observables_trace_label_return_id_irrelevant //
[2656]589  |7:
[1695]590    #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
591    #status_final #execute_assm #classifier_assm #after_return_assm #trace_label_return
[1921]592    #costed_assm #trace_any_label #unrepeating_witness
[1695]593    whd in ⊢ (??%?);
[1929]594    >(compute_trace_label_return_using_paid_ok_with_trace … cost_map … codom_dom ? dom_codom)
[1921]595    [1:
[1929]596      >(compute_trace_any_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
[1921]597      [1:
[2760]598        whd in match flatten_trace_any_label in ⊢ (???%); normalize nodelta
599        whd in match (observables_trace_any_label ??????);
600        >costlabels_of_observables_append
601        >(costlabels_of_observables_append … [?]) [2: normalize /2/]
[1921]602        >length_append >bigop_sum_rev >commutative_plus @eq_f2
603        [ @same_bigop [2: #i #H #_ -dom_codom @tech_cost_of_label_shift assumption
604                      |1: #i #H % ]
[2760]605        | >length_append whd in match (|?|+?);
606          >costlabels_of_observables_trace_label_return_id_irrelevant
607          [@same_bigop [#i #H %] #i #H #_ @(tech_cost_of_label_prefix … H) | skip]
[1921]608        ]
609      |2:
610        inversion unrepeating_witness
611        * #memb_1 #tal_unrepeating #tlr_unrepeating #_ assumption
612      ]
613    |2:
614      inversion unrepeating_witness
615      * #memb_1 #tal_unrepeating #tlr_unrepeating #_ assumption
[1695]616    ]
[2656]617  |8:
[1695]618    #end_flag #status_pre_fun_call #status_start_fun_call #status_final
[1921]619    #execute_assm #trace_any_label #classifier_assm #costed_assm #unrepeating_witness
[1695]620    whd in ⊢ (??%?);
[1929]621    @(compute_trace_any_label_using_paid_ok_with_trace … cost_map … codom_dom … dom_codom)
[1921]622    inversion unrepeating_witness
623    #memb_1 #tal_unrepeating #_ assumption
[1554]624  ]
[1695]625qed.
626 
[1898]627lemma compute_max_trace_label_return_cost_ok_with_trace_aux:
[1695]628  ∀code_memory: BitVectorTrie Byte 16.
[2516]629  ∀cost_labels: BitVectorTrie costlabel 16.
[1695]630  ∀cost_map: identifier_map CostTag nat.
631  ∀initial: Status code_memory.
632  ∀final: Status code_memory.
633  ∀trace: trace_label_return (ASM_abstract_status code_memory cost_labels) initial final.
[1921]634  ∀unrepeating_witness: tlr_unrepeating … trace.
[1695]635  ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
[1900]636  ∀dom_codom: (∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
[1929]637      pi1 … (block_cost code_memory pc cost_labels) = lookup_present … k_pres).
[1964]638        let ctrace ≝ flatten_trace_label_return … trace in
[1695]639          clock … code_memory … final =
[1964]640            clock … code_memory … initial + (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i)).
[1929]641  #code_memory #cost_labels #cost_map
[1921]642  #initial #final #trace #unrepeating_witness #codom_dom #dom_codom normalize nodelta
[1695]643  <compute_trace_label_return_using_paid_ok_with_trace try assumption
644  >commutative_plus >compute_trace_label_return_cost_using_paid_ok //
[1898]645qed.
646
647theorem compute_max_trace_label_return_cost_ok_with_trace:
648  ∀code_memory: BitVectorTrie Byte 16.
[2516]649  ∀cost_labels: BitVectorTrie costlabel 16.
[1900]650  ∀cost_labels_injective:
651   (∀pc,pc',l.
652     lookup_opt costlabel 16 pc cost_labels=Some costlabel l
653      →lookup_opt costlabel 16 pc' cost_labels=Some costlabel l→pc=pc').
[1898]654  ∀initial: Status code_memory.
655  ∀final: Status code_memory.
656  ∀trace: trace_label_return (ASM_abstract_status code_memory cost_labels) initial final.
[1921]657  ∀unrepeating_witness: tlr_unrepeating … trace.
[1929]658    let cost_map ≝ traverse_code code_memory cost_labels cost_labels_injective in
[1964]659    let ctrace ≝ flatten_trace_label_return … trace in
660      clock … code_memory … final = clock … code_memory … initial + (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map ? ctrace i)).
[1898]661  [1:
[1929]662    #code_memory #cost_labels #cost_labels_injective #initial #final #trace #unrepeating_witness
[1898]663    @compute_max_trace_label_return_cost_ok_with_trace_aux try assumption
664  |2:
665    skip
666  ]
667  normalize nodelta
[1929]668  cases (traverse_code ???)
[1898]669  #cost_map * #dom_codom #codom_dom try assumption
670  #pc #k #lookup_opt_assm @(dom_codom … lookup_opt_assm)
671  lapply (sym_eq ? ? ? lookup_opt_assm)
672  -lookup_opt_assm #lookup_opt_assm
[1929]673  @nat_of_bitvector_lt_bound
[1976]674qed.
675 
676include "utilities/permutations.ma".
[2516]677
[2657]678definition map_of_sigma_map:
679 ∀P.
680  (Σmap:identifier_map CostTag ℕ.P map) → identifier_map CostTag ℕ
681 ≝ λP,x.x.
682
683lemma costlabel_map_of_as_cost_labels_map_ok:
684 ∀ccode1,ccode2,cost_labels_injective,tl,Htl,PRF,PRF2.
685  lookup_present CostTag ℕ (compute_costs ccode1 ccode2 cost_labels_injective) tl
686  PRF
687  =
688   lookup_present CostTag ℕ (compute_costs ccode1 ccode2 cost_labels_injective)
689   (as_cost_get_label (ASM_abstract_status (load_code_memory ccode1) ccode2)
690    «tl,Htl») PRF2.
691//
692qed.
693
[1976]694lemma tech_cost_sum_eq_as_cost :
[2754]695  ∀compiled_code: labelled_object_code.
[2760]696  let cost_labels ≝ costlabels compiled_code in
697  let cost_map ≝ compute_costs (oc compiled_code) (costlabels compiled_code) (oc_injective_costlabels compiled_code) in
[2657]698  ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … k).
[1976]699  ∀trace.
[2671]700  (Σ_{i < |trace|}(tech_cost_of_label cost_labels (map_of_sigma_map … cost_map) codom_dom trace i)) =
[2760]701  (Σ_{l ∈ trace}(ASM_cost_map compiled_code l)).
702#ccode #codom_dom #trace
[1976]703@(list_elim_left … trace)
704[ %
705| #tl #hd #IH >append_length >commutative_plus
706  >(fold_permute … (hd@[tl]) (tl::hd)) [2: @perm_swap_append ]
[2671]707  whd in ⊢ (??%%); <IH
708  <tech_cost_of_label_shift [2: //]
[1976]709  cut (∀x,y,z,w.x = y → z = w → x + z = y + w) [ // ] #APP @APP -APP
[2760]710  [ cases tl -tl #tl #Htl @costlabel_map_of_as_cost_labels_map_ok
[1976]711  | @sym_eq @same_bigop /2 by tech_cost_of_label_prefix/
712  ]
713]
[2754]714qed.
Note: See TracBrowser for help on using the repository browser.