source: src/ASM/CostsProof.ma @ 1693

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

Changes to ASMCosts and CostsProofs? files to get everything working again.

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