root/src/ASM/CostsProof.ma @ 1910

include "ASM/ASMCostsSplit.ma".
include "ASM/WellLabeled.ma".
include "ASM/Status.ma".
include "common/StructuredTraces.ma".
include "arithmetics/bigops.ma".

include alias "arithmetics/nat.ma".
include alias "basics/logic.ma".

let rec compute_max_trace_label_label_cost
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status cm) (final_status: Status cm)
      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
        start_status final_status) on the_trace: nat ≝
  match the_trace with
  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
      compute_max_trace_any_label_cost … given_trace
  ]
and compute_max_trace_any_label_cost
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status cm) (final_status: Status cm)
     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag start_status final_status)
       on the_trace: nat ≝
  match the_trace with
  [ tal_base_not_return the_status _ _ _ _ ⇒ current_instruction_cost cm the_status
  | tal_base_return the_status _ _ _ ⇒ current_instruction_cost cm the_status
  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
      let current_instruction_cost ≝ current_instruction_cost cm pre_fun_call in
      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
        call_trace_cost + current_instruction_cost
  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
     _ _ _ call_trace _ final_trace ⇒
      let current_instruction_cost ≝ current_instruction_cost cm pre_fun_call in
      let call_trace_cost ≝ compute_max_trace_label_return_cost … call_trace in
      let final_trace_cost ≝ compute_max_trace_any_label_cost cm cost_labels end_flag … final_trace in
        call_trace_cost + current_instruction_cost + final_trace_cost
  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
      let current_instruction_cost ≝ current_instruction_cost cm status_pre in
      let tail_trace_cost ≝
       compute_max_trace_any_label_cost cm cost_labels end_flag
        status_init status_end tail_trace
      in
        current_instruction_cost + tail_trace_cost
  ]
and compute_max_trace_label_return_cost
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status cm) (final_status: Status cm)
    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels) start_status final_status)
      on the_trace: nat ≝
  match the_trace with
  [ tlr_base before after trace_to_lift ⇒ compute_max_trace_label_label_cost … trace_to_lift
  | tlr_step initial labelled final labelled_trace ret_trace ⇒
      let labelled_cost ≝ compute_max_trace_label_label_cost … labelled_trace in
      let return_cost ≝ compute_max_trace_label_return_cost … ret_trace in
        labelled_cost + return_cost
  ].

include alias "arithmetics/nat.ma".

lemma execute_1_ok_clock:
  ∀cm.
  ∀s.
    clock ?? (execute_1 cm s) = current_instruction_cost … s + clock … s.
  #cm #s cases (execute_1_ok cm s) #clock_assm #_ assumption
qed-.

let rec compute_max_trace_label_label_cost_is_ok
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status cm) (final_status: Status cm)
      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
        start_status final_status) on the_trace:
          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) ≝ ?
and compute_max_trace_any_label_cost_is_ok
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status cm) (final_status: Status cm)
     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag start_status final_status)
       on the_trace:
         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) ≝ ?
and compute_max_trace_label_return_cost_is_ok
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status cm) (final_status: Status cm)
    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels) start_status final_status)
      on the_trace:
        clock … cm … final_status = (compute_max_trace_label_return_cost cm cost_labels start_status final_status the_trace) + clock … cm … start_status ≝ ?.
  [1:
    cases the_trace
    #ends_flag #start_status #end_status #any_label_trace #is_costed
    normalize @compute_max_trace_any_label_cost_is_ok
  |2:
    cases the_trace
    [1,2:
      #start_status #final_status #is_next #is_not_return try (#is_costed)
      change with (current_instruction_cost cm start_status) in ⊢ (???(?%?));
      cases(is_next) @execute_1_ok_clock
    |3:
      #status_pre_fun_call #status_start_fun_call #status_final #is_next
      #classifier_assm #after_return_assm #call_trace #costed_assm
      whd in match (compute_max_trace_any_label_cost … (tal_base_call …));
      >(compute_max_trace_label_return_cost_is_ok … call_trace)
      >associative_plus @eq_f cases(is_next)
      @execute_1_ok_clock
    |4:
      #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
      #status_final #is_next #is_call #is_after_return #call_trace #not_costed #final_trace
      change with (
      let current_instruction_cost ≝ current_instruction_cost cm status_pre_fun_call in
      let call_trace_cost ≝ compute_max_trace_label_return_cost cm … call_trace in
      let final_trace_cost ≝ compute_max_trace_any_label_cost cm cost_labels end_flag … final_trace in
        call_trace_cost + current_instruction_cost + final_trace_cost) in ⊢ (???(?%?));
      normalize nodelta;
      >(compute_max_trace_any_label_cost_is_ok … cost_labels end_flag status_after_fun_call
          status_final final_trace)
      >(compute_max_trace_label_return_cost_is_ok … cost_labels status_start_fun_call
        status_after_fun_call call_trace)
      cases(is_next) in match (clock … cm status_start_fun_call);
      >(execute_1_ok_clock cm status_pre_fun_call)
      <associative_plus in ⊢ (??%?);
      <commutative_plus in match (
        compute_max_trace_any_label_cost cm cost_labels end_flag status_after_fun_call status_final final_trace
          + compute_max_trace_label_return_cost cm cost_labels status_start_fun_call status_after_fun_call call_trace);
      >associative_plus in ⊢ (??%?); >associative_plus in ⊢ (???%); >associative_plus in ⊢ (???%);
      @eq_f >commutative_plus in ⊢ (??%?); >associative_plus in ⊢ (??%?);
      @eq_f @commutative_plus 
    |5:
      #end_flag #status_pre #status_init #status_end #is_next
      #trace_any_label #is_other #is_not_costed
      change with (
      let current_instruction_cost ≝ current_instruction_cost cm status_pre in
      let tail_trace_cost ≝
       compute_max_trace_any_label_cost cm cost_labels end_flag
        status_init status_end trace_any_label
      in
        current_instruction_cost + tail_trace_cost) in ⊢ (???(?%?));
      normalize nodelta;
      >(compute_max_trace_any_label_cost_is_ok cm cost_labels end_flag
         status_init status_end trace_any_label)
      cases(is_next) in match (clock … cm status_init);
      >(execute_1_ok_clock … status_pre)
      >commutative_plus >associative_plus >associative_plus @eq_f
      @commutative_plus
    ]
  |3:
    cases the_trace
    [1:
      #status_before #status_after #trace_to_lift
      normalize @compute_max_trace_label_label_cost_is_ok
    |2:
      #status_initial #status_labelled #status_final #labelled_trace #ret_trace
      normalize
      >(compute_max_trace_label_return_cost_is_ok cm cost_labels status_labelled status_final ret_trace);
      >(compute_max_trace_label_label_cost_is_ok cm cost_labels doesnt_end_with_ret status_initial status_labelled labelled_trace);
      <associative_plus in ⊢ (??%?);
      >commutative_plus in match (
        compute_max_trace_label_return_cost cm cost_labels status_labelled status_final ret_trace
          + compute_max_trace_label_label_cost cm cost_labels doesnt_end_with_ret status_initial status_labelled labelled_trace);
      %
    ]
  ]
qed.

let rec compute_trace_label_label_cost_using_paid
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status cm) (final_status: Status cm)
      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
        start_status final_status) on the_trace: nat ≝
  match the_trace with
  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
      compute_paid_trace_label_label cm cost_labels … the_trace +
      compute_trace_any_label_cost_using_paid … given_trace
  ]
and compute_trace_any_label_cost_using_paid
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status cm) (final_status: Status cm)
     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag start_status final_status)
       on the_trace: nat ≝
  match the_trace with
  [ tal_base_not_return the_status _ _ _ _ ⇒ 0
  | tal_base_return the_status _ _ _ ⇒ 0
  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
      compute_trace_label_return_cost_using_paid … call_trace
  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
     _ _ _ call_trace _ final_trace ⇒
      let call_trace_cost ≝ compute_trace_label_return_cost_using_paid … call_trace in
      let final_trace_cost ≝ compute_trace_any_label_cost_using_paid cm cost_labels end_flag … final_trace in
        call_trace_cost + final_trace_cost
  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
     compute_trace_any_label_cost_using_paid cm cost_labels end_flag
      status_init status_end tail_trace
  ]
and compute_trace_label_return_cost_using_paid
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status cm) (final_status: Status cm)
    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels) start_status final_status)
      on the_trace: nat ≝
  match the_trace with
  [ tlr_base before after trace_to_lift ⇒ compute_trace_label_label_cost_using_paid … trace_to_lift
  | tlr_step initial labelled final labelled_trace ret_trace ⇒
      let labelled_cost ≝ compute_trace_label_label_cost_using_paid … labelled_trace in
      let return_cost ≝ compute_trace_label_return_cost_using_paid … ret_trace in
        labelled_cost + return_cost
  ].

let rec compute_trace_label_label_cost_using_paid_ok
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status cm) (final_status: Status cm)
      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
        start_status final_status) on the_trace:
 compute_trace_label_label_cost_using_paid cm cost_labels … the_trace =
 compute_max_trace_label_label_cost … the_trace ≝ ?
and compute_trace_any_label_cost_using_paid_ok
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status cm) (final_status: Status cm)
     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels)
      trace_ends_flag start_status final_status) on the_trace:      
  compute_paid_trace_any_label cm cost_labels trace_ends_flag … the_trace
  +compute_trace_any_label_cost_using_paid cm cost_labels trace_ends_flag … the_trace
  =compute_max_trace_any_label_cost cm cost_labels trace_ends_flag … the_trace ≝ ?
and compute_trace_label_return_cost_using_paid_ok
  (cm: ?)
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status cm) (final_status: Status cm)
    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels)
     start_status final_status) on the_trace:
 compute_trace_label_return_cost_using_paid cm cost_labels … the_trace =
 compute_max_trace_label_return_cost cm cost_labels … the_trace ≝ ?.
[ cases the_trace #endsf #ss #es #tr #H normalize
  @compute_trace_any_label_cost_using_paid_ok
| cases the_trace
  [ #ss #fs #H1 #H2 #H3 whd in ⊢ (??(?%%)%); <plus_n_O %
  | #ss #fs #H1 #H2 whd in ⊢ (??(?%%)%); <plus_n_O %
  |
    #sp #ss #sf #H1 #H2 #tr1 #tr2 #H3
    whd in ⊢ (???%); whd in ⊢ (??(??%)?); whd in ⊢ (??(?%?)?);
    >compute_trace_label_return_cost_using_paid_ok in ⊢ (??%?);
    >commutative_plus in ⊢ (??%?); @eq_f %
  | #ef #spfc #ssfc #safc #sf #H1 #H2 #H3 #tr1 #H4 #tr2 whd in ⊢ (??(?%%)%);
    <compute_trace_any_label_cost_using_paid_ok
    <compute_trace_label_return_cost_using_paid_ok
    -compute_trace_label_label_cost_using_paid_ok
    -compute_trace_label_return_cost_using_paid_ok
    -compute_trace_any_label_cost_using_paid_ok
    >commutative_plus in ⊢ (???(?%?));
    >commutative_plus in ⊢ (??(??%)?);
    >associative_plus >associative_plus in ⊢ (???%); @eq_f2 try %
    <associative_plus <commutative_plus %
  | #ef #sp #si #se #H1 #tr #H2 #H3 whd in ⊢ (??(?%%)%); >associative_plus @eq_f2
    [ % | @compute_trace_any_label_cost_using_paid_ok ]
  ]
| cases the_trace
  [ #sb #sa #tr normalize @compute_trace_label_label_cost_using_paid_ok
  | #si #sl #sf #tr1 #tr2 normalize @eq_f2
    [ @compute_trace_label_label_cost_using_paid_ok
    | @compute_trace_label_return_cost_using_paid_ok ]]]
qed.

include alias "ASM/BitVectorTrie.ma".

let rec compute_cost_trace_label_label
  (cm: BitVectorTrie Byte 16)
  (cost_labels: BitVectorTrie costlabel 16)
   (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status cm) (final_status: Status cm)
      (the_trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag
        start_status final_status) on the_trace:
         list (Σk:costlabel. ∃pc: Word. lookup_opt … pc cost_labels = Some … k) ≝
  match the_trace with
  [ tll_base ends_flag initial final given_trace labelled_proof ⇒
     let pc ≝ program_counter ? cm initial in
     let label ≝
      match lookup_opt … pc cost_labels return λx: option ?. match x with [None ⇒ False | Some _ ⇒ True] → costlabel with
      [ None ⇒ λabs. ⊥
      | Some l ⇒ λ_. l ] labelled_proof in
      (mk_Sig ?? label ?)::compute_cost_trace_any_label cm cost_labels ends_flag initial final … given_trace
  ]
and compute_cost_trace_any_label
  (cm: BitVectorTrie Byte 16)
  (cost_labels: BitVectorTrie costlabel 16)
  (trace_ends_flag: trace_ends_with_ret)
   (start_status: Status cm) (final_status: Status cm)
     (the_trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag start_status final_status)
       on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
  match the_trace with
  [ tal_base_not_return the_status _ _ _ _ ⇒ [ ]
  | tal_base_call pre_fun_call start_fun_call final _ _ _ call_trace _ ⇒
      compute_cost_trace_label_return … call_trace
  | tal_base_return the_status _ _ _ ⇒ [ ]
  | tal_step_call end_flag pre_fun_call start_fun_call after_fun_call final
     _ _ _ call_trace _ final_trace ⇒
      let call_cost_trace ≝ compute_cost_trace_label_return … call_trace in
      let final_cost_trace ≝ compute_cost_trace_any_label cm cost_labels end_flag … final_trace in
        call_cost_trace @ final_cost_trace
  | tal_step_default end_flag status_pre status_init status_end _ tail_trace _ _ ⇒
       compute_cost_trace_any_label cm cost_labels end_flag
        status_init status_end tail_trace
  ]
and compute_cost_trace_label_return
  (cm: BitVectorTrie Byte 16)
  (cost_labels: BitVectorTrie costlabel 16)
  (start_status: Status cm) (final_status: Status cm)
    (the_trace: trace_label_return (ASM_abstract_status cm cost_labels) start_status final_status)
      on the_trace: list (Σk:costlabel. ∃pc. lookup_opt … pc cost_labels = Some … k) ≝
  match the_trace with
  [ tlr_base before after trace_to_lift ⇒ compute_cost_trace_label_label cm … trace_to_lift
  | tlr_step initial labelled final labelled_trace ret_trace ⇒
      let labelled_cost ≝ compute_cost_trace_label_label cm … labelled_trace in
      let return_cost ≝ compute_cost_trace_label_return cm … ret_trace in
        labelled_cost @ return_cost
  ].
 [ %{pc} whd in match label;  generalize in match labelled_proof; whd in ⊢ (% → ?);
  cases (lookup_opt costlabel … pc cost_labels) normalize
  [ #abs cases abs | // ]
 | // ]
qed.

include alias "arithmetics/nat.ma".
include alias "basics/logic.ma".

lemma and_intro_right:
  ∀a, b: Prop.
    a → (a → b) → a ∧ b.
  #a #b /3/
qed.

lemma lt_m_n_to_exists_o_plus_m_n:
  ∀m, n: nat.
    m < n → ∃o: nat. m + o = n.
  #m #n
  cases m
  [1:
    #irrelevant
    %{n} %
  |2:
    #m' #lt_hyp
    %{(n - S m')}
    >commutative_plus in ⊢ (??%?);
    <plus_minus_m_m
    [1:
      %
    |2:
      @lt_S_to_lt
      assumption
    ]
  ]
qed.

lemma lt_O_n_to_S_pred_n_n:
  ∀n: nat.
    0 < n → S (pred n) = n.
  #n
  cases n
  [1:
    #absurd
    cases(lt_to_not_zero 0 0 absurd)
  |2:
    #n' #lt_hyp %
  ]
qed.

lemma exists_plus_m_n_to_exists_Sn:
  ∀m, n: nat.
    m < n → ∃p: nat. S p = n.
  #m #n
  cases m
  [1:
    #lt_hyp %{(pred n)}
    @(lt_O_n_to_S_pred_n_n … lt_hyp)
  |2:
    #m' #lt_hyp %{(pred n)}
    @(lt_O_n_to_S_pred_n_n)
    @(transitive_le … (S m') …)
    [1:
      //
    |2:
      @lt_S_to_lt
      assumption
    ]
  ]
qed.

include alias "arithmetics/bigops.ma".

(* This shoudl go in bigops! *)
theorem bigop_sum_rev: ∀k1,k2,p,B,nil.∀op:Aop B nil.∀f:nat→B.
 \big[op,nil]_{i<k1+k2|p i} (f i) =
 op \big[op,nil]_{i<k2|p (i+k1)} (f (i+k1)) \big[op,nil]_{i<k1|p i} (f i).
 #k1 #k2 #p #B #nil #op #f >bigop_sum
 >commutative_plus @same_bigop #i @leb_elim normalize
 [2,4: //
 | #H1 #H2 <plus_minus_m_m //
 | #H1 #H2 #H3 <plus_minus_m_m //]
qed.

(* This is taken by sigma_pi.ma that does not compile now *)
definition natAop ≝ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n)) 
   (λa,b,c.sym_eq ??? (associative_plus a b c)).

definition natACop ≝ mk_ACop nat 0 natAop commutative_plus.

definition natDop ≝ mk_Dop nat 0 natACop times (λn.(sym_eq ??? (times_n_O n)))
   distributive_times_plus.

unification hint  0 ≔ ;
   S ≟ mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n)) 
   (λa,b,c.sym_eq ??? (associative_plus a b c))
(* ---------------------------------------- *) ⊢
   plus ≡ op ? ? S.

unification hint  0 ≔ ;
   S ≟ mk_ACop nat 0 (mk_Aop nat 0 plus (λa.refl ? a) (λn.sym_eq ??? (plus_n_O n)) 
   (λa,b,c.sym_eq ??? (associative_plus a b c))) commutative_plus
(* ---------------------------------------- *) ⊢
   plus ≡ op ? ? S.
   
unification hint  0 ≔ ;
   S ≟ natDop
(* ---------------------------------------- *) ⊢
   plus ≡ sum ? ? S.

unification hint  0 ≔ ;
   S ≟ natDop
(* ---------------------------------------- *) ⊢
   times ≡ prod ? ? S.

notation > "Σ_{ ident i < n } f"
  with precedence 20
for @{'bigop $n plus 0 (λ${ident i}.true) (λ${ident i}. $f)}.

notation < "Σ_{ ident i < n } f"
  with precedence 20
for @{'bigop $n plus 0 (λ${ident i}:$X.true) (λ${ident i}:$Y. $f)}.

definition tech_cost_of_label0:
 ∀cost_labels: BitVectorTrie costlabel 16.
 ∀cost_map: identifier_map CostTag nat.
 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
 ∀ctrace:list (Σk:costlabel.∃pc. lookup_opt costlabel 16 pc cost_labels = Some ? k).
 ∀i,p. present … cost_map (nth_safe ? i ctrace p).
 #cost_labels #cost_map #codom_dom #ctrace #i #p
 cases (nth_safe … i ctrace ?) normalize #id * #id_pc #K
 lapply (codom_dom … K) #k_pres >(lookup_lookup_present … k_pres)
 % #abs destruct (abs)
qed.

include alias "arithmetics/nat.ma".
include alias "basics/logic.ma".

lemma ltb_rect:
 ∀P:Type[0].∀n,m. (n < m → P) → (¬ n < m → P) → P.
 #P #n #m lapply (refl … (ltb n m)) cases (ltb n m) in ⊢ (???% → %); #E #H1 #H2
 [ @H1 @leb_true_to_le @E | @H2 @leb_false_to_not_le @E ]
qed.

lemma same_ltb_rect:
 ∀P,n,m,H1,H2,n',m',H1',H2'.
  ltb n m = ltb n' m' → (∀x,y. H1 x = H1' y) → (∀x,y. H2 x = H2' y) →
   ltb_rect P n m H1 H2 =
   ltb_rect P n' m' H1' H2'.
 #P #n #m #H1 #H2 #n' #m' #H1' #H2' #E #K1 #K2 whd in ⊢ (??%?);
 cut (∀xxx,yyy,xxx',yyy'.
   match ltb n m
   return λx:bool.
           eq bool (ltb n m) x
            → (lt n m → P) → (Not (lt n m) → P) → P
    with
    [ true ⇒ 
        λE0:eq bool (ltb n m) true.
         λH10:lt n m → P.
          λH20:Not (lt n m) → P. H10 (xxx E0)
    | false ⇒
        λE0:eq bool (ltb n m) false.
         λH10:lt n m → P.
          λH20:Not (lt n m) → P. H20 (yyy E0)] 
    (refl … (ltb n m)) H1 H2 =
   match ltb n' m'
   return λx:bool.
           eq bool (ltb n' m') x
            → (lt n' m' → P) → (Not (lt n' m') → P) → P
    with
    [ true ⇒ 
        λE0:eq bool (ltb n' m') true.
         λH10:lt n' m' → P.
          λH20:Not (lt n' m') → P. H10 (xxx' E0)
    | false ⇒
        λE0:eq bool (ltb n' m') false.
         λH10:lt n' m' → P.
          λH20:Not (lt n' m') → P. H20 (yyy' E0)] 
    (refl … (ltb n' m')) H1' H2'
  ) [2: #X @X]
 >E cases (ltb n' m') #xxx #yyy #xxx' #yyy' normalize
 [ @K1 | @K2 ]
qed.


definition tech_cost_of_label:
 ∀cost_labels: BitVectorTrie costlabel 16.
 ∀cost_map: identifier_map CostTag nat.
 ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
 list (Σk:costlabel.∃pc. lookup_opt costlabel 16 pc cost_labels = Some ? k) →
 nat → nat
≝ λcost_labels,cost_map,codom_dom,ctrace,i.
 ltb_rect ? i (|ctrace|)
 (λH. lookup_present ?? cost_map (nth_safe ? i ctrace H) ?)
 (λ_.0).
 @tech_cost_of_label0 @codom_dom
qed.

lemma shift_nth_safe:
 ∀T,i,l2,l1,K1,K2.
  nth_safe T i l1 K1 = nth_safe T (i+|l2|) (l2@l1) K2.
 #T #i #l2 elim l2 normalize
  [ #l1 #K1 <plus_n_O #K2 %
  | #hd #tl #IH #l1 #K1 <plus_n_Sm #K2 change with (? < ?) in K1; change with (? < ?) in K2;
    whd in ⊢ (???%); @IH ] 
qed.

lemma shift_nth_prefix:
 ∀T,l1,i,l2,K1,K2.
  nth_safe T i l1 K1 = nth_safe T i (l1@l2) K2.
  #T #l1 elim l1 normalize
  [
    #i #l1 #K1 cases(lt_to_not_zero … K1)
  |
    #hd #tl #IH #i #l2
    cases i
    [
      //
    |
      #i' #K1 #K2 whd in ⊢ (??%%);
      @IH
    ]
  ]
qed.

lemma tech_cost_of_label_shift:
 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
  i < |l2| →
   tech_cost_of_label cost_labels cost_map codom_dom l2 i =
   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) (i+|l1|).
 #cost_labels #cost_Map #codom_dom #l1 #l2 #i #H
 whd in match tech_cost_of_label; normalize nodelta @same_ltb_rect
 [ @(ltb_rect ? i (|l2|)) @(ltb_rect ? (i+|l1|) (|l1@l2|)) #K1 #K2
   whd in match ltb; normalize nodelta
   [1: >le_to_leb_true try assumption applyS le_to_leb_true //
   |4: >not_le_to_leb_false try assumption applyS not_le_to_leb_false
       change with (¬ ? ≤ ?) in K1; applyS K1
   |2: @⊥ @(absurd (i+|l1| < |l1@l2|)) // >length_append
       applyS (monotonic_lt_plus_r … (|l1|)) //
   |3: @⊥ @(absurd ?? K2) >length_append in K1; #K1 /2 by lt_plus_to_lt_l/ ]
 | #H1 #H2
   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
   <(shift_nth_safe … H1) #p %
 | // ]
qed.

lemma tech_cost_of_label_prefix:
 ∀cost_labels,cost_map,codom_dom,l1,l2,i.
  i < |l1| →
   tech_cost_of_label cost_labels cost_map codom_dom l1 i =
   tech_cost_of_label cost_labels cost_map codom_dom (l1@l2) i.
 #cost_labels #cost_map #codom_dom #l1 #l2 #i #H
 whd in match tech_cost_of_label; normalize nodelta @same_ltb_rect
 [1:
   whd in match ltb; normalize nodelta
   >(le_to_leb_true … H) applyS le_to_leb_true
   >length_append whd in H; >commutative_plus @le_plus_a assumption
 |2:
   #K1 #K2
   generalize in match (tech_cost_of_label0 ??? (l1@l2) ??);
   <(shift_nth_prefix … l1 i l2 K1 K2) //
 |3:
   #_ #_ %
 ]
qed.
    
(* XXX: here *)
let rec compute_trace_label_return_using_paid_ok_with_trace
 (cm: ?) (total_program_size: nat) (good_program_witness: good_program cm total_program_size)
 (cost_labels: BitVectorTrie costlabel 16)
 (cost_map: identifier_map CostTag nat)
 (initial: Status cm) (final: Status cm)
 (trace: trace_label_return (ASM_abstract_status cm cost_labels) initial final)
 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
 on trace:
 ∀dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
   ∃reachable_witness: reachable_program_counter cm total_program_size pc.
   pi1 … (block_cost cm pc total_program_size cost_labels reachable_witness good_program_witness) = lookup_present … k_pres).
  let ctrace ≝ compute_cost_trace_label_return cm … trace in
  compute_trace_label_return_cost_using_paid cm … trace =
   (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i))
    ≝ ?
and compute_trace_any_label_using_paid_ok_with_trace
 (cm: ?) (total_program_size: nat) (good_program_witness: good_program cm total_program_size)
 (cost_labels: BitVectorTrie costlabel 16)
 (trace_ends_flag: trace_ends_with_ret)
 (cost_map: identifier_map CostTag nat)
 (initial: Status cm) (final: Status cm)
 (trace: trace_any_label (ASM_abstract_status cm cost_labels) trace_ends_flag initial final)
 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
   ∃reachable_witness: reachable_program_counter cm total_program_size pc.
   pi1 … (block_cost cm pc total_program_size cost_labels reachable_witness good_program_witness) = lookup_present … k_pres))
 on trace:
  let ctrace ≝ compute_cost_trace_any_label … trace in
  compute_trace_any_label_cost_using_paid … trace =
   (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i))
    ≝ ?
and compute_trace_label_label_using_paid_ok_with_trace
 (cm: ?) (total_program_size: nat) (good_program_witness: good_program cm total_program_size)
 (cost_labels: BitVectorTrie costlabel 16)
 (trace_ends_flag: trace_ends_with_ret)
 (cost_map: identifier_map CostTag nat)
 (initial: Status cm) (final: Status cm)
 (trace: trace_label_label (ASM_abstract_status cm cost_labels) trace_ends_flag initial final)
 (codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k))
 (dom_codom:(∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
   ∃reachable_witness: reachable_program_counter cm total_program_size pc.
   pi1 … (block_cost cm pc total_program_size cost_labels reachable_witness good_program_witness) = lookup_present … k_pres))
 on trace:
  let ctrace ≝ compute_cost_trace_label_label … trace in
  compute_trace_label_label_cost_using_paid … trace =
   (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i))
    ≝ ?.
  cases trace normalize nodelta
  [ #sb #sa #tr #dom_codom whd in ⊢ (??%?);
    whd in match (compute_cost_trace_label_return ?????);
    @(compute_trace_label_label_using_paid_ok_with_trace … good_program_witness) @dom_codom
  | #si #sl #sf #tr1 #tr2 #dom_codom
    whd in ⊢ (??%?);
    whd in match (compute_cost_trace_label_return ?????);
    >append_length >bigop_sum_rev >commutative_plus @eq_f2
    [ >(compute_trace_label_return_using_paid_ok_with_trace … good_program_witness … cost_map … codom_dom dom_codom)
      -compute_trace_label_return_using_paid_ok_with_trace
      @same_bigop [//] #i #H #_ -dom_codom @tech_cost_of_label_shift //
    | >(compute_trace_label_label_using_paid_ok_with_trace … good_program_witness … cost_map … codom_dom … dom_codom)
      -compute_trace_label_label_using_paid_ok_with_trace
      @same_bigop [//] #i #H #_ @(tech_cost_of_label_prefix … H)
    ]
  |8:
    #end_flag #start_status #end_status #trace_any_label #costed_assm
    whd in ⊢ (??%?); whd in ⊢ (??(?%?)?);
    >(compute_trace_any_label_using_paid_ok_with_trace … good_program_witness … cost_map … codom_dom … dom_codom)
    >bigop_0 in ⊢ (???%); >commutative_plus @eq_f2
    [1:
      @same_bigop [//] #i #H #_ -dom_codom >(plus_n_O i) >plus_n_Sm
      <(tech_cost_of_label_shift ??? [?] ? i) //
    |2:
      change with (? = lookup_present ? ? ? ? ?)
      generalize in match (tech_cost_of_label0 ? ? ? ? ? ?);
      normalize in match (nth_safe ? ? ? ?);
      whd in costed_assm; lapply costed_assm -costed_assm    
      inversion (lookup_opt ? ? (program_counter … cm start_status) cost_labels)
      [1:
        #_ #absurd cases absurd
      |2:
        normalize nodelta #cost_label #Some_assm #_ #p
        cases (dom_codom ? p ? Some_assm)
        #reachable_witness #block_cost_assm <block_cost_assm
        cases (block_cost ? ? ? ? ? ?)
        #cost -block_cost_assm #block_cost_assm
        cases (block_cost_assm ? ? ? trace_any_label (refl …)) %
      ]
    ]
  |3:
    #start_status #final_status #execute_assm #classifier_assm #costed_assm
    %
  |4:
    #start_status #final_status #execute_assm #classifier_assm %
  |5:
    #status_pre_fun_call #status_start_fun_call #status_final #execute_assm
    #classifier_assm #after_return_assm #trace_label_return #costed_assm
    whd in ⊢ (??%?);
    @(compute_trace_label_return_using_paid_ok_with_trace … good_program_witness … cost_map … codom_dom dom_codom)
  |6:
    #end_flag #status_pre_fun_call #status_start_fun_call #status_after_fun_call
    #status_final #execute_assm #classifier_assm #after_return_assm #trace_label_return
    #costed_assm #trace_any_label
    whd in ⊢ (??%?);
    >(compute_trace_label_return_using_paid_ok_with_trace … good_program_witness … cost_map … codom_dom dom_codom)
    >(compute_trace_any_label_using_paid_ok_with_trace … good_program_witness … cost_map … codom_dom … dom_codom)
    >length_append >bigop_sum_rev >commutative_plus @eq_f2
    [ @same_bigop [2: #i #H #_ -dom_codom @tech_cost_of_label_shift assumption
                  |1: #i #H % ]
    | @same_bigop [#i #H %] #i #H #_ @(tech_cost_of_label_prefix … H)
    ]
  |7:
    #end_flag #status_pre_fun_call #status_start_fun_call #status_final
    #execute_assm #trace_any_label #classifier_assm #costed_assm
    whd in ⊢ (??%?);
    @(compute_trace_any_label_using_paid_ok_with_trace … good_program_witness … cost_map … codom_dom … dom_codom)
  ]
qed.
  
lemma compute_max_trace_label_return_cost_ok_with_trace_aux:
  ∀code_memory: BitVectorTrie Byte 16.
  ∀total_program_size: nat.
  ∀good_program_witness: good_program code_memory total_program_size.
  ∀cost_labels: BitVectorTrie costlabel 16.
  ∀cost_map: identifier_map CostTag nat.
  ∀initial: Status code_memory.
  ∀final: Status code_memory.
  ∀trace: trace_label_return (ASM_abstract_status code_memory cost_labels) initial final.
  ∀codom_dom: (∀pc,k. lookup_opt … pc cost_labels = Some … k → present … cost_map k).
  ∀dom_codom: (∀k. ∀k_pres:present … cost_map k. ∀pc. lookup_opt … pc cost_labels = Some … k →
    ∃reachable_witness: reachable_program_counter code_memory total_program_size pc.
      pi1 … (block_cost code_memory pc total_program_size cost_labels reachable_witness good_program_witness) = lookup_present … k_pres).
        let ctrace ≝ compute_cost_trace_label_return code_memory … trace in
          clock … code_memory … final =
            clock … code_memory … initial + (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map codom_dom ctrace i)).
  #code_memory #total_program_size #good_program_witness #cost_labels #cost_map
  #initial #final #trace #codom_dom #dom_codom normalize nodelta
  <compute_trace_label_return_using_paid_ok_with_trace try assumption
  >commutative_plus >compute_trace_label_return_cost_using_paid_ok //
qed.

theorem compute_max_trace_label_return_cost_ok_with_trace:
  ∀code_memory: BitVectorTrie Byte 16.
  ∀total_program_size: nat.
  ∀total_program_size_invariant: total_program_size ≤ 2^16.
  ∀good_program_witness: good_program code_memory total_program_size.
  ∀cost_labels: BitVectorTrie costlabel 16.
  ∀cost_labels_injective:
   (∀pc,pc',l.
     lookup_opt costlabel 16 pc cost_labels=Some costlabel l
      →lookup_opt costlabel 16 pc' cost_labels=Some costlabel l→pc=pc').
  ∀reachable_program_counter_witness:
    ∀lbl: costlabel.
    ∀program_counter: Word.
      Some costlabel lbl=lookup_opt costlabel 16 program_counter cost_labels →
        reachable_program_counter code_memory total_program_size program_counter.
  ∀initial: Status code_memory.
  ∀final: Status code_memory.
  ∀trace: trace_label_return (ASM_abstract_status code_memory cost_labels) initial final.
    let cost_map ≝ traverse_code code_memory cost_labels cost_labels_injective total_program_size total_program_size_invariant
      reachable_program_counter_witness good_program_witness in
    let ctrace ≝ compute_cost_trace_label_return code_memory … trace in
      clock … code_memory … final = clock … code_memory … initial + (Σ_{i < |ctrace|} (tech_cost_of_label cost_labels cost_map ? ctrace i)).
  [1:
    #code_memory #total_program_size #total_program_size_invariant #good_program_witness
    #cost_labels #cost_labels_injective #reachable_program_counter_witness #initial #final #trace
    @compute_max_trace_label_return_cost_ok_with_trace_aux try assumption
  |2:
    skip
  ]
  normalize nodelta
  cases (traverse_code ? ? ? ? ? ? ?)
  #cost_map * #dom_codom #codom_dom try assumption
  #pc #k #lookup_opt_assm @(dom_codom … lookup_opt_assm)
  lapply (sym_eq ? ? ? lookup_opt_assm)
  -lookup_opt_assm #lookup_opt_assm
  cases (reachable_program_counter_witness … lookup_opt_assm)
  #fetch_n_assm #relevant assumption
qed.