source: src/ASM/CostsProof.ma @ 1511

include "ASM/ASMCosts.ma".
include "ASM/WellLabeled.ma".
include "ASM/Status.ma".

definition is_jump_p ≝
  λs.
  match s with
  [ AJMP _ ⇒ True
  | LJMP _ ⇒ True
  | SJMP _ ⇒ True
  | JMP _ ⇒ True
  | RealInstruction ri ⇒
    match ri with
    [ JZ _ ⇒ True
    | JNZ _ ⇒ True
    | JC _ ⇒ True
    | JNC _ ⇒ True
    | JB _ _ ⇒ True
    | JNB _ _ ⇒ True
    | JBC _ _ ⇒ True
    | CJNE _ _ ⇒ True
    | DJNZ _ _ ⇒ True
    | _ ⇒ False
    ]
  | _ ⇒ False
  ].

definition is_call_p ≝
  λs.
  match s with
  [ ACALL _ ⇒ True
  | LCALL _ ⇒ True
  | _ ⇒ False
  ].

definition next_instruction ≝
  λs: Status.
  let 〈instruction, ignore, ignore〉 ≝ fetch (code_memory … s) (program_counter … s) in
    instruction.

inductive trace_ends_with_ret: Type[0] ≝
  | ends_with_ret: trace_ends_with_ret
  | doesnt_end_with_ret: trace_ends_with_ret.

definition next_instruction_is_labelled ≝
  λcost_labels: BitVectorTrie Byte 16.
  λs: Status.
  let pc ≝ program_counter … (execute 1 s) in
    match lookup_opt … pc cost_labels with
    [ None ⇒ False
    | _    ⇒ True
    ].

definition current_instruction_cost ≝
  λs: Status.
    \snd (fetch (code_memory … s) (program_counter … s)).

definition next_instruction_properly_relates_program_counters ≝
  λbefore: Status.
  λafter : Status.
  let size ≝ current_instruction_cost before in
  let pc_before ≝ program_counter … before in
  let pc_after ≝ program_counter … after in
  let sum ≝ \snd (half_add … pc_before (bitvector_of_nat … size)) in
    sum = pc_after.

definition current_instruction ≝
  λs: Status.
  let pc ≝ program_counter … s in
  \fst (\fst (fetch … (code_memory … s) pc)).

definition current_instruction_is_labelled ≝
  λcost_labels: BitVectorTrie Byte 16.
  λs: Status.
  let pc ≝ program_counter … s in
    match lookup_opt … pc cost_labels with
    [ None ⇒ False
    | _    ⇒ True
    ].

inductive trace_label_return (cost_labels: BitVectorTrie Byte 16): Status → Status → Type[0] ≝
  | tlr_base:
      ∀status_before: Status.
      ∀status_after: Status.
        trace_label_label cost_labels ends_with_ret status_before status_after →
        trace_label_return cost_labels status_before status_after
  | tlr_step:
      ∀status_initial: Status.
      ∀status_labelled: Status.
      ∀status_final: Status.
          trace_label_label cost_labels doesnt_end_with_ret status_initial status_labelled →
            trace_label_return cost_labels status_labelled status_final →
              trace_label_return cost_labels status_initial status_final
with trace_label_label: trace_ends_with_ret → Status → Status → Type[0] ≝
  | tll_base:
      ∀ends_flag: trace_ends_with_ret.
      ∀start_status: Status.
      ∀end_status: Status.
        trace_label_label_pre cost_labels ends_flag start_status end_status →
        current_instruction_is_labelled cost_labels start_status →
        trace_label_label cost_labels ends_flag start_status end_status
with trace_label_label_pre: trace_ends_with_ret → Status → Status → Type[0] ≝
  | tllp_base_not_return:
      ∀start_status: Status.
        let final_status ≝ execute 1 start_status in
        current_instruction start_status ≠ (RealInstruction … (RET [[relative]])) →
        ¬ (is_jump_p (current_instruction start_status)) →
        current_instruction_is_labelled cost_labels final_status →
          trace_label_label_pre cost_labels doesnt_end_with_ret start_status final_status
  | tllp_base_return:
      ∀start_status: Status.
        let final_status ≝ execute 1 start_status in
          current_instruction start_status = (RealInstruction … (RET [[relative]])) →
            trace_label_label_pre cost_labels ends_with_ret start_status final_status
  | tllp_base_jump:
      ∀start_status: Status.
        let final_status ≝ execute 1 start_status in
          is_jump_p (current_instruction start_status) →
            current_instruction_is_labelled cost_labels final_status →
              trace_label_label_pre cost_labels doesnt_end_with_ret start_status final_status
  | tllp_step_call:
      ∀end_flag: trace_ends_with_ret.
      ∀status_pre_fun_call: Status.
      ∀status_after_fun_call: Status.
      ∀status_final: Status.
        let status_start_fun_call ≝ execute 1 status_pre_fun_call in
          is_call_p (current_instruction status_pre_fun_call) →
          next_instruction_properly_relates_program_counters status_pre_fun_call status_after_fun_call →
          trace_label_return cost_labels status_start_fun_call status_after_fun_call →
          trace_label_label_pre cost_labels end_flag status_after_fun_call status_final →
            trace_label_label_pre cost_labels end_flag status_pre_fun_call status_final
  | tllp_step_default:
      ∀end_flag: trace_ends_with_ret.
      ∀status_pre: Status.
      ∀status_end: Status.
        let status_init ≝ execute 1 status_pre in
          trace_label_label_pre cost_labels end_flag status_init status_end →
          ¬ (is_call_p (current_instruction status_pre)) →
          ¬ (is_jump_p (current_instruction status_pre)) →
          (current_instruction status_pre) ≠ (RealInstruction … (RET [[relative]])) →
          ¬ (current_instruction_is_labelled cost_labels status_init) →
            trace_label_label_pre cost_labels end_flag status_pre status_end.

(* XXX: to do later
definition compute_simple_path0 (s:Status) (is_labelled s) (well_balanced s) (labelled_p p): trace_lab_ret ≝ ….

lemma simple_path_ok:
 ∀st: Status.∀H.
 let p ≝ compute_simple_path0 st H in
   ∀n.
    nth_path n p = execute n st ∧
     (execute' (path_length p) st = 〈st',τ〉 →
      τ = cost_trace p)
  ].
*)

let rec compute_max_trace_label_label_cost
  (cost_labels: BitVectorTrie Byte 16) (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label 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_label_label_pre_cost … given_trace
  ]
and compute_max_trace_label_label_pre_cost
  (cost_labels: BitVectorTrie Byte 16) (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label_pre cost_labels trace_ends_flag start_status final_status)
        on the_trace: nat ≝
  match the_trace with
  [ tllp_base_not_return the_status not_return not_jump not_cost_label ⇒
      current_instruction_cost the_status
  | tllp_base_return the_status is_return ⇒ current_instruction_cost the_status
  | tllp_base_jump the_status is_jump is_cost ⇒
      current_instruction_cost the_status
  | tllp_step_call end_flag pre_fun_call after_fun_call final is_call
        next_intruction_coherence call_trace final_trace ⇒
      let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
      let call_trace_cost ≝ compute_max_trace_label_return_cost cost_labels … call_trace in
      let final_trace_cost ≝ compute_max_trace_label_label_pre_cost cost_labels end_flag after_fun_call final final_trace in
        call_trace_cost + current_instruction_cost + final_trace_cost
  | tllp_step_default end_flag status_pre status_end tail_trace is_not_call
        is_not_jump is_not_ret is_not_labelled ⇒
      let current_instruction_cost ≝ current_instruction_cost status_pre in
      let tail_trace_cost ≝ compute_max_trace_label_label_pre_cost cost_labels end_flag (execute 1 status_pre) status_end tail_trace in
        current_instruction_cost + tail_trace_cost
  ]
and compute_max_trace_label_return_cost
  (cost_labels: BitVectorTrie Byte 16) (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return 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
  ].

lemma pred_minus_1:
  ∀m, n: nat.
  ∀proof: n < m.
    pred (m - n) = m - n - 1.
  #m #n
  cases m
  [ #proof
    cases(lt_to_not_zero … proof)
  | #m' #proof
    normalize in ⊢ (???%)
    cases n
    [ normalize //
    | #n' normalize
      cases(m' - n')
      [ %
      | #Sm_n'
        normalize //
      ]
    ]
  ]
qed.

lemma succ_m_plus_one:
  ∀m: nat.
    S m = m + 1.
  #m
  elim m
  [ %
  | #m' #ind_hyp
    normalize
    <ind_hyp
    %
  ]
qed.

lemma minus_m_n_minus_minus_plus_1:
  ∀m, n: nat.
  ∀proof: n < m.
    m - n = (m - n - 1) + 1.
  #m
  elim m
  [ #n #proof
    cases(lt_to_not_zero … proof)
  | #m' #ind_hyp #n
    normalize
    cases n
    [ normalize //
    | #n' #proof normalize
      <ind_hyp
      [ %
      | @le_S_S_to_le
        assumption
      ]
    ]
  ]
qed.

lemma plus_minus_rearrangement:
  ∀m, n, o: nat.
  ∀proof_n_m: n < m.
  ∀proof_m_o: m < o.
    (m - n) + (o - m) = o - n.
  #m #n #o
  elim m
  [1: #proof_n_m 
      cases(lt_to_not_zero … proof_n_m)
  |2: #m' #ind_hyp
      #proof_n_m' #proof_m_o
      >minus_Sn_m
      [2: normalize in proof_n_m';
          @le_S_S_to_le
          assumption
      |1: >eq_minus_S_pred
          >pred_minus_1
          [1: >(succ_m_plus_one (m' - n))
              >(associative_plus (m' - n) 1 (o - m' - 1))
              <commutative_plus in match (1 + (o - m' - 1));
              <(minus_m_n_minus_minus_plus_1 o m') in match (o - m' - 1 + 1)
              [1: >ind_hyp
                [1: %
                |2: normalize
                    normalize in proof_m_o;
                    @le_S_S_to_le
                    @(le_S ? ? proof_m_o)
                |3: cases daemon (* XXX: problem here *)
                ] 
              |2: normalize in proof_m_o;
                  normalize
                  @le_S_S_to_le
                  @(le_S (S (S m')) o proof_m_o)
              ]
          |2: normalize
              normalize in proof_m_o;
              @le_S_S_to_le
              @(le_S (S (S m')) o proof_m_o)
          ]
      ]
  ]
qed.

example set_program_counter_ignores_clock:
  ∀s: Status.
  ∀pc: Word.
    clock … (set_program_counter … s pc) = clock … s.
  #s #pc %
qed.

example set_low_internal_ram_ignores_clock:
  ∀s: Status.
  ∀ram: BitVectorTrie Byte 7.
    clock … (set_low_internal_ram … s ram) = clock … s.
  #s #ram %
qed.

example set_8051_sfr_ignores_clock:
  ∀s: Status.
  ∀sfr: SFR8051.
  ∀v: Byte.
    clock … (set_8051_sfr ? s sfr v) = clock … s.
  #s #sfr #v %
qed.

example clock_set_clock:
  ∀s: Status.
  ∀v.
    clock … (set_clock … s v) = v.
  #s #v %
qed.

example write_at_stack_pointer_ignores_clock:
  ∀s: Status.
  ∀sp: Byte.
    clock … (write_at_stack_pointer … s sp) = clock … s.
  #s #sp
  change in match (write_at_stack_pointer (BitVectorTrie Byte 16) s sp) with (
      let 〈nu, nl〉 ≝ split bool 4 4 (get_8051_sfr … s SFR_SP) in
        ?);
  normalize nodelta;
  cases(split bool 4 4 (get_8051_sfr (BitVectorTrie Byte 16) s SFR_SP))
  #nu #nl normalize nodelta;
  cases(get_index_v bool 4 nu O (le_S_S O 3 (le_O_n 3)))
  [ normalize nodelta; %
  | normalize nodelta; %
  ]
qed.

example status_execution_progresses_processor_clock:
  ∀s: Status.
    clock … s ≤ clock … (execute 1 s).
  #s
  change in match (execute 1 s) with (execute_1 s);
  change in match (execute_1 s) with (
    let instr_pc_ticks ≝ fetch (code_memory (BitVectorTrie Byte 16) s)
                               (program_counter (BitVectorTrie Byte 16) s)
    in 
      execute_1_0 s instr_pc_ticks);
  normalize nodelta;
  whd in match (execute_1_0 s (fetch (code_memory (BitVectorTrie Byte 16) s)
     (program_counter (BitVectorTrie Byte 16) s)));
  normalize nodelta;
  cases (fetch (code_memory (BitVectorTrie Byte 16) s)
           (program_counter (BitVectorTrie Byte 16) s))
  #instruction_pc #ticks
  normalize nodelta;
  cases instruction_pc
  #instruction #pc
  cases instruction
  [1:
    #addr11 cases addr11 #addressing_mode
    normalize nodelta; cases addressing_mode
    normalize nodelta;
    [1,2,3,4,8,9,15,16,17,19:
      #assm whd in ⊢ (% → ?)
      #absurd cases(absurd)
    |5,6,7,10,11,12,13,14:
      whd in ⊢ (% → ?)
      #absurd cases(absurd)
    |18:
      #addr11 #irrelevant
      normalize nodelta;
      >set_program_counter_ignores_clock
      normalize nodelta;
      >set_program_counter_ignores_clock
      >write_at_stack_pointer_ignores_clock
      >set_8051_sfr_ignores_clock
      >write_at_stack_pointer_ignores_clock
      >set_8051_sfr_ignores_clock
      >clock_set_clock //
    ]
  |2:
    #addr16 cases addr16 #addressing_mode
    normalize nodelta; cases addressing_mode
    normalize nodelta;
    [1,2,3,4,8,9,15,16,17,18:
      #assm whd in ⊢ (% → ?)
      #absurd cases(absurd)
    |5,6,7,10,11,12,13,14:
      whd in ⊢ (% → ?)
      #absurd cases(absurd)
    |19:
      #addr16 #irrelevant
      normalize nodelta;
      >set_program_counter_ignores_clock
      >write_at_stack_pointer_ignores_clock
      >set_8051_sfr_ignores_clock
      >write_at_stack_pointer_ignores_clock
      >set_8051_sfr_ignores_clock
      >clock_set_clock
      >set_program_counter_ignores_clock //
    ]
  |3: #addr11 cases addr11 #addressing_mode
      normalize nodelta; cases addressing_mode
      normalize nodelta;
      [1,2,3,4,8,9,15,16,17,19:
        #assm whd in ⊢ (% → ?)
        #absurd cases(absurd)
      |5,6,7,10,11,12,13,14:
        whd in ⊢ (% → ?)
        #absurd cases(absurd)
      |18:
        #word11 #irrelevant
        normalize nodelta;
        >set_program_counter_ignores_clock
        >clock_set_clock
        >set_program_counter_ignores_clock //
      ]
  |4: #addr16 cases addr16 #addressing_mode
      normalize nodelta; cases addressing_mode
      normalize nodelta;
      [1,2,3,4,8,9,15,16,17,18:
        #assm whd in ⊢ (% → ?)
        #absurd cases(absurd)
      |5,6,7,10,11,12,13,14:
        whd in ⊢ (% → ?)
        #absurd cases(absurd)
      |19:
        #word #irrelevant
        normalize nodelta;
        >set_program_counter_ignores_clock
        >clock_set_clock
        >set_program_counter_ignores_clock //
      ]
  |5: #relative cases relative #addressing_mode
      normalize nodelta; cases addressing_mode
      normalize nodelta;
      [1,2,3,4,8,9,15,16,18,19:
        #assm whd in ⊢ (% → ?)
        #absurd cases(absurd)
      |5,6,7,10,11,12,13,14:
        whd in ⊢ (% → ?)
        #absurd cases(absurd)
      |17:
        #byte #irrelevant
        normalize nodelta;
        >set_program_counter_ignores_clock
        >set_program_counter_ignores_clock
        >clock_set_clock //
      ]
  |6: #indirect_dptr cases indirect_dptr #addressing_mode
      normalize nodelta; cases addressing_mode
      normalize nodelta;
      

lemma current_instruction_cost_is_ok:
  ∀s: Status.
    current_instruction_cost s = clock … (execute 1 s) - clock … s.
  #s
  change in match (execute 1 s) with (execute_1 s);
  change in match (execute_1 s) with (
    let instr_pc_ticks ≝ fetch (code_memory (BitVectorTrie Byte 16) s)
                               (program_counter (BitVectorTrie Byte 16) s)
    in 
      execute_1_0 s instr_pc_ticks);
  change in ⊢ (??%?) with (
    \snd (fetch (code_memory … s) (program_counter … s)));
  normalize nodelta;

let rec compute_max_trace_label_label_cost_is_ok
  (cost_labels: BitVectorTrie Byte 16) (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label cost_labels trace_ends_flag start_status final_status)
      on the_trace:
        compute_max_trace_label_label_cost cost_labels trace_ends_flag start_status final_status the_trace =
          (clock … final_status) - (clock … start_status) ≝ ?
and compute_max_trace_label_label_pre_cost_is_ok
  (cost_labels: BitVectorTrie Byte 16) (trace_ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label_pre cost_labels trace_ends_flag start_status final_status)
        on the_trace:
          compute_max_trace_label_label_pre_cost cost_labels trace_ends_flag start_status final_status the_trace =
            (clock … final_status) - (clock … start_status) ≝ ?
and compute_max_trace_label_return_cost_is_ok
  (cost_labels: BitVectorTrie Byte 16) (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return cost_labels start_status final_status)
      on the_trace:
        compute_max_trace_label_return_cost cost_labels start_status final_status the_trace =
          (clock … final_status) - (clock … start_status) ≝ ?.
  [1:
    cases the_trace
    #ends_flag #start_status #end_status #label_label_pre_trace
    #labelled_proof
    normalize
    @compute_max_trace_label_label_pre_cost_is_ok
  |3:
    cases the_trace
    [1:
      #status_before #status_after #trace_to_lift
      @compute_max_trace_label_label_cost_is_ok
    |2:
      #status_initial #status_labelled #status_final #labelled_trace #return_trace
      >compute_max_trace_label_return_cost_is_ok %
    ]
  |2: cases the_trace
    [1: #the_status #not_return #not_jump #not_cost
        change in ⊢ (??%?) with (current_instruction_cost the_status);
        @current_instruction_cost_is_ok
    |2: #the_status #is_return
        change in ⊢ (??%?) with (current_instruction_cost the_status);
        @current_instruction_cost_is_ok
    |3: #the_status #is_jump #is_cost
        change in ⊢ (??%?) with (current_instruction_cost the_status);
        @current_instruction_cost_is_ok
    |4: #end_flag #pre_fun_call #after_fun_call #final #is_call
        #next_instruction_coherence #call_trace #final_trace
        change in ⊢ (??%?) with (
          let current_instruction_cost ≝ current_instruction_cost pre_fun_call in
          let call_trace_cost ≝ compute_max_trace_label_return_cost cost_labels … call_trace in
          let final_trace_cost ≝ compute_max_trace_label_label_pre_cost cost_labels end_flag after_fun_call final final_trace in
            call_trace_cost + current_instruction_cost + final_trace_cost)
        normalize nodelta;
        >current_instruction_cost_is_ok
        >compute_max_trace_label_return_cost_is_ok
        >compute_max_trace_label_label_pre_cost_is_ok
        generalize in match next_instruction_coherence;
        change in ⊢ (% → ?) with (
          let size ≝ current_instruction_cost pre_fun_call in
          let pc_before ≝ program_counter … pre_fun_call in
          let pc_after ≝ program_counter … after_fun_call in
          let sum ≝ \snd (half_add … pc_before (bitvector_of_nat … size)) in
            sum = pc_after)
        normalize nodelta;
        >(plus_minus_rearrangement
          (clock (BitVectorTrie Byte 16) after_fun_call)
          (clock (BitVectorTrie Byte 16) (execute 1 pre_fun_call))
          (clock (BitVectorTrie Byte 16) pre_fun_call) ? ?) in ⊢ (??%?);
    |5: #end_flag #status_pre #status_end #tail_trace #is_not_call
        #is_not_jump #is_not_ret #is_not_labelled
        change in ⊢ (??%?) with (
          let current_instruction_cost ≝ current_instruction_cost status_pre in
          let tail_trace_cost ≝ compute_max_trace_label_label_pre_cost cost_labels end_flag (execute 1 status_pre) status_end tail_trace in
            current_instruction_cost + tail_trace_cost)
        normalize nodelta;
        >compute_max_trace_label_label_pre_cost_is_ok
        >current_instruction_cost_is_ok
    ]
  ]
qed.
        
let rec compute_max_trace_label_ret_cost_is_ok
  (cost_labels: BitVectorTrie Byte 16) (start_status: Status) (final_status: Status)
    (the_trace: trace_label_return cost_labels start_status final_status)
      on the_trace:
        compute_max_trace_label_ret_cost cost_labels start_status final_status the_trace =
        (clock … final_status) - (clock … start_status) ≝
  match the_trace with
  [ tlr_base before after trace_to_lift ⇒ ?
  | tlr_step initial pre_fun_call pre_fun_call_trace start_fun_call end_fun_call
      fun_call_trace pre_start_fun_call_coherence ⇒ ?
  ]
and compute_max_trace_label_label_pre_cost_is_ok
  (cost_labels: BitVectorTrie Byte 16) (ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label_pre cost_labels ends_flag start_status final_status)
        on the_trace:
          compute_max_trace_label_label_pre_cost cost_labels ends_flag start_status final_status the_trace =
            (clock … final_status) - (clock … start_status) ≝
  match the_trace with
  [ tllp_base_not_return the_status not_return not_jump not_cost_label ⇒ ?
  | tllp_base_return the_status is_return ⇒ ?
  | tllp_base_jump the_status cost_label is_jump is_cost ⇒ ?
  | tllp_step_call end_flag pre_fun_call start_fun_call end_fun_call after_fun_call final
      fun_call_trace is_call statuses_related pre_start_fun_call_coherence
      end_after_fun_call_coherence after_fun_call_trace ⇒ ?
  | tllp_step_default end_flag start initial end initial_end_trace not_call
      not_jump not_return not_cost ⇒ ?
  ]
and compute_max_trace_label_label_cost_is_ok
  (cost_labels: BitVectorTrie Byte 16) (ends_flag: trace_ends_with_ret)
    (start_status: Status) (final_status: Status)
      (the_trace: trace_label_label cost_labels ends_flag start_status final_status)
        on the_trace:
          compute_max_trace_label_label_cost cost_labels ends_flag start_status final_status the_trace =
            (clock … final_status) - (clock … start_status) ≝
  match the_trace with
  [ tll_base ends_flag initial final given_trace labelled_proof ⇒ ?
  ].
  [8: @(compute_max_trace_label_label_pre_cost_is_ok cost_labels ends_flag initial final given_trace)
  |1: @(compute_max_trace_label_label_cost_is_ok cost_labels ends_with_ret before after trace_to_lift)
  |4: normalize
      @minus_n_n
  |3: normalize
      @minus_n_n
  |5: normalize
      @minus_n_n
  |6: letin fun_call_cost_ok ≝ (compute_max_trace_label_ret_cost_is_ok cost_labels start_fun_call end_fun_call fun_call_trace)
      letin the_trace_cost_ok ≝ (compute_max_trace_label_label_pre_cost_is_ok cost_labels ends_flag start_status final_status the_trace)
  |*:
  ]
qed.
  
lemma compute_max_trace_label_ret_cost_is_ok:
  ∀cost_labels: BitVectorTrie Byte 16.
  ∀start_status: Status.
  ∀final_status: Status.
  ∀the_trace: trace_label_return cost_labels start_status final_status.
    compute_max_trace_label_ret_cost cost_labels start_status final_status the_trace =
      (clock … final_status) - (clock … start_status).
  #COST_LABELS #START_STATUS #FINAL_STATUS #THE_TRACE
  elim THE_TRACE

lemma trace_lab_rec_cost_ok:
 ∀p: trace_lab_rec.
  trace_lab_rec_cost p = Timer (last p) - Timer (first p).

let rec trace_lab_lab_cost_nocall (p: trace_lab_lab) : nat ≝
 match p with
 [ call ⇒ DO NOT ADD ANYTHING
 | _ ⇒ DO ADD ].

let rec trace_lab_rec_cost' (p: trace_lab_ret) : nat.
 | (call b bf tr af tl) as self ⇒
    trace_lab_lab_cost_nocall self + trace_lab_ret_cost' tr +
    trace_lab_rec_cost' tl

theorem main_lemma:
 ∀p. trace_lab_rec_cost p = trace_lab_rec_cost' p.

axiom lemma1:
 ∀p: simple_path.
  traverse_cost_internal (pc (hd p)) … = trace_lab_lab_cost_nocall p.

axiom lemma2:
 ∀s,l,cost_map.
  is_labelled l s →
   traverse_cost_internal s = cost_map l. 

axiom main_statement:
 ∀s.
 ∀cost_map.
 let p ≝ compute_simple_path0 s in
 ∑ (cost_trace p) cost_map = trace_lab_rec_cost' p.

axiom main_statement:
 ∀s.
 ∀cost_map.
 let p ≝ compute_simple_path0 s in
  execute' (path_length p) s = 〈s',τ〉 →
   Timer s' - Timer s = ∑ τ cost_map.