Fil-C on Nix

Filnix wiki

the formal campaign

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

DecisionWhy
the comparison with n is over-approximated, both answers allowedthen 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 - 1the 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
From Stdlib Require Import String ZArith List Bool Lia Relations
From Nanofil Require Import Term Syntax Values Memory Runtime Ops Semantics Run Machine Transport Panics Symbolic PrefixCode Sum
Import ListNotations
Open Scope Z_scope

The program

The checked module, decoded from the fixture prefix_term (prefix_decodes).

40Definition prefix_module: module ≔
Somemd
⇒
md
None
⇒
[ ]

The fixture decodes to prefix_module.

44Lemma prefix_decodes
Explore proof 2 tactics

Initial goal

vm_compute

⊢
SomeIFuncfn_name ≔ TAtom"prefix"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ W, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L4"; b_label ≔ TAtom"L4"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L5", TmpTAtom"v26"; TAtom"start", Const0; PhiTAtom"pr.1" L TAtom"L5", TmpTAtom"v24"; TAtom"start", Const0; b_insts ≔ LetTAtom"v10" W CmpSlt W TmpTAtom"pr.2"; TmpTAtom"v0"; b_jump ≔ JBranchTmpTAtom"v10" ToTAtom"L11" ToTAtom"L12"; b_label ≔ TAtom"L11"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v14" W CmpSlt W TmpTAtom"pr.2"; Const4; b_jump ≔ JGotoToTAtom"L12"; b_label ≔ TAtom"L12"; b_phis ≔ PhiTAtom"v16" W TAtom"L4", Const0; TAtom"L11", TmpTAtom"v14"; b_insts ≔ [ ]; b_jump ≔ JBranchTmpTAtom"v16" ToTAtom"L5" ToTAtom"L7"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v18" P Copy GlobalTAtom"xs"; LetTAtom"v20" L ExtSw TmpTAtom"pr.2"; LetTAtom"v21" L Shl TmpTAtom"v20"; Const3; FlightTAtom"v22" Add FAddressTmpTAtom"v18"; FValueTmpTAtom"v21" LowerOfTmpTAtom"v18"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v22"; LetTAtom"v23" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v24" L Add TmpTAtom"pr.1"; TmpTAtom"v23"; LetTAtom"v26" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L4"; b_label ≔ TAtom"L7"; 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"prefix"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ W, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L4"; b_label ≔ TAtom"L4"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L5", TmpTAtom"v26"; TAtom"start", Const0; PhiTAtom"pr.1" L TAtom"L5", TmpTAtom"v24"; TAtom"start", Const0; b_insts ≔ LetTAtom"v10" W CmpSlt W TmpTAtom"pr.2"; TmpTAtom"v0"; b_jump ≔ JBranchTmpTAtom"v10" ToTAtom"L11" ToTAtom"L12"; b_label ≔ TAtom"L11"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v14" W CmpSlt W TmpTAtom"pr.2"; Const4; b_jump ≔ JGotoToTAtom"L12"; b_label ≔ TAtom"L12"; b_phis ≔ PhiTAtom"v16" W TAtom"L4", Const0; TAtom"L11", TmpTAtom"v14"; b_insts ≔ [ ]; b_jump ≔ JBranchTmpTAtom"v16" ToTAtom"L5" ToTAtom"L7"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v18" P Copy GlobalTAtom"xs"; LetTAtom"v20" L ExtSw TmpTAtom"pr.2"; LetTAtom"v21" L Shl TmpTAtom"v20"; Const3; FlightTAtom"v22" Add FAddressTmpTAtom"v18"; FValueTmpTAtom"v21" LowerOfTmpTAtom"v18"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v22"; LetTAtom"v23" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v24" L Add TmpTAtom"pr.1"; TmpTAtom"v23"; LetTAtom"v26" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L4"; b_label ≔ TAtom"L7"; 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 prefix, the module's first item.

48Definition prefix_fn: func ≔
match prefix_module with
IFuncf :: _
⇒
f
_
⇒
mkFuncTAtom"prefix" TAtom"export" RClassL [ ] [ ]

The module's globals: the array xs, laid out as in Sum.v, and the function prefix.

56Definition prefix_globals: listname × ptr ≔
TAtom"xs", mkPtr65552 Ro65552; TAtom"prefix", mkPtr65536 FnTAtom"prefix"

The module's initial memory.

60Definition prefix_mem: mem ≔
Some_, m
⇒
m
None
⇒

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

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

73Definition prefix_gefree : word → mem → optionresunit × mem : genv ≔

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

77Lemma prefix_find
∀ free
Explore proof 3 tactics

Initial goal

⊢
∀free : word → mem → optionresunit × mem, find_fnprefix_gefree TAtom"prefix" = SomeDefinedprefix_fn

intros free

free :
word → mem → optionresunit × mem

vm_compute

free :
word → mem → optionresunit × mem
⊢
SomeDefinedfn_name ≔ TAtom"prefix"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ W, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L4"; b_label ≔ TAtom"L4"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L5", TmpTAtom"v26"; TAtom"start", Const0; PhiTAtom"pr.1" L TAtom"L5", TmpTAtom"v24"; TAtom"start", Const0; b_insts ≔ LetTAtom"v10" W CmpSlt W TmpTAtom"pr.2"; TmpTAtom"v0"; b_jump ≔ JBranchTmpTAtom"v10" ToTAtom"L11" ToTAtom"L12"; b_label ≔ TAtom"L11"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v14" W CmpSlt W TmpTAtom"pr.2"; Const4; b_jump ≔ JGotoToTAtom"L12"; b_label ≔ TAtom"L12"; b_phis ≔ PhiTAtom"v16" W TAtom"L4", Const0; TAtom"L11", TmpTAtom"v14"; b_insts ≔ [ ]; b_jump ≔ JBranchTmpTAtom"v16" ToTAtom"L5" ToTAtom"L7"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v18" P Copy GlobalTAtom"xs"; LetTAtom"v20" L ExtSw TmpTAtom"pr.2"; LetTAtom"v21" L Shl TmpTAtom"v20"; Const3; FlightTAtom"v22" Add FAddressTmpTAtom"v18"; FValueTmpTAtom"v21" LowerOfTmpTAtom"v18"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v22"; LetTAtom"v23" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v24" L Add TmpTAtom"pr.1"; TmpTAtom"v23"; LetTAtom"v26" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L4"; b_label ≔ TAtom"L7"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JRetTmpTAtom"pr.1" = SomeDefinedfn_name ≔ TAtom"prefix"; fn_linkage ≔ TAtom"export"; fn_ret ≔ RClassL; fn_params ≔ W, TAtom"v0"; fn_blocks ≔ b_label ≔ TAtom"start"; b_phis ≔ [ ]; b_insts ≔ [ ]; b_jump ≔ JGotoToTAtom"L4"; b_label ≔ TAtom"L4"; b_phis ≔ PhiTAtom"pr.2" W TAtom"L5", TmpTAtom"v26"; TAtom"start", Const0; PhiTAtom"pr.1" L TAtom"L5", TmpTAtom"v24"; TAtom"start", Const0; b_insts ≔ LetTAtom"v10" W CmpSlt W TmpTAtom"pr.2"; TmpTAtom"v0"; b_jump ≔ JBranchTmpTAtom"v10" ToTAtom"L11" ToTAtom"L12"; b_label ≔ TAtom"L11"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v14" W CmpSlt W TmpTAtom"pr.2"; Const4; b_jump ≔ JGotoToTAtom"L12"; b_label ≔ TAtom"L12"; b_phis ≔ PhiTAtom"v16" W TAtom"L4", Const0; TAtom"L11", TmpTAtom"v14"; b_insts ≔ [ ]; b_jump ≔ JBranchTmpTAtom"v16" ToTAtom"L5" ToTAtom"L7"; b_label ≔ TAtom"L5"; b_phis ≔ [ ]; b_insts ≔ LetTAtom"v18" P Copy GlobalTAtom"xs"; LetTAtom"v20" L ExtSw TmpTAtom"pr.2"; LetTAtom"v21" L Shl TmpTAtom"v20"; Const3; FlightTAtom"v22" Add FAddressTmpTAtom"v18"; FValueTmpTAtom"v21" LowerOfTmpTAtom"v18"; LetTAtom"chk0" A Check0 8 Read 1 TmpTAtom"v22"; LetTAtom"v23" L RawLoadLdL 0 TmpTAtom"chk0"; LetTAtom"v24" L Add TmpTAtom"pr.1"; TmpTAtom"v23"; LetTAtom"v26" W Add TmpTAtom"pr.2"; Const1; b_jump ≔ JGotoPollTAtom"L4"; b_label ≔ TAtom"L7"; 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

The name of prefix's parameter.

82Definition input_name: name ≔
TAtom"v0"

Any arguments whose first word is the integer n start prefix at its entry block with n as its parameter.

86Lemma prefix_call_frame
∀ n rest
call_frameprefix_fn WIntn :: rest = SomemkFrameprefix_fn input_name, WIntn [ ] None EnterTAtom"start" None
Explore proof 1 tactics

Initial goal

⊢
∀n : Z rest : listword, call_frameprefix_fn WIntn :: rest = Somefr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; 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 runs

The environment e with the parameter's word replaced by the integer n: a state of a computed run, for the input n.

95Definition with_inputn : Z e : env : env ≔
map
λ p  ⇒
→
fstp, WIntn
else
p
e

The run of prefix on the input k, computed by the model on the initial memory.

100Definition prefix_runk : Z : listpoint × env ≔
traceprefix_geλ_ _ ⇒ None 300 mkConfigmkFrameprefix_fn input_name, WIntk [ ] None EnterTAtom"start" None [ ] prefix_mem 1000

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.

107Definition prefix_runs: listlistpoint × env ≔
mapprefix_run 0; 1; 2; 3; 4; 5

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.

112Fixpoint exit_atr : listpoint × env : nat ≔
match r with
[ ]
⇒
O
Execl [ ] _, e :: r′
⇒
&&
match lookupTAtom"v10" e with
SomeWInt0
⇒
true
_
⇒
false
→
O
else
Sexit_atr′
_ :: r′
⇒
Sexit_atr′

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.

124Definition canonicalk i : nat : Prop ≔
k = 5%nat ∨ exit_atnthk prefix_runs [ ] ≤ i%nat

Each step

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

130Lemma pxs0
Explore proof 2 tactics

Initial goal

⊢

vm_compute

⊢
1 = 1

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity
131Lemma pxs1
Explore proof 2 tactics

Initial goal

⊢

vm_compute

⊢
2 = 2

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity
132Lemma pxs2
Explore proof 2 tactics

Initial goal

⊢

vm_compute

⊢
3 = 3

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity
133Lemma pxs3
Explore proof 2 tactics

Initial goal

⊢

vm_compute

⊢
4 = 4

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
vm_compute
reflexivity

Each long the step read from the array, known by Hb that the memory has the initial bytes: the long at its address.

137Ltac known_loads Hb ≔
rewrite ? load_bytes_same_ _ Hb;repeat match goal with|- context [load_bytesprefix_mem ?a 8]⇒first change a with 65552 ; rewrite pxs0 | change a with 65560 ; rewrite pxs1 | change a with 65568 ; rewrite pxs2 | change a with 65576 ; rewrite pxs3end

The next state is index S i of run k.

145Ltac next_in k ≔
exists k ; do 3 eexists ; split ; apply Nat.leb_le ; reflexivity | ; split ; first left ; reflexivity | right ; cbv ; lia | ; split ; reflexivity

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.

154Ltac run_step k Hn Hb ≔
cbv in Hn ; injection Hn as ← ← ; take_step ; known_loads Hb ; first right ; left ; reflexivity | right ; right ; eexists ; reflexivity | left ; first next_in k | next_in 5%nat | next_in 0%nat | next_in 1%nat | next_in 2%nat | next_in 3%nat | next_in 4%nat

The states of run k below 5, which start where it leaves run 5 (canonical): five of them, to its return.

164Ltac run_tail k Hc Hn Hb ≔
destruct Hc as Hc | Hc ; discriminate Hc | ; cbv in Hc ; destruct Nat.le_exists_sub_ _ Hc as j & Hj & _ ; rewrite Nat.add_comm in Hj ; subst ; do 5 destruct j as | j ; run_step k Hn Hb | ; destruct j ; cbv in Hn ; discriminate Hn

From index i of run k, for the 32-bit input n, in any memory that is mem_ok and with any fuel, prefix steps to index S i of some run with the same memory, ends for lack of fuel, or returns.

174Lemma prefix_progress
∀ free n k i pt e m fuel
0 ≤ n < 2 ^ 32
k ≤ 5%nat
nth_errornthk prefix_runs [ ] i = Somept, e
∃k′ pt′ e′ fuel′, k′ ≤ 5%nat ∧ canonicalk′ Si ∧ nth_errornthk′ prefix_runs [ ] Si = Somept′, e′ ∧ stepprefix_gefree mkConfigmkFrameprefix_fn with_inputn e [ ] None pt [ ] m fuel = NextmkConfigmkFrameprefix_fn with_inputn e′ [ ] None pt′ [ ] m fuel′ ∨ stepprefix_gefree mkConfigmkFrameprefix_fn with_inputn e [ ] None pt [ ] m fuel = DoneOutOfFuel ∨ ∃s, stepprefix_gefree mkConfigmkFrameprefix_fn with_inputn e [ ] None pt [ ] m fuel = DoneRetWInts
Proof 16 steps Qed
intros free n k i pt e m fuel Hin Hk Hc Hn Hb Hr
unfold xs_region in Hr
unfold canonical in *
set runs := prefix_runs in Hn , Hc |- *
vm_compute in runs
set f := prefix_fn
vm_compute in f
destruct k as | | | | | | k
–run_tail 0%nat Hc Hn Hb
–run_tail 1%nat Hc Hn Hb
–run_tail 2%nat Hc Hn Hb
–run_tail 3%nat Hc Hn Hb
–run_tail 4%nat Hc Hn Hb
–do 84 destruct i as | i ; run_step 5%nat Hn Hb |
destruct i ; cbv in Hn ; discriminate Hn
–lia

Over any runtime

prefix never panics under the runtime R.

205Module PrefixSafe R : Runtime
206Module P ≔ Panics R
207Module S ≔ SumSafe R

A machine state that one of the runs stands for: prefix at a canonical index of a run, with the input n, no caller, in a mem_ok memory.

212Definition prefix_invn : Z st : P.RM.mstate : Prop ≔
0 ≤ n < 2 ^ 32 ∧ ∃k i pt e, k ≤ 5%nat ∧ canonicalk i ∧ nth_errornthk prefix_runs [ ] i = Somept, e ∧ fstst = mkConfigmkFrameprefix_fn with_inputn e [ ] None pt [ ] c_memfstst c_fuelfstst ∧ mem_okprefix_mem c_memfstst

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

222Lemma prefix_mstep
Explore proof 19 tactics

Initial goal

⊢
∀n : Z st st′ : P.RM.mstate, P.RM.mstepP.program_genvprefix_module prefix_globals st st′ → prefix_invn st → prefix_invn st′

intros n st st′ Hs Hin & k & i & pt & e & Hk & Hc & Hn & Hst & Hm

n :
Z
st, st′ :
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
fstst = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst
⊢
prefix_invn st′

split ; exact Hin |

n :
Z
st, st′ :
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
fstst = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ fstst′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memfstst′; c_fuel ≔ c_fuelfstst′ ∧ mem_okprefix_mem c_memfstst′

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 open

n :
Z
c, c′ :
s :
R.state
E :
stepprefix_geR.free c = Nextc′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ c′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memc′; c_fuel ≔ c_fuelc′ ∧ mem_okprefix_mem c_memc′
focused goal
n :
Z
k0 :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepprefix_geR.free c = Freshq k0
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k1 i0 : nat pt0 : point e0 : env, k1 ≤ 5%nat ∧ canonicalk1 i0 ∧ nth_errornthk1 prefix_runs [ ] i0 = Somept0, e0 ∧ k0base = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memk0base; c_fuel ≔ c_fuelk0base ∧ mem_okprefix_mem c_memk0base
focused goal
n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

–rewrite Hst in E

3 open

n :
Z
c, c′ :
s :
R.state
pt :
e :
E :
stepprefix_geR.free c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ c′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memc′; c_fuel ≔ c_fuelc′ ∧ mem_okprefix_mem c_memc′
deferred goal
n :
Z
k0 :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepprefix_geR.free c = Freshq k0
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k1 i0 : nat pt0 : point e0 : env, k1 ≤ 5%nat ∧ canonicalk1 i0 ∧ nth_errornthk1 prefix_runs [ ] i0 = Somept0, e0 ∧ k0base = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memk0base; c_fuel ≔ c_fuelk0base ∧ mem_okprefix_mem c_memk0base
deferred goal
n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

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 open

n :
Z
c, c′ :
s :
R.state
pt :
e :
pt′ :
e′ :
fuel′ :
Z
E :
Nextc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′ = Nextc′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
k′ :
nat
Hk′ :
k′ ≤ 5%nat
Hc′ :
canonicalk′ Si
Hn′ :
nth_errornthk′ prefix_runs [ ] Si = Somept′, e′
E′ :
stepprefix_geR.free c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ c′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memc′; c_fuel ≔ c_fuelc′ ∧ mem_okprefix_mem c_memc′
deferred goal
n :
Z
k0 :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepprefix_geR.free c = Freshq k0
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k1 i0 : nat pt0 : point e0 : env, k1 ≤ 5%nat ∧ canonicalk1 i0 ∧ nth_errornthk1 prefix_runs [ ] i0 = Somept0, e0 ∧ k0base = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memk0base; c_fuel ≔ c_fuelk0base ∧ mem_okprefix_mem c_memk0base
deferred goal
n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

injection E as ←

3 open

n :
Z
s :
R.state
pt :
e :
pt′ :
e′ :
fuel′ :
Z
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
k′ :
nat
Hk′ :
k′ ≤ 5%nat
Hc′ :
canonicalk′ Si
Hn′ :
nth_errornthk′ prefix_runs [ ] Si = Somept′, e′
E′ :
stepprefix_geR.free c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′; c_fuel ≔ c_fuelc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′ ∧ mem_okprefix_mem c_memc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
deferred goal
n :
Z
k0 :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepprefix_geR.free c = Freshq k0
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k1 i0 : nat pt0 : point e0 : env, k1 ≤ 5%nat ∧ canonicalk1 i0 ∧ nth_errornthk1 prefix_runs [ ] i0 = Somept0, e0 ∧ k0base = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memk0base; c_fuel ≔ c_fuelk0base ∧ mem_okprefix_mem c_memk0base
deferred goal
n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

exists k′, Si, pt′, e′

3 open

n :
Z
s :
R.state
pt :
e :
pt′ :
e′ :
fuel′ :
Z
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
k′ :
nat
Hk′ :
k′ ≤ 5%nat
Hc′ :
canonicalk′ Si
Hn′ :
nth_errornthk′ prefix_runs [ ] Si = Somept′, e′
E′ :
stepprefix_geR.free c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
⊢
k′ ≤ 5%nat ∧ canonicalk′ Si ∧ nth_errornthk′ prefix_runs [ ] Si = Somept′, e′ ∧ c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′; c_fuel ≔ c_fuelc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′ ∧ mem_okprefix_mem c_memc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
deferred goal
n :
Z
k0 :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepprefix_geR.free c = Freshq k0
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k1 i0 : nat pt0 : point e0 : env, k1 ≤ 5%nat ∧ canonicalk1 i0 ∧ nth_errornthk1 prefix_runs [ ] i0 = Somept0, e0 ∧ k0base = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memk0base; c_fuel ≔ c_fuelk0base ∧ mem_okprefix_mem c_memk0base
deferred goal
n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

cbn [ c_mem c_fuel ]

3 open

n :
Z
s :
R.state
pt :
e :
pt′ :
e′ :
fuel′ :
Z
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
k′ :
nat
Hk′ :
k′ ≤ 5%nat
Hc′ :
canonicalk′ Si
Hn′ :
nth_errornthk′ prefix_runs [ ] Si = Somept′, e′
E′ :
stepprefix_geR.free c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Nextc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′
⊢
k′ ≤ 5%nat ∧ canonicalk′ Si ∧ nth_errornthk′ prefix_runs [ ] Si = Somept′, e′ ∧ c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e′; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt′; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ fuel′ ∧ mem_okprefix_mem c_memc
deferred goal
n :
Z
k0 :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepprefix_geR.free c = Freshq k0
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k1 i0 : nat pt0 : point e0 : env, k1 ≤ 5%nat ∧ canonicalk1 i0 ∧ nth_errornthk1 prefix_runs [ ] i0 = Somept0, e0 ∧ k0base = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memk0base; c_fuel ≔ c_fuelk0base ∧ mem_okprefix_mem c_memk0base
deferred goal
n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

auto

2 open

deferred goal
n :
Z
k0 :
Z → config
s :
R.state
base :
Z
s′ :
R.state
E :
stepprefix_geR.free c = Freshq k0
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k1 i0 : nat pt0 : point e0 : env, k1 ≤ 5%nat ∧ canonicalk1 i0 ∧ nth_errornthk1 prefix_runs [ ] i0 = Somept0, e0 ∧ k0base = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memk0base; c_fuel ≔ c_fuelk0base ∧ mem_okprefix_mem c_memk0base
deferred goal
n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

–rewrite Hst in E

2 open

n :
Z
k0 :
Z → config
s :
R.state
base :
Z
s′ :
R.state
pt :
e :
E :
stepprefix_geR.free c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc = Freshq k0
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k1 i0 : nat pt0 : point e0 : env, k1 ≤ 5%nat ∧ canonicalk1 i0 ∧ nth_errornthk1 prefix_runs [ ] i0 = Somept0, e0 ∧ k0base = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memk0base; c_fuel ≔ c_fuelk0base ∧ mem_okprefix_mem c_memk0base
deferred goal
n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

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
n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
∃k0 i0 : nat pt0 : point e0 : env, k0 ≤ 5%nat ∧ canonicalk0 i0 ∧ nth_errornthk0 prefix_runs [ ] i0 = Somept0, e0 ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e0; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt0; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

–exists k, i, pt, e

n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
k ≤ 5%nat ∧ canonicalk i ∧ nth_errornthk prefix_runs [ ] i = Somept, e ∧ P.RM.with_memc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc m′; c_fuel ≔ c_fuelP.RM.with_memc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc m′

rewrite Hst

n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
k ≤ 5%nat ∧ canonicalk i ∧ nth_errornthk prefix_runs [ ] i = Somept, e ∧ P.RM.with_memc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc m′ = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memP.RM.with_memc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc m′; c_fuel ≔ c_fuelP.RM.with_memc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc m′ ∧ mem_okprefix_mem c_memP.RM.with_memc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc m′

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

n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
k ≤ 5%nat ∧ canonicalk i ∧ nth_errornthk prefix_runs [ ] i = Somept, e ∧ c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc ∧ mem_okprefix_mem m′

split ; exact Hk |

n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
canonicalk i ∧ nth_errornthk prefix_runs [ ] i = Somept, e ∧ c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc ∧ mem_okprefix_mem m′

split ; exact Hc |

n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
nth_errornthk prefix_runs [ ] i = Somept, e ∧ c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc ∧ mem_okprefix_mem m′

split ; exact Hn |

n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc
⊢
c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ m′; c_fuel ≔ c_fuelc ∧ mem_okprefix_mem m′

split ; reflexivity |

n :
Z
s, s′ :
R.state
m′ :
Hsp :
R.safepoints c_memc s′ m′
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
c = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memc; c_fuel ≔ c_fuelc

eapply S.mem_ok_safepoint ; eauto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

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

Every state a run reaches from such a state is one.

244Lemma prefix_reachable
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
intros n st st′ H
induction H as st st′ Hs | st | st1 st2 st3 _ IH1 _ IH2 ; auto
apply prefix_mstep ; assumption

No such state fails: its step is to a next state, the end of fuel, or a return.

254Lemma prefix_not_fails
Explore proof 4 tactics

Initial goal

intros n st Hin & k & i & pt & e & Hk & Hc & Hn & Hst & Hm

n :
Z
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
fstst = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst

rewrite Hst

n :
Z
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
fstst = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst
⊢
¬failsP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst

unfold fails

n :
Z
Hin :
0 ≤ n < 2 ^ 32
k, i :
nat
pt :
e :
Hk :
k ≤ 5%nat
Hc :
Hn :
nth_errornthk prefix_runs [ ] i = Somept, e
Hst :
fstst = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstst; c_fuel ≔ c_fuelfstst
⊢
¬match stepP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn 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 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
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

prefix never panics: for every 32-bit input, under the runtime R, with any fuel, no state of its run fails.

266Theorem prefix_never_panics
P.never_panicsprefix_module TAtom"prefix" λxs ⇒ ∃n rest, xs = WIntn :: rest ∧ 0 ≤ n < 2 ^ 32
Explore proof 16 tactics

Initial goal

⊢
P.never_panicsprefix_module TAtom"prefix" λxs : listword ⇒ ∃n : Z rest : listword, xs = WIntn :: rest ∧ 0 ≤ n < 2 ^ 32

exists prefix_globals, prefix_mem, prefix_fn

⊢
initial_memoryprefix_module = Someprefix_globals, prefix_mem ∧ find_fnP.program_genvprefix_module prefix_globals TAtom"prefix" = SomeDefinedprefix_fn ∧ ∀xs : listword, ∃n : Z rest : listword, xs = WIntn :: rest ∧ 0 ≤ n < 2 ^ 32 → ∃fr : frame, call_frameprefix_fn xs = Somefr ∧ R.readyR.start prefix_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvprefix_module prefix_globals fstst

split ; exact prefix_initial |

⊢
find_fnP.program_genvprefix_module prefix_globals TAtom"prefix" = SomeDefinedprefix_fn ∧ ∀xs : listword, ∃n : Z rest : listword, xs = WIntn :: rest ∧ 0 ≤ n < 2 ^ 32 → ∃fr : frame, call_frameprefix_fn xs = Somefr ∧ R.readyR.start prefix_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvprefix_module prefix_globals fstst

split ; apply prefix_find |

⊢
∀xs : listword, ∃n : Z rest : listword, xs = WIntn :: rest ∧ 0 ≤ n < 2 ^ 32 → ∃fr : frame, call_frameprefix_fn xs = Somefr ∧ R.readyR.start prefix_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvprefix_module prefix_globals fstst

intros xs n & rest & → & Hin

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
⊢
∃fr : frame, call_frameprefix_fn WIntn :: rest = Somefr ∧ R.readyR.start prefix_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvprefix_module prefix_globals fstst

eexists

2 open

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
⊢
call_frameprefix_fn WIntn :: rest = Some?fr ∧ R.readyR.start prefix_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ ?fr; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvprefix_module prefix_globals fstst
shelved goal
n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32

split ; apply prefix_call_frame |

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
⊢
R.readyR.start prefix_mem → ∀fuel : Z st : P.RM.mstate, P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st → ¬failsP.program_genvprefix_module prefix_globals fstst

intros _ fuel st Hreach

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st

apply prefix_not_failsn

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st
⊢

eapply prefix_reachable ; exact Hreach |

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st
⊢
prefix_invn c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start

split ; exact Hin |

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st
⊢
∃k i : nat pt : point e : env, k ≤ 5%nat ∧ canonicalk i ∧ nth_errornthk prefix_runs [ ] i = Somept, e ∧ fstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn e; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ pt; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start ∧ mem_okprefix_mem c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start

exists 5%nat, O, EnterTAtom"start" None, input_name, WInt5

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st
⊢
5 ≤ 5%nat ∧ canonical5 0 ∧ nth_errornth5 prefix_runs [ ] 0 = SomeEnterTAtom"start" None, input_name, WInt5 ∧ fstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn input_name, WInt5; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start ∧ mem_okprefix_mem c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start

split ; lia |

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st
⊢
canonical5 0 ∧ nth_errornth5 prefix_runs [ ] 0 = SomeEnterTAtom"start" None, input_name, WInt5 ∧ fstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn input_name, WInt5; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start ∧ mem_okprefix_mem c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start

split ; left ; reflexivity |

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st
⊢
nth_errornth5 prefix_runs [ ] 0 = SomeEnterTAtom"start" None, input_name, WInt5 ∧ fstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn input_name, WInt5; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start ∧ mem_okprefix_mem c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start

split ; vm_compute ; reflexivity |

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st
⊢
fstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start = c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ with_inputn input_name, WInt5; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start; c_fuel ≔ c_fuelfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start ∧ mem_okprefix_mem c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start

split ; reflexivity |

n :
Z
rest :
listword
Hin :
0 ≤ n < 2 ^ 32
fuel :
Z
Hreach :
P.RM.mreachableP.program_genvprefix_module prefix_globals c_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start st
⊢
mem_okprefix_mem c_memfstc_frame ≔ fr_fn ≔ prefix_fn; fr_env ≔ input_name, WIntn; fr_locals ≔ [ ]; fr_doomed ≔ None; fr_at ≔ EnterTAtom"start" None; c_callers ≔ [ ]; c_mem ≔ prefix_mem; c_fuel ≔ fuel, R.start

split ; reflexivity | vm_compute ; reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
split ; exact prefix_initial |
split ; apply prefix_find |
intros xs n & rest & → & Hin
eexists
split ; apply prefix_call_frame |
intros _ fuel st Hreach
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

The theorem for the interpreter's runtime.

282Module InterpPrefix ≔ PrefixSafe InterpRuntime