source: src/ASM/CostsProof.ma @ 1935

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

Generalized some lemma in ASM/CostsProof.ma to work on abstract statuses, moving the abstract version in to common/StructuredTraces.ma. Ported rest of proof in ASM/CostsProof.ma to use new, generalized lemma.

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