source: src/ASM/CostsProof.ma @ 1927

Last change on this file since 1927 was 1927, checked in by mulligan, 9 years ago

Reduced complexity of good_program predicate, ported to new notion of as_label, reintroduced some deleted code from common/StructuredTraces.ma.

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