source: src/ASM/CostsProof.ma

Last change on this file was 3145, checked in by tranquil, 7 years ago
  • removed sigma types from traces of intensional events
  • completed correctness.ma using axiom files, a single daemon remains
File size: 26.6 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  (prog: labelled_object_code)
12   (trace_ends_flag: trace_ends_with_ret)
13    (start_status: Status (cm prog))
14    (final_status: Status (cm prog))
15      (the_trace: trace_label_label (OC_abstract_status prog) 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  (prog: labelled_object_code)
23  (trace_ends_flag: trace_ends_with_ret)
24   (start_status: Status (cm prog))
25   (final_status: Status (cm prog))
26     (the_trace: trace_any_label (OC_abstract_status prog) 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 … the_status
30  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost … the_status
31  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
32      let current_instruction_cost ≝ current_instruction_cost … 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 … 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 … 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 prog 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 … status_pre in
47      let tail_trace_cost ≝
48       compute_max_trace_any_label_cost prog 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  (prog: labelled_object_code)
55  (start_status: Status (cm prog))
56  (final_status: Status (cm prog))
57    (the_trace: trace_label_return (OC_abstract_status prog) 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  (prog: labelled_object_code)
71   (trace_ends_flag: trace_ends_with_ret)
72    (start_status: Status (cm prog))
73    (final_status: Status (cm prog))
74      (the_trace: trace_label_label (OC_abstract_status prog) trace_ends_flag
75        start_status final_status) on the_trace:
76          clock … (cm prog) … final_status = (compute_max_trace_label_label_cost prog trace_ends_flag start_status final_status the_trace) + (clock … (cm prog) … start_status) ≝ ?
77and compute_max_trace_any_label_cost_is_ok
78  (prog: labelled_object_code)
79  (trace_ends_flag: trace_ends_with_ret)
80    (start_status: Status (cm prog))
81    (final_status: Status (cm prog))
82     (the_trace: trace_any_label (OC_abstract_status prog) trace_ends_flag start_status final_status)
83       on the_trace:
84         clock … (cm prog) … final_status = (compute_max_trace_any_label_cost prog trace_ends_flag start_status final_status the_trace) + (clock … (cm prog) … start_status) ≝ ?
85and compute_max_trace_label_return_cost_is_ok
86  (prog: labelled_object_code)
87    (start_status: Status (cm prog))
88    (final_status: Status (cm prog))
89    (the_trace: trace_label_return (OC_abstract_status prog) start_status final_status)
90      on the_trace:
91        clock … (cm prog) … final_status = (compute_max_trace_label_return_cost prog start_status final_status the_trace) + clock … (cm prog) … start_status ≝ ?.
92  [1:
93    cases the_trace
94    #ends_flag #start_status #end_status #any_label_trace #is_costed
95    @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 … start_status) in ⊢ (???(?%?));
101      cases(proj2 … 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 prog … call_trace)
107      >associative_plus @eq_f cases(proj2 … 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(proj2 … 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 … status_pre_fun_call in
121      let call_trace_cost ≝ compute_max_trace_label_return_cost … … call_trace in
122      let final_trace_cost ≝ compute_max_trace_any_label_cost prog 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 prog end_flag status_after_fun_call
126          status_final final_trace)
127      >(compute_max_trace_label_return_cost_is_ok prog status_start_fun_call
128        status_after_fun_call call_trace)
129      cases(proj2 … is_next) in match (clock … (cm prog) status_start_fun_call);
130      >(execute_1_ok_clock … status_pre_fun_call)
131      <associative_plus in ⊢ (??%?);
132      <commutative_plus in match (
133        compute_max_trace_any_label_cost prog end_flag status_after_fun_call status_final final_trace
134          + compute_max_trace_label_return_cost prog 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 … status_pre in
143      let tail_trace_cost ≝
144       compute_max_trace_any_label_cost prog 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 prog end_flag
150         status_init status_end trace_any_label)
151      cases(proj2 … is_next) in match (clock … (cm prog) 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      @compute_max_trace_label_label_cost_is_ok
161    |2:
162      #status_initial #status_labelled #status_final #labelled_trace #ret_trace
163      >(compute_max_trace_label_return_cost_is_ok prog status_labelled status_final ret_trace);
164      >(compute_max_trace_label_label_cost_is_ok prog doesnt_end_with_ret status_initial status_labelled labelled_trace);
165      <associative_plus in ⊢ (??%?);
166      >commutative_plus in match (
167        compute_max_trace_label_return_cost prog status_labelled status_final ret_trace
168          + compute_max_trace_label_label_cost prog doesnt_end_with_ret status_initial status_labelled labelled_trace);
169      %
170    ]
171  ]
172qed.
173
174let rec compute_trace_label_label_cost_using_paid
175  (prog:labelled_object_code)
176   (trace_ends_flag: trace_ends_with_ret)
177    (start_status: Status (cm prog))
178    (final_status: Status (cm prog))
179      (the_trace: trace_label_label (OC_abstract_status prog) trace_ends_flag
180        start_status final_status) on the_trace: nat ≝
181  match the_trace with
182  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
183      compute_paid_trace_label_label prog … the_trace +
184      compute_trace_any_label_cost_using_paid … given_trace
185  ]
186and compute_trace_any_label_cost_using_paid
187  (prog:labelled_object_code)
188  (trace_ends_flag: trace_ends_with_ret)
189    (start_status: Status (cm prog))
190    (final_status: Status (cm prog))
191     (the_trace: trace_any_label (OC_abstract_status prog) trace_ends_flag start_status final_status)
192       on the_trace: nat ≝
193  match the_trace with
194  [ tal_base_not_return the_status _ _ _ _ ⇒ 0
195  | tal_base_return the_status _ _ _ ⇒ 0
196  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
197      compute_trace_label_return_cost_using_paid … call_trace
198  | tal_base_tailcall pre_fun_call start_fun_call final _ _ call_trace ⇒
199      compute_trace_label_return_cost_using_paid … call_trace
200  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
201     _ _ _ call_trace _ final_trace ⇒
202      let call_trace_cost ≝ compute_trace_label_return_cost_using_paid … call_trace in
203      let final_trace_cost ≝ compute_trace_any_label_cost_using_paid prog end_flag … final_trace in
204        call_trace_cost + final_trace_cost
205  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
206     compute_trace_any_label_cost_using_paid prog end_flag
207      status_init status_end tail_trace
208  ]
209and compute_trace_label_return_cost_using_paid
210  (prog:labelled_object_code)
211    (start_status: Status (cm prog))
212    (final_status: Status (cm prog))
213    (the_trace: trace_label_return (OC_abstract_status prog) start_status final_status)
214      on the_trace: nat ≝
215  match the_trace with
216  [ tlr_base before after trace_to_lift ⇒ compute_trace_label_label_cost_using_paid … trace_to_lift
217  | tlr_step initial labelled final labelled_trace ret_trace ⇒
218      let labelled_cost ≝ compute_trace_label_label_cost_using_paid … labelled_trace in
219      let return_cost ≝ compute_trace_label_return_cost_using_paid … ret_trace in
220        labelled_cost + return_cost
221  ].
222
223let rec compute_trace_label_label_cost_using_paid_ok
224  (prog:labelled_object_code)
225   (trace_ends_flag: trace_ends_with_ret)
226    (start_status: Status (cm prog))
227    (final_status: Status (cm prog))
228      (the_trace: trace_label_label (OC_abstract_status prog) trace_ends_flag
229        start_status final_status) on the_trace:
230 compute_trace_label_label_cost_using_paid prog … the_trace =
231 compute_max_trace_label_label_cost … the_trace ≝ ?
232and compute_trace_any_label_cost_using_paid_ok
233  (prog:labelled_object_code)
234  (trace_ends_flag: trace_ends_with_ret)
235    (start_status: Status (cm prog))
236    (final_status: Status (cm prog))
237     (the_trace: trace_any_label (OC_abstract_status prog)
238      trace_ends_flag start_status final_status) on the_trace:     
239  compute_paid_trace_any_label prog trace_ends_flag … the_trace
240  +compute_trace_any_label_cost_using_paid prog trace_ends_flag … the_trace
241  =compute_max_trace_any_label_cost prog trace_ends_flag … the_trace ≝ ?
242and compute_trace_label_return_cost_using_paid_ok
243  (prog:labelled_object_code)
244    (start_status: Status (cm prog))
245    (final_status: Status (cm prog))
246    (the_trace: trace_label_return (OC_abstract_status prog)
247     start_status final_status) on the_trace:
248 compute_trace_label_return_cost_using_paid prog … the_trace =
249 compute_max_trace_label_return_cost prog … the_trace ≝ ?.
250[ cases the_trace #endsf #ss #es #tr #H normalize
251  @compute_trace_any_label_cost_using_paid_ok
252| cases the_trace
253  [ #ss #fs #H1 #H2 #H3 whd in ⊢ (??(?%%)%); <plus_n_O %
254  | #ss #fs #H1 #H2 whd in ⊢ (??(?%%)%); <plus_n_O %
255  | #sp #ss #sf #H1 #H2 #tr1 #tr2 #H3
256    whd in ⊢ (???%); whd in ⊢ (??(??%)?); whd in ⊢ (??(?%?)?);
257    >compute_trace_label_return_cost_using_paid_ok in ⊢ (??%?);
258    >commutative_plus in ⊢ (??%?); @eq_f %
259  | #sp #ss #sf #H1 #H2 #tr1
260    whd in ⊢ (???%); whd in ⊢ (??(??%)?); whd in ⊢ (??(?%?)?);
261    >compute_trace_label_return_cost_using_paid_ok in ⊢ (??%?);
262    >commutative_plus in ⊢ (??%?); @eq_f %
263  | #ef #spfc #ssfc #safc #sf #H1 #H2 #H3 #tr1 #H4 #tr2 whd in ⊢ (??(?%%)%);
264    <compute_trace_any_label_cost_using_paid_ok
265    <compute_trace_label_return_cost_using_paid_ok
266    -compute_trace_label_label_cost_using_paid_ok
267    -compute_trace_label_return_cost_using_paid_ok
268    -compute_trace_any_label_cost_using_paid_ok
269    >commutative_plus in ⊢ (???(?%?));
270    >commutative_plus in ⊢ (??(??%)?);
271    >associative_plus >associative_plus in ⊢ (???%); @eq_f2 try %
272    <associative_plus <commutative_plus %
273  | #ef #sp #si #se #H1 #tr #H2 #H3 whd in ⊢ (??(?%%)%); >associative_plus @eq_f2
274    [ % | @compute_trace_any_label_cost_using_paid_ok ]
275  ]
276| cases the_trace
277  [ #sb #sa #tr normalize @compute_trace_label_label_cost_using_paid_ok
278  | #si #sl #sf #tr1 #tr2 normalize @eq_f2
279    [ @compute_trace_label_label_cost_using_paid_ok
280    | @compute_trace_label_return_cost_using_paid_ok ]]]
281qed.
282
283include alias "ASM/BitVectorTrie.ma".
284include alias "arithmetics/nat.ma".
285include alias "basics/logic.ma".
286include alias "arithmetics/bigops.ma".
287
288(*
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).
293 #k1 #k2 #p #B #nil #op #f >bigop_sum
294 >commutative_plus @same_bigop #i @leb_elim normalize
295 [2,4: //
296 | #H1 #H2 <plus_minus_m_m //
297 | #H1 #H2 #H3 <plus_minus_m_m //]
298qed.
299*)
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(*
331notation > "Σ_{ ident i < n } f"
332  with precedence 20
333for @{'bigop $n plus 0 (λ${ident i}.true) (λ${ident i}. $f)}.
334
335notation < "Σ_{ ident i < n } f"
336  with precedence 20
337for @{'bigop $n plus 0 (λ${ident i}:$X.true) (λ${ident i}:$Y. $f)}.
338
339definition tech_cost_of_label0:
340 ∀cost_labels: BitVectorTrie costlabel 16.
341 ∀cost_map: identifier_map CostTag nat.
342 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
343 ∀ctrace:list (Σk:costlabel.∃b.lookup_opt … b cost_labels = Some ? k).
344 ∀i,p. present … cost_map (nth_safe ? i ctrace p).
345 #cost_labels #cost_map #codom_dom #ctrace #i #p
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)
349qed.
350*)
351include alias "arithmetics/nat.ma".
352include alias "basics/logic.ma".
353(*
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 ]
358qed.
359
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 ]
398qed.
399
400definition tech_cost_of_label:
401 ∀cost_labels: BitVectorTrie costlabel 16.
402 ∀cost_map: identifier_map CostTag nat.
403 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
404 list (Σk:costlabel.∃b.lookup_opt … b cost_labels = Some ? k) →
405 nat → nat
406≝ λcost_labels,cost_map,codom_dom,ctrace,i.
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
411qed.
412
413lemma tech_cost_of_label_shift:
414 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
415  i < |l2| →
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
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
422   [1: >le_to_leb_true try assumption applyS le_to_leb_true / by /
423   |4: >not_le_to_leb_false try assumption applyS not_le_to_leb_false
424       change with (¬ ? ≤ ?) in K1; applyS K1
425   |2: @⊥ @(absurd (i+|l1| < |l1@l2|)) / by / >length_append
426       applyS (monotonic_lt_plus_r … (|l1|)) / by /
427   |3: @⊥ @(absurd ?? K2) >length_append in K1; #K1 /2 by lt_plus_to_lt_l/ ]
428 | #H1 #H2
429   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
430   <(shift_nth_safe … H1) #p %
431 | / by / ]
432qed.
433
434lemma tech_cost_of_label_prefix:
435 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
436  i < |l1| →
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
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
447   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
448   <(shift_nth_prefix … l1 i l2 K1 K2) //
449 |3:
450   #_ #_ %
451 ]
452qed.
453*)
454
455(* in the standard library there are two Aop's!!! *)
456lemma fold_sum' : ∀A,B.∀nil : B.∀op : Aop B nil.∀I,J,p.∀f : A → B.
457\fold[op, nil]_{i ∈ I@J | p i} (f i) =
458op (\fold[op, nil]_{i ∈ I | p i} (f i))
459 (\fold[op, nil]_{i ∈ J | p i} (f i)).
460#A #B #nil #op #I elim I -I [ #J #p #g >nill % ]
461#hd #tl #IH #J #p #f whd in ⊢ (??%(????%?)); cases p normalize nodelta
462[ <assoc @eq_f ] @IH
463qed.
464
465lemma lookup_present_to_lookup_def : ∀tag,A,m,x,x_prf,def.
466lookup_def tag A m x def = lookup_present tag A m x x_prf.
467#tag #A #m #x #x_prf #def
468whd in ⊢ (??%%); whd in x_prf; cases (lookup … m x) in x_prf;
469[ * #ABS cases (ABS ?) % ]
470#y #prf % qed.
471
472let rec compute_trace_label_return_using_paid_ok_with_trace
473 (prog: labelled_object_code)
474 (initial: Status (cm prog))
475 (final: Status (cm prog))
476 (trace: trace_label_return (OC_abstract_status prog) initial final)
477 on trace:
478 ∀unrepeating_witness: tlr_unrepeating … trace.
479  let ctrace ≝ flatten_trace_label_return (OC_abstract_status prog) … trace in
480  compute_trace_label_return_cost_using_paid prog … trace =
481   (Σ_{i ∈ ctrace} (ASM_cost_map prog i))
482    ≝ ?
483and compute_trace_any_label_using_paid_ok_with_trace
484 (prog: labelled_object_code)
485 (trace_ends_flag: trace_ends_with_ret)
486 (initial: Status (cm prog))
487 (final: Status (cm prog))
488 (trace: trace_any_label (OC_abstract_status prog) trace_ends_flag initial final)
489 on trace:
490  ∀unrepeating_witness: tal_unrepeating … trace.
491  let ctrace ≝ flatten_trace_any_label (OC_abstract_status prog) … trace_ends_flag … trace in
492  compute_trace_any_label_cost_using_paid … trace =
493   (Σ_{i ∈ ctrace} (ASM_cost_map prog i))
494    ≝ ?
495and compute_trace_label_label_using_paid_ok_with_trace
496 (prog: labelled_object_code)
497 (trace_ends_flag: trace_ends_with_ret)
498 (initial: Status (cm prog))
499 (final: Status (cm prog))
500 (trace: trace_label_label (OC_abstract_status prog) trace_ends_flag initial final)
501 (unrepeating_witness: tll_unrepeating … trace)
502 on trace:
503 ∀unrepeating_witness: tll_unrepeating … trace.
504  let ctrace ≝ flatten_trace_label_label (OC_abstract_status prog) … trace in
505  compute_trace_label_label_cost_using_paid … trace =
506   (Σ_{i ∈ ctrace} (ASM_cost_map prog i))
507    ≝ ?.
508  cases trace normalize nodelta
509  [ #sb #sa #tr #unrepeating_witness whd in ⊢ (??%?);
510    whd in match (flatten_trace_label_return ????);
511    @compute_trace_label_label_using_paid_ok_with_trace
512    assumption
513  | #si #sl #sf #tr1 #tr2 #unrepeating_witness
514    whd in ⊢ (??%?);
515    whd in match flatten_trace_label_return; normalize nodelta
516    whd in match (observables_trace_label_return ?????);
517    >costlabels_of_observables_append
518    change with (? = \fold[natAop,0]_{i ∈ ?}(?)) >fold_sum' @eq_f2
519    [ @compute_trace_label_label_using_paid_ok_with_trace
520      -compute_trace_label_label_using_paid_ok_with_trace
521      inversion unrepeating_witness
522      #tll_unrepeating #tlr_unrepeating #_ assumption
523    | @(compute_trace_label_return_using_paid_ok_with_trace)
524      -compute_trace_label_return_using_paid_ok_with_trace
525      inversion unrepeating_witness
526      #tll_unrepeating #tlr_unrepeating #_ assumption
527    ]
528  |9:
529    #end_flag #start_status #end_status #trace_any_label #costed_assm
530    #unrepeating_witness'
531    whd in ⊢ (??%?); whd in ⊢ (??(?%?)?);
532    whd in match flatten_trace_label_label; normalize nodelta
533    whd in match (observables_trace_label_label ??????);
534    >compute_trace_any_label_using_paid_ok_with_trace
535    [1:
536      change with (? = ? + ?) @eq_f2 [2: %]
537      change with (? = lookup_def ? ? ? ? ?)
538      whd in match (as_label_safe); normalize nodelta
539      @opt_safe_elim #cost_lbl whd in ⊢ (??%?→?); #Some_assm
540      cases (compute_costs ?) #m * #A #B
541      >(lookup_present_to_lookup_def … (A … Some_assm)) [2: //]
542      <(B … (Some_assm))
543      cases (pi2 ?? (block_cost ??)) try % assumption
544    |2:
545      assumption
546    ]
547  |3:
548    #start_status #final_status #execute_assm #classifier_assm #costed_assm
549    #unrepeating_witness
550    %
551  |4:
552    #start_status #final_status #execute_assm #classifier_assm #unrepeating_witness
553    %
554  |5:
555    #status_pre_fun_call #status_start_fun_call #status_final #execute_assm
556    #classifier_assm #after_return_assm #trace_label_return #costed_assm #unrepeating_witness
557    whd in ⊢ (??%?);
558    whd in match flatten_trace_any_label; normalize nodelta
559    whd in match (observables_trace_any_label ??????);
560    >(costlabels_of_observables_append … [?])
561    >costlabels_of_observables_trace_label_return_id_irrelevant [2: %{one} ]
562    @compute_trace_label_return_using_paid_ok_with_trace
563    //
564  |6:
565    #status_pre_fun_call #status_start_fun_call #status_final #execute_assm
566    #classifier_assm #trace_label_return #unrepeating_witness
567    whd in ⊢ (??%?);
568    whd in match flatten_trace_any_label; normalize nodelta
569    whd in match (observables_trace_any_label ??????);
570    >(costlabels_of_observables_append … [?])
571    >costlabels_of_observables_trace_label_return_id_irrelevant [2: %{one} ]
572    @compute_trace_label_return_using_paid_ok_with_trace
573    //
574  |7:
575    #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
576    #status_final #execute_assm #classifier_assm #after_return_assm #trace_label_return
577    #costed_assm #trace_any_label #unrepeating_witness
578    whd in ⊢ (??%?);
579    whd in match flatten_trace_any_label in ⊢ (???%); normalize nodelta
580    whd in match (observables_trace_any_label ??????);
581    >(costlabels_of_observables_append … [?])
582    >costlabels_of_observables_append
583    >costlabels_of_observables_trace_label_return_id_irrelevant [2: %{one} ]
584    >fold_sum' change with (? = \fold[plus,0]_{i∈?@?}?) >fold_sum'
585    cases unrepeating_witness * #H1 #H2 #H3 @eq_f2
586    [ @compute_trace_label_return_using_paid_ok_with_trace
587    | @compute_trace_any_label_using_paid_ok_with_trace
588    ] assumption
589  |8:
590    #end_flag #status_pre_fun_call #status_start_fun_call #status_final
591    #execute_assm #trace_any_label #classifier_assm #costed_assm #unrepeating_witness
592    whd in ⊢ (??%?);
593    @compute_trace_any_label_using_paid_ok_with_trace
594    cases unrepeating_witness
595    #memb_1 #tal_unrepeating assumption
596  ]
597qed.
598
599lemma compute_max_trace_label_return_cost_ok_with_trace :
600  ∀prog: labelled_object_code.
601  ∀initial: Status (cm prog).
602  ∀final: Status (cm prog).
603  ∀trace: trace_label_return (OC_abstract_status prog) initial final.
604  ∀unrepeating_witness: tlr_unrepeating … trace.
605    let cost_map ≝ ASM_cost_map … prog in
606    let ctrace ≝ flatten_trace_label_return … trace in
607      clock … (cm prog) … final = clock … (cm prog) … initial +
608        (Σ_{i ∈ ctrace} (cost_map i)).
609  #prog #initial #final #trace #unrepeating_witness normalize nodelta
610  <compute_trace_label_return_using_paid_ok_with_trace try assumption
611  >compute_trace_label_return_cost_using_paid_ok >commutative_plus //
612qed.
Note: See TracBrowser for help on using the repository browser.