rocq/theories/Prefix.v
The first program with an input proved never to panic: rocq/programs/prefix.c, the sum of the first n longs of a read-only global array, for every integer n (PrefixCode.v, checked current by rocq/programs.sh). The loop's index is compared with both n and the array's length, and only the second guards the access.
The statement is Panics.v's never_panics over every runtime, every input word and every fuel. As in Sum.v the proof checks a computed run step by step against abstract memory, but here the input changes the path: each iteration compares the index with n. The proof does not ask which way that comparison goes. It allows both answers at every iteration, so the states it covers are the six runs of prefix_runs (n from 0 to 5), with n itself left abstract in the environment (with_input). Run 5 takes the true answer every time; run k leaves it at the k-th comparison (exit_at), and its states before that are run 5's. Since the access is guarded by the comparison with 4 alone, every one of those states steps safely, whatever n is. Each step is taken by its rule from StepRules.v (Symbolic.v's take_step), with the state's environment and the array's longs supplying its premises.
Decisions
| Decision | Why |
|---|---|
| the comparison with n is over-approximated, both answers allowed | then nothing about n's value is needed beyond its range: the step's comparison is split on n's signed reading and on the answer (split_compares), and n stays a variable throughout |
a state is a run k and an index, with run 5 standing for every run before it leaves (canonical) | the six runs share their beginnings; listing each shared state once keeps the proof to 109 cases |
| the input is any list whose first word is a 32-bit integer word, 0 to 2^32 - 1 | the ABI passes an int as such a word; a pointer there is outside the C type, and extra words are ignored by call_frame. It also lets arithmetic drop the input's remainder modulo 2^32, which no reduction finishes on a variable |
The program
The checked module, decoded from the fixture prefix_term (prefix_decodes).
The fixture decodes to prefix_module.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The function prefix, the module's first item.
The module's globals: the array xs, laid out as in Sum.v, and the function prefix.
The module's initial memory.
Laying out the module succeeds, with prefix_globals and prefix_mem.
Explore proof 3 tactics
Initial goal
assert H : option_mapfst initial_memoryprefix_module = Someprefix_globals by vm_compute ; reflexivity
unfold prefix_mem
destruct initial_memoryprefix_module as g m | ; inversion H ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The genv of the module with any free; the program calls none.
prefix is a function of the core subset in the module.
Explore proof 3 tactics
Initial goal
intros free
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The name of prefix's parameter.
Any arguments whose first word is the integer n start prefix at its entry block with n as its parameter.
Explore proof 1 tactics
The runs
The environment e with the parameter's word replaced by the integer n: a state of a computed run, for the input n.
The run of prefix on the input k, computed by the model on the initial memory.
The runs on the inputs 0 to 5: every way the comparisons with n can go, since the loop stops at the first false one or after four.
Where the run r leaves the loop because the index is not below the input: the first point at the loop's branch with the comparison false; the run's length if there is none.
Index i of run k stands for a state: run 5 stands for every run up to where it leaves, so a run k below 5 is used only from there.
Each step
The four longs of the array in the initial memory, 1 to 4.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Each long the step read from the array, known by Hb that the memory has the initial bytes: the long at its address.
The next state is index S i of run k.
One state of run k: take its point and environment from Hn, take its step by its rule (take_step) with the longs it loads, and find it among the outcomes prefix_progress allows, trying run k first for the next state, then each run.
The states of run k below 5, which start where it leaves run 5 (canonical): five of them, to its return.
Proof 16 steps Qed
Over any runtime
Every machine step from such a state leads to one: a step is to the next index of some run (prefix_progress), never an allocation, and a safepoint keeps the state and mem_ok (Sum.v's mem_ok_safepoint).
Explore proof 19 tactics
Initial goal
intros n st st′ Hs Hin & k & i & pt & e & Hk & Hc & Hn & Hst & Hm
split ; exact Hin |
destruct Hs as c c′ s E | c q k0 s base s′ E _ _ | c s s′ m′ _ Hsp ; cbn [ fst snd ] in Hst , Hm |- * ; change P.program_genvprefix_module prefix_globals with prefix_geR.free in *
3 openfocused goal
focused goal
–rewrite Hst in E
3 opendeferred goal
deferred goal
destruct prefix_progressR.free n k i pt e c_memc c_fuelc Hin Hk Hc Hn Hm as k′ & pt′ & e′ & fuel′ & Hk′ & Hc′ & Hn′ & E′ | E′ | v & E′ ; rewrite E′ in E ; try discriminate
3 opendeferred goal
deferred goal
injection E as ←
3 opendeferred goal
deferred goal
exists k′, Si, pt′, e′
3 opendeferred goal
deferred goal
cbn [ c_mem c_fuel ]
3 opendeferred goal
deferred goal
auto
2 opendeferred goal
deferred goal
–rewrite Hst in E
2 opendeferred goal
destruct prefix_progressR.free n k i pt e c_memc c_fuelc Hin Hk Hc Hn Hm as k′ & pt′ & e′ & fuel′ & Hk′ & Hc′ & Hn′ & E′ | E′ | v & E′ ; rewrite E' in E ; discriminate
deferred goal
–exists k, i, pt, e
rewrite Hst
unfold P.RM.with_mem ; cbn [ c_mem c_fuel c_frame c_callers ]
split ; exact Hk |
split ; exact Hc |
split ; exact Hn |
split ; reflexivity |
eapply S.mem_ok_safepoint ; eauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Every state a run reaches from such a state is one.
Explore proof 3 tactics
Initial goal
intros n st st′ H
induction H as st st′ Hs | st | st1 st2 st3 _ IH1 _ IH2 ; auto
apply prefix_mstep ; assumption
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
No such state fails: its step is to a next state, the end of fuel, or a return.
Explore proof 4 tactics
Initial goal
intros n st Hin & k & i & pt & e & Hk & Hc & Hn & Hst & Hm
rewrite Hst
unfold fails
destruct prefix_progressR.free n k i pt e c_memfstst c_fuelfstst Hin Hk Hc Hn Hm as k′ & pt′ & e′ & fuel′ & _ & _ & _ & E | E | v & E ; change P.program_genvprefix_module prefix_globals with prefix_geR.free ; rewrite E ; simpl ; tauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 16 tactics
Initial goal
exists prefix_globals, prefix_mem, prefix_fn
split ; exact prefix_initial |
split ; apply prefix_find |
intros xs n & rest & → & Hin
eexists
2 opensplit ; apply prefix_call_frame |
intros _ fuel st Hreach
apply prefix_not_failsn
eapply prefix_reachable ; exact Hreach |
split ; exact Hin |
exists 5%nat, O, EnterTAtom"start" None, input_name, WInt5
split ; lia |
split ; left ; reflexivity |
split ; vm_compute ; reflexivity |
split ; reflexivity |
split ; reflexivity | vm_compute ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The theorem for the interpreter's runtime.