Temporal Higher-Order
Contracts
Tim Disney, Cormac Flanagan, Jay McCarthy

This material is based upon work supported by the National Science Foundation under Grants 1016334 and 0905650.
1

sort : fun2

sort : fun
4, true,(list 1 2 3)
2

sort : fun
4, true,(list 1 2 3)

quicksort,
insertionsort,+, modulo
2

sort :
list(Int)fun→list(Int)3

+, modulo

sort :
list(Int)fun→list(Int)3

+, modulo

sort :
list(Int)fun→list(Int)

quicksort,
insertionsort,
filter3

sort :
list(Int)(Int Int → Bool)→list(Int)4

sort :
list(Int)(Int Int → Bool)→list(Int)filter, map

4

sort :
list(Int)(Int Int → Bool)→list(Int) quicksort,

filter, map

insertionsort

4

sort :
list(Int)(Int Int → Bool)→list(Int)[not re-entrant]5

(define (cmp x y)
(f x y(sort m <=)))(sort l cmp)
6

sort :
list(Int)(cmp : Int Int → Bool)→list(Int)[not re-entrant, cmp isa capability]7

(define last-cmp #f)(define (partner l cmp)
(set! last-cmp cmp)
(quicksort l cmp))(define (thief x y)
(last-cmp x y))8• first-order preconditions (Eiffel, etc)
• higher-order contracts (Racket, etc)
• first-order temporal contracts (MOP, etc)
• higher-order temporal contracts

9

SortContract =sort : (List Pos)
(cmp : Pos!Pos!Bool)! (List Pos)
where
not ... call(sort,_) !ret(sort,_)*call(sort,_)andnot ... ret(sort,_) ... call(cmp,_)10

Client

Server11

Client

Server12

Client

Server13

Client

Server14

Step 1: Game Semantics

15

Figure 1: CSI Machine
Domains
State
Code
Store
Interface

CSI∈

Code × Store × Interface

C
S
I

::=
∈
∈

E[e] | Q[⊥]
P(Var × Var × Value)
Var → Value

Evaluation context
Quiescent context
Value
HandleEvent
Direction
Trace

E
Q
v
h
a
ρ
t

::=
::=
::=
::=
::=
::=
::=

E[• e] | E[v •] | E[ref •] | Q[rcv.callx •]• | E[send.callx •]c | x | λy. ec|x
ρ.ret(x, h) | ρ.call(x, h)send | rcv#aTransition relation (→) ⊆ State × Event ⊥ × State
&
&
&
&
&

E[(λx. e) v],
E[c v],
E[ref v],
E[x v],
E[y v],

S,
I'
S,
I'
S,
I'
"
S[(x, y) (→ v ], I 'S[(x, y) (→ v" ], I '&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→
→
→
→
→

&
&
&
&
&

E[e[x := v]],
E[v" ],
E[pair x y],E[v" ],
E[v],

S,
S,
S[(x, y) (→ v],
S[(x, y) (→ v" ],S[(x, y) (→ v],

I
I
I
I
I

'
'
'
'
'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],
&
Q[⊥],

S,
S,
S,
S,

I[h % v] 'I'I'
I[h % v] 'v" = δ(c, v)
x, y freshx )∈ BV(S)
I(x) = v[CALL][PRIM]
[REF]
[GET]
[SET]
[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I ' →rcv.call(y,t)& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '∅, I '→send.ret(start,t) & ⊥,16

Figure 1: CSI Machine
Domains
State
Code
Store
Interface

CSI∈

Code × Store × Interface

C
S
I

::=
∈
∈

E[e] | Q[⊥]
P(Var × Var × Value)
Var → Value

Evaluation context
Quiescent context
Value
HandleEvent
Direction
Trace

E
Q
v
h
a
ρ
t

::=
::=
::=
::=
::=
::=
::=

E[• e] | E[v •] | E[ref •] | Q[rcv.callx •]• | E[send.callx •]c | x | λy. ec|x
ρ.ret(x, h) | ρ.call(x, h)send | rcv#aTransition relation (→) ⊆ State × Event ⊥ × State
&
&
&
&
&

E[(λx. e) v],
E[c v],
E[ref v],
E[x v],
E[y v],

S,
I'
S,
I'
S,
I'
"
S[(x, y) (→ v ], I 'S[(x, y) (→ v" ], I '&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→
→
→
→
→

&
&
&
&
&

E[e[x := v]],
E[v" ],
E[pair x y],E[v" ],
E[v],

S,
S,
S[(x, y) (→ v],
S[(x, y) (→ v" ],S[(x, y) (→ v],

I
I
I
I
I

'
'
'
'
'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],
&
Q[⊥],

S,
S,
S,
S,

I[h % v] 'I'I'
I[h % v] 'v" = δ(c, v)
x, y freshx )∈ BV(S)
I(x) = v[CALL][PRIM]
[REF]
[GET]
[SET]
[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I ' →rcv.call(y,t)& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '∅, I '→send.ret(start,t) & ⊥,16

Figure 1: CSI Machine
Domains
State
Code
Store
Interface

CSI∈

Code × Store × Interface

C
S
I

::=
∈
∈

E[e] | Q[⊥]
P(Var × Var × Value)
Var → Value

Evaluation context
Quiescent context
Value
HandleEvent
Direction
Trace

E
Q
v
h
a
ρ
t

::=
::=
::=
::=
::=
::=
::=

E[• e] | E[v •] | E[ref •] | Q[rcv.callx •]• | E[send.callx •]c | x | λy. ec|x
ρ.ret(x, h) | ρ.call(x, h)send | rcv#aTransition relation (→) ⊆ State × Event ⊥ × State
&
&
&
&
&

E[(λx. e) v],
E[c v],
E[ref v],
E[x v],
E[y v],

S,
I'
S,
I'
S,
I'
"
S[(x, y) (→ v ], I 'S[(x, y) (→ v" ], I '&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→
→
→
→
→

&
&
&
&
&

E[e[x := v]],
E[v" ],
E[pair x y],E[v" ],
E[v],

S,
S,
S[(x, y) (→ v],
S[(x, y) (→ v" ],S[(x, y) (→ v],

I
I
I
I
I

'
'
'
'
'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],
&
Q[⊥],

S,
S,
S,
S,

I[h % v] 'I'I'
I[h % v] 'v" = δ(c, v)
x, y freshx )∈ BV(S)
I(x) = v[CALL][PRIM]
[REF]
[GET]
[SET]
[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I ' →rcv.call(y,t)& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '∅, I '→send.ret(start,t) & ⊥,16

Figure 1: CSI Machine
Domains
State
Code
Store
Interface

CSI∈

Code × Store × Interface

C
S
I

::=
∈
∈

E[e] | Q[⊥]
P(Var × Var × Value)
Var → Value

Evaluation context
Quiescent context
Value
HandleEvent
Direction
Trace

E
Q
v
h
a
ρ
t

::=
::=
::=
::=
::=
::=
::=

E[• e] | E[v •] | E[ref •] | Q[rcv.callx •]• | E[send.callx •]c | x | λy. ec|x
ρ.ret(x, h) | ρ.call(x, h)send | rcv#aTransition relation (→) ⊆ State × Event ⊥ × State
&
&
&
&
&

E[(λx. e) v],
E[c v],
E[ref v],
E[x v],
E[y v],

S,
I'
S,
I'
S,
I'
"
S[(x, y) (→ v ], I 'S[(x, y) (→ v" ], I '&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→
→
→
→
→

&
&
&
&
&

E[e[x := v]],
E[v" ],
E[pair x y],E[v" ],
E[v],

S,
S,
S[(x, y) (→ v],
S[(x, y) (→ v" ],S[(x, y) (→ v],

I
I
I
I
I

'
'
'
'
'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],
&
Q[⊥],

S,
S,
S,
S,

I[h % v] 'I'I'
I[h % v] 'v" = δ(c, v)
x, y freshx )∈ BV(S)
I(x) = v[CALL][PRIM]
[REF]
[GET]
[SET]
[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I ' →rcv.call(y,t)& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '∅, I '→send.ret(start,t) & ⊥,16

Figure 1: CSI Machine
Domains
State
Code
Store
Interface

CSI∈

Code × Store × Interface

C
S
I

::=
∈
∈

E[e] | Q[⊥]
P(Var × Var × Value)
Var → Value

Evaluation context
Quiescent context
Value
HandleEvent
Direction
Trace

E
Q
v
h
a
ρ
t

::=
::=
::=
::=
::=
::=
::=

E[• e] | E[v •] | E[ref •] | Q[rcv.callx •]• | E[send.callx •]c | x | λy. ec|x
ρ.ret(x, h) | ρ.call(x, h)send | rcv#aTransition relation (→) ⊆ State × Event ⊥ × State
&
&
&
&
&

E[(λx. e) v],
E[c v],
E[ref v],
E[x v],
E[y v],

S,
I'
S,
I'
S,
I'
"
S[(x, y) (→ v ], I 'S[(x, y) (→ v" ], I '&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→
→
→
→
→

&
&
&
&
&

E[e[x := v]],
E[v" ],
E[pair x y],E[v" ],
E[v],

S,
S,
S[(x, y) (→ v],
S[(x, y) (→ v" ],S[(x, y) (→ v],

I
I
I
I
I

'
'
'
'
'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],
&
Q[⊥],

S,
S,
S,
S,

I[h % v] 'I'I'
I[h % v] 'v" = δ(c, v)
x, y freshx )∈ BV(S)
I(x) = v[CALL][PRIM]
[REF]
[GET]
[SET]
[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I ' →rcv.call(y,t)& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '∅, I '→send.ret(start,t) & ⊥,16

Figure 1: CSI Machine
Domains
State
Code
Store
Interface

CSI∈

Code × Store × Interface

C
S
I

::=
∈
∈

E[e] | Q[⊥]
P(Var × Var × Value)
Var → Value

Evaluation context
Quiescent context
Value
HandleEvent
Direction
Trace

E
Q
v
h
a
ρ
t

::=
::=
::=
::=
::=
::=
::=

E[• e] | E[v •] | E[ref •] | Q[rcv.callx •]• | E[send.callx •]c | x | λy. ec|x
ρ.ret(x, h) | ρ.call(x, h)send | rcv#aTransition relation (→) ⊆ State × Event ⊥ × State
&
&
&
&
&

E[(λx. e) v],
E[c v],
E[ref v],
E[x v],
E[y v],

S,
I'
S,
I'
S,
I'
"
S[(x, y) (→ v ], I 'S[(x, y) (→ v" ], I '&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→
→
→
→
→

&
&
&
&
&

E[e[x := v]],
E[v" ],
E[pair x y],E[v" ],
E[v],

S,
S,
S[(x, y) (→ v],
S[(x, y) (→ v" ],S[(x, y) (→ v],

I
I
I
I
I

'
'
'
'
'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],
&
Q[⊥],

S,
S,
S,
S,

I[h % v] 'I'I'
I[h % v] 'v" = δ(c, v)
x, y freshx )∈ BV(S)
I(x) = v[CALL][PRIM]
[REF]
[GET]
[SET]
[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I ' →rcv.call(y,t)& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '∅, I '→send.ret(start,t) & ⊥,16

Figure 1: CSI Machine
Domains
State
Code
Store
Interface

CSI∈

Code × Store × Interface

C
S
I

::=
∈
∈

E[e] | Q[⊥]
P(Var × Var × Value)
Var → Value

Evaluation context
Quiescent context
Value
HandleEvent
Direction
Trace

E
Q
v
h
a
ρ
t

::=
::=
::=
::=
::=
::=
::=

E[• e] | E[v •] | E[ref •] | Q[rcv.callx •]• | E[send.callx •]c | x | λy. ec|x
ρ.ret(x, h) | ρ.call(x, h)send | rcv#aTransition relation (→) ⊆ State × Event ⊥ × State
&
&
&
&
&

E[(λx. e) v],
E[c v],
E[ref v],
E[x v],
E[y v],

S,
I'
S,
I'
S,
I'
"
S[(x, y) (→ v ], I 'S[(x, y) (→ v" ], I '&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→
→
→
→
→

&
&
&
&
&

E[e[x := v]],
E[v" ],
E[pair x y],E[v" ],
E[v],

S,
S,
S[(x, y) (→ v],
S[(x, y) (→ v" ],S[(x, y) (→ v],

I
I
I
I
I

'
'
'
'
'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],
&
Q[⊥],

S,
S,
S,
S,

I[h % v] 'I'I'
I[h % v] 'v" = δ(c, v)
x, y freshx )∈ BV(S)
I(x) = v[CALL][PRIM]
[REF]
[GET]
[SET]
[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I ' →rcv.call(y,t)& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '∅, I '→send.ret(start,t) & ⊥,16

Figure 1: CSI Machine
Domains
State
Code
Store
Interface

CSI∈

Code × Store × Interface

C
S
I

::=
∈
∈

E[e] | Q[⊥]
P(Var × Var × Value)
Var → Value

Evaluation context
Quiescent context
Value
HandleEvent
Direction
Trace

E
Q
v
h
a
ρ
t

::=
::=
::=
::=
::=
::=
::=

E[• e] | E[v •] | E[ref •] | Q[rcv.callx •]• | E[send.callx •]c | x | λy. ec|x
ρ.ret(x, h) | ρ.call(x, h)send | rcv#aTransition relation (→) ⊆ State × Event ⊥ × State
&
&
&
&
&

E[(λx. e) v],
E[c v],
E[ref v],
E[x v],
E[y v],

S,
I'
S,
I'
S,
I'
"
S[(x, y) (→ v ], I 'S[(x, y) (→ v" ], I '&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→
→
→
→
→

&
&
&
&
&

E[e[x := v]],
E[v" ],
E[pair x y],E[v" ],
E[v],

S,
S,
S[(x, y) (→ v],
S[(x, y) (→ v" ],S[(x, y) (→ v],

I
I
I
I
I

'
'
'
'
'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],
&
Q[⊥],

S,
S,
S,
S,

I[h % v] 'I'I'
I[h % v] 'v" = δ(c, v)
x, y freshx )∈ BV(S)
I(x) = v[CALL][PRIM]
[REF]
[GET]
[SET]
[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I ' →rcv.call(y,t)& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '∅, I '→send.ret(start,t) & ⊥,16

Figure 1: CSI Machine
Domains
State
Code
Store
Interface

CSI∈

Code × Store × Interface

C
S
I

::=
∈
∈

E[e] | Q[⊥]
P(Var × Var × Value)
Var → Value

Evaluation context
Quiescent context
Value
HandleEvent
Direction
Trace

E
Q
v
h
a
ρ
t

::=
::=
::=
::=
::=
::=
::=

E[• e] | E[v •] | E[ref •] | Q[rcv.callx •]• | E[send.callx •]c | x | λy. ec|x
ρ.ret(x, h) | ρ.call(x, h)send | rcv#aTransition relation (→) ⊆ State × Event ⊥ × State
&
&
&
&
&

E[(λx. e) v],
E[c v],
E[ref v],
E[x v],
E[y v],

S,
I'
S,
I'
S,
I'
"
S[(x, y) (→ v ], I 'S[(x, y) (→ v" ], I '&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→
→
→
→
→

&
&
&
&
&

E[e[x := v]],
E[v" ],
E[pair x y],E[v" ],
E[v],

S,
S,
S[(x, y) (→ v],
S[(x, y) (→ v" ],S[(x, y) (→ v],

I
I
I
I
I

'
'
'
'
'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],
&
Q[⊥],

S,
S,
S,
S,

I[h % v] 'I'I'
I[h % v] 'v" = δ(c, v)
x, y freshx )∈ BV(S)
I(x) = v[CALL][PRIM]
[REF]
[GET]
[SET]
[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I ' →rcv.call(y,t)& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '∅, I '→send.ret(start,t) & ⊥,16

&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],&Q[⊥],

I[h % v] 'I'I'
I[h % v] '

S,
S,
S,
S,

x )∈ BV(S)
I(x) = v[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]

Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I1 ' →rcv.call(y,t)∅, I1 ' →∅, I1 ' →send.call(t,f )∅, J1 '
→rcv.ret(t,g)& rcv.cally (g 4),∅, J1 ' →send.call(g,4)& rcv.cally (send.callg ⊥),∅, J1 '
→rcv.call(f,4)& rcv.cally (send.callg (rcv.callf ((λx. x+1) 4))), ∅, J1 ' →2& rcv.cally (send.callg (rcv.callf 5)),∅, J1 ' →send.ret(f,5)& rcv.cally (send.callg ⊥),∅, J1 ' →rcv.call(f,5)& rcv.cally (send.callg (rcv.callf ((λx. x+1) 5))), ∅, J1 ' →2& rcv.cally (send.callg (rcv.callf 6)),∅, J1 ' →send.ret(f,6)& rcv.cally (send.callg ⊥),∅, J1 ' →rcv.ret(g,6)& rcv.cally 6,∅, J1 ' →send.ret(y,6)& ⊥,∅, J1 '

& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '→send.ret(start,t) & ⊥,∅, I2 '

& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,& rcv.cally ((λt. t (λx. x+1) 4) t),& rcv.cally ((t (λx. x+1)) 4),& rcv.cally (send.callt ⊥) 4),

noting the initial evaluation of a module. Once the evaluation of eterminates, it will return send.ret(start , h) and wait for incoming
events. The meaning of a module e is then the set of all possible
event sequences !a that e can generate under the CSI machine:
[[−]]

:

Module → P(Trace)→rcv.call(t,f )→→send.ret(t,g)→rcv.call(g,4)→→send.call(f,4)& rcv.callt ((λf. λx. f (f x)) f ), ∅, I2 '& rcv.callt (λx. f (f x)),∅, I2 '
& ⊥,∅, J2 '
& rcv.callg ((λx. f (f x)) 4),∅, J2 '
& rcv.callg (f (f 4)),∅, J2 '
& rcv.callg (send.callf (f ⊥)), ∅, J2 '→rcv.ret(f,5)→send.call(f,5)& rcv.callg (f 5),& rcv.callg (send.callf ⊥),∅, J2 '∅, J2 '

→rcv.ret(f,6)→send.ret(g,6)& rcv.callg 6,& ⊥,∅, J2 '∅, J2 'are:
EV ( C, S, I )IV ( C, S, I )

def

=
def
=

dom(I)(F V (C) ∪ F V (rng(S)) ∪ F V (rng (I)))\ BV (S)17&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],&Q[⊥],

I[h % v] 'I'I'
I[h % v] '

S,
S,
S,
S,

x )∈ BV(S)
I(x) = v[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]

Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I1 ' →rcv.call(y,t)∅, I1 ' →∅, I1 ' →send.call(t,f )∅, J1 '
→rcv.ret(t,g)& rcv.cally (g 4),∅, J1 ' →send.call(g,4)& rcv.cally (send.callg ⊥),∅, J1 '
→rcv.call(f,4)& rcv.cally (send.callg (rcv.callf ((λx. x+1) 4))), ∅, J1 ' →2& rcv.cally (send.callg (rcv.callf 5)),∅, J1 ' →send.ret(f,5)& rcv.cally (send.callg ⊥),∅, J1 ' →rcv.call(f,5)& rcv.cally (send.callg (rcv.callf ((λx. x+1) 5))), ∅, J1 ' →2& rcv.cally (send.callg (rcv.callf 6)),∅, J1 ' →send.ret(f,6)& rcv.cally (send.callg ⊥),∅, J1 ' →rcv.ret(g,6)& rcv.cally 6,∅, J1 ' →send.ret(y,6)& ⊥,∅, J1 '

& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '→send.ret(start,t) & ⊥,∅, I2 '

& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,& rcv.cally ((λt. t (λx. x+1) 4) t),& rcv.cally ((t (λx. x+1)) 4),& rcv.cally (send.callt ⊥) 4),

noting the initial evaluation of a module. Once the evaluation of eterminates, it will return send.ret(start , h) and wait for incoming
events. The meaning of a module e is then the set of all possible
event sequences !a that e can generate under the CSI machine:
[[−]]

:

Module → P(Trace)→rcv.call(t,f )→→send.ret(t,g)→rcv.call(g,4)→→send.call(f,4)& rcv.callt ((λf. λx. f (f x)) f ), ∅, I2 '& rcv.callt (λx. f (f x)),∅, I2 '
& ⊥,∅, J2 '
& rcv.callg ((λx. f (f x)) 4),∅, J2 '
& rcv.callg (f (f 4)),∅, J2 '
& rcv.callg (send.callf (f ⊥)), ∅, J2 '→rcv.ret(f,5)→send.call(f,5)& rcv.callg (f 5),& rcv.callg (send.callf ⊥),∅, J2 '∅, J2 '

→rcv.ret(f,6)→send.ret(g,6)& rcv.callg 6,& ⊥,∅, J2 '∅, J2 'are:
EV ( C, S, I )IV ( C, S, I )

def

=
def
=

dom(I)(F V (C) ∪ F V (rng(S)) ∪ F V (rng (I)))\ BV (S)17&E[x v],&E[send.callx ⊥],&Q[⊥],& Q[rcv.callx v],

S,
S,
S,
S,

I'
I'
I'
I'

→send.call(x,h)→rcv.ret(x,h)→rcv.call(x,h)→send.ret(x,h)& E[send.callx ⊥],&E[h],&Q[rcv.callx (v h)],&Q[⊥],

I[h % v] 'I'I'
I[h % v] '

S,
S,
S,
S,

x )∈ BV(S)
I(x) = v[SEND - CALL][RCV- RET]
[RCV- CALL][SEND - RET]

Figure 2: Example of Linking and Running Two CSI Machines Concurrently
The two CSI machines shown below cooperate to evaluate linkRun([[H]], [[twice]]). After the initial bootstrapping, send events of one machine match rcv
events of the other and vice-versa. The final send.ret(y, 6) event reports the result of the execution is 6.
Evaluation of H = (λt. t (λx. x+1) 4)
I1 = [y (→ (λt. t (λx. x+1) 4)]
J1 = [y (→ (λt. t (λx. x+1) 4), f (→ (λx. x+1)]

Evaluation of twice = (λf. λx. f (f x))
I2 = [t (→ (λf. λx. f (f x))]J2 = [t (→ (λf. λx. f (f x)), g (→ (λx. f (f x))]∅, ∅ ' →send.ret(start,y)∅, I1 ' →rcv.call(y,t)∅, I1 ' →∅, I1 ' →send.call(t,f )∅, J1 '
→rcv.ret(t,g)& rcv.cally (g 4),∅, J1 ' →send.call(g,4)& rcv.cally (send.callg ⊥),∅, J1 '
→rcv.call(f,4)& rcv.cally (send.callg (rcv.callf ((λx. x+1) 4))), ∅, J1 ' →2& rcv.cally (send.callg (rcv.callf 5)),∅, J1 ' →send.ret(f,5)& rcv.cally (send.callg ⊥),∅, J1 ' →rcv.call(f,5)& rcv.cally (send.callg (rcv.callf ((λx. x+1) 5))), ∅, J1 ' →2& rcv.cally (send.callg (rcv.callf 6)),∅, J1 ' →send.ret(f,6)& rcv.cally (send.callg ⊥),∅, J1 ' →rcv.ret(g,6)& rcv.cally 6,∅, J1 ' →send.ret(y,6)& ⊥,∅, J1 '

& rcv.callstart (λf. λx. f (f x)), ∅, ∅ '→send.ret(start,t) & ⊥,∅, I2 '

& rcv.callstart (λt. t (λx. x+1) 4),& ⊥,& rcv.cally ((λt. t (λx. x+1) 4) t),& rcv.cally ((t (λx. x+1)) 4),& rcv.cally (send.callt ⊥) 4),

noting the initial evaluation of a module. Once the evaluation of eterminates, it will return send.ret(start , h) and wait for incoming
events. The meaning of a module e is then the set of all possible
event sequences !a that e can generate under the CSI machine:
[[−]]

:

Module → P(Trace)→rcv.call(t,f )→→send.ret(t,g)→rcv.call(g,4)→→send.call(f,4)& rcv.callt ((λf. λx. f (f x)) f ), ∅, I2 '& rcv.callt (λx. f (f x)),∅, I2 '
& ⊥,∅, J2 '
& rcv.callg ((λx. f (f x)) 4),∅, J2 '
& rcv.callg (f (f 4)),∅, J2 '
& rcv.callg (send.callf (f ⊥)), ∅, J2 '→rcv.ret(f,5)→send.call(f,5)& rcv.callg (f 5),& rcv.callg (send.callf ⊥),∅, J2 '∅, J2 '

→rcv.ret(f,6)→send.ret(g,6)& rcv.callg 6,& ⊥,∅, J2 '∅, J2 'are:
EV ( C, S, I )IV ( C, S, I )

def

=
def
=

dom(I)(F V (C) ∪ F V (rng(S)) ∪ F V (rng (I)))\ BV (S)17

Step 2: Contracts are
Trace Predicates

18

⟦e⟧

19

K ∩ ⟦e⟧20

Universal Contract:⟦(λx. x)⟧21

Properties• Complete: Any computable predicate• Non-interference: No new behaviors

22

Step 3: Programming
Simple Contracts

23

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a
24

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a
24

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a
24

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a
24

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a
24

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a
24

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a
24

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a
24

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a
24

When
eventaccesses
transmitstoafunction
function referencesx, the second
component
hat it does
notangain
through
its enof M is called, which again has the opportunity to halt execution
ironment.
by retuning
Otherwise,
the function
returnpair ofBasedon thisfalse.
discussion,
the typeτ of theshould
monitor
Ma is:

monitors for handling call and ret events on the function x.
τ = The(Constant→ Bool)× then(Unit→ (False+ (τ argument
× τ )))
function guard
below
converts
its monitor
M into an appropriate contract implementation that queries M to
Whenverify
an event
transmitsaconstant,
thefirstcomponentofMthat each transmitted event is permitted:

alled to decide if that event is permitted. That function can us
1 guard M =mutableinternal state to track and enforce temporal propertie2
λx.
if(constant?
x)
thenhus, temporal properties of the contracts are implemented vi
3
assert ((fst M) x) != false
mperative
state
in
the
monitor.
4x
When anevent transmits a function x, the second componen
5
else
fM
is called,6
letwhich
MM = again(snd hasM)()the opportunity to halt executio
y 7retuning false.
the function should return a pair oassertOtherwise,
MM != false
8(guard(snd(guard(fstMM) y)))
monitorsfor λy.
handling
callandMM)
ret(xeventson thefunctionx.
The function guard below then converts its monitor argumen
M intoappropriate
contract implementation that queries M t
5.1 anExample
Monitors
erifyUsingthat eachtransmitted
event
ispermitted:
the monitor interface, it is straightforward to implement a24

Step 4: Programming
Temporal Contracts

25

Figure 3: Declarative HOT Contracts
M ::= S where R
S ::= flat (e) | n : S1 "→ S2∗
R ::= A | !A | RR | R | not R | R ∪ R| . . . | call(n, ?x) R | ret(n, ?x) R
A ::= call(n, p) | ret(n, p)
p ::= | x | cn ∈ Name

HOT contract
Structural contract
Temporal contract
Event patterns
Value patterns
Function names

the variable names of inter-module calls (or stack frames).
26

Figure 3: Declarative HOT Contracts
M ::= S where R
S ::= flat (e) | n : S1 "→ S2∗
R ::= A | !A | RR | R | not R | R ∪ R| . . . | call(n, ?x) R | ret(n, ?x) R
A ::= call(n, p) | ret(n, p)
p ::= | x | cn ∈ Name

HOT contract
Structural contract
Temporal contract
Event patterns
Value patterns
Function names

the variable names of inter-module calls (or stack frames).
26

that the trace
and which is parameterized over a number
otherwise.
Thesatisfies
code is S,
roughly:of calln and retn functions that communicate to the temporal
let
s
=
s
0
code above. The additional
argument
calln = λi. · · · check and update s appropriately · · ·f : .(Constant∪ {λx.x} )→ Bool)...
..
= function”
λo. · · · check
andcalled
updates appropriately·n
is anret“observerthat isandcan signal an· ·error. . . a value passes. . . through this S boundary; it is used in thewheneverin compile(λx.true,S)followingrecursive definitionof compile.
The
functioncompile(f,S)
generatesamonitorthat
ensurescompile : (Constant ∪ {λx.x} )→ Bool ) × S )→ Monitor
that the trace satisfies S,
def and which is parameterized over a number(e))=
ofcompile(f,calln andflat
retn functions that communicate to the temporal(e x) &&argument(f x))
code pairabove.(λx.
The additional(λ. false)f : (Constantdef ∪ {λx.x} )→ Bool)
compile(f, n : S1 )→ S2 ) =is an pair“observer(λx.function”
false) that is called and can signal an error
whenever a (λ.
value passes
through&&this(pair
S boundary;
it is usednin(f (λx.x))
compile(call, Sthe1)
following recursive definition of compile. compile(retn , S2 ))))
defcompile(f,y) =compile: (Constant∪ {λx.x} )→ Bool ) × S )→ Monitor
def
let (chkconst,chkfn)= ycompile(f, flat (e)) =pair (λx. (f x)&& (chkconst x))
pair (λx. (e x) && (f x))(λ. (f (λx.x)) && (chkfn()))(λ. false)
def

C
aft
fo
tio
fi
sub
the
S1
Rre
E
rig
c
cal
is
a
Co
fu
fol
(r
fin
re
in

m
req
coth
isT
asn
o
fun
th
(re
th
ret
T
inc
27

that the trace
and which is parameterized over a number
otherwise.
Thesatisfies
code is S,
roughly:of calln and retn functions that communicate to the temporal
let
s
=
s
0
code above. The additional
argument
calln = λi. · · · check and update s appropriately · · ·f : .(Constant∪ {λx.x} )→ Bool)...
..
= function”
λo. · · · check
andcalled
updates appropriately·n
is anret“observerthat isandcan signal an· ·error. . . a value passes. . . through this S boundary; it is used in thewheneverin compile(λx.true,S)followingrecursive definitionof compile.
The
functioncompile(f,S)
generatesamonitorthat
ensurescompile : (Constant ∪ {λx.x} )→ Bool ) × S )→ Monitor
that the trace satisfies S,
def and which is parameterized over a number(e))=
ofcompile(f,calln andflat
retn functions that communicate to the temporal(e x) &&argument(f x))
code pairabove.(λx.
The additional(λ. false)f : (Constantdef ∪ {λx.x} )→ Bool)
compile(f, n : S1 )→ S2 ) =is an pair“observer(λx.function”
false) that is called and can signal an error
whenever a (λ.
value passes
through&&this(pair
S boundary;
it is usednin(f (λx.x))
compile(call, Sthe1)
following recursive definition of compile. compile(retn , S2 ))))
defcompile(f,y) =compile: (Constant∪ {λx.x} )→ Bool ) × S )→ Monitor
def
let (chkconst,chkfn)= ycompile(f, flat (e)) =pair (λx. (f x)&& (chkconst x))
pair (λx. (e x) && (f x))(λ. (f (λx.x)) && (chkfn()))(λ. false)
def

C
aft
fo
tio
fi
sub
the
S1
Rre
E
rig
c
cal
is
a
Co
fu
fol
(r
fin
re
in

m
req
coth
isT
asn
o
fun
th
(re
th
ret
T
inc
27

that the trace
and which is parameterized over a number
otherwise.
Thesatisfies
code is S,
roughly:of calln and retn functions that communicate to the temporal
let
s
=
s
0
code above. The additional
argument
calln = λi. · · · check and update s appropriately · · ·f : .(Constant∪ {λx.x} )→ Bool)...
..
= function”
λo. · · · check
andcalled
updates appropriately·n
is anret“observerthat isandcan signal an· ·error. . . a value passes. . . through this S boundary; it is used in thewheneverin compile(λx.true,S)followingrecursive definitionof compile.
The
functioncompile(f,S)
generatesamonitorthat
ensurescompile : (Constant ∪ {λx.x} )→ Bool ) × S )→ Monitor
that the trace satisfies S,
def and which is parameterized over a number(e))=
ofcompile(f,calln andflat
retn functions that communicate to the temporal(e x) &&argument(f x))
code pairabove.(λx.
The additional(λ. false)f : (Constantdef ∪ {λx.x} )→ Bool)
compile(f, n : S1 )→ S2 ) =is an pair“observer(λx.function”
false) that is called and can signal an error
whenever a (λ.
value passes
through&&this(pair
S boundary;
it is usednin(f (λx.x))
compile(call, Sthe1)
following recursive definition of compile. compile(retn , S2 ))))
defcompile(f,y) =compile: (Constant∪ {λx.x} )→ Bool ) × S )→ Monitor
def
let (chkconst,chkfn)= ycompile(f, flat (e)) =pair (λx. (f x)&& (chkconst x))
pair (λx. (e x) && (f x))(λ. (f (λx.x)) && (chkfn()))(λ. false)
def

C
aft
fo
tio
fi
sub
the
S1
Rre
E
rig
c
cal
is
a
Co
fu
fol
(r
fin
re
in

m
req
coth
isT
asn
o
fun
th
(re
th
ret
T
inc
27

that the trace
and which is parameterized over a number
otherwise.
Thesatisfies
code is S,
roughly:of calln and retn functions that communicate to the temporal
let
s
=
s
0
code above. The additional
argument
calln = λi. · · · check and update s appropriately · · ·f : .(Constant∪ {λx.x} )→ Bool)...
..
= function”
λo. · · · check
andcalled
updates appropriately·n
is anret“observerthat isandcan signal an· ·error. . . a value passes. . . through this S boundary; it is used in thewheneverin compile(λx.true,S)followingrecursive definitionof compile.
The
functioncompile(f,S)
generatesamonitorthat
ensurescompile : (Constant ∪ {λx.x} )→ Bool ) × S )→ Monitor
that the trace satisfies S,
def and which is parameterized over a number(e))=
ofcompile(f,calln andflat
retn functions that communicate to the temporal(e x) &&argument(f x))
code pairabove.(λx.
The additional(λ. false)f : (Constantdef ∪ {λx.x} )→ Bool)
compile(f, n : S1 )→ S2 ) =is an pair“observer(λx.function”
false) that is called and can signal an error
whenever a (λ.
value passes
through&&this(pair
S boundary;
it is usednin(f (λx.x))
compile(call, Sthe1)
following recursive definition of compile. compile(retn , S2 ))))
defcompile(f,y) =compile: (Constant∪ {λx.x} )→ Bool ) × S )→ Monitor
def
let (chkconst,chkfn)= ycompile(f, flat (e)) =pair (λx. (f x)&& (chkconst x))
pair (λx. (e x) && (f x))(λ. (f (λx.x)) && (chkfn()))(λ. false)
def

C
aft
fo
tio
fi
sub
the
S1
Rre
E
rig
c
cal
is
a
Co
fu
fol
(r
fin
re
in

m
req
coth
isT
asn
o
fun
th
(re
th
ret
T
inc
27

that the trace
and which is parameterized over a number
otherwise.
Thesatisfies
code is S,
roughly:of calln and retn functions that communicate to the temporal
let
s
=
s
0
code above. The additional
argument
calln = λi. · · · check and update s appropriately · · ·f : .(Constant∪ {λx.x} )→ Bool)...
..
= function”
λo. · · · check
andcalled
updates appropriately·n
is anret“observerthat isandcan signal an· ·error. . . a value passes. . . through this S boundary; it is used in thewheneverin compile(λx.true,S)followingrecursive definitionof compile.
The
functioncompile(f,S)
generatesamonitorthat
ensurescompile : (Constant ∪ {λx.x} )→ Bool ) × S )→ Monitor
that the trace satisfies S,
def and which is parameterized over a number(e))=
ofcompile(f,calln andflat
retn functions that communicate to the temporal(e x) &&argument(f x))
code pairabove.(λx.
The additional(λ. false)f : (Constantdef ∪ {λx.x} )→ Bool)
compile(f, n : S1 )→ S2 ) =is an pair“observer(λx.function”
false) that is called and can signal an error
whenever a (λ.
value passes
through&&this(pair
S boundary;
it is usednin(f (λx.x))
compile(call, Sthe1)
following recursive definition of compile. compile(retn , S2 ))))
defcompile(f,y) =compile: (Constant∪ {λx.x} )→ Bool ) × S )→ Monitor
def
let (chkconst,chkfn)= ycompile(f, flat (e)) =pair (λx. (f x)&& (chkconst x))
pair (λx. (e x) && (f x))(λ. (f (λx.x)) && (chkfn()))(λ. false)
def

C
aft
fo
tio
fi
sub
the
S1
Rre
E
rig
c
cal
is
a
Co
fu
fol
(r
fin
re
in

m
req
coth
isT
asn
o
fun
th
(re
th
ret
T
inc
27

Step 5: Racket
Implementation28

Differences• No non-interference

guarantee (inheritedfrom Racket contracts)• Continuations allow 0,
1, and many returns• Mutation intermediation
through standard
contracts• Safe w.r.t concurrency
with kill-safe server• Temporal formula

macros like and using
De Morgan’s law• Recursive temporal

formulas with delays

29Step 6: Evaluation30

Racket Standard
Library
Atomic519

number?

Transient

51

map

Anti-transient

17

curry

Unconstrained

13

apply

31

Monitors

HOT

HOT w/ dseq

3000.00ms

2275.00ms

1550.00ms

825.00ms

2007

Atomicity32Adversarial Defense• Tic-Tac-Toe game
• Player : Board →• May not call

• May only call

• Catches cheating

Board

board-set once

board-set withsame arguments in
one gamehumans and AIs
with contracts

33

Future Work• Interaction with types• Concurrency• Explain contract violations

34