rocq/spikes/SepListSum.v
The listsum spike proved with the hand-rolled separation logic of Sep.v (docs/logic.md): spikes/listsum.c never panics, with no premise, under any runtime, the interpreter's among them.
The proof is Buffer.v's: an assertion at each point of each function, one step from a configuration where it holds is safe_step, and a safepoint keeps it; Panics.v's never_panics_by_invariant turns that into never_panics. What is new is the shape of the assertions. Each is facts about the temporaries and a separation-logic assertion on the memory, and sum has a specification of its own with a frame: from the list lst p xs and any frame F it walks the list, dropping each node it has passed into htrue, and returns an integer with htrue and F still there (sum_step). listsum builds the list one fresh node at a time and calls sum with the empty frame, suspended on the callers' stack.
The configuration invariant ls_inv adds the one fact about the whole memory, live_disjoint: either listsum runs with no caller, or sum runs with listsum suspended after its call. A safepoint (R.at_safepoint is abstract, so one may be due before any instruction that is not evidence-preserving, and at each poll edge) keeps every assertion: it changes no region (collector_live) and no byte, and changes an aux slot only where a freed object's capability is stored, which no list does (sum_safepoint, ls_safepoint).
Integer arithmetic on an unknown stays folded when a step is computed (Symbolic.v).
Computing a step over memory the assertions describe
A pointer is its two fields.
Explore proof 2 tactics
Source script
Rewrite in E every alignment test of an address the context proves 8-aligned to its answer, before drop_wraps would turn the remainder into an unknown.
Rewrite in E the facts about memory and the module a step reads besides Symbolic.v's: a node's next slot, as bytes and as aux, a function found by name, a callee's frame, and a pointer rebuilt from its fields.
Compute E, an equation r = step g c, as Symbolic.v's compute_step does, with stores and aux kept folded, offsets of 0 dropped, and the facts above.
sum
The function sum.
Every point of sum, numbered: the entry start (0, 1); the loop's head L3, entered from start or from the body (2, 3), before its two instructions and its branch (4 to 6); the body L4, entered (7), then before each of its six instructions and its jump back, which polls (8 to 14); and the exit L5 (15, 16).
At the loop's head, after its first j instructions: the list from pr.1, the sum pr.2 an integer, the walked nodes in htrue, and the frame F; then v7, the list's address, and v8, whether it is not null.
In the body, after its first j instructions: the node at a, its value v and next pointer next, the rest xs; then the pointer v11 to the value and its checked proof chk0, the value v12, the new sum v13, the half-checked node pointer chk1, and the next pointer v15.
What holds at point k of sum_points with the frame F: at the entry, the precondition, the list from the parameter v0 and F; on the edge back, the loop's state in v15 and v13; at the head, sum_head; in the body, sum_body; at the exit, the postcondition, the sum an integer, and htrue and F.
A configuration running sum with the frame F and the callers callers below it: at point k, with no locals and no doom, where the assertion of k holds.
Facts the steps read from the assertions
A list's address is 0 or inside the address space.
Explore proof 3 tactics
Initial goal
intros p xs R S m Hfit H
destruct star_elim_l_ _ _ _ H as S1 & H1
exact lst_range_ _ _ _ Hfit H1
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
What a node of the list at a gives the steps that read it.
Explore proof 4 tactics
Initial goal
intros a v next xs R S m Hfit H
destruct lst_cons_facts_ _ _ _ _ _ _ Hfit H as a′ & E & Hr
injection E as ←
exact Hr
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Add to the context what the separation-logic facts H give a step: a list's address range, and a node's region and next slot.
sum's step
The point of the next configuration is point n of sum_points or a later one.
Turn the separation-logic hypotheses into what the next point's assertion needs: htrue added at the loop's entry; the list dropped into it at the exit; at a nonnull list, its first node, its pointer taken apart; after the body, the walked node dropped.
The next configuration runs sum at its point, with the same callers and frame and the memory unchanged.
One point of sum_step: the point from Hk, the assertion Ha taken apart with what it gives about memory, the step computed, and its result shown safe.
sum's specification, as one step: from any configuration running sum where its assertion holds with the frame F, under any callers, the step returns an integer to the caller with htrue and F holding, or is safe_step into such a configuration with the same callers and frame, the memory unchanged. Any frame: sum never writes, and a frame need survive only safepoints (sum_safepoint).
Explore proof 29 tactics
Initial goal
intros ge F callers c Hfit k & pt & e & Ec & Hk & Ha
rewrite Ec
clear Ec
cbn [ c_mem ] in Hfit |- *
set m := c_memc in *
set fuel := c_fuelc in *
clearbody m fuel
set pts := sum_points in Hk
vm_compute in pts
remember sum_fn as f eqn: Hf
block_fact f sum_fn Hf TAtom"start" b0 Hb0
block_fact f sum_fn Hf TAtom"L3" b3 Hb3
block_fact f sum_fn Hf TAtom"L4" b4 Hb4
block_fact f sum_fn Hf TAtom"L5" b5 Hb5
assert Hret : fn_retf = RClassL by rewrite Hf ; reflexivity
do 16 destruct k as | k ; right ; sum_point pts Hk Ha Hfit |
destruct k as | k ; left | destruct k ; discriminate Hk
cbv in Hk
injection Hk as ←
clear pts
cbn [ sum_assert ] in Ha
destruct Ha as s & Hs & S & HS
exists s mod 2 ^ 64, S
split ; | exact HS
cbn - [ return_step ]
rewrite Hret
cbn - [ return_step ]
rewrite Hs
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Safepoints in sum
What survives a safepoint holds after it.
Explore proof 2 tactics
Initial goal
intros P S m m′ HP H Hr Hb Ha
exact HPS m m′ H Hr Hb Ha
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Move every separation-logic hypothesis about the memory m to the memory m' after a safepoint.
The poll on the back edge leaves the list alone: a safepoint keeps the assertion at every point of sum, for any frame that survives it. The environment and the point do not change; the memory changes only as safepoint_shape allows, which every assertion survives (lst_safepoint).
Explore proof 11 tactics
Initial goal
intros F callers c m′ HF k & pt & e & Ec & Hk & Ha Hr Hb Hx
exists k, pt, e
split ; rewrite Ec ; reflexivity |
cbn [ c_mem ]
split ; exact Hk |
set m := c_memc in *
clearbody m
assert Hlt : k < lengthsum_points%nat by apply nth_error_Some ; rewrite Hk ; discriminate
vm_compute in Hlt
do 17 destruct k as | k ; cbn [ sum_assert Nat.sub ] in Ha |- * ; try unfold sum_head in Ha |- * ; try unfold sum_body in Ha |- * ; cbn [ Nat.leb Nat.eqb ] in Ha |- * ; unfold int_at in * ; facts ; sp_hyps m m′ HF Hr Hb Hx ; show_facts ; eassumption |
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
listsum
The function listsum.
Every point of listsum, numbered: the entry start (0, 1); the loop's head L4, entered from start or from the body (2, 3), its comparison and its branch (4, 5); the body L5, entered (6), then before each of its eight instructions and its jump back, which polls (7 to 15); the exit L7, entered (16), before its call of sum (17) and before its return (18).
In the loop, after the first j instructions of the body: the list built so far from pr.1, the index pr.2 an integer; then, from the allocation on, the new node at b, from v12, at first with a null next pointer and the value 0, its checked proof chk0, after the pointer store with the list for its next pointer, the pointer v16 to its value and the long v18 to store there, its half-checked proof chk1, after the store any value, and the next index v21.
A configuration running listsum with no caller: at point k, with no locals and no doom, the input v0 an integer, and the assertion of k.
listsum suspended in its call of sum, with the environment e: it resumes before its return, reading the result into v23.
The configuration invariant: live objects do not overlap, and either listsum runs with no caller, or sum runs, with the empty frame, above listsum suspended in its call.
Facts listsum's steps read
sum is the module's function of that name.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The point listsum resumes at after its call.
Explore proof 2 tactics
The initial memory holds no object.
Explore proof 2 tactics
A node's region, inside the address space.
Explore proof 7 tactics
Initial goal
intros b x v R S m Hfit H
destruct star_elim_l_ _ _ _ H as S1 & H1
pose proof node_region_ _ _ _ _ H1 as Hr
split ; exact Hr |
destruct Hfit_ _ Hr
cbn in *
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The list after a node is 0 or inside the address space.
Explore proof 4 tactics
Initial goal
intros b x v h xs S m Hfit H
destruct star_elim_r_ _ _ _ H as S2 & H2
pose proof lst_range_ _ _ _ Hfit H2
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A fresh node's base is positive, 16-aligned, and ends at or below 2^64.
Explore proof 3 tactics
Initial goal
intros m b H0 & H1 & H2 & _
cbn in *
auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A node at a 16-aligned address and the rest make a list.
Explore proof 4 tactics
Initial goal
intros b h v xs S m Hb Hm
apply lst_cons_intro ; exact Hb |
Z.to_euclidean_division_equations
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The step from sum's return into listsum, resumed with the result in v23.
Explore proof 4 tactics
Initial goal
intros f e0 l d p e x m fuel H
cbn in H
subst l
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 6 tactics
Initial goal
intros I J m r H Hs
destruct r as c | o | q k | why ; cbn in * ; auto
destruct Hs as He Hk
split ; exact He |
intros base Hf
apply H , Hk , Hf
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Add to the context the region of a node the assertion owns.
The point of the next configuration is point n of ls_points or a later one.
Turn the separation-logic hypotheses into what the next point's assertion needs, from the memory the next configuration has: the empty list at the loop's entry; the new node beside the list after the allocation; the node's next slot after the pointer store, and its value after the store of the long; the list one longer on the edge back; the empty frame at the call.
The memory after the step keeps live objects apart: it is the same, a store's, or an allocation's at a fresh base.
The next configuration is in ls_inv: listsum at its point, or, after the call, sum at its entry with listsum suspended.
One point of ls_here_safe: as sum_point.
Explore proof 21 tactics
Initial goal
intros ge c Hfd Hd Hfit k & pt & e & Ec & Hk & Hv0 & Ha
rewrite Ec
clear Ec
cbn [ c_mem ] in *
set m := c_memc in *
set fuel := c_fuelc in *
clearbody m fuel
set pts := ls_points in Hk
vm_compute in pts
remember listsum_fn as f eqn: Hf
remember sum_fn as fs eqn: Hfs in Hfd |- *
assert Hff : find_fnge TAtom"sum" = SomeDefinedfs by unfold find_fn ; rewrite Hfd ; reflexivity
clear Hfd
assert Hcf : ∀x rest, call_framefs x :: rest = SomemkFramefs TAtom"v0", x [ ] None EnterTAtom"start" None by subst fs ; exact sum_call_frame
block_fact f listsum_fn Hf TAtom"start" b0 Hb0
block_fact f listsum_fn Hf TAtom"L4" b4 Hb4
block_fact f listsum_fn Hf TAtom"L5" b5 Hb5
block_fact f listsum_fn Hf TAtom"L7" b7 Hb7
assert Hret : fn_retf = RClassL by rewrite Hf ; reflexivity
do 19 destruct k as | k ; ls_point pts Hk Ha Hfit Hd |
destruct k ; discriminate Hk
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 22 tactics
Initial goal
intros ge c Hfd Hd Hh | e & Hs & Hv0 Hfit
2 open–exact ls_here_safege c Hfd Hd Hfit Hh
–destruct sum_stepge emp _ c Hfit Hs as x & S & E & _ | Hsafe
2 openfocused goal
+rewrite E
2 opendeferred goal
destruct Hs as k & pt & e′ & Ec & _
2 opendeferred goal
rewrite Ec , return_to_listsum by reflexivity
2 opendeferred goal
cbn [ safe_step ]
2 opendeferred goal
split ; exact Hd |
2 opendeferred goal
left
2 opendeferred goal
unfold int_at in Hv0
2 opendeferred goal
destruct Hv0 as n & Hn & _
2 opendeferred goal
exists 18%nat, ExecTAtom"L7" [ ] JRetTmpTAtom"v23", putTAtom"v23" WIntx mod 2 ^ 64 e
2 opendeferred goal
split ; reflexivity |
2 opendeferred goal
split ; vm_compute ; reflexivity |
2 opendeferred goal
split ; show_facts | cbn [ ls_assert ] ; show_facts
deferred goal
+revert Hsafe
apply safe_step_mono
intros c′ Hc′ Em
split ; rewrite Em ; exact Hd |
right
exists e
split ; assumption
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The poll on the back edge leaves the list alone: a safepoint keeps ls_inv, given that it keeps live objects apart, for listsum's points as for sum's (sum_safepoint).
Explore proof 18 tactics
Initial goal
intros c m′ _ Hh | e & Hs & Hv0 Hd′ Hr Hb Hx ; split ; exact Hd′ | | exact Hd′ |
2 openfocused goal
–left
2 opendeferred goal
destruct Hh as k & pt & e & Ec & Hk & Hv0 & Ha
2 opendeferred goal
exists k, pt, e
2 opendeferred goal
split ; rewrite Ec ; reflexivity |
2 opendeferred goal
split ; exact Hk |
2 opendeferred goal
split ; exact Hv0 |
2 opendeferred goal
cbn [ c_mem ]
2 opendeferred goal
set m := c_memc in *
2 opendeferred goal
clearbody m
2 opendeferred goal
assert Hlt : k < lengthls_points%nat by apply nth_error_Some ; rewrite Hk ; discriminate
2 opendeferred goal
vm_compute in Hlt
2 opendeferred goal
do 19 (destruct k as | k;)
2 opendeferred goal
lia
deferred goal
–right
exists e
split ; | exact Hv0
exact sum_safepointemp _ c m′ emp_sp_stable Hs Hr Hb Hx
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A call with an integer first argument starts where ls_inv holds, with any fuel: the initial memory holds no object.
Explore proof 11 tactics
Initial goal
intros n fuel
split
2 openfocused goal
–intros b1 r1 b2 r2 E _
2 opendeferred goal
cbn [ c_mem ] in E
2 opendeferred goal
rewrite ls_mem_regions in E
2 opendeferred goal
discriminate
deferred goal
–left
exists O, EnterTAtom"start" None, TAtom"v0", WIntn
split ; reflexivity |
split ; vm_compute ; reflexivity |
split ; exists n ; split ; reflexivity | exact I | exact I
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Over any runtime
listsum.c never panics under the runtime R.
Panics.v's property over R.
What a safepoint of R does (Pieces.v).
listsum.c never panics: for every input whose first word is an integer, with any fuel, no state of its run fails, wherever its nodes are placed.
Explore proof 13 tactics
Initial goal
apply P.never_panics_by_invariant_ _ _ ls_globals ls_mem listsum_fn ls_inv
5 openfocused goal
focused goal
focused goal
focused goal
–exact ls_initial
4 opendeferred goal
deferred goal
deferred goal
deferred goal
–apply ls_find_listsum
3 opendeferred goal
deferred goal
deferred goal
–intros xs n & rest & →
3 opendeferred goal
deferred goal
eexists
4 opendeferred goal
deferred goal
split ; apply listsum_call_frame |
3 opendeferred goal
deferred goal
intros fuel
3 opendeferred goal
deferred goal
apply ls_start
2 opendeferred goal
deferred goal
–intros c s Hc Hr
2 opendeferred goal
apply ls_safe ; exact ls_find_direct_sum | exact Hc | exact R.address_space_ _ Hr
deferred goal
–intros c s s′ m′ Hc _ _ Hsp
destruct SS.safepoint_shape_ _ _ _ Hsp as Hr & Hb & Ha
exact ls_safepointc m′ Hc SS.live_disjoint_safepoint_ _ _ _ Hsp proj1Hc Hr Hb Ha
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The theorem for the interpreter's runtime.
listsum.c never panics under the interpreter's runtime.
Explore proof 1 tactics
Initial goal
exact InterpSepListSum.listsum_never_panics
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.