Preorder-constrained simulation for program re nement with e ects
Koko Muroya (RIMS, Kyoto University), Takahiro Sanada (RIMS, Kyoto University), Natsuki Urabe (NII)

Goal: coinductive, non-syntactical technique for proving program re nement
Program re nement t ⊑ u:coinductive:“stepwise” reasoning
non-syntactical:
cf. applicative bisimilarity [Abramsky ’90]

“observation of evaluating t is also
observable in evaluating u”

in the presence of e ects
✓ mutable state, errors✓ nondeterministic choice✓ I/O× probabilistic choice

Example: reduction semantics as NAStarting point: counting simulation [M. ’20]

nondeterministic automaton

Def. Let Q be a preorder on ℕ.

Ω = (TΩ ∪ {✓}, {τ} ∪ Ω ∪ ℕ, → , {✓})for λ-calculus w/ algebraic e ects Ω :● terms TΩ as states● ✓ as a nal state● algebraic operations Ω & ground results ℕ as labels
where Ω = {fi ∣ f ∈ Ω,0 ≤ i ≤ arity( f ) − 1}

● reduction as transitionf∈ΩτE[(λx . t) v] → E[t[v/x]]x00
Rm0yxnm)QnR y (1 +xx00
R(b) Step 0m0nfin→✓

E[ f(t0, …, tarity( f )−1)] → E[ti]FinalM : For each w = a1 . . . ax1 . . . xn 2 X1⇤ such that na2
anx1···xn and xn 2y 0 2 X2 such that wQw0 ; yStepM : For eachw
M = a1 . . . aFinal : Fora1 each
R yM
⌃ such thatx x. . . x x21 Xx
1n0 aak2{1,.
.
.
,M},2n ⌃2 w(a) Final0x0 x1 w ⇤ · ·0·a1 . . . ak Qw ;yy0 2 X; and2 y such00Fig. 3. Conditions of the ⇤-simulation. Parts in black
2x are yuniversally
Qquantified,andparts
inmagenta
areexistentiallyquantified.
M⊑{ } uIV.5
Prop. For { }, ∃R : Q-sim. tRu n⟹ t Theorem. Step(soundness).
If: For each0 M0R yR ynation
(i.e.
w
Qw
andw
1
⌃
such2 Qw
tha
1xx
implies x Q y. k 2 {1, . . . ,0(a) Final(b) StepxM0a.
.
.
aQw;
1k abov
The soundness theorem

Proposal:
Preorder-constrainedFig. 3. Conditionsof the ⇤-simulation. Parts in black aresimulation
universallygeneral case (Thm.
??). IV.5 (soTheoremyyxnation(i.e.
w⇤
1 Qw0Def.w Let M w∈0 ℕ, and let w0 be a preorderon.
Σ*Definition
IV.6.
LetQ
✓
⌃w
R yR
Rpreorder. we implies
call R x✓ QXy. ⇥0x

quantified,and parts inRmagenta
are existentiallyquantified.
000xk

w

yx

yyxxM

1

bounded Q-constrained
simulati
The soundness
to A2 if, for generalany (x, casey) 2(Thm.
R, thR 0000w xkyyyx
holds.
xn000wDefinition IV.6. Lw
w
w
0Final:Ifx
2
Fthenthereex1RRRw w′ xa1x⋯ak w′yy
y0 preorder. we callx
R 0andy2
Xsuchthat"Qw
02xw xknyy
bounded Q-constra
10M
M
(c)
Final(a) Final(b)
Stepandy2
F2 .
00
to A2 if, for anyw w
w
1
Step : For each a1 . . . an 2
R y
R yholds. +xxnx
Thm.
x1 . . . xn 2 X01 such that: Ifexist
x 2kF12(d) Step1 (i)(e) Step1 (ii)xnQ 2 F1Final, there0Randy2XFor,∃R:(M,Q̃)-sim.
tRu⟹t⊑u0002aFig. 4. ●Conditions of {Def. IV.1.
xk are yuniversallyxnquantified,w in black} Partsy andy { 2 X}2 satisfying:(1)
10parts in magenta are existentially quantified.
and0 y 2 F2 .
00and (3-i) xk Ry , or (3-ii) kw ww
1Step: For each
R yR y● For { },xx
Theorem IV.7. AssumethatQ isx.
.
.
x2X1nMNM3) Step ^∃RFinal=)
Final(d) Step1 (i)(e) Step1 (ii)xnIf 2R Fis1 , anthe: M(M, =remove(τ,)-sim.
tRu⟹t⊑u1)(monotonicity),){}
M1014) Step ^ Fig.
Final=)
Step
4. Conditions of Def. IV.1. Parts in black are universally quantified,andy 0 R2 isXalso
simulation
thena2 satiparts in magenta are existentially quantified.
Forand each(3-i) xk R
● IV.3. {Let , A1 0, = 1(X2) (soundness) For2Theorem}, 1 , ⌃, 1 , F1 ) and A2 =exists anTheorem1-bounded
Q-co(X2 , ⌃, 2 , F2 ) be NAs with the same alphabet, Q ✓ ⌃⇤ ⇥⌃⇤IV.7.
Ass∃R:(M,=)-sim.
tRu⟹t⊑uM a relation. LetN M, N 2 NMremove(τ){ that, xRy
be a preorder, andR
✓X⇥
X
be0, then1} x Q y.
123) Step ^ Final =) Final
1) (monotonicity)M
13)(completeness)
There exsuch that M  4)
N .Step
TheMfollowing
holds.
^ Final =) Step
simulationRthe
constrained
simulationsu1) (Monotonicity) If R is an (M, Q)-simulation, it is also2)(soundness)
FTheorem IV.3. Let A1 = (X1 , ⌃, 1 , F1 ) and Ay2 2 =X,xyimplies
xR2Qan (N, Q)-simulation.
⇤⇤
exists an 1-b(X2 , ⌃, 2 , F2 ) be NAs with the same alphabet, Q ✓ ⌃ ⇥⌃2) (Monotonicity)
If
M>
0andRisan(M,Q)-simulation,that xRy thenbe a preorder, and R ✓ X1 ⇥ X2 be a relation. Let B.
M,AgdaN 2N
Implementation
it is alsosucha Q-simulation.
3) (completenessthat M N . The followingholds.
✔
✔
✔
✔
V. G AME -T
HEORETIC C3) (Soundness) If M > 0, Q is closed under concatenation,
constrained si1)
(Monotonicity)
IfRisan(M,Q)-simulation,
itisalso
and R is an (M, Q)-simulation,
each (x,y) 2 X1 ⇥ X2 3
344y1)2 X
2, x
Proposition
V.1.
ForM Q2
an(N,Q)-simulation.
satisfies xRy =) x Q y.
bounded Q-constrained sim2)(Monotonicity)
If
M>0andRisan(M,Q)-simulation,
3 under concatenation,444) (Soundness) If Q is closed
and R 3B.
Agda
Implemen
and
only
if
Simulator
is winitisalsoaQ-simulation.
is an Q-simulation, each (x, y) 2 X1 ⇥ X2 satisfies
M,1,Q
thegameG. G AME ττττV.
3)(Soundness)
If
M>
0,Q
is
closedunderconcatenation,
A,A
1
2xRy =) x Q y.
02)
For
M,N,N
2 N1 such t✔
✔
andRisan(M,Q)-simulation,
0 each (x, y) 2 X1 ⇥ X25) (Completeness) There3+0
exists a Q-simulation
R such that 3+03+13+1
Proposition
V.1.x, ywinningfromastate(",satisfiesxRy=)xx Qy y.=) xR0 y.
each(x,y)2X⇥
Xsatisfies
12Q
10boundedQ-coSimulatorisalsowinningf4) (Soundness)
IfQ
isclosedunder
concatenation,andRττ00
1
M,N ,Q
and
only if Sim
obsolete
below:
gameG.
is an Q-simulation, each (x, y) 2 X1 ⇥ X2 satisfies A1 ,A2M,
10
the game GA1
3+in(0,1)
1+2+0
1+2+10xRy =)⇤ x Q0⇤ y.
0yx
Definition IV.4. Let Q ✓ ⌃ ⇥ ⌃ be a preProposition
V.2.
AssumethatwQ2)
ForM,N,N
005)(Completeness)
Thereexists
aQ-simulation
Rsuchthatw⇤τw
01winningorderandM
2N.
wecallR✓
X⇥
Xan⌃canbecheckedinlinear
tim
Rfrom
1
2
0
10y xR y.
x Q y =)each(x,y)
2X⇥
X
satisfiesx
1
2
M -bounded Q-constrained simulation fromFor M, N 2 N, existence
ofisanSimulator
aor(1,0)
1+2+in(0,1)
in(1+2+0,1+2+1)
0xMM,N,Q
A1 to A2 if, for any(x,y)
2R,thefollowingsimulation
Rsatisfying
xRycaobsolete below:
game GA1 ,A2R0 time to |⌃|, |X1 | and |X2 |.
holds.
xw
ky00⇤⇤yx
Definition IV.4. Let Q ✓ ⌃ ⇥ ⌃ be a pre- w0
Proposition V.2. A0Rw
⇤w
yx X2 anorder and M 2 N. we call R ✓ X1 ⇥⌃canbecheckedRyx
M -bounded Q-constrained simulation fromFor M, N 2 N, ex
MA1 to A2 if, for any (x, y) 2 R, the following
simulation R satisRholds.
w xky 0 time to |⌃|, |X1 | a(a) FinalM(b) StepM(c) Final1

Program re nement as "trace inclusion”
Q● error t ⊑{wu⟺:0}
w′t ↠ ✓ ⟹ u ↠ ✓ ∧ |w|Q|w|● nondeterministic choice t ⊑{ :2} u ⟺ww′t ↠ ✓ ⟹ u ↠ ✓ ∧ w =remove(τ,● I/O t ⊑{ :2,u:1}
1
w′

0:1,w

0,⟺w′)
1t ↠ ✓ ⟹ u ↠ ✓ ∧ w =remove(τ) w′

Example pairs of NAs
✔

✔

14

14

1414
ττ

6+8
τ

2×7{a} τx2{b}x1{a}xx2bx1ax{a, b}2×(3+4)2τ2110y1

32×3+2×40y(d) ✓⇤ -trace inclusion

ce in-y2x1

1

✔

1

6+2×4xy2{a, b}✔

10or(1,1)1xy(e)+ -trace inclusion

1Two challenges

Advanced topics

that exhibit Q-trace inclusions.

1. Standard stepwise comparison is not satisfactory.

Rxa

R0

y0yR yx(a) Final(b) Stepxxa● two-player reachability game● up-to technique in terms of preorders𝚝𝚞𝚛𝚘𝚘𝚞𝚘𝚗𝚝￼￼𝚒𝚛𝚘𝚛𝚛𝚘𝚛𝚘𝚝𝚞𝚘𝚝𝚞𝚝𝚘𝚞𝚘𝚝𝚞𝚘𝚛𝚗𝚛𝚛𝚘𝚛𝚛𝚎𝚛𝚛𝚎𝚛𝚛𝚎𝚘𝚒𝚛𝚛𝚛𝚗𝚎𝚎𝚘

ff

fi

fi

ff

ff

ff

￼￼
fi

fi

fi

￼￼𝒬￼𝚛𝚛𝚛𝚛𝚗𝚗𝚗
𝒬𝚗𝒜𝒜𝒬𝒜𝒜𝒜𝚘𝚘𝚘𝚘𝚒𝚒𝚒𝚒Rw0y● complete variant of preorder-constrained simulation

Fig. 2. Conditions of the standard simulation. Parts in black are universally
2. Observation varies between e ects.
quantified, and parts in magenta are existentially quantified.
𝚒● generalised notion of trace inclusion