rocq/theories/Sum.v
The first program proved never to panic: rocq/programs/sum.c, a loop that sums a read-only global array of four longs, as nanofil -O compiles it (SumCode.v, checked current by rocq/programs.sh). Step 1 of formal.md's quest: a closed module, with no input and no external call.
The statement is Panics.v's never_panics over every runtime R, every argument list and every fuel: no state a run reaches fails. The proof is a symbolic execution of the one path the program has. The run on the module's initial memory is computed once by the model's own step (sum_points, 59 states); then sum_progress shows that from each of those states, in any memory that agrees with the initial one on what the program reads (mem_ok), the step is the next state of the list, the last return, or the end of fuel. A safepoint may change the memory, but mem_ok_safepoint shows it keeps mem_ok, by Runtime.v's axioms: the array is global data, which no free empties, and no byte moves.
Decisions
| Decision | Why |
|---|---|
| the run is computed, then each step checked against abstract memory | the computed list is only a guess the proof checks; the memory and fuel stay universally quantified, so nothing about one runtime's placement is assumed |
mem_ok tracks the bytes and the array's region, not the aux | the program loads no pointer, so it reads memory only through the array's bounds and bytes |
no use of R.ready | the program allocates nothing, so readiness, which only governs fresh allocations, plays no part |
| the input is any argument list | sum takes no parameters, and call_frame ignores extra words |
The program
The checked module, decoded from the fixture sum_term (sum_decodes).
The fixture decodes to sum_module: the proof is about what nanofil makes of sum.c.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The function sum, the module's first item.
The module's globals, each name with its pointer: the array xs and the function sum.
The module's initial memory, as initial_memory/4 lays it out.
Laying out the module succeeds, with sum_globals and sum_mem.
Explore proof 3 tactics
Initial goal
assert H : option_mapfst initial_memorysum_module = Somesum_globals by vm_compute ; reflexivity
unfold sum_mem
destruct initial_memorysum_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.
sum 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
Any argument list starts sum at its entry block with no temporaries.
Explore proof 1 tactics
The path
The one path of sum, computed by running the model on the initial memory: 59 points, ending at the return of 10. The proof does not trust it; sum_progress checks every step.
What the program reads of memory
The array xs: 32 bytes of read-only global data.
The memory m agrees with the initial memory m0 on everything a program that only reads the array reads: the bytes, and the array's region.
The initial memory agrees with itself.
Explore proof 1 tactics
A load reads only bytes: two memories with the same bytes load the same value.
Explore proof 4 tactics
Initial goal
intros m m′ H a n
unfold load_bytes
rewrite H
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Each step of the path
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
Compute the step in the goal for a memory known only by Hb and Hr and the fuel: at a block's entry, which tests the fuel, split on whether fuel is left, and rewrite that test first, before the arithmetic it guards is unfolded; then reduce the step without unfolding the memory's regions, loads or the initial memory, and rewrite what the reduction is stuck on (the array's region, its loads), again until nothing changes.
One point of the path: take its point and environment from Hn, compute the step, and find it among the three outcomes sum_progress allows.
From the n-th point of the path, in any memory m that is mem_ok and with any fuel, sum steps to the next point with the same memory, ends for lack of fuel, or returns 10.
Proof 7 steps Qed
Over any runtime
sum never panics under the runtime R.
Explore proof 8 tactics
Initial goal
intros m0 s m s′ m′ Hsp Hb Hr
split
2 open–rewrite R.non_moving_ _ _ _ Hsp
2 openexact Hb
–assert Hold : object_region65552 m_regionsm ≠ None by rewrite Hr ; discriminate
pose proof R.rooting_ _ _ _ Hsp 65552 Hold as Hin
destruct object_region65552 m_regionsm′ as reg′ | eqn: E′ ; | contradiction
destruct R.safepoint_lifetime_ _ _ _ Hsp _ _ E′ as reg & Hreg & → | Hk & _ ; rewrite Hr in Hreg ; injection Hreg as ← ; reflexivity | discriminate Hk
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A machine state on the path: its configuration is sum at one of sum_points, with no caller, in a mem_ok memory.
Every machine step from a state on the path stays on it: a step is the next point (sum_progress), never an allocation, and a safepoint keeps the point and mem_ok.
Explore proof 16 tactics
Initial goal
intros st st′ Hs n & pt & e & Hn & Hc & Hm
destruct Hs as c c′ s E | c q k s base s′ E _ _ | c s s′ m′ _ Hsp ; cbn [ fst snd ] in Hc , Hm |- * ; change P.program_genvsum_module sum_globals with sum_geR.free in *
3 openfocused goal
focused goal
–rewrite Hc in E
3 opendeferred goal
deferred goal
destruct sum_progressR.free n pt e c_memc c_fuelc Hn Hm as pt′ & e′ & fuel′ & Hn′ & E′ | E′ | E′ ; rewrite E′ in E ; try discriminate
3 opendeferred goal
deferred goal
injection E as ←
3 opendeferred goal
deferred goal
exists Sn, pt′, e′
3 opendeferred goal
deferred goal
cbn [ c_mem c_fuel ]
3 opendeferred goal
deferred goal
auto
2 opendeferred goal
deferred goal
–rewrite Hc in E
2 opendeferred goal
destruct sum_progressR.free n pt e c_memc c_fuelc Hn Hm as pt′ & e′ & fuel′ & Hn′ & E′ | E′ | E′ ; rewrite E' in E ; discriminate
deferred goal
–exists n, pt, e
rewrite Hc
unfold P.RM.with_mem ; cbn [ c_mem c_fuel c_frame c_callers ]
split ; exact Hn |
split ; reflexivity |
eapply mem_ok_safepoint ; eauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Every state a run reaches from a state on the path is on it.
Explore proof 3 tactics
Initial goal
intros st st′ H
induction H as st st′ Hs | st | st1 st2 st3 _ IH1 _ IH2 ; auto
apply sum_mstep ; assumption
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
No state on the path fails: its step is the next point, the end of fuel, or the return of 10.
Explore proof 4 tactics
Initial goal
intros st n & pt & e & Hn & Hc & Hm
rewrite Hc
unfold fails
destruct sum_progressR.free n pt e c_memfstst c_fuelfstst Hn Hm as pt′ & e′ & fuel′ & _ & E | E | E ; change P.program_genvsum_module sum_globals with sum_geR.free ; rewrite E ; simpl ; tauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
sum never panics: called with any arguments, under the runtime R, with any fuel, no state of its run fails.
Explore proof 13 tactics
Initial goal
exists sum_globals, sum_mem, sum_fn
split ; exact sum_initial |
split ; apply sum_find |
intros xs _
eexists
2 opensplit ; apply sum_call_frame |
intros _ fuel st Hreach
apply sum_not_fails
eapply sum_reachable ; exact Hreach |
exists O, EnterTAtom"start" None, [ ]
split ; reflexivity |
split ; reflexivity |
exact mem_ok_initial
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The theorem for the interpreter's runtime.