Fil-C on Nix

Filnix wiki

the formal campaign

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

DecisionWhy
the run is computed, then each step checked against abstract memorythe 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 auxthe program loads no pointer, so it reads memory only through the array's bounds and bytes
no use of R.readythe program allocates nothing, so readiness, which only governs fresh allocations, plays no part
the input is any argument listsum takes no parameters, and call_frame ignores extra words
From Stdlib Require Import String ZArith List Bool Relations
From Nanofil Require Import Term Syntax Values Memory Runtime Ops Semantics Run Machine Transport Panics SumCode
Import ListNotations
Open Scope Z_scope

The program

The checked module, decoded from the fixture sum_term (sum_decodes).

38Definition sum_module: module ≔
Somemd
⇒
md
None
⇒
[ ]

The fixture decodes to sum_module: the proof is about what nanofil makes of sum.c.

43Lemma sum_decodes
Explore proof 2 tactics

Initial goal

vm_compute

⊢
SomeIFuncfn_name ≔ TAtom"sum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ [ ]; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L2"; b_label ≔ TAtom"L2"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L3", TmpTAtom"v17"; TAtom"start", Const0; PhiTAtom"pr.1" L TAtom"L3", TmpTAtom"v15"; TAtom"start", Const0; b_insts ≔ LetTAtom"v7" W CmpSlt W TmpTAtom"pr.2"; Const4; b_jump ≔ JBranchTmpTAtom"v7" ToTAtom"L3" ToTAtom"L5"; b_label ≔ TAtom"L3"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v9" P Copy GlobalTAtom"xs"; LetTAtom"v11" L ExtSw TmpTAtom"pr.2"; LetTAtom"v12" L Shl TmpTAtom"v11"; Const3; FlightTAtom"v13" Add FAddressTmpTAtom"v9"; FValueTmpTAtom"v12" LowerOfTmpTAtom"v9"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v13"; LetTAtom"v14" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v15" L Add TmpTAtom"pr.1"; TmpTAtom"v14"; LetTAtom"v17" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L2"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JRetTmpTAtom"pr.1"; IDataTAtom"xs" LRoTAtom"local" 8 Str1; 0; 0; 0; 0; 0; 0; 0; 2; 0; 0; 0; 0; 0; 0; 0; 3; 0; 0; 0; 0; 0; 0; 0; 4; 0; 0; 0; 0; 0; 0; 0 = SomeIFuncfn_name ≔ TAtom"sum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ [ ]; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L2"; b_label ≔ TAtom"L2"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L3", TmpTAtom"v17"; TAtom"start", Const0; PhiTAtom"pr.1" L TAtom"L3", TmpTAtom"v15"; TAtom"start", Const0; b_insts ≔ LetTAtom"v7" W CmpSlt W TmpTAtom"pr.2"; Const4; b_jump ≔ JBranchTmpTAtom"v7" ToTAtom"L3" ToTAtom"L5"; b_label ≔ TAtom"L3"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v9" P Copy GlobalTAtom"xs"; LetTAtom"v11" L ExtSw TmpTAtom"pr.2"; LetTAtom"v12" L Shl TmpTAtom"v11"; Const3; FlightTAtom"v13" Add FAddressTmpTAtom"v9"; FValueTmpTAtom"v12" LowerOfTmpTAtom"v9"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v13"; LetTAtom"v14" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v15" L Add TmpTAtom"pr.1"; TmpTAtom"v14"; LetTAtom"v17" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L2"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JRetTmpTAtom"pr.1"; IDataTAtom"xs" LRoTAtom"local" 8 Str1; 0; 0; 0; 0; 0; 0; 0; 2; 0; 0; 0; 0; 0; 0; 0; 3; 0; 0; 0; 0; 0; 0; 0; 4; 0; 0; 0; 0; 0; 0; 0

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity

The function sum, the module's first item.

47Definition sum_fn: func ≔
match sum_module with
IFuncf :: _
⇒
f
_
⇒
mkFuncTAtom"sum" TAtom"export" RClassL [ ] [ ]

The module's globals, each name with its pointer: the array xs and the function sum.

55Definition sum_globals: listname × ptr ≔
TAtom"xs", mkPtr65552 Ro65552; TAtom"sum", mkPtr65536 FnTAtom"sum"

The module's initial memory, as initial_memory/4 lays it out.

59Definition sum_mem: mem ≔
Some_, m
⇒
m
None
⇒

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
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

The genv of the module with any free; the program calls none.

71Definition sum_gefree : word → mem → optionresunit × mem : genv ≔

sum is a function of the core subset in the module.

75Lemma sum_find
∀ free
Explore proof 3 tactics

Initial goal

⊢
∀free : word → mem → optionresunit × mem, find_fnsum_gefree TAtom"sum" = SomeDefinedsum_fn

intros free

free :
word → mem → optionresunit × mem
⊢

vm_compute

free :
word → mem → optionresunit × mem
⊢
SomeDefinedfn_name ≔ TAtom"sum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ [ ]; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L2"; b_label ≔ TAtom"L2"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L3", TmpTAtom"v17"; TAtom"start", Const0; PhiTAtom"pr.1" L TAtom"L3", TmpTAtom"v15"; TAtom"start", Const0; b_insts ≔ LetTAtom"v7" W CmpSlt W TmpTAtom"pr.2"; Const4; b_jump ≔ JBranchTmpTAtom"v7" ToTAtom"L3" ToTAtom"L5"; b_label ≔ TAtom"L3"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v9" P Copy GlobalTAtom"xs"; LetTAtom"v11" L ExtSw TmpTAtom"pr.2"; LetTAtom"v12" L Shl TmpTAtom"v11"; Const3; FlightTAtom"v13" Add FAddressTmpTAtom"v9"; FValueTmpTAtom"v12" LowerOfTmpTAtom"v9"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v13"; LetTAtom"v14" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v15" L Add TmpTAtom"pr.1"; TmpTAtom"v14"; LetTAtom"v17" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L2"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JRetTmpTAtom"pr.1" = SomeDefinedfn_name ≔ TAtom"sum"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ [ ]; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L2"; b_label ≔ TAtom"L2"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L3", TmpTAtom"v17"; TAtom"start", Const0; PhiTAtom"pr.1" L TAtom"L3", TmpTAtom"v15"; TAtom"start", Const0; b_insts ≔ LetTAtom"v7" W CmpSlt W TmpTAtom"pr.2"; Const4; b_jump ≔ JBranchTmpTAtom"v7" ToTAtom"L3" ToTAtom"L5"; b_label ≔ TAtom"L3"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v9" P Copy GlobalTAtom"xs"; LetTAtom"v11" L ExtSw TmpTAtom"pr.2"; LetTAtom"v12" L Shl TmpTAtom"v11"; Const3; FlightTAtom"v13" Add FAddressTmpTAtom"v9"; FValueTmpTAtom"v12" LowerOfTmpTAtom"v9"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v13"; LetTAtom"v14" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v15" L Add TmpTAtom"pr.1"; TmpTAtom"v14"; LetTAtom"v17" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L2"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JRetTmpTAtom"pr.1"

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros free
vm_compute
reflexivity

Any argument list starts sum at its entry block with no temporaries.

80Lemma sum_call_frame
∀ xs
call_framesum_fn xs = SomemkFramesum_fn [ ] [ ] None EnterTAtom"start" None
Explore proof 1 tactics

Initial goal

⊢
∀xs : listword, call_framesum_fn xs = Somefr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
reflexivity

The path

The points and environments of the run in the genv ge from the configuration c, one per step, for at most n steps, until a step is not Next.

89Fixpoint tracege : genv n : nat c : config : listpoint × env ≔
::
match n with
O
⇒
[ ]
Sn′
⇒
match stepge c with
Nextc′
⇒
tracege n′ c′
_
⇒
[ ]

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.

99Definition sum_points: listpoint × env ≔
tracesum_geλ_ _ ⇒ None 200 mkConfigmkFramesum_fn [ ] [ ] None EnterTAtom"start" None [ ] sum_mem 1000

What the program reads of memory

The array xs: 32 bytes of read-only global data.

105Definition xs_region: region ≔

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.

110Definition mem_okm0 m : mem : Prop ≔

The initial memory agrees with itself.

114Lemma mem_ok_initial
Explore proof 1 tactics

Initial goal

split ; reflexivity | vm_compute ; reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
split ; reflexivity | vm_compute ; reflexivity

A load reads only bytes: two memories with the same bytes load the same value.

119Lemma load_bytes_same
∀ m m′ a n
load_bytesm a n = load_bytesm′ a n
Explore proof 4 tactics

Initial goal

⊢
∀m m′ : mem, m_bytesm = m_bytesm′ → ∀a n : Z, load_bytesm a n = load_bytesm′ a n

intros m m′ H a n

m, m′ :
H :
a, n :
Z
⊢
load_bytesm a n = load_bytesm′ a n

unfold load_bytes

m, m′ :
H :
a, n :
Z
⊢
fix go n0 : nat acc : Z {struct n0} : Z ≔
match n0 with
0%nat
⇒
acc
Sn′
⇒
gon′ acc × 256 + m_bytesm a + Z.of_natn′
Z.to_natn 0
=
fix go n0 : nat acc : Z {struct n0} : Z ≔
match n0 with
0%nat
⇒
acc
Sn′
⇒
gon′ acc × 256 + m_bytesm′ a + Z.of_natn′
Z.to_natn 0

rewrite H

m, m′ :
H :
a, n :
Z
⊢
fix go n0 : nat acc : Z {struct n0} : Z ≔
match n0 with
0%nat
⇒
acc
Sn′
⇒
gon′ acc × 256 + m_bytesm′ a + Z.of_natn′
Z.to_natn 0
=
fix go n0 : nat acc : Z {struct n0} : Z ≔
match n0 with
0%nat
⇒
acc
Sn′
⇒
gon′ acc × 256 + m_bytesm′ a + Z.of_natn′
Z.to_natn 0

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros m m′ H a n
unfold load_bytes
rewrite H
reflexivity

Each step of the path

The four longs of the array in the initial memory, 1 to 4.

126Lemma xs0
load_bytessum_mem 65552 8 = 1
Explore proof 2 tactics

Initial goal

⊢
load_bytessum_mem 65552 8 = 1

vm_compute

⊢
1 = 1

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity
127Lemma xs1
load_bytessum_mem 65560 8 = 2
Explore proof 2 tactics

Initial goal

⊢
load_bytessum_mem 65560 8 = 2

vm_compute

⊢
2 = 2

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity
128Lemma xs2
load_bytessum_mem 65568 8 = 3
Explore proof 2 tactics

Initial goal

⊢
load_bytessum_mem 65568 8 = 3

vm_compute

⊢
3 = 3

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity
129Lemma xs3
load_bytessum_mem 65576 8 = 4
Explore proof 2 tactics

Initial goal

⊢
load_bytessum_mem 65576 8 = 4

vm_compute

⊢
4 = 4

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity

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.

138Ltac step_eq Hb Hr fuel ≔
match goal with|- context [step?g ?c]⇒remember stepg c as r eqn: Estep;try (match type of Estep withcontext [Enter_ _]⇒case_eq fuel =? 0 ; introend);cbv beta iota zeta delta - [ object_region m_regions load_bytes sum_mem sum_module Z.eqb ] in Estep;try (match goal withHf : fuel =? 0 = _ |- _⇒rewrite Hf in Estepend);repeat progress cbv beta iota zeta delta - [ object_region m_regions load_bytes sum_mem sum_module ] in Estep ; rewrite ?Hr , ? load_bytes_same_ _ Hb , ?xs0 , ?xs1 , ?xs2 , ?xs3 in Estep;subst rend

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.

152Ltac point_step Hn Hb Hr fuel ≔
cbv in Hn ; injection Hn as ← ← ; step_eq Hb Hr fuel ; first right ; right ; reflexivity | right ; left ; reflexivity | left ; do 3 eexists ; split ; | reflexivity ; reflexivity

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.

162Lemma sum_progress
∀ free n pt e m fuel
nth_errorsum_points n = Somept, e
∃pt′ e′ fuel′, nth_errorsum_points Sn = Somept′, e′ ∧ stepsum_gefree mkConfigmkFramesum_fn e [ ] None pt [ ] m fuel = NextmkConfigmkFramesum_fn e′ [ ] None pt′ [ ] m fuel′ ∨ stepsum_gefree mkConfigmkFramesum_fn e [ ] None pt [ ] m fuel = DoneOutOfFuel ∨ stepsum_gefree mkConfigmkFramesum_fn e [ ] None pt [ ] m fuel = DoneRetWInt10
Proof 7 steps Qed
intros free n pt e m fuel Hn Hb Hr
set pts := sum_points in Hn |- *
vm_compute in pts
set f := sum_fn
vm_compute in f
do 59 destruct n as | n ; point_step Hn Hb Hr fuel |
destruct n ; discriminate

Over any runtime

sum never panics under the runtime R.

180Module SumSafe R : Runtime
181Module P ≔ Panics R

What R does at a safepoint keeps mem_ok: no byte moves (R.non_moving), and the array is still an object (R.rooting) whose bounds only a free of a heap object could empty (R.safepoint_lifetime); it is global data.

187Lemma mem_ok_safepoint
∀ m0 s m s′ m′
R.safepoints m s′ m′
mem_okm0 m
mem_okm0 m′
Explore proof 8 tactics

Initial goal

⊢
∀m0 : mem s : R.state m : mem s′ : R.state m′ : mem, R.safepoints m s′ m′ → mem_okm0 m → mem_okm0 m′

intros m0 s m s′ m′ Hsp Hb Hr

m0 :
s :
R.state
m :
s′ :
R.state
m′ :
Hsp :
R.safepoints m s′ m′
Hb :
⊢
mem_okm0 m′

split

2 open

m0 :
s :
R.state
m :
s′ :
R.state
m′ :
Hsp :
R.safepoints m s′ m′
Hb :
⊢
m_bytesm′ = m_bytesm0
focused goal
m0 :
s :
R.state
m :
s′ :
R.state
m′ :
Hsp :
R.safepoints m s′ m′
Hb :
⊢

–rewrite R.non_moving_ _ _ _ Hsp

2 open

m0 :
s :
R.state
m :
s′ :
R.state
m′ :
Hsp :
R.safepoints m s′ m′
Hb :
⊢
deferred goal
m0 :
s :
R.state
m :
s′ :
R.state
m′ :
Hsp :
R.safepoints m s′ m′
Hb :
⊢

exact Hb

deferred goal
m0 :
s :
R.state
m :
s′ :
R.state
m′ :
Hsp :
R.safepoints m s′ m′
Hb :
⊢

–assert Hold : object_region65552 m_regionsm ≠ None by rewrite Hr ; discriminate

m0 :
s :
R.state
m :
s′ :
R.state
m′ :
Hsp :
R.safepoints m s′ m′
Hb :
Hold :
object_region65552 m_regionsm ≠ None
⊢

pose proof R.rooting_ _ _ _ Hsp 65552 Hold as Hin

m0 :
s :
R.state
m :
s′ :
R.state
m′ :
Hsp :
R.safepoints m s′ m′
Hb :
Hold :
object_region65552 m_regionsm ≠ None
Hin :
object_region65552 m_regionsm′ ≠ None
⊢

destruct object_region65552 m_regionsm′ as reg′ | eqn: E′ ; | contradiction

m0 :
s :
R.state
m :
s′ :
R.state
m′ :
Hsp :
R.safepoints m s′ m′
Hb :
Hold :
object_region65552 m_regionsm ≠ None
reg′ :
E′ :
object_region65552 m_regionsm′ = Somereg′
Hin :
Somereg′ ≠ None
⊢
Somereg′ = Somexs_region

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
intros m0 s m s′ m′ Hsp Hb Hr
split
–rewrite R.non_moving_ _ _ _ Hsp
exact 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

A machine state on the path: its configuration is sum at one of sum_points, with no caller, in a mem_ok memory.

201Definition sum_invst : P.RM.mstate : Prop ≔
∃n pt e, nth_errorsum_points n = Somept, e ∧ fstst = mkConfigmkFramesum_fn e [ ] None pt [ ] c_memfstst c_fuelfstst ∧ mem_oksum_mem c_memfstst

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.

209Lemma sum_mstep
Explore proof 16 tactics

Initial goal

⊢

intros st st′ Hs n & pt & e & Hn & Hc & Hm

st, st′ :
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
fstst = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst
⊢
sum_invst′

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 open

c, c′ :
s :
R.state
E :
stepsum_geR.free c = Nextc′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invc′, s
focused goal
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepsum_geR.free c = Freshq k
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invkbase, s′
focused goal
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢

–rewrite Hc in E

3 open

c, c′ :
s :
R.state
pt :
e :
E :
stepsum_geR.free c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc′
n :
nat
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invc′, s
deferred goal
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepsum_geR.free c = Freshq k
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invkbase, s′
deferred goal
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢

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 open

c, c′ :
s :
R.state
pt :
e :
pt′ :
e′ :
fuel′ :
Z
E :
Nextc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′ = Nextc′
n :
nat
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
Hn′ :
nth_errorsum_points Sn = Somept′, e′
E′ :
stepsum_geR.free c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
⊢
sum_invc′, s
deferred goal
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepsum_geR.free c = Freshq k
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invkbase, s′
deferred goal
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢

injection E as ←

3 open

s :
R.state
pt :
e :
pt′ :
e′ :
fuel′ :
Z
n :
nat
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
Hn′ :
nth_errorsum_points Sn = Somept′, e′
E′ :
stepsum_geR.free c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
⊢
sum_invc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′, s
deferred goal
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepsum_geR.free c = Freshq k
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invkbase, s′
deferred goal
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢

exists Sn, pt′, e′

3 open

s :
R.state
pt :
e :
pt′ :
e′ :
fuel′ :
Z
n :
nat
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
Hn′ :
nth_errorsum_points Sn = Somept′, e′
E′ :
stepsum_geR.free c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
⊢
nth_errorsum_points Sn = Somept′, e′ ∧ fstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′, s = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′, s; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′, s ∧ mem_oksum_mem c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′, s
deferred goal
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepsum_geR.free c = Freshq k
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invkbase, s′
deferred goal
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢

cbn [ c_mem c_fuel ]

3 open

s :
R.state
pt :
e :
pt′ :
e′ :
fuel′ :
Z
n :
nat
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
Hn′ :
nth_errorsum_points Sn = Somept′, e′
E′ :
stepsum_geR.free c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
⊢
nth_errorsum_points Sn = Somept′, e′ ∧ fstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′, s = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′, s; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′, s ∧ mem_oksum_mem c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′, s
deferred goal
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepsum_geR.free c = Freshq k
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invkbase, s′
deferred goal
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢

auto

2 open

deferred goal
k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepsum_geR.free c = Freshq k
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invkbase, s′
deferred goal
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢

–rewrite Hc in E

2 open

k :
Z → config
s :
R.state
base :
Z
s′ :
R.state
pt :
e :
E :
stepsum_geR.free c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Freshq k
n :
nat
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
sum_invkbase, s′
deferred goal
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢

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
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢

–exists n, pt, e

s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
nth_errorsum_points n = Somept, e ∧ fstP.RM.with_memc m′, s′ = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstP.RM.with_memc m′, s′; c_fuel ≔ c_fuelfstP.RM.with_memc m′, s′ ∧ mem_oksum_mem c_memfstP.RM.with_memc m′, s′

rewrite Hc

s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
nth_errorsum_points n = Somept, e ∧ fstP.RM.with_memc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc m′, s′ = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstP.RM.with_memc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc m′, s′; c_fuel ≔ c_fuelfstP.RM.with_memc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc m′, s′ ∧ mem_oksum_mem c_memfstP.RM.with_memc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc m′, s′

unfold P.RM.with_mem ; cbn [ c_mem c_fuel c_frame c_callers ]

s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
nth_errorsum_points n = Somept, e ∧ fstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc, s′ = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc, s′; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc, s′ ∧ mem_oksum_mem c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc, s′

split ; exact Hn |

s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
fstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc, s′ = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc, s′; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc, s′ ∧ mem_oksum_mem c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc, s′

split ; reflexivity |

s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
c = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
mem_oksum_mem c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc, s′

eapply mem_ok_safepoint ; eauto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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 *
–rewrite Hc in E
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
injection E as ←
exists Sn, pt′, e′
cbn [ c_mem c_fuel ]
auto
–rewrite Hc in E
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
–exists n, pt, e
rewrite Hc
split ; exact Hn |
split ; reflexivity |
eapply mem_ok_safepoint ; eauto

Every state a run reaches from a state on the path is on it.

225Lemma sum_reachable
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
intros st st′ H
induction H as st st′ Hs | st | st1 st2 st3 _ IH1 _ IH2 ; auto
apply sum_mstep ; assumption

No state on the path fails: its step is the next point, the end of fuel, or the return of 10.

234Lemma sum_not_fails
Explore proof 4 tactics

Initial goal

intros st n & pt & e & Hn & Hc & Hm

n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
fstst = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst

rewrite Hc

n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
fstst = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst
⊢
¬failsP.program_genvsum_module sum_globals c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst

unfold fails

n :
nat
pt :
e :
Hn :
nth_errorsum_points n = Somept, e
Hc :
fstst = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst
⊢
¬match stepP.program_genvsum_module sum_globals c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst with Next_ ⇒ False | Doneo ⇒ failureo | Freshq _ ⇒ req_extentq < 0 | Stuck_ ⇒ True end

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
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

sum never panics: called with any arguments, under the runtime R, with any fuel, no state of its run fails.

245Theorem sum_never_panics
P.never_panicssum_module TAtom"sum" λ_ ⇒ True
Explore proof 13 tactics

Initial goal

⊢
P.never_panicssum_module TAtom"sum" λ_ : listword ⇒ True

exists sum_globals, sum_mem, sum_fn

⊢
initial_memorysum_module = Somesum_globals, sum_mem ∧ find_fnP.program_genvsum_module sum_globals TAtom"sum" = SomeDefinedsum_fn ∧ ∀xs : listword, True → ∃fr : frame, call_framesum_fn xs = Somefr ∧ R.readyR.start sum_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvsum_module sum_globals fstst

split ; exact sum_initial |

⊢
find_fnP.program_genvsum_module sum_globals TAtom"sum" = SomeDefinedsum_fn ∧ ∀xs : listword, True → ∃fr : frame, call_framesum_fn xs = Somefr ∧ R.readyR.start sum_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvsum_module sum_globals fstst

split ; apply sum_find |

⊢
∀xs : listword, True → ∃fr : frame, call_framesum_fn xs = Somefr ∧ R.readyR.start sum_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvsum_module sum_globals fstst

intros xs _

xs :
listword
⊢
∃fr : frame, call_framesum_fn xs = Somefr ∧ R.readyR.start sum_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvsum_module sum_globals fstst

eexists

2 open

xs :
listword
⊢
call_framesum_fn xs = Some?fr ∧ R.readyR.start sum_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ ?fr; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvsum_module sum_globals fstst
shelved goal
xs :
listword

split ; apply sum_call_frame |

xs :
listword
⊢
R.readyR.start sum_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvsum_module sum_globals fstst

intros _ fuel st Hreach

xs :
listword
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st

apply sum_not_fails

xs :
listword
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st
⊢

eapply sum_reachable ; exact Hreach |

xs :
listword
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st
⊢
sum_invc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start

exists O, EnterTAtom"start" None, [ ]

xs :
listword
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st
⊢
nth_errorsum_points 0 = SomeEnterTAtom"start" None, [ ] ∧ fstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start ∧ mem_oksum_mem c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start

split ; reflexivity |

xs :
listword
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st
⊢
fstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start = c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start ∧ mem_oksum_mem c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start

split ; reflexivity |

xs :
listword
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvsum_module sum_globals c_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start st
⊢
mem_oksum_mem c_memfstc_frame ≔ fr_fn ≔ sum_fn; fr_env ≔ [ ]; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ sum_mem; c_fuel ≔ fuel, R.start

exact mem_ok_initial

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
split ; exact sum_initial |
split ; apply sum_find |
intros xs _
eexists
split ; apply sum_call_frame |
intros _ fuel st Hreach
eapply sum_reachable ; exact Hreach |
exists O, EnterTAtom"start" None, [ ]
split ; reflexivity |
split ; reflexivity |

The theorem for the interpreter's runtime.

257Module InterpSum ≔ SumSafe InterpRuntime