Space-Efficient Manifest Contracts
Michael Greenberg
Princeton University
April 5, 2017

arXiv:1410.2813v2 [cs.PL] 4 Apr 2017

Abstract
The standard algorithm for higher-order contract checking can lead to unbounded space consumption and
can destroy tail recursion, altering a program’s asymptotic space complexity. While space efficiency for gradual
types—contracts mediating untyped and typed code—is well studied, sound space efficiency for manifest contracts—
contracts that check stronger properties than simple types, e.g., “is a natural” instead of “is an integer”—remains
an open problem.
We show how to achieve sound space efficiency for manifest contracts with strong predicate contracts. The
essential trick is breaking the contract checking down into coercions: structured, blame-annotated lists of checks.
By carefully preventing duplicate coercions from appearing, we can restore space efficiency while keeping the same
observable behavior.
Along the way, we define a framework for space efficiency, traversing the design space with three different
space-efficient manifest calculi. We examine the diverse correctness criteria for contract semantics; we conclude
with a coercion-based language whose contracts enjoy (galactically) bounded, sound space consumption—they are
observationally equivalent to the standard, space-inefficient semantics.
This is an extended version of Greenberg [2015], with a great deal of material that does not appear in the
conference paper: an exploration of the design space with two other space-efficient calculi and complete proofs.

1

Introduction

Types are an extremely successful form of lightweight specification: programmers can state their intent—e.g., plus is
a function that takes two numbers and returns another number—and then type checkers can ensure that a program
conforms to the programmer’s intent. Types can only go so far though: division is, like addition, a function that takes
two numbers and returns another number... so long as the second number isn’t zero. Conventional type systems do
a good job of stopping many kinds of errors, but most type systems cannot protect partial operations like division
and array indexing. Advanced techniques—singleton and dependent types, for example—can cover many of these
cases, allowing programmers to use types like “non-zero number” or “index within bounds” to specify the domains
on which partial operations are safe. Such techniques are demanding: they can be difficult to understand, they force
certain programming idioms, and they place heavy constraints on the programming language, requiring purity or
even strong normalization.
Contracts are a popular compromise: programmers write type-like contracts of the form Int → {x :Int | x 6=
0} → Int, where the predicates x 6= 0 are written in code. These type-like specifications can then be checked at
runtime Findler and Felleisen [2002]. Models of contract calculi have taken two forms: latent and manifest Greenberg
et al. [2012]. We take the manifest approach here, which means checking contracts with casts, written hT1 ⇒T2 il e.
Checking a predicate contract (also called a refinement type, though that term is overloaded) like {x :Int | x 6= 0}
on a number n involves running the predicate x 6= 0 with n for x . Casts from one predicate contract to another,
h{x :B | e1 }⇒{x :B | e2 }il , take a constant k and check to see that e2 [k /x ] −→∗ true. It’s hard to know what to do
with function casts at runtime: in hT11 →T12 ⇒T21 →T22 il e, we know that e is a T11 →T12 , but what does that tell
us about treating e as a T21 →T22 ? Findler and Felleisen’s insight is that we must defer checking, waiting until the
cast value e gets an argument Findler and Felleisen [2002]. These deferred checks are recorded on the value by means
of a function proxy, i.e., hT11 →T12 ⇒T21 →T22 il e is a value when e is a value; applying a function proxy unwraps
it contravariantly. We check the domain contract T1 on e, run the original function f on the result, and then check
that result against the codomain contract T2 :
(hT11 →T12 ⇒T21 →T22 il e1 ) e2 −→
hT12 ⇒T22 il (e1 (hT21 ⇒T11 il e2 ))
Findler and Felleisen neatly designed a system for contract checking in a higher-order world, but there is a problem:
contract checking is space inefficient Herman et al. [2007].

1

Contract checking’s space inefficiency can be summed up as follows: function proxies break tail calls. Calls to
an unproxied function from a tail position can be optimized to not allocate stack frames. Proxied functions, however,
will unwrap to have codomain contracts—breaking tail calls. We discuss other sources of space inefficiency below,
but breaking tail calls is the most severe. Consider factorial written in accumulator passing style. The developer may
believe that the following can be compiled to use tail calls:
fact : {x :Int | x ≥ 0}→{x :Int | x ≥ 0}→{x :Int | x ≥ 0}
= λx :{x :Int | true}. λy:{y:Int | true}.
if x = 0 then y else fact (x − 1) (x ∗ y)
A cast insertion algorithm Swamy et al. [2009] might produce the following non-tail recursive function:
fact =
h{x :Int | true}→{y:Int | true}→{z :Int | true}⇒
{x :Int | x ≥ 0}→{y:Int | y ≥ 0}→{z :Int | x ≥ 0}ilfact
λx :{x :Int | true}. λy:{y:Int | true}.
if x = 0 then y else
(h{x :Int | x ≥ 0}⇒{x :Int | true}ilfact (fact . . . ))
Tail-call optimization is essential for usable functional languages. Space inefficiency has been one of two significant
obstacles for pervasive use of higher-order contract checking. (The other is state, which we do not treat here.)
In this work, we show how to achieve semantics-preserving space efficiency for non-dependent contract checking.
Our approach is inspired by work on gradual typing Siek and Taha [2006], a form of (manifest) contracts designed
to mediate dynamic and simple typing—that is, gradual typing (a) allows the dynamic type, and (b) restricts the
predicates in contracts to checks on type tags. Herman et al. [2007] developed the first space-efficient gradually typed
system, using Henglein’s coercions Henglein [1994]; Siek and Wadler [2010] devised a related system supporting
blame. The essence of the solution is to allow casts to merge: given two adjacent casts hT2 ⇒T3 il2 (hT1 ⇒T2 il1 e),
we must somehow combine them into a single cast. Siek and Wadler annotate their casts with an intermediate type
representing the greatest lower bound of the types encountered. Such a trick doesn’t work in our more general setting:
simple types plus dynamic form a straightforward lattice using type precision as the ordering, but it’s less clear what
to do when we have arbitrary predicate contracts.
We offer three modes of space-efficiency; all of the modes are defined in a single calculus which we call λH . Each
mode enjoys varying levels of soundness with respect to the standard, space-inefficient semantics of classic λH . We
sketch here the mode-indexed rules for combining annotations on casts—the key rules for space efficiency.
The forgetful mode uses empty annotations, •; we combine two casts by dropping intermediate types:
•

•

•

hT2 ⇒T3 il2 (hT1 ⇒T2 il1 e) −→F hT1 ⇒T3 il2 e
Surprisingly, this evaluation rule is type safe and somewhat sound with respect to the classic mode, as discovered by
Greenberg [2013]: if classic λH produces a value, so does forgetful λH .
The heedful mode uses sets of types Si as its annotations, making sure to save the intermediate type:
S

S

2
1
l2
l1
hT2 ⇒T
(hT1 ⇒T
e) −→H hT1
3i
2i

S1 ∪S2 ∪{T2 }

T3 il2 e

⇒

In Siek and Wadler’s terms, we use the powerset lattice for annotations, while they use pointed types. Heedful and
classic λH are almost identical, except sometimes they blame different labels.
Finally, the eidetic mode annotates casts with refinement lists and function coercions—a new form of coercion
inspired by Greenberg [2013]. The coercions keep track of checking so well that the type indices and blame labels on
casts are unnecessary:
c

c

2
1
•
•
hT2 ⇒T
3 i (hT1 ⇒T2 i e) −→E hT1

join(c1 ,c2 )

⇒

T3 i• e

These coercions form a skew lattice: refinement lists have ordering constraints that break commutativity. Eidetic λH
is space efficient and observationally equivalent to the classic mode.
Since eidetic and classic λH behave the same, why bother with forgetful and heedful? First and foremost, the
calculi offer insights into the semantics of contracts: the soundness of forgetful λH depends on a certain philosophy
of contracts; heedful λH relates to threesomes without blame Siek and Wadler [2010]. Second, we offer them as
alternative points in the design space. Finally and perhaps cynically, they are strawmen—warm up exercises for
eidetic λH .
We claim two contributions:
2

1. Eidetic λH is the first manifest contract calculus that is both sound and space efficient with respect to the
classic semantics—a result contrary to Greenberg [2013], who conjectured that such a result is impossible. We
believe that space efficiency is a critical step towards the implementation of practical languages with manifest
contracts.
2. A framework for defining space efficiency in manifest contract systems, with an exploration of the design space.
We identify common structures and methods in the operational semantics as well as in the proofs of type
soundness, soundness with regard to the classic framework, and space bounds.
We do not prove a blame theorem ?, since we lack the clear separation of dynamic and static typing found in gradual
typing. We conjecture that such a theorem could be provedfor classic and eidetic λH —but perhaps not for forgetful
and heedful λH , which skip checks and change blame labels. Our model has two limits worth mentioning: we do not
handle dependency, a common and powerful feature in manifest systems; and, our bounds for space efficiency are
galactic—they establish that contracts consume constant space, but do nothing to reduce that constant Lipton [2010].
Our contribution is showing that sound space efficiency is possible where it was believed to be impossible Greenberg
[2013]; we leave evidence that it is practicable for future work.
Our proofs are available in the extended version Greenberg [2014], Appendices A–C.
Readers who are very familiar with this topic can read Figures 1, 2, and 4 and then skip directly to Section 3.5.
Readers who understand the space inefficiency of contracts but aren’t particularly familiar with manifest contracts
can skip Section 2 and proceed to Section 3.

2

Function proxies

Space inefficient contract checking breaks tail recursion—a showstopping problem for realistic implementations of
pervasive contract use. Racket’s contract system PLT [b], the most widely used higher-order contract system, takes
a “macro” approach to contracts: contracts typically appear only on module interfaces, and aren’t checked within a
module. Their approach comes partly out of a philosophy of breaking invariants inside modules but not out of them,
but also partly out of a need to retain tail recursion within modules. Space inefficiency has shaped the way their
contract system has developed. They do not use our “micro” approach, wherein annotations and casts permeate the
code.
Tail recursion aside, there is another important source of space inefficiency: the unbounded number of function
proxies. Hierarchies of libraries are a typical example: consider a list library and a set library built using increasingly
sorted lists. We might have:
null : α List→{x :Bool | true}
= ...
head : {x :α List | not (null x )}→α
= ...
empty : α Set→{x :Bool | true}
= null
min : {x :α Set | not (empty x )}→α = head
Our code reuse comes with a price: even though the precondition on min is effectively the same as that on head,
we must have two function proxies, and the non-emptiness of the list representing the set is checked twice: first
by checking empty, and again by checking null (which is the same function). Blame systems like those in Racket
encourage modules to declare contracts to avoid being blamed, which can result in redundant checking like the above
when libraries requirements imply sub-libraries’ requirements.
Or consider a library of drawing primitives based around painters, functions of type Canvas→Canvas. An underlying graphics library offers basic functions for manipulating canvases and functions over canvases, e.g., primFlipH is
a painter transformer—of type (Canvas→Canvas)→(Canvas→Canvas)—that flips the generated images horizontally.
A wrapper library may add derived functions while re-exporting the underlying functions with refinement types
specifying a canvas’s square dimensions, where SquareCanvas = {x :Canvas | width(x ) = height(x )}:
flipH p = hCanvas→Canvas⇒
SquareCanvas→SquareCanvasil
(primFlipH
(hSquareCanvas→SquareCanvas⇒
Canvas→Canvasil p))
The wrapper library only accepts painters with appropriately refined types, but must strip away these refinements
before calling the underlying implementation—which demands Canvas→Canvas painters. The wrapper library then

3

has to cast these modified functions back to the refined types. Calling flipH (flipH p) yields:
hCanvas→Canvas⇒SquareCanvas→SquareCanvasil
(primFlipH
(hSquareCanvas→SquareCanvas⇒Canvas→Canvasil
(hCanvas→Canvas⇒SquareCanvas→SquareCanvasil
(primFlipH
(hSquareCanvas→SquareCanvas⇒
Canvas→Canvasil p)))))
That is, we first cast p to a plain painter and return a new painter p 0 . We then cast p 0 into and then immediately
out of the refined type, before continuing on to flip p 0 . All the while, we are accumulating many function proxies
beyond the wrapping done by the underlying implementation of primFlipH. Redundant wrapping can become quite
extreme, especially for continuation-passing programs. Function proxies are the essential problem: nothing bounds
their accumulation. Unfolding unboundedly many function proxies creates stacks of unboundedly many checks—
which breaks tail calls. If we can have a constant number of function proxies that produce stacks of checks of a
constant size, then we can have tail call optimization. A space-efficient scheme for manifest contracts bounds the
number of function proxies that can accumulate.
We can also adapt Herman et al.’s mutually recursive even and odd functions, writing them with type ascriptions
in the following apparently tail recursive program consuming constant space:
odd = λx :{x :Int | true}. if (x = 0)
then false : {b:Bool | b ∨ (x mod 2 = 0)}
else even (x − 1)
even : {x :Int | true}→{b:Bool | b ∨ (x − 1 mod 2 = 0)} =
λx :{x :Int | true}. if (x = 0) then true else odd (x − 1)
A cast insertion algorithm Swamy et al. [2009] might produce:
odd = λx :{x :Int | true}. if (x = 0)
then h{b:Bool | true}⇒
{b:Bool | b ∨ (x mod 2 = 0)}il1 false
else even (x − 1)
even = h{x :Int | true}→{b:Bool | true}⇒
{x :Int | true}→
{b:Bool | b ∨ ((x + 1) mod 2 = 0)}il2
(λx :{x :Int | true}. if (x = 0)
then true
else h{b:Bool | b ∨ (x − 1 mod 2 = 0)}⇒
{b:Bool | true}il3 (odd (x − 1)))
Note that the casts labeled l2 and l3 both break tail recursion: the former leads to unwrapping whenever even is
called, while the latter moves the call to odd from tail position. Breaking tail-call optimization is very bad: we went
from constant space to linear space. That is, inserting contract checks can change a program’s asymptotic space
efficiency!

3

Classic manifest contracts

The standard manifest contract calculus, λH , is originally due to Flanagan Flanagan [2006]. We give the syntax
for the non-dependent fragment in Figure 1. We have highlighted in yellow the four syntactic forms relevant to
contract checking. This paper paper discusses four modes of λH : classic λH , mode C; forgetful λH , mode F; heedful
λH , mode H;and eidetic λH , mode E. Each of these languages uses the syntax of Figure 1, while the typing rules
and operational semantics are indexed by the mode m. The proofs and metatheory are also mode-indexed. In an
extended version of this work, we develop two additional modes with slightly different properties from eidetic λH ,
filling out a “framework” for space-efficient manifest contracts Greenberg [2014]. We omit the other two modes here
to save space for eidetic λH , which is the only mode that is sound with respect to classic λH . We summarize how
each of these modes differ in Section 3.2—but first we (laconically) explain the syntax and the interesting bits of the
operational semantics.

4

Modes
m ::=
|
|
|
Types
B ::=
T ::=
Terms
e ::=

C
F
H
E

classic λH ; Section 3
forgetful λH ; Section 4
heedful λH ; Section 5
eidetic λH ; Section 6

Bool | . . .
{x :B | e} | T1 →T2

x | k | λx :T . e | e1 e2 | op(e1 , . . . , en ) |
a
hT1 ⇒T2 il e | h{x :B | e1 }, e2 , k il | ⇑l |
h{x :B | e1 }, s, r , k , ei•
Annotations: type set, coercions, and refinement lists
a ::= • | S | c
S ::= ∅ | {T1 , ..., Tn }
c ::= r | c1 7→ c2
r ::= nil | {x :B | e}l , r
Statuses
s ::= X | ?
Locations
l ::= • | l1 | ...

Figure 1: Syntax of λH
The metavariable B is used for base types, of which at least Bool must be present. There are two kinds of types.
First, predicate contracts {x :B | e}, also called refinements of base types or just refinement types, denotes constants k
of base type B such that e[k /x ] holds—that is, such that e[k /x ] −→∗m true for any mode m. Function types T1 →T2
are standard.
The terms of λH are largely those of the simply-typed lambda calculus: variables, constants k , abstractions,
applications, and operations should all be familiar. The first distinguishing feature of λH ’s terms is the cast, written
a
hT1 ⇒T2 il e. Here e is a term of type T1 ; the cast checks whether e can be treated as a T2 —if e doesn’t cut it,
the cast will use its label l to raise the uncatchable exception ⇑l , read “blame l ”. Our casts also have annotations
a. Classic and forgetful λH don’t need annotations—we write • and say “none”. Heedful λH uses type sets S to
track space-efficiently pending checks.Eidetic λH uses coercions c, based on coercions in Henglein [1994]. We explain
coercions in greater detail in Section 6, but they amount to lists of blame-annotated refinement types r and function
coercions.
The three remaining forms—active checks, blame, and coercion stacks—only occur as the program evaluates.
Casts between refinement types are checked by active checks h{x :B | e1 }, e2 , k il . The first term is the type being
checked—necessary for the typing rule. The second term is the current status of the check; it is an invariant
that e1 [k /x ] −→∗m e2 . The final term is the constant being checked, which is returned wholesale if the check
succeeds. When checks fail, the program raises blame, an uncatchable exception written ⇑l . A coercion stack
h{x :B | e1 }, s, r , k , ei• represents the state of checking a coercion; we only use it in eidetic λH , so we postpone
discussing it until Section 6.

3.1

Core operational semantics

Our mode-indexed operational semantics for our manifest calculi comprise three relations: valm e identifies terms that
are values in mode m (or m-values), resultm e identifies m-results, and e1 −→m e2 is the small-step reduction relation
for mode m. It is more conventional to fix values as a syntactic subset, but that approach would be confusing here:
we would need three different metavariables to unambiguously refer to values from each language. The mode-indexed
value and result relations neatly avoid any potential confusion between metavariables. Each mode defines its own
value rule for function proxies. Figure 2 defines the core rules. The rules for classic λH (m = C) are in salmon; the
shared space-efficient rules are in periwinkle. To save space, we pass over standard rules.
The mode-agnostic value rules are straightforward: constants are always values (V Const), as are lambdas
(V Abs). Each mode defines its own value rule for function proxies, V Proxym. The classic rule, V ProxyC, says
that a function proxy
•
hT11 →T12 ⇒T21 →T22 il e
is a C-value when e is a C-value. That is, function proxies can wrap lambda abstractions and other function proxies
5

Values and results

valm e

resultm e
valC e

V Const

valm k

V Abs

valm λx :T . e

valm e
resultm e

•

valC hT11 →T12 ⇒T21 →T22 il e

R Val

V ProxyC

R Blame

resultm ⇑l

e1 −→m e2

Shared operational semantics

valm e2
(λx :T . e12 ) e2 −→m e12 [e2 /x ]

valm e1 ... valm en
op(e1 , ... , en ) −→m [[op]] (e1 , ... , en )

E Beta
a

valm hT11 →T12 ⇒T21 →T22 il e1

valm e2

cod(a)

a

E Op

E Unwrap

dom(a)

(hT11 →T12 ⇒T21 →T22 il e1 ) e2 −→m hT12 ⇒ T22 il (e1 (hT21 ⇒ T11 il e2 ))
dom(•)
dom(S)
dom(c1 7→ c2 )

•
S

=
=
=

T ∈S
c1

cod(•)
cod(S)
cod(c1 7→ c2 )

dom(T )

•

h{x :B | e1 }⇒{x :B | e2 }il k −→C h{x :B | e2 }, e2 [k /x ], k il
E CheckOK

h{x :B | e}, true, k il −→m k
e1 −→m e10
e1 e2 −→m e10 e2

e −→C e 0
hT1 ⇒T2

il

•

e −→C hT1 ⇒T2

e0

il

valm e1 e2 −→m e20
e1 e2 −→m e1 e20

a0

a

a

a3 = mergem (T1 , a1 , T2 , a2 , T3 )
a

a

2
1
3
l
l0
l
hT2 ⇒T
3 i (hT1 ⇒T2 i e2 ) −→m hT1 ⇒T3 i e2

⇑l e2 −→m ⇑l

E AppRaiseL

valm e1
e1 ⇑l −→m ⇑l

valm e1 ... valm ei−1
op(e1 , . . . , ei−1 , ⇑l, . . . , en ) −→m ⇑l

E CheckFail

E AppR

E OpInner

E AppRaiseR

E OpRaise

E CheckInner

0

e2 6= hT1 ⇒T2 il e200

hT2 ⇒T3 il e2 −→m hT2 ⇒T3 il e20
a

cod(T )

e2 −→m e20
h{x :B | e1 }, e2 , k il −→m h{x :B | e1 }, e20 , k il

E CastInnerC

e2 −→m e20

T ∈S

c2

h{x :B | e}, false, k il −→m ⇑l

E AppL

m 6= C

•
S

E CheckNoneC

valm e1 ... valm ei−1 ei −→m ei0
op(e1 , . . . , ei−1 , ei , . . . , en ) −→m op(e1 , . . . , ei−1 , ei0 , . . . , en )

•

=
=
=

E CastInner

E CastMerge

S

hT1 ⇒T2 il ⇑l 0 −→m ⇑l 0

h{x :B | e}, ⇑l, k il 0 −→m ⇑l

E CastRaise

E CheckRaise

Figure 2: Core operational semantics of λH ; classic λH rules are salmon; space-efficient rules are periwinkle

6

alike. Other modes only allow lambda abstractions to be proxiedwhile requiring that the annotations are appropriate.
All of the space-efficient calculi in the literature take our approach, where a function cast applied to a value is a
value; some space inefficient ones do, too Findler and Felleisen [2002], Gronski and Flanagan [2007], Greenberg et al.
[2012]. In other formulations of λH in the literature, function proxies are implemented by introducing a new lambda
as a wrapper à la Findler and Felleisen’s wrap operator Findler and Felleisen [2002], Flanagan [2006], Siek and Taha
[2006], Belo et al. [2011]. Such an η-expansion semantics is convenient, since then applications only ever reduce by
β-reduction. But it wouldn’t suit our purposes at all: space efficiency demands that we combine function proxies.
We can also imagine a third, ungainly semantics that looks into closures rather than having explicit function proxies.
Results don’t depend on the mode: m-values are always m-results (R Val); blame is always a result, too (R Blame).
E Beta applies lambda abstractions via substitution, using a call-by-value rule. Note that β reduction in mode m
requires that the argument is an m-value. The reduction rule for operations (E Op) defers to operations’ denotations,
[[op]]; since these may be partial (e.g., division), we assign types to operations that guarantee totality (see Section 3.3).
That is, partial operations are a potential source of stuckness, and the types assigned to operations must guarantee
the absence of stuckness. Robin Milner famously stated that “well typed expressions don’t go wrong” Milner [1978];
his programs could go wrong by (a) applying a boolean like a function or (b) conditioning on a function like a
boolean. Systems with more base types can go wrong in more ways, some of which are hard to capture in standard
type systems. Contracts allow us to bridge that gap. Letting operations get stuck is a philosophical stance—contracts
expand the notion of “wrong”—that supports our forgetful semantics (Section 4).
E Unwrap applies function proxies to values, contravariantly in the domain and covariantly in the codomain.
We also split up each cast’s annotation, using dom(a) and cod(a). E CheckNone turns a cast between refinement
types into an active check with the same blame label. We discard the source type—we already know that k is a
{x :B | e1 }—and substitute the scrutinee into the target type, e2 [k /x ], as the current state of checking. We must also
hold onto the scrutinee, in case the check succeeds. We are careful to not apply this rule in heedful and eidetic modes,
which must generate annotations before running checks; we discuss these more in those modes’ sections. Active checks
evaluate by the congruence rule E CheckInner until one of three results adheres: the predicate returns true, so the
whole active check returns the scrutinee (E CheckOK); the predicate returns false, so the whole active check raises
blame using the label on the chceck (E CheckFail); or blame was raised during checking, and we propagate it via
E CheckRaise. heedful and eidetic use slightly different forms, described in their respective sections.
The core semantics includes several other congruence rules: E AppL, E AppR, and E OpInner. Since space
bounds rely not only on limiting the number of function proxies but also on accumulation of casts on the stack, the
core semantics doesn’t include a cast congruence rule. The congruence rule for casts in classic λH , E CastInnerC,
allows for free use of congruence. In the space-efficient calculi, the use of congruence is instead limited by the
rules E CastInner and E CastMerge. Cast arguments only take congruent steps when they aren’t casts themselves. A cast applied to another cast merges, using the merge function. Each space-efficient calculus uses a different
annotation scheme, so each one has a different merge function. We deliberately leave merge undefined sometimes—
heedful and eidetic λH must control when E CastMerge can apply. Note that we don’t need to specify m 6= C in
E CastMerge—we just don’t define a merge operator for classic λH . We have E CastMerge arbitrarily retain the
label of the outer cast. No choice is “right” here—we discuss this issue further in Section 5. In addition to congruence rules, there are blame propagation rules, which are universal: E AppRaiseL, E AppRaiseR, E CastRaise,
E OpRaise. These rules propagate the uncatchable exception ⇑l while obeying call-by-value rules.

3.2

Cast merges by example

Each mode’s section explains its semantics in detail, but we can summarize the cast merging rules here by example.
Consider the following term:
•
e = h{x :Int | x mod 2 = 0}⇒{x :Int | x 6= 0}il3
•
(h{x :Int | x ≥ 0}⇒{x :Int | x mod 2 = 0}il2
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1))
Here e runs three checks on integer −1: first for non-negativity (blaming l1 on failure), then for evenness (blaming l2
on failure), and then for non-zeroness (blaming l3 on failure). Classic and eidetic λH both blame l1 ; heedful λH also
raises blame, though it blames a different label, l3 ; forgetful λH actually accepts the value, returning −1. We discuss
the operational rules for modes other than C in detail in each mode’s section; for now, we repeat the derived rules
for merging casts from Section 1.
Classic λH evaluates the casts step-by-step: first it checks whether −1 is positive, which fails, so e −→∗C ⇑l1 (see
Figure 3). We first step by E CheckNone, starting checking at the innermost cast. Using congruence rules, we run
E Op to reduce the contract’s predicate, finding false. E CheckFail then raises blame and E CastRaise propagates

7

•

e = h{x :Int | x mod 2 = 0}⇒{x :Int | x 6= 0}il3
•
(h{x :Int | x ≥ 0}⇒{x :Int | x mod 2 = 0}il2
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1))
(E CastInnerC/E CheckNone)
•
−→C h{x :Int | x ≥ 0}⇒{x :Int | x 6= 0}il3
•
(h{x :Int | x ≥ 0}⇒{x :Int | x mod 2 = 0}il2
h{x :Int | x ≥ 0}, −1 ≥ 0, −1il1 )
(E CastInnerC/E CheckInner/E Op)
−→C . . . h{x :Int | x ≥ 0}, false, −1il1
(E CastInnerC/E CheckFail)
−→C . . . ⇑l1
(E CastRaise)
−→∗C ⇑l1

Figure 3: An example of classic λH
it. Forgetful λH doesn’t use annotations at all—it just forgets the intermediate casts, effectively using the following
rule:
•
•
•
hT2 ⇒T3 il2 (hT1 ⇒T2 il1 e) −→F hT1 ⇒T3 il2 e
It never checks for non-negativity or evenness, skipping straight to the check that −1 is non-zero.
•

e −→F h{x :Int | x ≥ 0}⇒{x :Int | x 6= 0}il3
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1)
•
−→F h{x :Int | true}⇒{x :Int | x 6= 0}il3 −1
−→∗F −1
Heedful λH works by annotating casts with a set of intermediate types, effectively using the rule:
S

S

1
2
l1
l2
e) −→H hT1
(hT1 ⇒T
hT2 ⇒T
2i
3i

S1 ∪S2 ∪{T2 }

T3 il2 e

⇒

Every type in a type set needs to be checked, but the order is essentially nondeterministic: heedful λH checks that
−1 is non-negative and even in some order. Whichever one is checked first fails; both cases raise ⇑l3 .
{{x :Int|x mod 2=0}}

e −→∗H h{x :Int | x ≥ 0}
⇒
{x :Int | x 6= 0}il3
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1)
S

−→∗H h{x :Int | true}⇒{x :Int | x 6= 0}il3 −1
where S = {{x :Int | x mod 2 = 0}, {x :Int | x ≥ 0}}
Finally, eidetic λH uses coercions as its annotations; coercions c are detailed checking plans for running checks
in the same order as classic λH while skipping redundant checks. As we will see in Section 6, eidetic λH generates
coercions and then drops blame labels, giving us the rule:
c

c

2
1
•
•
hT2 ⇒T
3 i (hT1 ⇒T2 i e) −→E hT1

join(c1 ,c2 )

⇒

T 3 i• e

There are no redundant checks in the example term e, so eidetic λH does exactly the same checking as classic, finding
e −→∗E ⇑l1 .

3.3

Type system

All modes share a type system, given in Figure 4. All judgments are universal and simply thread the mode through—
except for annotation well formedness `m a k T1 ⇒ T2 , which is mode specific, and a single eidetic-specific rule given
in Figure 9in Section 6. The type system comprises several relations: context well formedness `m Γ and type well
formedness `m T ; type compatibility ` T1 k T2 , a mode-less comparison of the skeleton of two types; annotation
well formedness `m a k T1 ⇒ T2 ; and term typing Γ `m e : T .
Context well formedness is entirely straightforward; type well formedness requires some care to get base types off
the ground. We establish as an axiom that the raw type {x :B | true} is well formed for every base type B (WF Base);
we then use raw types to check that refinements are well formed: {x :B | e} is well formed in mode m if e is well
typed as a boolean in mode m when x is a value of type B (WF Refine). Without WF Base, WF Refine wouldn’t
8

`m Γ

Context and type well formedness

`m Γ `m T
`m Γ, x :T

WF Empty

`m ∅

`m {x :B | true}

`m T

WF Base

x :{x :B | true} `m e : {x :Bool | true}
`m {x :B | e}

` {x :B | e1 } k {x :B | e2 }
Expression typing
`m Γ x :T ∈ Γ
Γ `m x : T
`m Γ

` T11 k T21 ` T12 k T22
` T11 →T12 k T21 →T22

S Refine

WF Fun

`m a k T 1 ⇒ T 2
S Fun

` T1 k T2 `m T1 `m T2
`m • k T1 ⇒ T2

A None

Γ `m e : T
`m T1 Γ, x :T1 `m e12 : T2
Γ `m λx :T1 . e12 : T1 →T2

T Var

`m {x :B | e} ty(k ) = B e[k /x ] −→∗m true
Γ `m k : {x :B | e}
Γ `m e1 : (T1 →T2 ) Γ `m e2 : T1
Γ `m e1 e2 : T2
`m Γ

`m T1 `m T2
`m T1 →T2

WF Refine

` T1 k T2

Type compatibility and annotation well formedness

WF Extend

T Const

`m Γ `m T
Γ `m ⇑l : T

T Abs

T Blame

ty(op) = T1 → ... → Tn →T Γ `m ei : Ti
Γ `m op(e1 , . . . , en ) : T
`m a k T1 ⇒ T2

T App

Γ `m e : T1

a

Γ `m hT1 ⇒T2 il e : T2

`m {x :B | e1 } ty(k ) = B ∅ `m e2 : {x :Bool | true}
Γ `m h{x :B | e1 }, e2 , k il : {x :B | e1 }

e1 [k /x ] −→∗m e2

T Op

T Cast

T Check

Figure 4: Universal typing rules of λH
have a well formed context. Function types are well formed in mode m when their domains and codomains are well
formed in mode m. (Unlike many recent formulations, our functions are not dependent—we leave dependency as
future work.) Type compatibility ` T1 k T2 identifies types which can be cast to each other: the types must have the
same “skeleton”. It is reasonable to try to cast a non-zero integer {x :Int | x 6= 0} to a positive integer {x :Int | x > 0},
but it is senseless to cast it to a boolean {x :Bool | true} or to a function type T1 →T2 . Every cast must be between
compatible types; at their core, λH programs are simply typed lambda calculus programs. Type compatibility is
reflexive, symmetric, and transitive; i.e., it is an equivalence relation.
Our family of calculi use different annotations. All source programs (defined below) begin without annotations—
we write the empty annotation •, read “none”. The universal annotation well formedness rule just defers to type
compatibility (A None); it is an invariant that `m a k T1 ⇒ T2 implies ` T1 k T2 .
As for term typing, the T Var, T Abs, T Op, and T App rules are entirely conventional. T Blame types blame
at any (well formed) type. A constant k can be typed by T Const at any type {x :B | e} in mode m if: (a) k is
a B , i.e., ty(k ) = B ; (b) the type in question is well formed in m; and (c), if e[k /x ] −→∗m true. As an immediate
consequence, we can derive the following rule typing constants at their raw type, since true −→∗m true in all modes
and raw types are well formed in all modes (WF Base):
`m Γ
ty(k ) = B
Γ `m k : {x :B | true}
This approach to typing constants in a manifest calculus is novel: it offers a great deal of latitude with typing, while
avoiding the subtyping of some formulations Greenberg et al. [2012], Flanagan [2006], Knowles and Flanagan [2010],
Knowles et al. [2006] and the extra rule of others Belo et al. [2011]. We assume that ty(k ) = Bool iff k ∈ {true, false}.
We require in T Op that ty(op) only produces well formed first-order types, i.e., types of the form `m {x :B1 |
e1 } → ... → {x :Bn | en }. We require that the type is consistent with the operation’s denotation: [[op]] (k1 , ... , kn ) is
defined iff ei [ki /x ] −→∗m true for all m. For this evaluation to hold for every system we consider, the types assigned
to operations can’t involve casts that both (a) stack and (b) can fail—because forgetful λH may skip them, leading
to different typings. We believe this is not so stringent a requirement: the types for operations ought to be simple,

9

e.g. ty(div) = {x :Real | true}→{y:Real | y 6= 0}→{z :Real | true}, and stacked casts only arise in stack-free terms
due to function proxies. In general, it is interesting to ask what refinement types to assign to constants, as careless
assignments can lead to circular checking (e.g., if division has a codomain cast checking its work with multiplication
and vice versa).
a
The typing rule for casts, T Cast, relies on the annotation well formedness rule: hT1 ⇒T2 il e is well formed in
mode m when `m a k T1 ⇒ T2 and e is a T1 . Allowing any cast between compatible base types is conservative: a
cast from {x :Int | x > 0} to {x :Int | x ≤ 0} always fails. Earlier work has used SMT solvers to try to statically reject
certain casts and eliminate those that are guaranteed to succeed Flanagan [2006], Knowles et al. [2006], Bierman et al.
[2010]; we omit these checks, as we view them as secondary—a static analysis offering bug-finding and optimization,
and not the essence of the system.
The final rule, T Check, is used for checking active checks, which should only occur at runtime. In fact, they
should only ever be applied to closed terms; the rule allows for any well formed context as a technical device for
weakening(Lemma A.1).
Active checks h{x :B | e1 }, e2 , k il arise as the result of casts between refined base types, as in the following classic
λH evaluation of a successful cast:
•

h{x :B | e}⇒{x :B | e 0 }il k −→C h{x :B | e 0 }, e 0 [k /x ], k il
−→∗C h{x :B | e 0 }, true, k il
−→C k
If we are going to prove type soundness via syntactic methods Wright and Felleisen [1994], we must have enough
information to type k at {x :B | e 0 }. For this reason, T Check requires that e1 [k /x ] −→∗m e2 ; this way, we know
that e 0 [k /x ] −→∗m true at the end of the previous derivation, which is enough to apply T Const. The other premises
of T Check ensure that the types all match up: that the target refinement type is well formed; that k has the base
type in question; and that e2 , the current state of the active check, is also well formed.
To truly say that our languages share a syntax and a type system, we highlight a subset of type derivations as
source program type derivations. We show that source programs well typed in one mode are well typed in the all
modes (Appendix A).
3.1 Definition [Source program]: A source program type derivation obeys the following rules:
– T Const only ever assigns the type {x :ty(k ) | true}. Variations in each mode’s evaluation aren’t reflected
in the (source program) type system. (We could soundly relax this requirement to allow {x :ty(k ) | e} such that
e[k /x ] −→∗m true for any mode m.)
– Casts have empty annotations a = •. Casts also have blame labels, and not empty blame (also written •).
– T Check, T Stack (Section 6), and T Blame are not used—these are for runtime only.
Note that source programs don’t use any of the typing rules that defer to the evaluation relation (T Check and
T Stack), so we can maintain a clear phase distinction between type checking programs and running them.

3.4

Metatheory

One distinct advantage of having a single syntax with parameterized semantics is that some of the metatheory can be
done once for all modes. Each mode proves its own canonical forms lemma—since each mode has a unique notion of
value—and its own progress and preservation lemmas for syntactic type soundness Wright and Felleisen [1994]. But
other standard metatheoretical machinery—weakening, substitution, and regularity—can be proved for all modes at
once (see Section A.1). To wit, we prove syntactic type soundness in Appendix A.2 for classic λH in just three modespecific lemmas: canonical forms, progress, and preservation. In every theorem statement, we include a reference to
the lemma number where it is proved in the appendix. In PDF versions, this reference is hyperlinked.

3.5

Overview

In the rest of this paper, we give the semantics for three space-efficient modes for λH , relating the languages’ behavior
on source programs (Definition 3.1). The forgetful mode is space efficient without annotations, converging to a value
more often than classic λH (m = F; Section 4). The heedful mode is space efficient and uses type sets to converge to
a value exactly when classic λH does; it may blame different labels, though (m = H; Section 5). The eidetic mode
is space efficient and uses coercions to track pending checks; it behaves exactly like classic λH (m = E; Section 6).
We show that source programs that are well typed in one mode are well typed in all of them (Lemmas A.19, A.27,
and A.35). We relate these space-efficient modes back to classic λH in Section 7.
10

Values and merging

valF e

valm k

V Const

valm λx :T . e

V Abs

V ProxyF

∅

valF hT11 →T12 ⇒T21 →T22 il λx :T . e
mergeF (T1 , •, T2 , •, T3 ) = •

Figure 5: Operational semantics of forgetful λH
One may wonder why we even bother to mention forgetful and heedful λH , if eidetic λH is soundly space efficient
with respect to classic λH . These two ‘intermediate’ modes are interesting as an exploration of the design space—but
also in their own right.
Forgetful λH takes a radical approach that involves skipping checks—its soundness is rather surprising and offers
insights into the semantics of contracts. Contracts have been used for more than avoiding wrongness, though: they
have been used in Racket for abstraction and information hiding PLT [a,b]. Forgetful λH can’t use contracts for
information hiding. Suppose we implement user records as functions from strings to strings. We would like to pass a
user record to an untrusted component, hiding some fields but not others. We can achieve this by specifying a whiteor blacklist in a contract, e.g., {f :String | f 6= “password00 }→{v :String | true}. Wrapping a function in this contract
introduces a function proxy... which can be overwritten by E CastMerge! To really get information hiding, the
programmer must explicitly η-expand the function proxy, writing (λf :{f :String | f 6= “password00 }. . . . ). Forgetful
λH ’s contracts can’t enforce abstractions.1
While Siek and Wadler [2010] uses the lattice of type precision in their threesomes without blame, our heedful λH
uses the powerset lattice of types. Just as Siek and Wadler use labeled types and meet-like composition for threesomes
with blame, we may be able to derive something similar for heedful and eidetic λH : in a (non-commutative) skew
lattice, heedful uses a potentially re-ordering conjunction while eidetic preserves order. A lattice-theoretic account
of casts, coercions, and blame may be possible.

4

Forgetful space efficiency

In forgetful λH , we offer a simple solution to space-inefficient casts: just forget about them. Function proxies only
ever wrap lambda abstractions; trying to cast a function proxy simply throws away the inner proxy. Just the same,
when accumulating casts on the stack, we throw away all but the last cast. Readers may wonder: how can this ever
be sound? Several factors work together to make forgetful λH a sound calculus. In short, the key ingredients are
call-by-value evaluation and the observation that type safety only talks about reduction to values in this setting.
In this section, our mode m = F: our evaluation relation is −→F and we use typing judgments of the form, e.g.
Γ `F e : T . Forgetful λH is the simplest of the space-efficient calculi: it just uses the standard typing rules from
Figure 4 and the space-efficient reduction rules from Figure 2. We give the new operational definitions for m = F
in Figure 5: a new value rule and the definition of the merge operator. First, V ProxyF says that function proxies
in forgetful λH are only values when the proxied value is a lambda (and not another function proxy). Limiting the
number of function proxies is critical for establishing space bounds, as we do in Section 8. Forgetful casts don’t use
annotations, so they just use A None. The forgetful merge operator just forgets the intermediate type T2 .
We demonstrate this semantics on the example from Section 3.1 in Figure 6. We first step by merging casts,
forgetting the intermediate type. Then contract checking proceeds as normal for the target type; since −1 is nonzero, the check succeeds and returns its scrutinee by E CheckOK.
The type soundness property typically has two parts: (a) well typed programs don’t go ‘wrong’ (for us, getting
stuck), and (b) well typed programs reduce to programs that are well typed at the same type. How could a forgetful
λH program go wrong, violating property (a)? The general “skeletal” structure of types means we never have to
worry about errors caught by simple type systems, such as trying to apply a non-function. Our semantics can get
stuck by trying to apply an operator to an input that isn’t in its domain, e.g., trying to divide by zero. To guarantee
that we avoid stuck operators, λH generally relies on subject reduction, property (b). Operators are assigned types
1

This observation is due to Sam Tobin-Hochstadt.

11

•

e = h{x :Int | x mod 2 = 0}⇒{x :Int | x 6= 0}il3
•
(h{x :Int | x ≥ 0}⇒{x :Int | x mod 2 = 0}il2
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1))
(E CastMerge)
•
−→F h{x :Int | x ≥ 0}⇒{x :Int | x 6= 0}il3
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1)
(E CastMerge)
•
−→F h{x :Int | true}⇒{x :Int | x 6= 0}il3 −1
(E CheckNone)
−→F h{x :Int | x 6= 0}, −1 6= 0, −1il3
(E CheckInner/E Op)
−→F h{x :Int | x 6= 0}, true, −1il3
(E CheckOK)
−→F −1

Figure 6: Example of forgetful λH
that avoid stuckness, i.e., ty(op) and [[op]] agree. Some earlier systems have done this Flanagan [2006], Knowles and
Flanagan [2010] while others haven’t Greenberg et al. [2012], Belo et al. [2011]. We view it as a critical component of
contract calculi. So for, say, integer division, ty(div) = {x :Int | true}→{y:Int | y 6= 0}→{z :Int | true}. To actually use
div in a program, the second argument must be typed as a non-zero integer—by a non-source typing with T Const
directly (see Definition 3.1) or by casting (T Cast). It may seem dangerous: casts protect operators from improper
values, preventing stuckness; forgetful λH eliminates some casts. But consider the cast eliminated by E CastMerge:
•

•

0

•

hT2 ⇒T3 il (hT1 ⇒T2 il e) −→F hT1 ⇒T3 il e
While the program tried to cast e to a T2 , it immediately cast it back out—no operation relies on e being a T2 .
Skipping the check doesn’t risk stuckness. Since λH is call-by-value, we can use the same reasoning to allow functions
to assume that their inputs inhabit their types—a critical property for programmer reasoning.
Forgetful λH enjoys soundness via a standard syntactic proof of progress and preservation, reusing the theorems
from Section A.1. What’s more, source programs are well typed in classic λH iff they are well typed in forgetful λH :
both languages can run the same terms. Proofs are in Appendix A.3.

5

Heedful space efficiency

Heedful λH (m = H) takes the cast merging strategy from forgetful λH , but uses type sets on casts and function
proxies to avoid dropping casts. Space efficiency for heedful λH rests on the use of sets: classic λH allows for arbitrary
lists of function proxies and casts on the stack to accumulate. Restricting this accumulation to a set gives us a
straightforward bound on the amount of accumulation: a program of fixed size can only have so many types at each
size. We discuss this idea further in Section 8.
We extend the typing rules and operational semantics in Figure 7. Up until this point, we haven’t used annotations.
Heedful λH collects type sets as casts merge to record the types that must be checked. The A TypeSet annotation
well formedness rule extends the premises of A None with the requirement that if `H S k T1 ⇒ T2 , then all the
types in S are well formed and compatible with T1 and T2 . Type set compatibility is stable under removing elements
from the set S, and it is symmetric and transitive with respective to its type indices (since compatibility itself is
symmetric and transitive).
One might expect the types in type sets to carry blame labels—might we then be able to have sound space
efficiency? It turns out that just having labels in the sets isn’t enough—we actually need to keep track of the
ordering of checks. Eidetic λH (Section 6) does exactly this tracking. Consider this calculus a warmup.
Heedful λH adds some evaluation rules to the universal ones found in Figure 2. First E TypeSet takes a
source program cast without an annotation and annotates it with an empty set. E CheckEmpty is exactly like
E CheckNone, though we separate the two to avoid conflating the empty annotation • and the empty set ∅. In
E CheckSet, we use an essentially unspecified function choose to pick a type from a type set to check. Using
the choose function is theoretically expedient, as it hides all of heedful λH ’s nondeterminism. Nothing is inherently
problematic with this nondeterminism, but putting it in the reduction relation itself complicates the proof of strong
normalization that is necessary for the proof relating classic and heedful λH (Section 7).

12

Type set well formedness

`m S k T1 ⇒ T2
` T1 k T2 `H T1 `H T2
∀T ∈ S. `H T ` T k T1
`H S k T 1 ⇒ T 2

Values and operational semantics

A TypeSet

e1 −→H e2

valH e

V ProxyH

S

valH hT11 →T12 ⇒T21 →T22 il λx :T . e
•

∅

E TypeSet

hT1 ⇒T2 il e −→H hT1 ⇒T2 il e
∅

h{x :B | e1 }⇒{x :B | e2 }il k −→H
h{x :B | e2 }, e2 [k /x ], k il
choose(S) = {x :B | e2 }
S

h{x :B | e1 }⇒{x :B | e3 }il k −→H

E CheckEmpty

E CheckSet

S\{x :B|e2 }

h{x :B | e2 }
⇒
{x :B | e3 }il
h{x :B | e2 }, e2 [k /x ], k il
choose(S) ∈ S when S 6= ∅
mergeH (T1 , S1 , T2 , S2 , T3 ) = S1 ∪ S2 ∪ {T2 }
dom(S)
cod(S)

=
=

S
ST ∈S dom(T )
T ∈S cod(T )

Figure 7: Annotation typing and operational semantics of heedful λH

13

•

e = h{x :Int | x mod 2 = 0}⇒{x :Int | x 6= 0}il3
•
(h{x :Int | x ≥ 0}⇒{x :Int | x mod 2 = 0}il2
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1))
(E TypeSet, E CastInner/E TypeSet)
∅

−→∗H h{x :Int | x mod 2 = 0}⇒{x :Int | x 6= 0}il3
∅

(h{x :Int | x ≥ 0}⇒{x :Int | x mod 2 = 0}il2
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1))
(E CastMerge)
{{x :Int|x mod 2=0}}

−→H h{x :Int | x ≥ 0}
⇒
{x :Int | x 6= 0}il3
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1)
(E CastInner/E TypeSet)
{{x :Int|x mod 2=0}}

−→H h{x :Int | x ≥ 0}

⇒

{x :Int | x 6= 0}il3

∅

(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1)
(E CastMerge)
S

−→H h{x :Int | true}⇒{x :Int | x 6= 0}il3 −1
where S = {{x :Int | x mod 2 = 0}, {x :Int | x ≥ 0}}
(E CheckSet, choose(S) = {x :Int | x mod 2 = 0})
S0

−→H h{x :Int | x mod 2 = 0}⇒{x :Int | x 6= 0}il3
h{x :Int | x mod 2 = 0}, −1 mod 2 = 0, −1il3
where S 0 = {{x :Int | x ≥ 0}}
(E CastInner/E CheckInner/E Op)
S0

−→H h{x :Int | x mod 2 = 0}⇒{x :Int | x 6= 0}il3
h{x :Int | x mod 2 = 0}, 1 = 0, −1il3
(E CastInner/E CheckInner/E Op)
S0

−→H h{x :Int | x mod 2 = 0}⇒{x :Int | x 6= 0}il3
h{x :Int | x mod 2 = 0}, false, −1il3
(E CastInner/E CheckFail)
∅

−→H h{x :Int | x ≥ 0}⇒{x :Int | x 6= 0}il3 ⇑l3
(E CastRaise)
−→H ⇑l3

Figure 8: Example of heedful λH
For function types, we define dom(S) and cod(S) by mapping the underlying function on types over the set. Note
that this may shrink the size of the set S, but never grow it—there can’t be more unique (co)domain types in S than
there are types.
The merge operator, used in E CastMerge, merges two sets by unioning the two type sets with the intermediate
type, i.e.:
S

S

1
2
l1
l2
e) −→H hT1
(hT1 ⇒T
hT2 ⇒T
2i
3i

S1 ∪S2 ∪{T2 }

⇒

T3 il2 e

There are some subtle interactions here between the different annotations: we won’t merge casts that haven’t yet
stepped by E TypeSet because mergeH (T1 , •, T2 , •, T3 ) isn’t defined.
We demonstrate the heedful semantics by returning to the example from Section 3.1 in Figure 8. To highlight the
difference between classic and heedful λH , we select a choose function that has heedful check the refinements out of
order, failing on the check for evenness rather than the check for positivity. The real source of difference, however,
is that E CastMerge takes the second blame label of the two casts it merges. Taking the first wouldn’t be right,
either: suppose that the target type of the l1 cast wasn’t {x :Int | x ≥ 0}, but some other type that −1 inhabits. Then
classic λH would blame l2 , but heedful λH would have held onto l1 . The solution to this blame tracking problem is
to hold onto blame labels in annotations—which, again, is exactly what we do in eidetic λH .
The syntactic proof of type soundness for heedful λH appears in an appendix in Appendix A.4. We also have
“source typing” for heedful λH : source programs are well typed when m = C iff they are well typed when m = H. As
a corollary, source programs are well typed in F if and only if they are well typed in H.

14

6

Eidetic space efficiency

Eidetic λH uses coercions, a more refined system of annotations than heedful λH ’s type sets. Coercions do two critical
things that type sets don’t: they retain check order, and they track blame. Our coercions are ultimately inspired
by those of Henglein [1994]; we discuss the relationship between our coercions and his in related work (Section 9).
Recall the syntax of coercions from Figure 1:
c ::= r | c1 7→ c2
r ::= nil | {x :B | e}l , r
Coercions come in two flavors: blame-annotated refinement lists r —zero or more refinement types, each annotated
with a blame label—and function coercions c1 7→ c2 . We write them as comma separated lists, omitting the empty
refinement list nil when the refinement list is non-empty. We define the coercion well formedness rules, an additional
typing rule, and reduction rules for eidetic λH in Figure 9. To ease the exposition, our explanation doesn’t mirror
the rule groupings in the figure.
As a general intuition, coercions are plans for checking: they contain precisely those types to be checked. Refinement lists are well formed for casts between {x :B | e1 } and {x :B | e2 } when: (a) every type in the list is a
blame-annotated, well formed refinement of B , i.e., all the types are of the form {x :B | e}l and are therefore similar
to the indices; (b) there are no duplicated types in the list; and (c) the target type {x :B | e2 } is implied by some other
type in the list. Note that the input type for all refinement lists can be any well formed refinement—this corresponds
to the intuition that base types have no negative parts, i.e., casts between refinements ignore the type on the left.
Finally, we simply write “no duplicates in r ”—it is an invariant during the evaluation of source programs. Function
coercions, on the other hand, have a straightforward (contravariant) well formedness rule.
The E Coerce rule translates source-program casts to coercions: coerce(T1 , T2 , l ) is a coercion representing
•
exactly the checking done by the cast hT1 ⇒T2 il . All of the refinement types in coerce(T1 , T2 , l ) are annotated with
the blame label l , since that’s the label that would be blamed if the cast failed at that type. Since a coercion is a
complete plan for checking, a coercion annotation obviates the need for type indices and blame labels. To this end,
E Coerce drops the blame label from the cast, replacing it with an empty label. We keep the type indices so that
we can reuse E CastMerge from the universal semantics, and also as a technical device in the preservation proof.
The actual checking of coercions rests on the treatment of refinement lists: function coercions are expanded as
functions are applied by E Unwrap, so they don’t need much special treatment beyond a definition for dom and
cod. Eidetic λH uses coercion stacks h{x :B | e1 }, s, r , k , e2 i• to evaluate refinement lists. Coercion stacks are type
checked by T Stack (in Figure 9). We explain the operational semantics before explaining the typing rule. Coercion
stacks are runtime-only entities comprising five parts: a target type, a status, a pending refinement list, a constant
scrutinee, and a checking term. We keep the target type of the coercion for preservation’s sake. The status bit s is
either X or ?: when the status is X, we are currently checking or have already checked the target type {x :B | e1 };
when it is ?, we haven’t. The pending refinement list r holds those checks not yet done. When s = ?, the target type
is still in r . The scrutinee k is the constant we’re checking; the checking term e2 is either the scrutinee k itself, or it
is an active check on k .
The evaluation of a coercion stack proceeds as follows. First, E CoerceStack starts a coercion stack when a
cast between refinements meets a constant, recording the target type, setting the status to ?, and setting the checking
term to k . Then E StackPop starts an active check on the first type in the refinement list, using its blame label
on the active check—possibly updating the status if the type being popped from the list is the target type. The
active check runs by the congruence rule E StackInner, eventually returning k itself or blame. In the latter case,
E StackRaise propagates the blame. If not, then the scrutinee is k once more and E StackPop can fire again.
Eventually, the refinement list is exhausted, and E StackDone returns k .
Now we can explain T Stack’s many jobs. It must recapitulate A Refine, but not exactly—since eventually the
target type will be checked and no longer appear in r . The status s differentiates what our requirement is: when
s = ?, the target type is in r . When s = X, we either know that k inhabits the target type or that we are currently
checking the target type (i.e., an active check of the target type at some blame label reduces to our current checking
term).
Finally, we must define a merge operator, mergeE . We define it in terms of the join operator, which is very nearly
concatenation on refinement lists and a contravariant homomorphism on function coercions. It’s not concatenation
because it uses an implication predicate, the pre-order ⊃, to eliminate duplicates (because ⊃ is reflexive) and hide
subsumed types (because ⊃ is adequate). We read {x :B | e1 } ⊃ {x :B | e2 } as “{x :B | e1 } implies {x :B | e2 }”. When
eliminating types, join always chooses the leftmost blame label. Contravariance means that join(c1 , c2 ) takes leftmost
labels in positive positions and rightmost labels in negative ones. The coerce metafunction and join operator work

15

{x :B | e1 } ⊃ {x :B | e2 }

Coercion implication predicate: axioms

(Reflexivity) If `E {x :B | e} then {x :B | e} ⊃ {x :B | e}.
(Transitivity) If {x :B | e1 } ⊃ {x :B | e2 } and {x :B | e2 } ⊃ {x :B | e3 } then {x :B | e1 } ⊃ {x :B | e3 }.
(Adequacy) If {x :B | e1 } ⊃ {x :B | e2 } then ∀k ∈ KB . e1 [k /x ] −→∗E true implies e2 [k /x ] −→∗E true.
(Decidability) For all `E {x :B | e1 } and `E {x :B | e2 }, it is decidable whether {x :B | e1 } ⊃ {x :B | e2 }.
`m c k T1 ⇒ T2

Coercion well formedness and term typing
`E {x :B | e1 } `E {x :B | e2 }
∀{x :B | e} ∈ r . `E {x :B | e} no duplicates in r
∃{x :B | e} ∈ r . {x :B | e} ⊃ {x :B | e2 }
`E r k {x :B | e1 } ⇒ {x :B | e2 }

Γ `m e : T

`E c1 k T21 ⇒ T11 `E c2 k T12 ⇒ T22
`E c 1 →
7 c2 k (T11 →T12 ) ⇒ (T21 →T22 )

A Refine

`E Γ `E {x :B | e1 } ty(k ) = B ∅ `E e2 : {x :B | e3 } ∀{x :B | e} ∈ r . `E {x :B | e}
s = X implies e1 [k /x ] −→∗E true ∨ (∃{x :B | e}. ∃l. {x :B | e} ⊃ {x :B | e1 } ∧ h{x :B | e}, e[k /x ], k il −→∗E e2 )
s = ? implies (∃{x :B | e} ∈ r . {x :B | e} ⊃ {x :B | e1 })
Γ `E h{x :B | e1 }, s, r , k , e2 i• : {x :B | e1 }
Values and operational semantics

A Fun

T Stack

e1 −→E e2

valE e
c 7→c

valE hT11 →T12 1⇒ 2 T21 →T22 i• λx :T . e

•

hT1 ⇒T2 il e −→E hT1

V ProxyE

E Coerce

coerce(T1 ,T2 ,l)

⇒

T2 i• e

r

h{x :B | e1 }⇒{x :B | e2 }i• k −→E h{x :B | e2 }, ?, r , k , k i•

E CoerceStack

h{x :B | e}, s, ({x :B | e 0 }l , r ), k , k i• −→E h{x :B | e}, s ∨ (e = e 0 ), r , k , h{x :B | e 0 }, e 0 [k /x ], k il i•
e 0 −→E e 00
h{x :B | e}, s, r , k , e 0 i• −→E h{x :B | e}, s, r , k , e 00 i•

E StackInner

h{x :B | e}, X, nil, k , k i• −→E k

h{x :B | e}, s, r , k , ⇑l 0 i• −→E ⇑l 0

E StackPop

E StackRaise

E StackDone

Cast translation and coercion operations
mergeE (T1 , c1 , T2 , c2 , T3 )
dom(c1 7→ c2 )
cod(c1 7→ c2 )
join({x :B | e}l , nil)
join({x :B | e}l , r )

=
=

=
=
=

join(c1 , c2 )
c1
c2

coerce({x :B | e1 }, {x :B | e2 }, l)
coerce(T11 →T12 , T21 →T22 , l)

{x :B | e}l
{x :B | e}l , drop (r , {x :B | e})

drop (nil, {x :B | e})

=

drop (({x :B | e1 }l , r ), {x :B | e})

=

=
=

{x :B | e2 }l
coerce(T21 , T11 , l) 7→ coerce(T12 , T22 , l)

join(nil, r2 )
join(({x :B | e}l , r1 ), r2 )
join(c11 7→ c12 , c21 7→ c22 )

nil
(
drop (r , {x :B | e})
{x :B | e1 }l , drop (r , {x :B | e})

=
=
=

X ∨ (e1 = e2 )
{x :B | e} ⊃ {x :B | e1 }
? ∨ (e1 = e2 )
{x :B | e} 6⊃ {x :B | e1 }

Figure 9: Typing rules and operational semantics for eidetic λH

16

r2
join({x :B | e}l , join(r1 , r2 ))
join(c21 , c11 ) 7→ join(c12 , c22 )
=
=

X
(

X
?

e1 = e2
otherwise

together to make sure that the refinement lists are correctly ordered. As we show below, ‘correctly ordered’ means
the positive parts take older labels and negative parts take newer ones. As for heedful λH , E CastMerge is slightly
subtle—we never merge casts with • as an annotation because such merges aren’t defined.
In Figure 9, we only give the axioms for ⊃: it must be an adequate, decidable pre-order. Syntactic type equality is
the simplest implementation of the ⊃ predicate, but the reflexive transitive closure of any adequate decidable relation
would work.
By way of example, consider a cast from T1 = {x :Int | x ≥ 0}→{x :Int | x ≥ 0} to T2 = {x :Int | true}→{x :Int |
•
x > 0}. For brevity, we refer to the domains as Ti 1 and the codomains as Ti 2 . We find that (hT1 ⇒T2 il v1 ) v2 steps
in classic λH to:
•
h{x :Int | x ≥ 0}⇒{x :Int | x > 0}il
•
(v1 (h{x :Int | true}⇒{x :Int | x ≥ 0}il v2 ))
Note that T1 ’s domain is checked but its codomain isn’t; the reverse is true for T2 . When looking at a cast, we can
read off which refinements are checked by looking at the positive parts of the target type and the negative parts of
the source type. The relationship between casts and polarity is not a new one Findler [2006], Gronski and Flanagan
[2007], Herman et al. [2007], Wadler and Findler [2009], Greenberg [2013]. Unlike casts, coercions directly express
the sequence of checks to be performed. Consider the coercion generated from the cast above, recalling that Ti 1 and
Ti 2 are the domains and codomains of T1 and T2 :
•

−→E

(hT1 ⇒T2 il v1 ) v2
c
(hT1 ⇒T2 i• v1 ) v2
where c = {x :Int | x ≥ 0}l 7→ {x :Int | x > 0}l
c
(hT11 →T12 ⇒T21 →T22 i• v1 ) v2

−→E

hT12

−→E

{x :Int|x >0}l

⇒

T22 i• (v1 (hT21

{x :Int|x ≥0}l

⇒

T11 i• v2 ))

In this example, there is only a single blame label, l . Tracking blame labels is critical for exactly matching classic
λH ’s behavior. The examples rely on ⊃ being reflexive. First, we return to our example from before in Figure 10.
Throughout the merging, each refinement type retains its own original blame label, allowing eidetic λH to behave
just like classic λH .
We offer a final pair of examples, showing how coercions with redundant types are merged. The intuition here
is that positive positions are checked covariantly—oldest (innermost) cast first—while negative positions are checked
contravariantly—newest (outermost) cast first. Consider the classic λH term:
T1
T2
T3
e

=
=
=
=

{x :Int | e11 }→{x :Int | e21 }
{x :Int | e12 }→{x :Int | e22 }
{x :Int | e13 }→{x :Int | e22 }
•
•
hT2 ⇒T3 il2 (hT1 ⇒T2 il1 v )

Note that the casts run inside-out, from old to new in the positive position, but they run from the outside-in, new to
old, in the negative position.
•

e v 0 −→C h{x :Int | e22 }⇒{x :Int | e22 }il2
•
(h{x :Int | e21 }⇒{x :Int | e22 }il1
•
(v (h{x :Int | e12 }⇒{x :Int | e12 }il1
•
(h{x :Int | e13 }⇒{x :Int | e12 }il2 v 0 ))))
The key observation for eliminating redundant checks is that only the check run first can fail—there’s no point in
checking a predicate contract twice on the same value. So eidetic λH merges like so:
e −→∗E hT2

{x :Int|e12 }l2 7→{x :Int|e22 }l2

⇒

T3 i•

{x :Int|e11 }l1 7→{x :Int|e22 }l1

⇒

(hT1
c
−→E hT1 ⇒T3 i• v
where

T2 i• v )

c = join({x :Int | e12 }l2 , {x :Int | e11 }l1 ) 7→
join({x :Int | e22 }l1 , {x :Int | e22 }l2 )
= {x :Int | e12 }l2 , {x :Int | e11 }l1 7→ {x :Int | e22 }l1

17

•

e = h{x :Int | x mod 2 = 0}⇒{x :Int | x 6= 0}il3
•
(h{x :Int | x ≥ 0}⇒{x :Int | x mod 2 = 0}il2
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1))
(E Coerce)
{x :Int|x 6=0}l3

⇒
{x :Int | x 6= 0}il3
−→E h{x :Int | x mod 2 = 0}
•
(h{x :Int | x ≥ 0}⇒{x :Int | x mod 2 = 0}il2
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1))
(E CastInner/E Coerce)
{x :Int|x 6=0}l3

⇒

−→E h{x :Int | x mod 2 = 0}

{x :Int | x 6= 0}il3

{x :Int|x mod 2=0}l2

(h{x :Int | x ≥ 0}
⇒
{x :Int | x mod 2 = 0}il2
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1))
(E CastMerge)
r0

−→E h{x :Int | x ≥ 0}⇒{x :Int | x 6= 0}il3
•
(h{x :Int | true}⇒{x :Int | x ≥ 0}il1 −1)
0
where r = {x :Int | x mod 2 = 0}l2 , {x :Int | x 6= 0}l3
(E CastInner/E Coerce)
r0

−→E h{x :Int | x ≥ 0}⇒{x :Int | x 6= 0}il3
{x :Int|x ≥0}l1

{x :Int | x ≥ 0}il1 −1)
(E CastMerge)
r
−→E h{x :Int | true}⇒{x :Int | x 6= 0}il3 −1
where r = {x :Int | x ≥ 0}l1 , r 0
(E CoerceStack)
−→E h{x :Int | x 6= 0}, ?, r , −1, −1i•
(E StackPop)
−→E h{x :Int | x 6= 0}, ?, r 0 , −1,
h{x :Int | x ≥ 0}, −1 ≥ 0, −1il1 i•
−→∗E ⇑l1
(h{x :Int | true}

⇒

Figure 10: Example of eidetic λH
The coercion merge operator eliminates the redundant codomain check, choosing to keep the one with blame label
l1 . Choosing l1 makes sense here because the codomain is a positive position and l1 is the older, innermost cast. We
construct a similar example for merges in negative positions.
T1
T20
T30
e0

=
=
=
=

{x :Int | e11 }→{x :Int | e21 }
{x :Int | e11 }→{x :Int | e22 }
{x :Int | e13 }→{x :Int | e23 }
•
•
hT20 ⇒T30 il2 (hT1 ⇒T20 il1 v )

Again, the unfolding runs the positive parts inside-out and the negative parts outside-in when applied to a value v 0 :
•

h{x :Int | e22 }⇒{x :Int | e23 }il2
•
(h{x :Int | e21 }⇒{x :Int | e22 }il1
•
(v (h{x :Int | e11 }⇒{x :Int | e11 }il1
•
(h{x :Int | e13 }⇒{x :Int | e11 }il2 v 0 ))))
Running the example in eidetic λH , we reduce the redundant checks in the domain:
e 0 −→∗E hT20

{x :Int|e11 }l2 7→{x :Int|e23 }l2

⇒

l1

T30 i•

{x :Int|e11 } 7→{x :Int|e22 }l1

(hT1
⇒
T20 i• v )
c
0 •
−→E hT1 ⇒T3 i v
where
c = join({x :Int | e11 }l2 , {x :Int | e11 }l1 ) 7→
join({x :Int | e22 }l1 , {x :Int | e23 }l2 )
= {x :Int | e12 }l2 7→ {x :Int | e22 }l1 , {x :Int | e23 }l2

18

Forgetful λH

Heedful λH

e1

F e2

e1

H e2

⇓
•

hT1 ⇒T2

il

e1

⇓
•

hT1 ⇒T2

•

hT1 ⇒T2

e2

il

•

hT1 ⇒T2 il e2

e1

resultH e10

e

∗
H

∗
H

∗
F

∗
F val
F

il

∼

=
valH e

e1

=

resultH e20

E e2

⇓
hT1 ⇒T2

il

•

hT1 ⇒T2 il e2

e1

∗

∗
E

resultE e

E

•

Figure 11: Cast congruence lemmas as commutative diagrams
Following the outside-in rule for negative positions, we keep the blame label l2 from the newer, outermost cast.
As we did for the other calculi, we present the routine syntactic proof of type soundness in (Appendix A.5).
Like forgetful and heedful λH before, eidetic λH shares source programs (Definition 3.1) with classic λH . With
this final lemma, we know that all modes share the same well typed source programs.

7

Soundness for space efficiency

We want space efficiency to be sound : it would be space efficient to never check anything. Classic λH is normative:
the more a mode behaves like classic λH , the “sounder” it is.
A single property summarizes how a space-efficient calculus behaves with respect to classic λH : cast congruence.
•
•
In classic λH , if e1 −→C e2 then hT1 ⇒T2 il e1 and hT1 ⇒T2 il e2 behave identically. This cast congruence principle
is easy to see, because E CastInnerC applies freely. In the space-efficient modes, however, E CastInner can only
apply when E CastMerge doesn’t. Merged casts may not behave the same as running the two casts separately. We
summarize the results in commutative diagrams in Figure 11. Forgetful λH has the property that if the unmerged
casts reduce to a value, then so do the merged ones. But the merged casts may reduce to a value when the unmerged
ones reduce to blame, because forgetful merging skips checks. Heedful λH has a stronger property: the merged and
unmerged casts coterminate at results, if the merged term reduces to blame or a value, so does the unmerged term.
If they both go to values, they go to the exact same value; but if they both go to blame, they may blame different
labels. This is a direct result of E CastMerge saving only one label from casts. Finally, eidetic λH has a property
as strong as heedful λH : the merged and unmerged casts coterminate exactly.
It is particularly nice that the key property for relating modes can be proved entirely within each mode, i.e., the
cast congruence lemma for forgetful λH is proved independently of classic λH .
The proofs are in Appendix B, but there are two points worth observing here. First, we need strong normalization
to prove cast congruence for heedful λH : if we reorder checks, we need to know that reordering checks doesn’t change
the observable behavior. Second, both heedful and eidetic λH eliminate redundant checks when merging casts, the
former by using sets and the latter by means of the join operator and the reflexivity of ⊃. These two calculi require
proofs that checking is idempotent: checking a property once is as good as checking it twice. Naturally, this property
only holds without state.
We summarize the relationships between each mode in Table 1. Our proofs relating classic λH and the spaceefficient modes are by (mode-indexed)logical relations, found in Figure 12. The relation is modal: in e1 ∼m e2 : T ,
the term e1 is a classic λH term, while e2 and T are in mode m. Each mode’s logical relation matches its cast
congruence lemma: the forgetful logical relation allows more blame on the classic side (not unlike the asymmetric
logical relations of Greenberg et al. [2012]); the heedful logical relation is blame-inexact, allowing classic and heedful
λH to raise different labels; the eidetic logical relation is exact. The proofs can be found in Appendix B. They
follow a fairly standard pattern in each mode m: we show that applying C-casts and m-casts between similar and

19

Mode
Classic (m = C)
Forgetful (m = F)
Heedful (m = H)
Eidetic (m = E)

Reduction behavior
Normative
−→∗C val ⇒ −→∗F val (Lemma B.6)
−→∗C result ⇔ −→∗H result (Lemma B.20)
−→∗C result = −→∗E result (Lemma B.25)

Table 1: Soundness results for λH

Value rules

e1 ∼m e2 : T
k ∼m k : {x :B | e} ⇐⇒ ty(k ) = B ∧ e[k /x ] −→∗m true
e11 ∼m e21 : T1 →T2 ⇐⇒ valC e11 ∧ valm e12 ∧
∀e12 ∼m e22 : T1 . e11 e12 'm e21 e22 : T2

Term rules

e1 ⇓m e2 : T

e1 'm e2 : T
e1 ⇓m e2 : T ⇐⇒ e1 −→∗C e10 ∧ valC e10 ∧
e2 −→∗m e20 ∧ valm e20 ∧
e10 ∼m e20 : T
e1 'F e2 : T ⇐⇒ e1 −→∗C ⇑l ∨ e1 ⇓F e2 : T
e1 'H e2 : T ⇐⇒ (e1 −→∗C ⇑l ∧ e2 −→∗H ⇑l 0 ) ∨ e1 ⇓H e2 : T
e1 'E e2 : T ⇐⇒ (e1 −→∗C ⇑l ∧ e2 −→∗E ⇑l) ∨ e1 ⇓E e2 : T

Type rules

T1 ∼m T2
{x :B | e1 } ∼m {x :B | e2 } ⇐⇒
∀e10 ∼m e20 : {x :B | true}.
e1 [e10 /x ] 'm e2 [e20 /x ] : {x :Bool | true}
T11 →T12 ∼m T21 →T22 ⇐⇒ T11 ∼m T21 ∧ T12 ∼m T22

Closing substitutions and open terms

Γ |=m δ

Γ ` e1 'm e2 : T

Γ |=m δ ⇐⇒ ∀x ∈ dom(Γ). δ1 (x ) ∼m δ2 (x ) : Γ(x )
Γ ` e1 'm e2 : T ⇐⇒ ∀Γ |=m δ. δ1 (e1 ) 'm δ2 (e2 ) : T

Figure 12: Modal logical relations relating classic λH to space-efficient modes

20

Mode
Classic (m = C)
Forgetful (m = F)
Heedful (m = H)
Eidetic (m = E)

Cast size
2Wh + L
2Wh + L
2Wh + 2Wh + L
s2L+WB

Pending casts
∞
|e|
|e|
|e|

Table 2: Space efficiency of λH
related types to related values yields related values (i.e., casts are applicative); we then show that well typed Csource programs are related to m-source programs. As far as alternative techniques go, an induction over evaluation
derivations wouldn’t give us enough information about evaluations that return lambda abstractions. Other contextual
equivalence techniques (e.g., bisimulation) would probably work, too.
Our equivalence results for forgetful and heedful λH are subtle: they would break down if we had effects other
than blame. Forgetful λH changes which contracts are checked, and so which code is run. Heedful λH can reorder
when code is run. Well typed λH programs in this paper are strongly normalizing. If we allowed nontermination, for
example, then we could construct source programs that diverge in classic λH and converge in forgetful λH , or source
programs that diverge in one of classic and heedful λH and converge in the other. Similarly, if blame were a catchable
exception, we would have no relation for these two modes at all: since they can raise different blame labels, different
exception handlers could have entirely different behavior. Eidetic λH doesn’t reorder checks, though, so its result is
more durable. As long as checks are pure—they return the same result every time—eidetic and classic λH coincide.
Why bother proving strong results for forgetful and heedful if they only adhere in such a restricted setting? First,
we wish to explore the design space. Moreover, forgetful and heedful offer insights into the semantics and structure
of casts. Second, we want to show soundness of space efficiency in isolation. Implementations always differ from the
theory. Once this soundness has been established, whether an inefficient classic implementation would differ for a
given program is less relevant when the reference implementation has a heedful semantics. Analagously, languages
with first-class stack traces make tail-call optimization observable, but this change in semantics is typically considered
worthwhile—space efficiency is more important.

8

Bounds for space efficiency

We have claimed that forgetful, heedful, and eidetic λH are space efficient: what do we mean? What sort of space
efficiency have we achievedin our various calculi? We summarize the results in Table 2; proofs are in Appendix C.
From a high level, there are only a finite number of types that appear in our programs, and this set of types can only
reduce as the program runs. We can effectively code each type in the program as an integer, allowing us to efficiently
run the ⊃ predicate.
Suppose that a type of height h can be represented in Wh bits and a label in L bits. (Type heights are defined
in Figure 14 in Appendix C.) Casts in classic and forgetfulλH each take up 2Wh + L bits: two types and a blame
label. Casts in heedful λH take up more space—2Wh + 2Wh + L bits—because they need to keep track of the type
set. Coercions in eidetic λH have a different form: the only types recorded are those of height 1, i.e., refinements of
base types. Pessimistically, each of these may appear at every position in a function coercion c1 7→ c2 . We use s to
indicate the “size” of a function type, i.e., the number of positions it has. As a first pass, a set of refinements and
blame labels take up 2L+W1 space. But in fact these coercions must all be between refinements of the same base type,
leading to 2L+WB space per coercion, where WB is the highest number of refinements of any single base type. We
now have our worst-case space complexity: s2L+WB . A more precise bound might track which refinements appear in
which parts of a function type, but in the worst case—each refinement appears in every position—it degenerates to
the bound we give here. Classic λH can have an infinite number of “pending casts”—casts and function proxies—in
a program. Forgetful, heedful and eidetic λH can have no more than one pending cast per term node. Abstractions
are limited to a single function proxy, and E CastMerge merges adjacent pending casts.
The text of a program e is finite, so the set of types appearing in the program, types(e), is also finite. Since
reduction doesn’t introduce types, we can bound the number of types in a program (and therefore the size of casts).
We can therefore fix a numerical coding for types at runtime, where we can encode a type in W = log2 (|types(e)|)
bits. In a given cast, W over-approximates how many types can appear: the source, target, and annotation must
all be compatible, which means they must also be of the same height. We can therefore represent the types in casts
with fewer bits: Wh = log2 (|{T | T ∈ types(e) ∧ height(T ) = h}|). In the worst case, we revert to the original bound:
all types in the program are of height 1. Even so, there are never casts between different base types B and B 0 , so

21

WB = maxB log2 (|{{x :B | e} ∈ types(e)}|). Eidetic λH ’s coercions never hold types greater than height 1. The types
on its casts are erasable once the coercions are generated, because coercions drive the checking.

8.1

Representation choices

We have shown that sound space efficiency is possible, and it is future work to produce a feasible implementation.
The bounds we find here are galactic. Having established that contracts are theoretically space efficient, making
an implementation practically space efficient is a different endeavor, involving careful choices of representations and
calling conventions.
Eidetic λH ’s space bounds rely only on the reflexivity of the ⊃ predicate, since we leave it abstract. We have
identified one situation where the relation allows us to find better space bounds: mutual implication.
If {x :B | e1 } ⊃ {x :B | e2 } and {x :B | e2 } ⊃ {x :B | e1 }, then these two types are equivalent, and only one ever
need be checked. Which to check could be determined by a compiler with a suitably clever cost model. Note that
our proofs don’t entirely justify this optimization. By default, our join operator will take whichever of {x :B | e1 }
and {x :B | e2 } was meant to be checked first. Adapting join to always choose one based on some preference relation
would not be particularly hard, and we believe the proofs adapt easily.
Other analyses of the relation seem promising at first, but in fact do not allow more compact representations.
Suppose we have a program where {x :B | e1 } ⊃ {x :B | e2 } but not vice versa, and that B is our worst case type.
That is, WB = 2, because there are 2 different refinements of B and fewer refinements of other base types. The
worst-case representation for a refinement list is 2 bits, with bit bi indicating whether ei is present in the list. Can
we do any better than 2 bits, since e1 can stand in for e2 ? Could we represent the two types as just 1 bit? We
cannot when (a) there are constants that pass one type but not the other and (b) when refinement lists are in the
reverse order of implication. Suppose there is some k such that e2 [k /x ] −→∗E true and e1 [k /x ] −→∗E false. Now we
0
consider a concatenation of refinement lists in the reverse ordering: join({x :B | e2 }l , {x :B | e1 }l ). We must retain
both checks, since different failures lead to different blame. The k that passes e2 but not e1 should raise ⇑l 0 , but
other k 0 that fail for both types should raise ⇑l . One bit isn’t enough to capture the situation of having the coercion
0
{x :B | e2 }l , {x :B | e1 }l .
Finally, what is the right representation for a function? When calling a function, do we need to run coercions
or not? Jeremy Siek suggested a “smart closure” which holds the logic for branching inside its own code; this may
support better branch prediction than an indirect jump or branching at call sites.

9

Related work

Some earlier work uses first-class casts, whereas our casts are always applied to a term Belo et al. [2011], Knowles
and Flanagan [2010]. It is of course possible to η-expand a cast with an abstraction, so no expressiveness is lost.
Leaving casts fully applied saves us from the puzzling rules managing how casts work on other casts in space-efficient
0
•
•
•
semantics, like: hT11 →T12 ⇒T21 →T22 il hT11 ⇒T12 il −→F hT21 ⇒T22 il .
Previous approaches to space-efficiency have focused on gradual typing Siek and Taha [2006]. This work uses
coercions Henglein [1994], casts, casts annotated with intermediate types a/k/a threesomes, or some combination
of all three Siek et al. [2009], Siek and Wadler [2010], Herman et al. [2010], Siek and Garcia [2012], Garcia [2013].
Recent work relates all three frameworks, making particular use of coercions ?. Our type structure differs from that
of gradual types, so our space bounds come in a somewhat novel form. Gradual types, without the more complicated
checking that comes with predicate contracts, allow for simpler designs. Siek and Wadler [2010] can define a simple
recursive operator on labeled types with a strong relationship to subtyping, the fundamental property of casts. We
haven’t been able to discover a connection in our setting. Instead, we ignore the type structure of functions and focus
our attention on managing labels in lists of first-order predicate contracts. In the gradual world, only ? take a similar
approach, “recursively deconstruct[ing] higher-order types down to their first-order parts” when they compute the
closure of flows into and out of type variables. Gradual types occasionally have simpler proofs, too, e.g., by induction
on evaluation Siek et al. [2009]; even when strong reasoning principles are needed, the presence of dynamic types
leads them to use bisimulation Siek and Wadler [2010], Garcia [2013], ?. We use logical relations because λH ’s type
structure is readily available, and because they allow us to easily reason about how checks evaluate.
Our coercions are inspired by Henglein’s coercions for modeling injection to and projection from the dynamic
type Henglein [1994]. Henglein’s primitive coercions tag and untag values, while ours represent checks to be performed
on base types; both our formulation and Henglein’s use structural function coercions.
Greenberg [2013], the most closely related work, offers a coercion language combining the dynamic types of
Henglein’s original work with predicate contracts; his Efficient language does not quite achieve “sound” space

22

efficeincy. Rather, it is forgetful, occasionally dropping casts. He omits blame, though he conjectures that blame
for coercions reads left to right (as it does in Siek and Garcia [2012]); our eidetic λH verifies this conjecture. While
Greenberg’s languages offer dynamic, simple, and refined types, our types here are entirely refined. His coercions use
Henglein’s ! and ? syntax for injection and projection, while our coercions lack such a distinction. In our refinement
lists, each coercion simultaneously projects from one refinement type and injects into another (possibly producing
blame). We reduce notation by omitting the interrobang ‘?!’.
Dimoulas et al. [2013] introduce option contracts, which offer a programmatic way of turning off contract checking,
as well as a controlled way to “pass the buck”, handing off contracts from component to component. Option contracts
address time efficiency, not space efficiency. Findler et al. [2008] studied space and time efficiency for datatype
contracts, as did Koukoutos and Kuncak [2014].
Racket contracts have a mild form of space efficiency: the tail-marks-match? predicate2 checks for exact duplicate contracts and blame at tail positions. The redundancy it detects seems to rely on pointer equality. Since Racket
contracts are (a) module-oriented “macro” contracts and (b) first class, this optimization is somewhat unpredictable—
and limited compared with our heedful and eidetic calculi, which can handle differing contracts and blame labels.
#lang racket
(define (count-em-integer? x)
(printf "checking ~s\n" x)
(integer? x))
;; yes:
(letrec ([f
(contract (-> any/c count-em-integer?)
(lambda (x)
(printf "x: ~s\n" x)
(if (zero? x) x (f (- x 1))))
’pos
’neg)])
(f 3))
;; no:
(letrec ([f
(contract (-> any/c count-em-integer?)
(contract (-> any/c count-em-integer?)
(lambda (x)
(printf "x: ~s\n" x)
(if (zero? x) x (f (- x 1))))
’pos
’neg)
’pos
’neg)])
(f 3))

10

Conclusion and future work

Semantics-preserving space efficiency for manifest contracts is possible—leaving the admissibility of state as the
final barrier to practical utility. We established that eidetic λH behaves exactly like its classic counterpart without
compromising space usage. Forgetful λH is an interesting middle ground: if contracts exist to make partial operations
safe (and not abstraction or information hiding), forgetfulness may be a good strategy.
We believe it would be easy to design a latent version of eidetic λH , following the translations in Greenberg et al.
[2010].
In our simple (i.e., not dependent) case, our refinement types close over a single variable of base type. Space
efficiency for a dependent calculus remains open. The first step towards dependent types would be extending ⊃
with a context (and a source of closing substitutions, a serious issue Belo et al. [2011]). In a dependent setting the
2

From racket/collects/racket/contract/private/arrow.rkt.

23

definition of what it means to compare closures isn’t at all clear. Closures’ environments may contain functions, and
closures over extensionally equivalent functions may not be intensionally equal. A more nominal approach to contract
comparison may resolve some of the issues here. Comparisons might be more straightforward when contracts are
explicitly declared and referenced by name. Similarly, a dependent ⊃ predicate might be more easily defined over
some explicit structured family of types, like a lattice. Findler et al. [2008] has made some progress in this direction.
Finally, a host of practical issues remain. Beyond representation choices, having expensive checks makes it
important to predict when checks happen. The ⊃ predicate compares closures and will surely have delicate interactions
with optimizations.

Acknowledgments
Comments from Rajeev Alur, Ron Garcia, Fritz Henglein, Greg Morrisett, Stephanie Weirich, Phil Wadler, and
Steve Zdancewic improved a previous version of this work done at the University of Pennsylvania. Some comments
from Benjamin Pierce led me to realize that a cast formulation was straightforward. Discussions with Atsushi Igarashi,
Robby Findler, and Sam Tobin-Hochstadt greatly improved the quality of the exposition. Phil Wadler encouraged me
to return to coercions to understand the eidetic formulation. The POPL reviewers had many excellent suggestions,
and Robby Findler helped once more with angelic guidance. Hannah de Keijzer proofread the paper.
This work was supported in part by the NSF under grants TC 0915671 and SHF 1016937 and by the DARPA
CRASH program through the United States Air Force Research Laboratory (AFRL) under Contract No. FA865010-C-7090. The views expressed are the author’s and do not reflect the official policy or position of the Department
of Defense or the U.S. Government.

References
Anonymous. Blame, coercion, and threesomes: Together again for the first time. In submission., 2014.
J. F. Belo, M. Greenberg, A. Igarashi, and B. C. Pierce. Polymorphic contracts. In European Symposium on
Programming (ESOP), 2011.
G. M. Bierman, A. D. Gordon, C. Hriţcu, and D. Langworthy. Semantic subtyping with an SMT solver. In International Conference on Functional Programming (ICFP), 2010.
C. Dimoulas, R. Findler, and M. Felleisen. Option contracts. In OOPSLA, pages 475 – 494, 2013.
R. B. Findler. Contracts as pairs of projections. In Symposium on Logic Programming, 2006.
R. B. Findler and M. Felleisen. Contracts for higher-order functions. In International Conference on Functional
Programming (ICFP), 2002.
R. B. Findler, S.-Y. Guo, and A. Rogers. Lazy contract checking for immutable data structures. In Implementation
and Application of Functional Languages, pages 111–128. 2008. doi: 10.1007/978-3-540-85373-2 7.
C. Flanagan. Hybrid type checking. In Principles of Programming Languages (POPL), 2006.
R. Garcia. Calculating threesomes, with blame. In International Conference on Functional Programming (ICFP),
2013.
M. Greenberg. Manifest Contracts. PhD thesis, University of Pennsylvania, November 2013.
M. Greenberg. A framework for space-efficient manifest contracts, 2014. URL TODO. Technical report.
M. Greenberg. Space-efficient manifest contracts. In POPL, 2015.
M. Greenberg, B. C. Pierce, and S. Weirich. Contracts made manifest. In Principles of Programming Languages
(POPL), 2010.
M. Greenberg, B. C. Pierce, and S. Weirich. Contracts made manifest. JFP, 22(3):225–274, May 2012.
J. Gronski and C. Flanagan. Unifying hybrid types and contracts. In Trends in Functional Programming (TFP),
2007.

24

F. Henglein. Dynamic typing: Syntax and proof theory. Sci. Comput. Program., 22(3):197–230, 1994.
D. Herman, A. Tomb, and C. Flanagan. Space-efficient gradual typing. In Trends in Functional Programming (TFP),
pages 404–419, 2007.
D. Herman, A. Tomb, and C. Flanagan. Space-efficient gradual typing. Higher Order Symbol. Comput., 23(2):
167–189, June 2010.
K. Knowles and C. Flanagan. Hybrid type checking. ACM Trans. Prog. Lang. Syst., 32:6:1–6:34, 2010.
K. Knowles, A. Tomb, J. Gronski, S. N. Freund, and C. Flanagan. Sage: Hybrid checking for flexible specifications.
In Scheme and Functional Programming Workshop, 2006.
E. Koukoutos and V. Kuncak. Checking data structure properties orders of magnitude faster. In Runtime Verification,
pages 263–268. 2014. doi: 10.1007/978-3-319-11164-3 22.
R. Lipton, October 2010. URL http://goo.gl/6Grgt0.
R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348–375,
Aug. 1978.
PLT. PLT Racket, 2013a. URL http://racket-lang.org.
PLT. PLT Racket contract system, 2013b. URL http://pre.plt-scheme.org/docs/html/guide/contracts.html.
J. Siek, R. Garcia, and W. Taha. Exploring the design space of higher-order casts. In Programming Languages and
Systems, volume 5502 of LNCS, pages 17–31. 2009.
J. G. Siek and R. Garcia. Interpretations of the gradually-typed lambda calculus. In Scheme and Functional
Programming (SFP), 2012.
J. G. Siek and W. Taha. Gradual typing for functional languages. In Scheme and Functional Programming Workshop,
September 2006.
J. G. Siek and P. Wadler. Threesomes, with and without blame. In Principles of Programming Languages (POPL),
pages 365–376, 2010.
N. Swamy, M. Hicks, and G. M. Bierman. A theory of typed coercions and its applications. In International Conference
on Functional Programming (ICFP), pages 329–340, 2009. ISBN 978-1-60558-332-7.
P. Wadler and R. B. Findler. Well-typed programs can’t be blamed. In European Symposium on Programming
(ESOP), 2009.
A. K. Wright and M. Felleisen. A syntactic approach to type soundness. Information and Computation, 115:38–94,
1994.

25

A

Proofs of type soundness

This appendix includes the proofs of type soundness for all four modes of λH ; we first prove some universally applicable
metatheoretical properties.

A.1

Generic metatheory

A.1 Lemma [Weakening]: If Γ1 , Γ2 `m e : T and `m T 0 and x is fresh, then `m Γ1 , x :T 0 , Γ2 and Γ1 , x :T 0 , Γ2 `m
e : T.
Proof:

The context well formedness is by induction on Γ2 .

(WF Empty) By WF Extend.
(WF Extend) By WF Extend and the IH.
By induction on e, leaving Γ2 generalized.
(e = y) If y:T ∈ Γ1 , Γ2 , then y:T ∈ Γ1 , x :T 0 , Γ2 .
(e = k ) By T Const and the first part of the IH.
(e = λy:T1 . e) By T Abs and the IH on e, using Γ2 , y:T1 .
•

(e = hT1 ⇒T2 il e 0 ) By T Cast and the IHs.
c

(e = hT1 ⇒T2 i• e 0 ) By T Coerce and the IHs.
(e = ⇑l ) By T Blame and the IH.
(e = e1 e2 ) By T App and the IHs.
(e = op(e1 , . . . , en )) By T Op and the IHs.
(e = h{x :B | e1 }, e2 , k il ) By T Check and the IH, observing that e2 and k are closed.



A.2 Lemma [Substitution]: If Γ1 , x :T 0 , Γ2 `m e : T and ∅ `m e 0 : T 0 , then Γ1 , Γ2 `m e[e 0 /x ] : T and `m Γ1 , Γ2 .
Proof:

By induction on the typing derivation.

(T Var) By the assumption of typing and weakening, Lemma A.1.
(T Const) By T Const and the IH (for `m Γ1 , Γ2 ).
(T Abs) By T Abs and the IH, renaming the variable.
(T Op) By T Op and the IHs.
(T App) By T App and the IHs.
(T Cast) By T Cast and the IHs, observing that all types are closed, though the term may not be.
(T Coerce) By T Coerce and the IHs, observing that all types are closed, though the term may not be.
(T Blame) By T Blame and the IH (for `m Γ1 , Γ2 ).
(T Check) By T Check and the IH (for `m Γ1 , Γ2 ). Note that the subterms are all closed, so the substitution
actually has no effect other than strengthening the context.

A.3 Lemma [Coercion typing regularity]: If `E c k T1 ⇒ T2 then `E T1 and `E T2 .
Proof:

By induction on the coercion well formedness derivation.

(A Refine) By assumption.
(A Fun) By WF Fun on the IHs.

A.4 Lemma [Regularity]: If Γ `m e : T , then `m Γ and `m T .
Proof:

By induction on the typing relation.

(T Var) We have `m Γ by assumption, and `m T by induction on the derivation of `m Γ.
(T Const) We have `m Γ and `m T by assumption.
(T Abs) By the IH, we get `m Γ, x :T1 and `m T2 . By inversion we find `m Γ; by WF Fun and the assumption
that `m T1 , we find `m T1 →T2 .
26

(T
(T
(T
(T
(T
(T

Op) We have `m Γ and `m T by assumption.
App) By the IH, `m T1 →T2 and `m Γ. By inversion, `m T2 .
Cast) By WF Fun and inversion of the type set well formedness; `m Γ is by the IH on Γ `m e : T1 .
Coerce) It must be that m = E; by coercion regularity (Lemma A.3).
Blame) By assumption.
Check) By assumption.


A.5 Lemma [Similarity is reflexive]: If ` T k T .
Proof:

By induction on T .

(T = {x :B | e}) By S Refine.
(T = T1 →T2 ) By S Fun and the IHs.

A.6 Lemma [Similarity is symmetric]: If ` T1 k T2 , then ` T2 k T1 .
Proof:

By induction on the similarity derivation.

(S Refine) By S Refine.
(S Fun) By S Fun and the IHs.

A.7 Lemma [Similarity is transitive]: If ` T1 k T2 and ` T2 k T3 , then ` T1 k T3 .
Proof:

By induction on the derivation of ` T1 k T2 .

(S Refine) The other derivation must also be by S Refine; by S Refine.
(S Fun) The other derivation must also be by S Fun; by S Fun and the IHs.

A.8 Lemma [Well formed type sets have similar indices]:
If `m S k T1 ⇒ T2 then ` T1 k T2 .
Proof:

Immediate, by inversion.



A.9 Lemma [Type set well formedness is symmetric]: `m a k T1 ⇒ T2 iff `m a k T2 ⇒ T1 for all m 6= E.
Proof: We immediately have `m T1 and `m T2 , and ` T1 k T2 iff ` T2 k T1 by Lemma A.6.
If m = C or m = F, then by A None and symmetry of similarity (Lemma A.6.
If m = H, then let T ∈ S be given. The `H T premises hold immediately; we are then done by transitivity
(Lemma A.7) and symmetry (Lemma A.6) of similarity (` T k T1 iff ` T k T2 when ` T1 k T2 ).

A.10 Lemma [Type set well formedness is transitive]: If ` T1 k T2 and `m a k T2 ⇒ T3 and `m T1 and
m 6= E then `m a k T1 ⇒ T3 .
Proof: We immediately have `m T1 and `m T3 ; we have ` T1 k T3 by transitivity of similarity (Lemma A.7).
If m = C or m = F, we are done immediately by A None.
If, on the other hand, m = H, let T ∈ S be given. We know that `H T and ` T k T2 ; by symmetry (Lemma A.6)
and transitivity (Lemma A.7) of similarity, we are done by A TypeSet.


A.2

Classic type soundness

A.11 Lemma [Classic determinism]: If e −→C e1 and e −→C e2 then e1 = e2 .
Proof:

By induction on the first evaluation derivation.



A.12 Lemma [Classic canonical forms]: If ∅ `C e : T and valC e then:
– If T = {x :B | e 0 }, then e = k and ty(k ) = B and e 0 [e/x ] −→∗C true.
•
– If T = T1 →T2 , then either e = λx :T . e 0 or e = hT11 →T12 ⇒T21 →T22 il e 0 .
27

Proof: By inversion of valC e and inspection of the typing rules. V Const/T Const are the only rules that types
values at base types; V Abs/T Abs and V Proxy/T Cast are the only rules that type values at function types. 
A.13 Lemma [Classic progress]: If ∅ `C e : T , then either:
1. resultC e, i.e., e = ⇑l or valC e; or
2. there exists an e 0 such that e −→C e 0 .
Proof:

By induction on the typing derivation.

(T Var) A contradiction—x isn’t well typed in the empty environment.
(T Const) e = k is a result by V Const and R Val.
(T Abs) e = λx :T . e 0 is a result by V Abs and R Val.
(T Op) We know that ty(op) is a first order type {x :B1 | e10 } → ... → {x :Bn | en0 }→T . From left to right, we
apply the IH on ei . If ei is a result, there are two cases: either ei = ⇑l , and we step by E OpRaise; or ei = ki , since
constants are the only values at base types by canonical forms (Lemma A.12), and we continue on to the next ei . If
any of the ei step, we know that all of terms before them are values, so we can step by E OpInner. If all of the ei
are constants ki , then ∅ `C ki : {x :Bi | ei0 }, and so ei0 [ki /x ] −→∗C true. Therefore [[op]] (k1 , ... , kn ) is defined, and we
can step by E Op.
(T App) By the IH on e1 , we know that e1 : is blame, is a value, or steps to some e10 . In the first case, we take a
step by E AppRaiseL. In the latter, we take a step by E AppL.
If valC e1 , then we can apply the IH on e2 , which is blame, is a value, or steps to some e20 . The first and last cases
are as before, using E AppRaiseR and E AppR.
If valC e2 , we must go by cases on the shape of e1 . Since ∅ `C e1 : T1 →T2 , by canonical forms (Lemma A.12) we
know that e1 can only be an abstraction, a wrapped abstraction, or a cast.
(e1 = λx :T1 . e10 ) We step to e10 [e2 /x ] by E Beta.
•
•
•
(e1 = hT11 →T12 ⇒T21 →T22 il e10 ) We step to hT12 ⇒T22 il (e10 (hT21 ⇒T11 il e2 )) by E Unwrap, noting that all
of the type sets are empty.
(T Cast) If e 0 −→C e 00 , then by E CastInnerC. If e 0 is blame, then by E CastRaise. If valC e 0 , then we
invert ` T1 k T2 , finding that either:
(Ti = {x :B | ei }) By canonical forms (Lemma A.12), e2 = k .
E CheckNone.
(Ti = Ti 1 →Ti 2 ) This is a value, V ProxyC.

We can step to h{x :B | e2 }, e2 [k /x ], k il by

(T Blame) ⇑l is a result by R Blame.
(T Check) By the IH on e2 , we know that e2 : is ⇑l 0 , is a value by valC e2 , or takes a step to some e20 . In the
first case, we step to ⇑l 0 by E CheckRaise. In the last case, we step by E CheckInner. If valC e2 , by canonical
forms (Lemma A.12) we know that e2 is a k such that ty(k ) = Bool, i.e., e2 is either true or false. In the former case,
we step to k by E CheckOK; in the latter case, we step to ⇑l by E CheckFail.

A.14 Lemma [Classic preservation]: If ∅ `C e : T and e −→C e 0 , then ∅ `C e 0 : T .
Proof:
(T
(T
(T
(T

By induction on the typing derivation.

Var) Contradictory—x isn’t well typed in an empty context.
Const) Contradictory—constants don’t step.
Abs) Contradictory—lambdas don’t step.
Op) By cases on the step taken.

(E Op) [[op]] (k1 , ... , kn ) = k ; we assume that ty(op) correctly assigns types, i.e., if ty(op) = {x :B1 | e10 } → ... →
{x :Bn | en0 }→{x :B | e}, then e[k /x ] −→∗C true and `C {x :B | e}. We can therefore conclude that ∅ `C k : {x :B | e}
by T Const.
(E OpInner) By the IH and T Op.
(E OpRaise) We assume that ty(op) only assigns well formed types, so ∅ `C ⇑l : T .
(T App) By cases on the step taken.
(E Beta) We know that x :T1 `C e1 : T2 and ∅ `C e2 : T1 ; we are done by substitution (Lemma A.2).

28

(E Unwrap) By inversion of `C ∅ k T11 →T12 ⇒ T21 →T22 , we find well formedness judgments `C T11 and
`C T12 and `C T21 and `C T22 and similarity judgments ` T11 k T21 and ` T12 k T22 ; by symmetry (Lemma A.6),
` T21 k T11 . Noting that dom(•) = cod(•) = •, we can apply A None, finding `C • k T21 ⇒ T11 and `C • k T12 ⇒
•
•
T22 . We can then apply T Cast, T App, and assumptions to find ∅ `C hT12 ⇒T22 il (e1 (hT21 ⇒T11 il e2 )) : T22 .
(E AppL) By T App and the IH.
(E AppR) By T App and the IH.
(E AppRaiseL) By regularity, `C T2 , so we are done by T Blame.
(E AppRaiseR) By regularity, `C T2 , so we are done by T Blame.
(T Cast) By cases on the step taken.
(E CheckNone) We have `C Γ and `C {x :B | e2 } and ty(k ) = B by inversion and e2 [k /x ] −→∗C e2 [k /x ] by
reflexivity. By substitution (and T Const, to find ∅ `C k : {x :B | true}), we find ∅ `C e2 [k /x ] : {x :Bool | true}. We
can now apply T Check, and are done.
(E CastInnerC) By T Cast and the IH.
(E CastRaise) We have by assumption that `C T2 , so we are done by T Blame.
(T Blame) Contradictory—blame doesn’t step.
(T Check) By cases on the step taken.
(E CheckOK) Since `C ∅ and ty(k ) = B and `C {x :B | e1 } and e1 [k /x ] −→∗C true, we can apply T Const to
find ∅ `C k : {x :B | e1 }.
(E CheckFail) Since `C ∅ and `C {x :B | e1 }, T Blame shows ∅ `C ⇑l : {x :B | e1 }.
(E CheckInner) By T Check and the IH.
(E CheckRaise) As for E CheckFail—the differing label doesn’t matter.


A.3

Forgetful type soundness

Just as we did for classic λH in Appendix A.2, we reuse the theorems from Appendix A.1. Note that if e is a value
in forgetful λH , it’s also a value in classic λH , i.e., valF e implies valC e.
A.15 Lemma [Forgetful determinism]:
If e −→F e1 and e −→F e2 then e1 = e2 .
Proof:

By induction on the first evaluation derivation.



A.16 Lemma [Forgetful canonical forms]: If ∅ `F e : T and valF e then:
– If T = {x :B | e 0 }, then e = k and ty(k ) = B and e 0 [e/x ] −→∗F true.
•
– If T = T1 →T2 , then either e = λx :T . e 0 or e = hT11 →T12 ⇒T21 →T22 il λx :T11 . e 0 .
Proof: By inspection of the rules: T Const is the only rule that types values at base types; T Abs and T Cast
are the only rules that type values at function types.

A.17 Lemma [Forgetful progress]: If ∅ `F e : T , then either:
1. resultF e is a result, i.e., e = ⇑l or valF e; or
2. there exists an e 0 such that e −→F e 0 .
Proof:

By induction on the typing derivation.

(T Var) A contradiction—x isn’t well typed in the empty environment.
(T Const) e = k is a result.
(T Abs) e = λx :T . e 0 is a result.
(T Op) We know that ty(op) is a first order type {x :B1 | e10 } → ... → {x :Bn | en0 }→T . From left to right, we
apply the IH on ei . If ei is a result, there are two cases: either ei = ⇑l , and we step by E OpRaise; or ei = ki , since
constants are the only values at base types by canonical forms (Lemma A.16), and we continue on to the next ei . If
any of the ei step, we know that all of terms before them are values, so we can step by E OpInner. If all of the ei
are constants ki , then ∅ `F ki : {x :Bi | ei0 }, and so ei0 [ki /x ] −→∗F true. Therefore [[op]] (k1 , ... , kn ) is defined, and we
can step by E Op.

29

(T App) By the IH on e1 , we know that e1 : is blame, is a value, or steps to some e10 . In the first case, we take a
step by E AppRaiseL. In the latter, we take a step by E AppL.
If valC e1 , then we can apply the IH on e2 , which is blame, is a value, or steps to some e20 .
If e2 is blame, we step by E AppRaiseR. Otherwise, we must go by cases. Since ∅ `F e1 : T1 →T2 and valF e1 , by
canonical forms (Lemma A.16) we know that e1 can only be an abstraction, a wrapped abstraction, or a cast.
(e1 = λx :T1 . e10 ) If valF e2 , we step to e10 [e2 /x ] by E Beta. If e2 −→F e20 , we step by E AppR (since e1 isn’t a
cast).
•
•
•
(e1 = hT11 →T12 ⇒T21 →T22 il e10 ) If valF e2 , we step to hT12 ⇒T22 il (e10 (hT21 ⇒T11 il e2 )) by E Unwrap (noting
0
that the annotation is •). If e2 −→F e2 , we step by E AppR (since e1 isn’t a cast).
(T Cast) If e 0 = ⇑l 0 , then we step by E CastRaise. If valF e2 , then we have `F • k T1 ⇒ T2 ; by inversion
` T1 k T2 . By inversion, one of the following cases adheres:
(Ti = {x :B | e1 i }) By canonical forms (Lemma A.16), e2 = k . We can step to h{x :B | e12 }, e12 [k /x ], k il by
E CheckNone.
(Ti = Ti 1 →Ti 2 ) By canonical forms (Lemma A.16), e2 is a lambda or a function proxy. In the latter case, we
step by E CastMerge; either way, we have a function proxy, which is a value.
•

If e2 isn’t a value or blame, then e2 −→F e20 . If e2 6= hT31 →T32 ⇒T11 →T12 il e200 , then we can step by E CastInner.
If e2 is in fact an application of a cast, we step by E CastMerge.
(T Blame) ⇑l is a result.
(T Check) By the IH on e2 , we know that e2 : is ⇑l 0 , is a value, or takes a step to some e20 . In the first case,
we step to ⇑l 0 by E CheckRaise. In the last case, we step by E CheckInner. If valF e2 , by canonical forms
(Lemma A.16) we know that e2 is a k such that ty(k ) = Bool, i.e., e2 is either true or false. In the former case, we
step to k by E CheckOK; in the latter case, we step to ⇑l by E CheckFail.

A.18 Lemma [Forgetful preservation]: If ∅ `F e : T and e −→F e 0 then ∅ `F e 0 : T .
Proof:
(T
(T
(T
(T

By induction on the typing derivation.

Var) Contradictory—we assumed e was well typed in an empty context.
Const) Contradictory—k is a value and doesn’t step.
Abs) Contradictory—λx :T1 . e 0 is a value and doesn’t step.
Op) By cases on the step taken.

(E Op) [[op]] (k1 , ... , kn ) = k ; we assume that ty(op) correctly assigns types, i.e., if ty(op) = {x :B1 | e10 } → ... →
{x :Bn | en0 }→{x :B | e}, then e[k /x ] −→∗F true and `F {x :B | e}. We can therefore conclude that ∅ `F k : {x :B | e}
by T Const.
(E OpInner) By the IH and T Op.
(E OpRaise) We assume that ty(op) only assigns well formed types, so ∅ `F ⇑l : T .
(T App) By cases on the step taken.
(E Beta) We know that x :T1 `F e1 : T2 and ∅ `F e2 : T1 ; we are done by substitution (Lemma A.2).
(E Unwrap) By inversion of `F ∅ k T11 →T12 ⇒ T21 →T22 , we find well formedness judgments `F T11 and `F T12
and `F T21 and `F T22 and similarity judgments ` T11 k T21 and ` T12 k T22 ; by symmetry (Lemma A.6), ` T21 k
T11 . Noting that dom(•) = cod(•) = •, we can apply A None to find derivations `F • k T21 ⇒ T11 and `F • k T12 ⇒
•
•
T22 . We can then apply T Cast, T App, and assumptions to find ∅ `F hT12 ⇒T22 il (e1 (hT21 ⇒T11 il e2 )) : T22 .
(E AppL) By T App and the IH.
(E AppR) By T App and the IH.
(E AppRaiseL) By regularity, `F T2 , so we are done by T Blame.
(E AppRaiseR) By regularity, `F T2 , so we are done by T Blame.
(T Cast) By cases on the step taken.
(E CheckNone) We have `F Γ and `F {x :B | e2 } and ty(k ) = B by inversion and e2 [k /x ] −→∗F e2 [k /x ] by
reflexivity. By substitution (and T Const, to find ∅ `F k : {x :B | true}), we find ∅ `F e2 [k /x ] : {x :Bool | true}. We
can now apply T Check, and are done.
(E CastInner) By T Cast and the IH.
(E CastMerge) We can combine the two T Cast derivations (using Lemma A.10 and the fact that a = • to
find similarity). Then we are done by T Cast.
30

(E CastRaise) We have `F T2 by assumption, so we are done by T Blame.
(T Blame) Contradictory—⇑l is a result and doesn’t step.
(T Check) By cases on the step taken.
(E CheckOK) Since `F ∅ and ty(k ) = B and `F {x :B | e1 } and e1 [k /x ] −→∗F true, we can apply T Const to
find ∅ `F k : {x :B | e1 }.
(E CheckFail) Since `F ∅ and `F {x :B | e1 }, T Blame shows ∅ `F ⇑l : {x :B | e1 }.
(E CheckInner) By T Check and the IH.
(E CheckRaise) As for E CheckFail—the differing label doesn’t matter.

In addition to showing type soundness, we prove that a source program (Definition 3.1) is well typed with m = F
iff it is well typed with m = C.
A.19 Lemma [Source program typing for forgetful λH ]:
Source programs are well typed in C iff they are well typed in F, i.e.:
– Γ `C e : T as a source program iff Γ `F e : T as a source program.
– `C T as a source program iff `F T as a source program.
– `C Γ as a source program iff `F Γ as a source program.
Proof: By mutual induction on e, T , and Γ. Since all of the rules are syntax directed, we use the rule names for
cases (but prove both directions at once).
Expressions e
(T Var) By the IH on Γ and T Var.
(T Const) By the IH on Γ and T Const, noting that true −→∗m true in every mode m.
(T Abs) By the IH on T1 and e12 and T Abs.
(T Op) By the IHs on the arguments ei and T Op.
(T App) By the IHs on e1 and e2 and T App.
(T Cast) By the IHs on T1 and T2 and T Cast, noting that similarity holds irrespective of modes and that the
annotation is •.
(T Blame) Contradictory—doesn’t occur in source programs.
(T Check) Contradictory—doesn’t occur in source programs.
Types T
(WF Base) Immediately true—WF Base is an axiom.
(WF Refine) By the IH on e and WF Refine.
(WF Fun) By the IHs on T1 and T2 and WF Fun.
Contexts Γ
(WF Empty) Immediately true—WF Empty is an axiom.
(WF Extend) By the IHs on Γ and T and WF Extend.


A.4

Heedful type soundness

A.20 Lemma [Heedful canonical forms]: If ∅ `H e : T and valH e then:
– If T = {x :B | e 0 }, then e = k and ty(k ) = B and e 0 [e/x ] −→∗H true.
S

– If T = T1 →T2 , then either e = λx :T . e 0 or e = hT11 →T12 ⇒T21 →T22 il λx :T11 . e 0 .
Proof: By inspection of the rules: T Const is the only rule that types values at base types; T Abs and T Cast
are the only rules that type values at function types. Note that now our proxies may have type sets in them.

A.21 Lemma [Heedful progress]: If ∅ `H e : T , then either:

31

1. resultH e, i.e., e = ⇑l or valH e; or
2. there exists an e 0 such that e −→H e 0 .
Proof:

By induction on the typing derivation.

(T Var) A contradiction—x isn’t well typed in the empty environment.
(T Const) e = k is a result by V Const and R Val.
(T Abs) e = λx :T . e 0 is a result by V Abs and R Val.
(T Op) We know that ty(op) is a first order type {x :B1 | e10 } → ... → {x :Bn | en0 }→T . From left to right, we
apply the IH on ei . If ei is a result, there are two cases: either ei = ⇑l , and we step by E OpRaise; or ei = ki , since
constants are the only values at base types by canonical forms (Lemma A.20), and we continue on to the next ei . If
any of the ei step, we know that all of terms before them are values, so we can step by E OpInner. If all of the ei
are constants ki , then ∅ `E ki : {x :Bi | ei0 }, and so ei0 [ki /x ] −→∗H true. Therefore [[op]] (k1 , ... , kn ) is defined, and we
can step by E Op.
(T App) By the IH on e1 , we know that e1 : is blame, is a value, or steps to some e10 . In the first case, we take a
step by E AppRaiseL. In the latter, we take a step by E AppL.
If valH e1 , then we can apply the IH on e2 , which is blame, is a value, or steps to some e20 . The first and last cases
are as before, using E AppRaiseR and E AppR.
If valH e2 , we must go by cases on the shape of e1 . Since ∅ `H e1 : T1 →T2 , by canonical forms (Lemma A.20) we
know that e1 can only be an abstraction, a wrapped abstraction, or a cast.
(e1 = λx :T1 . e10 ) We step to e10 [e2 /x ] by E Beta.
S

cod(S)

dom(S)

(e1 = hT11 →T12 ⇒T21 →T22 il e10 ) We step to hT12 ⇒ T22 il (e10 (hT21 ⇒ T11 il e2 )) by E Unwrap.
S

(T Cast) If the annotation is •, we step by E TypeSet. We have e = hT1 ⇒T2 il e1 . If e1 is blame, then we
step by E CastRaise. If e1 is a value, then we go by cases on valH e1 :
(V Const) The case must be between refinements, and we step by E CheckSet or E CheckEmpty.
(V Abs) The cast must be between function types, and we have a value.
(V ProxyH) The cast must be between function types, and we step by E CastMerge.
S

0

2
l
Finally, it may be the case that e1 −→H e10 . If e1 6= hT3 ⇒T
e100 , then we step by E CastInner. On the other
1i
hand, if e1 is a cast term, we step by E CastMerge.
(T Blame) ⇑l is a result by R Blame.
(T Check) By the IH on e2 , we know that e2 : is ⇑l 0 , is a value by valH e2 , or takes a step to some e20 . In the
first case, we step to ⇑l 0 by E CheckRaise. In the last case, we step by E CheckInner. If valE e2 , by canonical
forms (Lemma A.20) we know that e2 is a k such that ty(k ) = Bool, i.e., e2 is either true or false. In the former case,
we step to k by E CheckOK; in the latter case, we step to ⇑l by E CheckFail.


Before proving preservation, we must establish some properties about type sets: type sets as merged by E CastMerge
are well formed; the dom and cod operators take type sets of function types and produce well formed type sets.
A.22 Lemma [Merged type sets are well formed]: If `H S1 k T1 ⇒ T2 and `H S2 k T2 ⇒ T3 then `H (S1 ∪
S2 ∪ {T2 }) k T1 ⇒ T3 .
Proof: By transitivity of similarity, we have ` T1 k T3 . We have `H T1 and `H T3 from each of the A TypeSet
derivations, so it remains to show the premises for each T ∈ S.
Let T ∈ (S1 ∪ S2 ∪ {T2 }). We have ` T k T1 and `H T (a) by assumption and symmetry (Lemma A.6) if
T = T2 ; and (b) by A TypeSet and symmetry and transitivity (Lemma A.7) if T ∈ S1 ∪ S2 . We can therefore apply
A TypeSet, and we are done.

A.23 Lemma [Domain type set well formedness]: If `H S k T11 →T12 ⇒ T21 →T22 then `H dom(S) k T21 ⇒
T11 .
Proof: First, observe that for every T ∈ S, we know that ` T k T11 →T12 , so each Ti = Ti 1 →Ti 2 by inversion.
This means that dom(S) is well defined.
By inversion of similarity and type well formedness, we have ` T11 k T21 and `H T11 and `H T21 . By symmetry
of similarity, we have ` T21 k T11 (Lemma A.6).
Let Ti 1 ∈ dom(S) by given. We know that there exists some Ti 2 such that Ti 1 →Ti 2 ∈ S and ` Ti 1 →Ti 2 k
T11 →T12 and `H Ti 1 →Ti 2 . By inversion, we find ` Ti 1 k T11 and `H Ti 1 . By transitivity of similarity (Lemma A.7),
we have ` Ti 1 k T21 , and we are done by A TypeSet.

32

A.24 Lemma [Codomain type set well formedness]: If `H S k T11 →T12 ⇒ T21 →T22 then `H cod(S) k T12 ⇒
T22 .
Proof: First, observe that for every T ∈ S, we know that ` T k T11 →T12 , so each Ti = Ti 1 →Ti 2 by inversion.
This means that dom(S) is well defined.
By inversion of similarity and type well formedness, we have ` T12 k T22 and `H T12 and `H T22 .
Let Ti 2 ∈ dom(S) by given. We know that there exists some Ti 2 such that Ti 1 →Ti 2 ∈ S and ` Ti 1 →Ti 2 k
T12 →T12 and `H Ti 1 →Ti 2 . By inversion, we find ` Ti 2 k T12 and `H Ti 2 . We are done by A TypeSet.

A.25 Lemma [Reducing type sets]: If `H S k T1 ⇒ T3 then `H (S \ T2 ) k T1 ⇒ T3 .
Proof: All of the T ∈ S remain well formed and similar to T1 and T3 , as do the well formedness and similarity
relations for T1 and T3 .

A.26 Lemma [Heedful preservation]: If ∅ `H e : T and e −→H e 0 then ∅ `H e 0 : T .
Proof:
(T
(T
(T
(T

By induction on the typing derivation.

Var) Contradictory—we assumed e was well typed in an empty context.
Const) Contradictory—k is a value and doesn’t step.
Abs) Contradictory—λx :T1 . e 0 is a value and doesn’t step.
Op) By cases on the step taken.

(E Op) [[op]] (k1 , ... , kn ) = k ; we assume that ty(op) correctly assigns types, i.e., if ty(op) = {x :B1 | e10 } → ... →
{x :Bn | en0 }→{x :B | e}, then e[k /x ] −→∗H true and `H {x :B | e}. We can therefore conclude that ∅ `H k : {x :B | e}
by T Const.
(E OpInner) By the IH and T Op.
(E OpRaise) We assume that ty(op) only assigns well formed types, so ∅ `H ⇑l : T .
(T App) By cases on the step taken.
(E Beta) We know that x :T1 `H e1 : T2 and ∅ `H e2 : T1 ; we are done by substitution (Lemma A.2).
cod(S)

S

dom(S)

(E Unwrap) We have e = (hT11 →T12 ⇒T21 →T22 il e1 ) e2 −→H hT12 ⇒ T22 il (e1 (hT21 ⇒ T11 il e2 )) = e 0 .
By inversion, ` T11 →T12 k T21 →T22 and `H S k T11 →T12 ⇒ T21 →T22 . By Lemma A.23, `H dom(S) k T21 ⇒
T11 ; by Lemma A.24, `H cod(S) k T12 ⇒ T22 .
dom(S)

By inversion, ∅ `H e2 : T21 ; so ∅ `H hT21 ⇒ T11 il e2 : T11 by T Cast. By inversion, ∅ `H e1 : T11 →T12 , so
dom(S)

∅ `H e1 (hT21 ⇒ T11 il e2 ) : T12 by T App. By the type set typing for cod(S), we can apply T Cast to finish the
case, typing the whole term at T22 .
(E AppL) By T App and the IH.
(E AppR) By T App and the IH.
(E AppRaiseL) By regularity, `H T2 , so we are done by T Blame.
(E AppRaiseR) By regularity, `H T2 , so we are done by T Blame.
(T Cast) By cases on the step taken.
(E TypeSet) By the assumptions, using A None to derive A TypeSet—which holds vacuously, since the set is
empty.
(E CheckEmpty) We have `H Γ and `H {x :B | e2 } and ty(k ) = B by inversion and e2 [k /x ] −→∗H e2 [k /x ] by
reflexivity. By substitution (and T Const, to find ∅ `H k : {x :B | true}), we find ∅ `H e2 [k /x ] : {x :Bool | true}. We
can now apply T Check, and are done.
(E CheckSet) We have
S

S\{x :B|e2 }

h{x :B | e1 }⇒{x :B | e3 }il k −→H h{x :B | e2 }

⇒

{x :B | e3 }il h{x :B | e2 }, e2 [k /x ], k il

where choose(S) = {x :B | e2 }, so {x :B | e2 } ∈ S. We have `H Γ and `H {x :B | e2 } and ty(k ) = B by inversion
and e2 [k /x ] −→∗H e2 [k /x ] by reflexivity. By substitution (and T Const, to find ∅ `H k : {x :B | true}), we find
∅ `H e2 [k /x ] : {x :Bool | true}. We can now apply T Check to type the active check at {x :B | e2 }.
By inversion of the original type set well formedness derivation, ` {x :B | e2 } k {x :B | e1 } and `H {{x :B | e2 }}∪S k
{x :B | e1 } ⇒ {x :B | e3 }; by Lemma A.25, `H S \ {x :B | e2 } k {x :B | e2 } ⇒ {x :B | e3 }. We have ` {x :B | e2 } k
{x :B | e3 } transitivity of similarity (` {x :B | e1 } k {x :B | e3 } and Lemma A.7). So now we can apply T Cast to our
T Check derivation, and we are done.
(E CastInner) By T Cast and the IH.
33

(E CastMerge) We have
S

S

2
1
l2
l1
hT2 ⇒T
(hT1 ⇒T
e) −→H
3i
2i

hT1

(S1 ∪S2 ∪{T2 })

⇒

T3 il2 e.

By Lemma A.22, `H (S1 ∪ S2 ∪ {T2 }) k T1 ⇒ T3 . We already know that ∅ `H e1 : T1 (by assumption) and `H T3
(by inversion of the outer cast’s typing derivation), so we can apply T Cast to type the resulting merged cast.
(E CastRaise) We have `H T2 by assumption, so we are done by T Blame.
(T Blame) Contradictory—⇑l is a result and doesn’t step.
(T Check) By cases on the step taken.
(E CheckOK) Since `H ∅ and ty(k ) = B and `H {x :B | e1 } and e1 [k /x ] −→∗H true, we can apply T Const to
find ∅ `H k : {x :B | e1 }.
(E CheckFail) Since `H ∅ and `H {x :B | e1 }, T Blame shows ∅ `H ⇑l : {x :B | e1 }.
(E CheckInner) By T Check and the IH.
(E CheckRaise) As for E CheckFail—the differing label doesn’t matter.

Just as we did for forgetful λH in (Appendix A.3), we show that source programs are well typed heedfully iff they
are well typed classically—iff they are well typed forgetfull (Lemma A.19). that is, source programs are valid staring
points in any mode.
A.27 Lemma [Source program typing for heedful λH ]:
Source programs are well typed in C iff they are well typed in H, i.e.:
– Γ `C e : T as a source program iff Γ `H e : T as a source program.
– `C T as a source program iff `H T as a source program.
– `C Γ as a source program iff `H Γ as a source program.
Proof: By mutual induction on e, T , and Γ. Since all of the rules are syntax directed, we use the rule names for
cases (but prove both directions at once).
Expressions e
(T
(T
(T
(T
(T
(T
(T
(T

Var) By the IH on Γ and T Var.
Const) By the IH on Γ and T Const, noting that true −→∗m true in every mode m.
Abs) By the IH on T1 and e12 and T Abs.
Op) By the IHs on the arguments ei and T Op.
App) By the IHs on e1 and e2 and T App.
Cast) By the IHs on T1 and T2 and T Cast, using A None for the source program.
Blame) Contradictory—doesn’t occur in source programs.
Check) Contradictory—doesn’t occur in source programs.

Types T
(WF Base) Immediately true—WF Base is an axiom.
(WF Refine) By the IH on e and WF Refine.
(WF Fun) By the IHs on T1 and T2 and WF Fun.
Contexts Γ
(WF Empty) Immediately true—WF Empty is an axiom.
(WF Extend) By the IHs on Γ and T and WF Extend.


34

A.5

Eidetic type soundness

A.28 Lemma [Determinism of eidetic λH ]: If e −→E e1 and e −→E e2 then e1 = e2 .
Proof:

By induction on the first evaluation derivation. In every case, only a single step can be taken.



A.29 Lemma [Eidetic canonical forms]: If ∅ `E e : T and valE e then:
– If T = {x :B | e 0 }, then e = k and ty(k ) = B and e 0 [e/x ] −→∗E true.
c 7→c
– If T = T21 →T22 , then either e = λx :T . e 0 or e = hT11 →T12 1⇒ 2 T21 →T22 i• λx :T11 . e 0 .
Proof: By inspection of the rules: T Const is the only rule that types values at base types; T Abs and T Cast
are the only rules that type values at function types. Note that now our proxies use coercions and not types and
type sets.

A.30 Lemma [Eidetic progress]: If ∅ `E e : T , then either:
1. resultE e, i.e., e = ⇑l or valE e; or
2. there exists an e 0 such that e −→E e 0 .
Proof:

By induction on the typing derivation.

(T Var) A contradiction—x isn’t well typed in the empty environment.
(T Const) e = k is a result by V Const and R Val.
(T Abs) e = λx :T . e 0 is a result by V Abs and R Val.
(T Op) We know that ty(op) is a first order type {x :B1 | e10 } → ... → {x :Bn | en0 }→T . From left to right, we
apply the IH on ei . If ei is a result, there are two cases: either ei = ⇑l , and we step by E OpRaise; or ei = ki , since
constants are the only values at base types by canonical forms (Lemma A.29), and we continue on to the next ei . If
any of the ei step, we know that all of terms before them are values, so we can step by E OpInner. If all of the ei
are constants ki , then ∅ `E ki : {x :Bi | ei0 }, and so ei0 [ki /x ] −→∗H true. Therefore [[op]] (k1 , ... , kn ) is defined, and we
can step by E Op.
(T App) By the IH on e1 , we know that e1 : is blame, is a value, or steps to some e10 . In the first case, we take a
step by E AppRaiseL. In the latter, we take a step by E AppL.
If valE e1 , then we can apply the IH on e2 , which is blame, is a value, or steps to some e20 . The first and last cases
are as before, using E AppRaiseR and E AppR.
If valE e2 , we must go by cases on the shape of e1 . Since ∅ `E e1 : T1 →T2 , by canonical forms (Lemma A.29) we
know that e1 can only be an abstraction, a wrapped abstraction, or a cast.
(e1 = λx :T1 . e10 ) We step to e10 [e2 /x ] by E Beta.
c1
c 7→c
c2
•
•
0
(e1 = hT11 →T12 1⇒ 2 T21 →T22 i• λx :T11 . e10 ) We step to hT12 ⇒T
22 i ((λx :T11 . e1 ) (hT21 ⇒T11 i e2 )) by E Unwrap.
coerce(T1 ,T2 ,l)

(T Cast) We step by E Coerce to hT1
⇒
T2 i• e.
c
•
(T Coerce) We have e = hT1 ⇒T2 i e1 . If e1 is blame, then we step by E CoerceRaise. If e1 is a value, then
we go by cases on valE e1 :
(V Const) The case must be between refinements, and we step by E CoerceStack.
(V Abs) The cast must be between function types, and we have a value by V ProxyE.
(V ProxyE) We step by E CastMerge.
c0

Finally, it may be the case that e1 −→E e10 . If e1 6= hT3 ⇒T1 i• e100 , then we step by E CastInner. On the other
hand, if e1 is a coercion term, we step by E CastMerge.
(T Blame) ⇑l is a result by R Blame.
(T Stack) By cases on the shape of r : if r = nil, we know that s = X. We step by E StackDone if e = k ;
otherwise, we step by E StackInner or E StackRaise. If not, we go by cases on the shape of e. If e = k , then we
step by E StackPop. Otherwise, we step by E StackInner or E StackRaise.
(T Check) By the IH on e2 , we know that e2 : is ⇑l 0 , is a value by valE e2 , or takes a step to some e20 . In the first
case, we step to ⇑l 0 by E CheckRaise. In the last case, we step by E CheckInner. If valE e2 , by canonical forms
(Lemma A.29) we know that e2 is a k such that ty(k ) = Bool, i.e., e2 is either true or false. In the former case, we
step to k by E CheckOK; in the latter case, we step to ⇑l by E CheckFail.


35

A.31 Lemma [Extended refinement lists are well formed]:
If `E {x :B | e} and `E r k {x :B | e1 } ⇒ {x :B | e2 } then `E join({x :B | e}l , r ) k {x :B | e1 } ⇒ {x :B | e2 }.
Proof:

By cases on the rule used.

(A Refine) All of the premises are immediately restored except in one tricky case. When {x :B | e} ⊃ {x :B | e 0 }
where {x :B | e 0 } ∈ r is the only type implying {x :B | e2 }. Then drop (r , {x :B | e}) isn’t well formed on its own, but
adding {x :B | e}l makes it so by transitivity. If not, then we know that drop (r , {x :B | e}) is well formed, and so is
its extensions by assumption.
We know that there are no duplicates by reflexivity of ⊃.
(A Fun) Contradictory.

A.32 Lemma [Merged coercions are well formed]: If `E c1 k T1 ⇒ T2 and `E c2 k T2 ⇒ T3 then `E join(c1 , c2 ) k
T1 ⇒ T3 .
Proof:

By induction on c1 ’s typing derivation.

(A Refine) By the IH, Lemma A.31, and A Refine.
(A Fun) By the IHs and A Fun.

A.33 Lemma [coerce generates well formed coercions]:
If ` T1 k T2 then `E coerce(T1 , T2 , l ) k T1 ⇒ T2 .
Proof:

By induction on the similarity derivation.

(S Refine) By A Refine, with coerce({x :B | e1 }, {x :B | e2 }, l ) = {x :B | e2 }l .
(S Fun) By A Fun and the IHs.

A.34 Lemma [Eidetic preservation]: If ∅ `E e : T and e −→E e 0 then ∅ `E e 0 : T .
Proof:
(T
(T
(T
(T

By induction on the typing derivation.

Var) Contradictory—we assumed e was well typed in an empty context.
Const) Contradictory—k is a value and doesn’t step.
Abs) Contradictory—λx :T1 . e 0 is a value and doesn’t step.
Op) By cases on the step taken.

(E Op) [[op]] (k1 , ... , kn ) = k ; we assume that ty(op) correctly assigns types, i.e., if ty(op) = {x :B1 | e10 } → ... →
{x :Bn | en0 }→{x :B | e}, then e[k /x ] −→∗E true and `E {x :B | e}. We can therefore conclude that ∅ `E k : {x :B | e}
by T Const.
(E OpInner) By the IH and T Op.
(E OpRaise) We assume that ty(op) only assigns well formed types, so ∅ `E ⇑l : T .
(T App) By cases on the step taken.
(E Beta) We know that x :T1 `E e1 : T2 and ∅ `E e2 : T1 ; we are done by substitution (Lemma A.2).
c 7→c
c2
c1
•
•
0
(E Unwrap) We have e = (hT11 →T12 1⇒ 2 T21 →T22 i• e1 ) e2 −→E hT12 ⇒T
22 i (e1 (hT21 ⇒T11 i e2 )) = e .
By inversion, `E c1 k T21 ⇒ T11 and `E c2 k T12 ⇒ T22 . We are done by T Coerce and T App.
(E AppL) By T App and the IH.
(E AppR) By T App and the IH.
(E AppRaiseL) By regularity, `E T2 , so we are done by T Blame.
(E AppRaiseR) By regularity, `E T2 , so we are done by T Blame.
(T Cast) If the annotation is •, we step by E Coerce, which is well typed by T Coerce (using Lemma A.33).
Otherwise, by cases on the step taken.
(E CoerceStack We have `E Γ and `E {x :B | e1 } and ty(k ) = B by inversion. The quantification over r is also
by inversion, of coercion well formedness. Since s = ?, we can find {x :B | e} ∈ r such that {x :B | e} ⊃ {x :B | e1 }
by that same well formedness derivation. So: by T Stack.
(E CoerceInner) By T Coerce and the IH.
36

(E CastMerge) We have

c

c

2
1
•
•
hT2 ⇒T
3 i (hT1 ⇒T2 i e) −→E

hT1

join(c1 ,c2 )

⇒

T3 i• e.

By Lemma A.32, `E join(c1 , c2 ) k T1 ⇒ T3 . We already know that ∅ `E e1 : T1 (by assumption) and `E T3 (by
inversion of the outer cast’s typing derivation), so we can apply T Coerce to type the resulting merged coercion.
(E CoerceRaise) We have `E T2 by assumption, so we are done by T Blame.
(T Stack) By cases on the step taken.
(E StackDone) We know by assumption that `E {x :B | e} and e[k /x ] −→∗E true, so by T Const.
(E StackPop) We have `E Γ and `E {x :B | e2 } and ty(k ) = B by inversion. The quantification over r is also by
inversion, of coercion well formedness.
If {x :B | e 0 } ⊃ {x :B | e}, then our new status is X and we enter a checking form—so the reduction h{x :B |
e 0 }, e 0 [k /x ], k il −→∗E e2 holds by reflexivity.
If not, then our status is whatever it was before. If it was X, then that is because we either (a) already knew
that e1 [k /x ] −→∗E true or because h{x :B | e 0 }, e 0 [k /x ], k il −→∗E k for some {x :B | e 0 } ⊃ {x :B | e1 }—which implies
that e1 [k /x ] −→∗E true by adequacy of ⊃. So if s = X, our side condition is covered. If s = ?, then we know that
{x :B | e1 } remains to be checked, and some {x :B | e 0 } ⊃ {x :B | e1 } is in r .
We can type the active check using our assumptions, where e2 [k /x ] −→∗E e2 [k /x ] by reflexivity. By substitution
(and T Const, to find ∅ `E k : {x :B | true}), we find ∅ `E e2 [k /x ] : {x :Bool | true}. We can now apply T Check,
and can then apply an outer T Stack.
E StackInner By T Stack and the IH. If s = X, we need to extend the evaluation derivation by one step.
E StackRaise We have `E {x :B | e} and `E Γ already, so by T Blame.
(T Blame) Contradictory—⇑l is a result and doesn’t step.
(T Check) By cases on the step taken.
(E CheckOK) Since `E ∅ and ty(k ) = B and `E {x :B | e1 } and e1 [k /x ] −→∗E true, we can apply T Const to
find ∅ `E k : {x :B | e1 }.
(E CheckFail) Since `E ∅ and `E {x :B | e1 }, T Blame shows ∅ `E ⇑l : {x :B | e1 }.
(E CheckInner) By T Check and the IH.
(E CheckRaise) As for E CheckFail—the differing label doesn’t matter.

A.35 Lemma [Source program typing for eidetic λH ]: Source programs are well typed in C iff they are well
typed in E, i.e.:
– Γ `C e : T as a source program iff Γ `E e : T as a source program.
– `C T as a source program iff `E T as a source program.
– `C Γ as a source program iff `E Γ as a source program.
Proof: By mutual induction on e, T , and Γ. Since all of the rules are syntax directed, we use the rule names for
cases (but prove both directions at once).
Expressions e
(T Var) By the IH on Γ and T Var.
(T Const) By the IH on Γ and T Const, noting that true −→∗m true in every mode m.
(T Abs) By the IH on T1 and e12 and T Abs.
(T Op) By the IHs on the arguments ei and T Op.
(T App) By the IHs on e1 and e2 and T App.
(T Cast) By the IHs on T1 and T2 and T Cast, noting that similarity holds irrespective of modes and that the
annotation is •.
(T Blame) Contradictory—doesn’t occur in source programs.
(T Check) Contradictory—doesn’t occur in source programs.
(T Stack) Contradictory—doesn’t occur in source programs.

37

Types T
(WF Base) Immediately true—WF Base is an axiom.
(WF Refine) By the IH on e and WF Refine.
(WF Fun) By the IHs on T1 and T2 and WF Fun.
Contexts Γ
(WF Empty) Immediately true—WF Empty is an axiom.
(WF Extend) By the IHs on Γ and T and WF Extend.


B

Proofs of space-efficiency soundness

This appendix contains the proofs relating classic λH to each other mode: forgetful, heedful, and eidetic.

B.1

Relating classic and forgetful manifest contracts

If we evaluate a λH term with the classic semantics and find a value, then the forgetful semantics finds a similar
value—identical if they’re constants. Since forgetful λH drops some casts, some terms reduce to blame in classic λH
while they reduce to values in forgetful λH .
The relationship between classic and forgetful λH is blame-inexact, to borrow the terminology of Greenberg et al.
[2012]: we define an asymmetric logical relation in Figure 12, relating classic values to forgetful values—and everything
to classic blame. The proof proceeds largely like that of Greenberg et al. [2012]: we define a logical relation on terms
and an inductive invariant relation on types, prove that casts between related types are logically related, and then
show that well typed source programs are logically related.
Before we explain the logical relation proof itself, there is one new feature of the proof that merits discussion:
we need to derive a congruence principle for casts forgetful λH . When proving that casts between related types are
related (Lemma B.5), we want to be able to reason with the logical relation—which involves reducing the cast’s
•
•
argument to a value. But if e −→∗F e 0 such that resultF e 0 , how to hT1 ⇒T2 il e and hT1 ⇒T2 il e 0 relate? If e 0 = ⇑l 0
•
•
is blame, then it may be that hT1 ⇒T2 il e reduces to a value while hT1 ⇒T2 il ⇑l 0 propagates the blame. But if e 0 is
a value, then both casts reduce to the same value. We show this property first for a single step e −→F e 0 , and then
lift it to many steps.
B.1 Lemma [Cast congruence (single step)]: If
–
–
–
–

•

∅ `F e : T1 and and `F ∅ k T1 ⇒ T2 (and so ∅ `F hT1 ⇒T2 il e : T2 ),
e −→F e1 (and so ∅ `F e1 : T1 ),
•
hT1 ⇒T2 il e1 −→∗F e2 , and
valF e2
•

then hT1 ⇒T2 il e −→∗F e2 .
Proof: By cases on the step e −→F e1 . There are three groups of reductions: straightforward merge-free reductions,
merging reductions (the interesting cases, where a reduction step taken in e has an exposed cast), and (contradictory)
reductions where blame is raised.
Merge-free reductions
(E
(E
(E
(E
(E
(E
(E

Beta) By E CastInner and E Beta.
Op) By E CastInner and E Op.
Unwrap) By E CastInner and E Unwrap.
AppL) By E CastInner with E AppL.
AppR) By E CastInner with E AppR.
CheckOK) By E CastInner and E CheckOK.
OpInner) By E CastInner and E OpInner.

38

Merging reductions The interesting case of the proof occurs when the reduction step taken in e has an exposed
cast: E CheckNone or a congruence/merge rule (E CastInner or E CastMerge). Applying a cast to e and e1
leads to slightly different reductions, because we merge the cast in e and not in e1 . If no blame is raised, then the
reductions join back up.
0

•

0

(E CheckNone) We have e = (hT3 ⇒{x :B | e11 }il k ) where T1 = {x :B | e11 } and e1 = h{x :B | e11 }, e11 [k /x ], k il
•
•
and h{x :B | e11 }⇒T2 il e1 −→∗F e2 such that valF e2 . We must show that h{x :B | e11 }⇒T2 il e −→∗F e2 .
•
By inversion of the similarity relation ` {x :B | e11 } k T2 , we know that T2 = {x :B | e12 }. If h{x :B | e11 }⇒{x :B |
l
l0
∗
e12 }i e1 reduces to a value, then it must be the case that e1 = h{x :B | e11 }, e11 [k /x ], k i −→F k and that
•
e12 [k /x ] −→∗F true (and so the entire term reduces h{x :B | e11 }⇒{x :B | e12 }il e1 −→∗F k = e2 ). If not, we would
0
have gotten ⇑l or ⇑l .
Instead, we find that:
•

−→F
−→F
−→∗F
−→F

0

•

h{x :B | e11 }⇒{x :B | e12 }il (hT3 ⇒{x :B | e11 }il k )
•
hT3 ⇒{x :B | e12 }il k
h{x :B | e12 }, e12 [k /x ], k il
h{x :B | e12 }, true, k il
k = e2

(E CastInner) We have:

0

•

0

•

e = hT3 ⇒T1 il e11 −→F hT3 ⇒T1 il e12 = e1
00

•

with e11 −→F e12 and e11 6= hT4 ⇒T3 il e200 .
In the original derivation with e1 , we have
•

0

•

•

hT1 ⇒T2 il (hT3 ⇒T1 il e12 ) −→F hT3 ⇒T2 il e12
−→∗F e2
by E CastMerge and then assumption. We find a new derivation with e as follows:
•

−→F
−→F
−→∗F

0

•

hT1 ⇒T2 il (hT3 ⇒T1 il e11 )
(E CastMerge)
•
hT3 ⇒T2 il e11
(E CastInner)
00
•
since e11 6= hT4 ⇒T3 il e200
•
hT3 ⇒T2 il e12
(assumption)
e2

(E CastMerge) We have:
0

•

•

e = hT3 ⇒T1 il (hT4 ⇒T3 il

00

0

•

e11 ) −→F hT4 ⇒T1 il e11 = e1

In the original derivation with e1 , we have
•

•

0

•

hT1 ⇒T2 il (hT4 ⇒T1 il e11 ) −→F hT4 ⇒T2 il e11 −→∗F e2
We can build a new derivation with e as follows, stepping twice by E CastMerge:
•

−→F
−→F
−→∗F

0

•

•

00

hT1 ⇒T2 il (hT3 ⇒T1 il (hT4 ⇒T3 il e11 ))
00
•
•
hT3 ⇒T2 il (hT4 ⇒T3 il e11 )
•
l
hT4 ⇒T2 i e11
(assumption)
e2

Contradictory blame-raising reductions
(E
(E
(E
(E
(E
(E

•

AppRaiseL) Contradiction—in this case, e1 = ⇑l 0 , and hT1 ⇒T2 il e1 −→∗F ⇑l 0 , which isn’t a value.
•
AppRaiseR) Contradiction—in this case, e1 = ⇑l 0 , and hT1 ⇒T2 il e1 −→∗F ⇑l 0 , which isn’t a value.
•
0
CastRaise) Contradiction—in this case, e1 = ⇑l , and hT1 ⇒T2 il e1 −→∗F ⇑l 0 , which isn’t a value.
•
CheckFail) Contradiction—in this case, e1 = ⇑l 0 , and hT1 ⇒T2 il e1 −→∗F ⇑l 0 , which isn’t a value.
•
0
OpRaise) Contradiction—in this case, e1 = ⇑l , and hT1 ⇒T2 il e1 −→∗F ⇑l 0 , which isn’t a value.
•
CheckRaise) Contradiction—in this case, e1 = ⇑l 0 , and hT1 ⇒T2 il e1 −→∗F ⇑l 0 , which isn’t a value.
39


Once we have cast congruence for a single step, a straightforward induction gives us reasoning principle applicable
to many steps.
B.2 Lemma [Cast congruence]: If
–
–
–
–

•

∅ `F e : T1 and `F ∅ k T1 ⇒ T2 (and so ∅ `F hT1 ⇒T2 il e : T2 ),
e −→∗F e1 (and so ∅ `F e1 : T1 ),
•
hT1 ⇒T2 il e1 −→∗F e2 , and
valF e2
•

then hT1 ⇒T2 il e −→∗F e2 . Diagrammatically:
Forgetful λH
e1

e2

F

⇓
•

•

l

hT1 ⇒T2 il e2

hT1 ⇒T2 i e1

∗
F

∗
F val
F

Proof:

e

By induction on the derivation e −→∗F e1 , using the single-step cast congruence (Lemma B.1).



We define the logical relation in Figure 12. It is defined in a split style, with separate definitions for values and
terms. Note that terms that classically reduce to blame are related to all forgetful terms, but terms that classically
reduce to values reduce forgetfully to similar values. We lift these closed relations on values and terms to open terms
by means of dual closing substitutions. As in Greenberg et al. [2012], we define an inductive invariant to relate types,
using it to show that casts between related types on related values yield related values, i.e., casts are applicative
(Lemma B.5). One important subtle technicality is that the type indices of this logical relation are forgetful types—
in the constant case of the value relation, we evaluate the predicate in the forgetful semantics. We believe the choice
is arbitrary, but have not tried the proof using classic type indices.
B.3 Lemma [Value relation relates only values]: If e1 ∼F e2 : T then valC e1 and valF e2 .
Proof: By induction on T . We have e1 = e2 = k when T = {x :B | e} (and so we are done by V Const). When
T = T1 →T2 , we have the value derivations as assumptions.

B.4 Lemma [Relation implies similarity]: If T1 ∼F T2 then ` T1 k T2 .
Proof:

By induction on T1 , using S Refine and S Fun.



B.5 Lemma [Relating classic and forgetful casts]: If T11 ∼F T21 and T12 ∼F T22 and ` T11 k T12 , then forall
0
•
•
e1 ∼F e2 : T21 , we have hT11 ⇒T12 il e1 'F hT21 ⇒T22 il e2 : T22 .
Proof: By induction on the sum of the heights of T21 and T22 . By Lemma B.4, we know that ` T11 k T21 and
` T12 k T22 ; by Lemma A.7, we know that ` T21 k T22 . We go by cases on T22 .
(T22 = {x :B | e22 }) It must be the case (by similarity) that all of the other types are also refinements. Moreover,
it must be that case that e1 = e2 = k .
Both sides step by E CheckNone. Since e1 ∼F e2 : T21 = {x :B | e21 }, we can find that e1 ∼F e2 : {x :B | true}
trivially. Then, since {x :B | e12 } ∼F {x :B | e22 }, we know that e12 [k /x ] 'F e22 [k /x ] : {x :Bool | true}.
If e12 [k /x ] −→∗C ⇑l 0 , then the entire classic side steps to ⇑l 0 by E CheckInner and E CheckRaise, and then
we are done. If not, then both predicates reduce to a boolean together. If they reduce to false, then the classic side
eventually reduces to ⇑l via E CheckInner and E CheckFail, and we are done. If they both go to true, then both
sides step by E CheckInner and E CheckOK to yield k , and we can find k ∼F k : {x :B | e22 } easily—we have a
derivation for e22 [k /x ] −→∗F true handy.

40

(T22 = T221 →T222 ) By Lemma B.3, we know that valC e1 and valF e2 . The classic side is a value e11 (by
V ProxyC), while the forgetful side steps by one of its E CastMerge rules to some value e21 , depending on the
shape of e2 : an abstraction yields a value by V ProxyF, while a function proxy yields another function proxy by
E CastMerge.
We must now show that e11 ∼F e21 : T221 →T222 , knowing that e1 ∼F e2 : T211 →T212 . Let e12 ∼F e22 : T221 be
•
•
given. On the classic side, we step by E Unwrap to find hT112 ⇒T122 il (e1 (hT121 ⇒T111 il e12 )). (Recall that the
annotations are all •.)
We now go by cases on the step taken on the whether or not e2 is a value or needed to merge:
•

(V ProxyF) We have e21 = hT211 →T212 ⇒T221 →T222 il λx :T211 . e20 since e2 = λx :T211 . e20 . We must show that:
•

•

•

hT112 ⇒T122 il (e1 (hT121 ⇒T111 il e12 )) 'F (hT211 →T212 ⇒T221 →T222 il λx :T211 . e20 ) e22 : T222
•

•

The forgetful side steps by E Unwrap, yielding hT212 ⇒T222 il ((λx :T211 . e20 ) (hT221 ⇒T211 il e22 )). By the IH, we
•
•
know that hT121 ⇒T111 il e12 'F hT221 ⇒T211 il e22 : T211 . If we get blame on the classic side, we are done immediately.
0
0
0
0
Otherwise, each side reduces to values e12
∼F e22
: T211 . We know by assumption that e1 e12
'F e2 e22
: T212 ; again,
00
00
blame on the classic side finishes this case. So suppose both sides go to values e12 ∼F e22 : T212 . By the IH, we know
•
•
00
00
that hT112 ⇒T122 il e12
'F hT212 ⇒T222 il e22
: T222 , and we are done.
0
•
•
(E CastMerge) We have e21 = hT31 →T32 ⇒T221 →T222 il λx :T31 . e20 since e2 = hT31 →T32 ⇒T211 →T212 il λx :T31 . e20 .
We must show that:
•

•

•

hT112 ⇒T122 il (e1 (hT121 ⇒T111 il e12 )) 'F (hT31 →T32 ⇒T221 →T222 il λx :T31 . e20 ) e22 : T222
•

•

The right hand steps by E Unwrap, yielding hT32 ⇒T222 il ((λx :T31 . e20 ) (hT221 ⇒T31 il e22 )). We must show that
•
•
this forgetful term is related to the classic term hT112 ⇒T122 il (e1 (hT121 ⇒T111 il e12 )).
We must now make a brief digression to examine the behavior of the cast that was eliminated by E CastMerge.
•
•
We know by the IH that hT121 ⇒T111 il e12 'F hT221 ⇒T211 il e22 : T211 , so either the classic side goes to blame—and
•
0
0
0
00
we are done—or both sides go to values e12 ∼F e22 : T211 . By Lemma B.2, we can find that hT211 ⇒T31 il e22
−→∗F e22
•
•
•
•
l
l
∗
00
l
l
implies hT211 ⇒T31 i (hT221 ⇒T211 i e22 ) −→F e22 . But then we have that hT211 ⇒T31 i (hT221 ⇒T211 i e22 ) −→F
•
•
00
0
hT211 ⇒T31 il e22 , so we then know that hT221 ⇒T31 il e22 −→∗F e22
, just as if it were applied to e22
.
•
Now we can return to the meat of our proof. If hT121 ⇒T111 il e12 −→∗F ⇑l 0 , we are done. If it reduces to a value
•
0
0
e12
, then we are left considering the term hT112 ⇒T122 il (e1 e12
) on the classic side. We know that e1 ∼F e2 : T21 .
•
•
0
0
Unfolding the definition of e2 , this means that e1 e12 'F hT32 ⇒T212 il ((λx :T31 . e20 ) (hT211 ⇒T31 il e22
)) : T212 . If
the classic side produces blame, we are done, as indicated in the digression above. If not, then both sides produce
values. For these terms to produce values, it must be the case that (a) the domain cast on the forgetful side produces
a value, (b) the forgetful function produces a value given that input, and (c) the forgetful codomain cast produces
•
•
0
a value. Now, we know from our digression above that hT211 ⇒T31 il e22
and hT211 ⇒T31 il e22 reduce to the exact
•
•
00
l
0
l
0
∗
00
same value, e22 . So if hT32 ⇒T212 i ((λx :T31 . e2 ) (hT211 ⇒T31 i e22 )) −→F e22 then we can also see
•

•

•

00
.
hT32 ⇒T212 il ((λx :T31 . e20 ) (hT211 ⇒T31 il e22 )) −→∗F hT32 ⇒T212 il e32 −→∗F e22

We have shown that the domains and then the applied inner functions are equivalent. It now remains to show
that
•
•
•
00
hT112 ⇒T122 il e11
'F hT32 ⇒T222 il ((λx :T31 . e20 ) (hT221 ⇒T31 il e22 )) : T222
We write the entire forgetful term to highlight the fact that we cannot freely apply congruence, but must instead
carefully apply cast congruence (Lemma B.2) as we go.
•
•
00
00
By the IH, we know that either hT112 ⇒T122 il e11
goes to blame or it goes to a value along with hT212 ⇒T222 il e22
.
•
l
∗
00
In the former case we are done; in the latter case, we already know that hT32 ⇒T212 i e32 −→F e22 , so we can apply
•
•
•
00
000
cast congruence (Lemma B.2) to see that if hT212 ⇒T222 il e22
−→∗F e22
then hT212 ⇒T222 il (hT32 ⇒T212 il e32 ) −→∗F
•
•
•
•
000
e22
. But we know that hT212 ⇒T222 il (hT32 ⇒T212 il e32 ) −→F hT32 ⇒T222 il e32 , so we then we know that hT32 ⇒T222 il e32 −→∗F
•
•
•
000
e22
. Since hT32 ⇒T222 il ((λx :T31 . e20 ) (hT221 ⇒T31 il e22 )) −→∗F hT32 ⇒T222 il e32 , we have shown that the classic
000
000
term and forgetful term reduce to values e12
∼F e22
: T222 , and we are done.

B.6 Lemma [Relating classic and forgetful source programs]:
1. If Γ `C e : T as a source program then Γ ` e 'F e : T .
41

2. If `C T as a source program then T ∼F T .
Proof:

By mutual induction on the typing derivations.

Term typing Γ `C e : T
T Var We know by assumption that δ1 (x ) ∼F δ2 (x ) : T .
T Const Since we are dealing with a source program, T = {x :B | true}. We have immediately that ty(k ) = B
and true[k /x ] 'F true[k /x ] : {x :Bool | true}, so k 'F k : {x :B | true}.
T Abs Let Γ |=F δ. We must show that λx :T1 . δ1 (e1 ) ∼F λx :T2 . δ2 (e1 ) : T1 →T2 . Let e2 ∼F e20 : T1 . We must
show that applying the abstractions to these values yields related values. Both sides step by E Beta, to δ1 (e1 )[e2 /x ]
and δ2 (e1 )[e20 /x ], respectively. But Γ, x :T1 |=F δ[e2 , e20 /x ], so we can apply IH (1) e1 , the two sides reduce to related
values.
T Op By IH (1) on each arguments, either one of the arguments goes to blame in the classic evaluation, and we
are done by E OpRaise. Otherwise, all of the arguments reduce to related values. Since ty(op) is first order, these
values must be related at refined base types, which means that they are in fact all equal constants. We then reduce
by E Op on both sides to have [[op]] (k1 , . . . , kn ). We have assumed that the denotations of operations agree with
their typings in all modes, so then [[op]] (k1 , . . . , kn ) satisfies the refinement for −→F in particular, and we are done.
T App Let Γ |=F δ. We must show that δ1 (e1 ) δ1 (e2 ) 'F δ2 (e1 ) δ2 (e2 ) : T2 . But by IH (1) on e1 and e2 , we are
done directly.
T Cast Let Γ |=F δ. By IH (1) on e 0 , δ1 (e 0 ) 'F δ2 (e 0 ) : T1 , either δ1 (e 0 ) −→∗C ⇑l 0 (and we are done) or δ1 (e 0 )
•
and δ2 (e 0 ) reduce to values e1 ∼F e2 : T1 . By Lemma B.5 (using IH (2) on the types), we know that hT1 ⇒T2 il e1 'F
•
•
hT1 ⇒T2 il e2 : T2 . If hT1 ⇒T2 il e1 −→∗C ⇑l 0 , we are done. If not, then we know that the cast applied to both values
•
•
reduce to values e10 ∼F e20 : T2 , but we must still show that hT1 ⇒T2 il δ1 (e 0 ) 'F hT1 ⇒T2 il δ2 (e 0 ) : T2 for the terms.
•
The classic side obviously goes to e10 . On the forgetful side, we can see by Lemma B.2 that hT1 ⇒T2 il e2 −→∗F e20
•
implies hT1 ⇒T2 il δ2 (e 0 ) −→∗F e20 , since δ2 (e 0 ) −→∗F e2 . Constructing this derivation completes the case.
T Blame Contradiction—doesn’t appear in source programs. Though in fact it is in the relation, since ⇑l 'F e : T
for any e and T .
T Check Contradiction—doesn’t appear in source programs.
Type well formedness `C T
WF Base We can immediately see true[k /x ] 'F true[k /x ] : {x :Bool | true} for any k ∼F k : {x :B | true}, i.e., any
k such that ty(k ) = B .
WF Refine By inversion, we know that x :{x :B | true} `C e : {x :Bool | true}; by IH (1), we find that δ1 (e) 'F
δ2 (e) : {x :Bool | true}, i.e., that e[e1 /x ] 'F e[e2 /x ] : {x :Bool | true} for all e1 ∼F e2 : {x :B | true}—which is what we
needed to know.
WF Fun By IH (2) on each of the types.


B.2

Relating classic and heedful manifest contracts

Heedful λH reorders casts, so we won’t necessarily get the same blame as we do in classic λH . We can show, however,
that they blame the same amount: heedful λH raises blame if and only if classic λH does, too. We define a blameinexact, symmetric logical relation.
The proof follows the same scheme as the proof for forgetful λH in Section B.1: we first prove a cast congruence
principle; then we define a logical relation relating classic and heedful λH ; we prove a lemma establishing a notion
of applicativity for casts using an inductive invariant grounded in the logical relation, and then use that lemma to
prove that well typed source programs are logically related.
S
S
Cast congruence—that hT1 ⇒T2 il e and hT1 ⇒T2 il e1 behave identically when e −→H e1 —holds almost exactly.
The pre- and post-step terms may end blaming different labels, but otherwise return identical values. Note that this
cast congruence lemma (a) has annotations other than •, and (b) is stronger than Lemma B.1, since we not only
get the same value out, but we also get blame when the inner reduction yields blame—though the label may be
different. The potentially different blame labels in heedful λH ’s cast congruence principle arises because of how casts
are merged: heedful λH is heedful of types, but forgets blame labels.

42

S

B.7 Lemma [First-order casts don’t change their arguments]: If h{x :B | e1 }⇒{x :B | e2 }il k −→∗H e and
valH e then e = k .
Proof:

By induction on the size of S.
∅

(S = ∅) The only possible step is h{x :B | e1 }⇒{x :B | e2 }il k −→H h{x :B | e2 }, e2 [k /x ], k il by E CheckEmpty.
So if the original cast term reduces to a value, then so must this term. But the only step out of an active check that
produces a value produces k by E CheckOK.
(S = {{x :B | e3 }} ∪ S 0 ) If S is nonempty, then we must step by E CheckSet for some {x :B | e3 } ∈ S to
S\{x :B|e3 }

h{x :B | e3 }
⇒
{x :B | e2 }il h{x :B | e3 }, e3 [k /x ], k il . For this entire term to reduce to a value, the active check
must reduce to a value—if it goes to blame, so does the whole term. But the only value it can produce is k itself, by
E CheckOK. By the IH, we know that h{x :B | e3 }

S\{x :B|e3 }

⇒

{x :B | e2 }il k goes to k if it reduces to a value.


B.8 Lemma [Determinism of heedful λH ]: If e −→H e1 and e −→H e2 then e1 = e2 .
Proof: By induction on the first evaluation derivation. In every case, only a single step can be taken. Critically,

E CheckSet uses the choose function, which makes some deterministic choice.
Heedful λH ’s cast congruence proof requires an extra principle. We first show that casting is idempotent: we can
safely remove the source type from a type set.
B.9 Lemma [Idempotence of casts]:
S

If ∅ `H h{x :B | e1 }⇒{x :B | e2 }il k : {x :B | e2 } and ∅ `H k : {x :B | e3 } then for all resultH e, then:
S

(a) h{x :B | e1 }⇒{x :B | e2 }il k −→∗H e iff
(b) h{x :B | e1 }

S\{x :B|e3 }

⇒

{x :B | e2 }il k −→∗H e.

Proof: If {x :B | e1 } 6∈ S, then the proof is trivial, since the (a) and (b) are the same. The rest of the proof assumes
that {x :B | e1 } ∈ S.
We prove both directions by induction on S. In both cases, S = ∅ is immediate—the two are the same!
For the only if (⇐) direction, if choose(S) = {x :B | e1 }, then we step (a) by E CheckSet choosing {x :B | e1 },
finding h{x :B | e1 }

S\{x :B|e1 }

⇒

{x :B | e2 }il h{x :B | e1 }, e1 [k /x ], k il . By inversion of the typing derivation, e1 [k /x ] −→∗H
S\{x :B|e1 }

true, so we can step by E CheckInner and E CheckOK to h{x :B | e1 }
⇒
{x :B | e2 }il k , which is exactly (b),
and we are done. If not, the two casts step to the same sub-checks and co-reduce until eventually choose(S) = {x :B |
e1 }.
S\{x :B|e3 }

For the if (⇒) direction, (a) chooses a type to check and steps by E CheckSet to h{x :B | e3 }
⇒
{x :B |
e2 }il h{x :B | e3 }, e3 [k /x ], k il where choose(S) = {x :B | e3 }. If e3 = e1 , then we know by the typing derivation that
S\{x :B|e1 }

⇒
{x :B | e2 }il k
e3 [k /x ] −→∗H true, so the active check must succeed and (a) necessarily steps to h{x :B | e1 }
by determinism(Lemma B.8)—and we are done, since this is the term for which we needed to produce a derivation.
S\{x :B|e1 }\{x :B|e3 }

If e3 6= e1 , then we take a similar step in (b) to h{x :B | e3 }
⇒
{x :B | e2 }il h{x :B | e3 }, e3 [k /x ], k il .
Now whatever the derivation for (a) does to the active check, we can recapitulate in (b). If (a) produces ⇑l 0 for some
l 0 , via either E CheckRaise or E CheckFail, then we are done with the whole proof. If (a) produces a value, it
must produce k itself by E CheckOK. But by the IH we know that h{x :B | e3 }
implies that h{x :B | e3 }

S\{x :B|e3 }\{x :B|e1 }

⇒

l

{x :B | e2 }i k

−→∗H

S\{x :B|e3 }

⇒

{x :B | e2 }il k −→∗H e

e, and we are done.


We need strong normalization to prove cast congruence: if we reorder checks, we need to know that reordering
checks doesn’t change the observable behavior. We define a unary logical relation to show strong normalization in
Figure 13. We assume throughout at the terms are well typed at their indices: e ∈ [[T ]] implies ∅ `H e : T and
|= T implies `H T and |= S k T1 ⇒ T2 implies `H S k T1 ⇒ T2 and Γ |= e : T implies Γ `H e : T by definition.
Making this assumption simplifies many of the technicalities. First, typed terms stay well typed as they evaluate
(by preservation, Lemma A.26), so a well typed relation allows us to reason exclusively over typed terms. Second,
it allows us to ignore the refinements in our relation, essentially using the simple type structure. After proving cast
congruence, we show that all well typed terms are in fact in the relation, i.e., that all heedful terms normalize.
B.10 Lemma [Expansion and contraction]: If e1 −→∗H e2 then e1 ∈ [[T ]] iff e2 ∈ [[T ]].
43

Normalizing closed terms

Normalizing open terms

e ∈ [[T ]]
e ∈ [[{x :B | e}]]

⇐⇒

e ∈ [[T1 →T2 ]]

⇐⇒

Γ |= e : T

Γ |= σ

Γ |= e : T
Γ |= σ
Normalizing types and type sets

|= T

e −→∗H ⇑l ∨
e −→∗H k ∧ ty(k ) = B
∀e 0 ∈ [[T1 ]]. resultH e 0 ⇒ e e 0 ∈ [[T2 ]]

⇐⇒
⇐⇒

∀σ. Γ |= σ ⇒ σ(e) ∈ [[T ]]
∀x :T ∈ Γ. σ(x ) ∈ [[T ]]

|= S k T1 ⇒ T2

∀k . ty(k ) = B implies e[k /x ] ∈ [[{x :Bool | true}]]
|= {x :B | e}
|= T1 |= T2
|= T1 →T2

SWF Refine

SWF Fun

` T1 k T2 |= T1 |= T2
∀T ∈ S. |= T ` T k T1
|= S k T1 ⇒ T2

SWF TypeSet

Figure 13: Strong normalization for heedful λH
Proof:

By induction on T .

(T = {x :B | e 00 }) By determinism (Lemma B.8).
(T = T1 →T2 ) Given some e 0 ∈ [[T1 ]], we must show that e1 e 0 ∈ [[T2 ]] iff e2 e 0 ∈ [[T2 ]]. We have e1 e 0 −→∗H e2 e 0
by induction on the length of the evaluation derivation and E AppL, so we are done by the IH on T2 .

B.11 Lemma [Blame inhabits every type]: ⇑l ∈ [[T ]] for all T .
Proof:

By induction on T .

(T = {x :B | e 00 }) By definition.
(T = T1 →T2 ) By the IH, ⇑l 0 ∈ [[T1 ]]. We must show that ⇑l ⇑l 0 ∈ [[T2 ]]. This term steps to ⇑l by E AppRaiseL,
and then we are done by contraction (Lemma B.10).

B.12 Lemma [Strong normalization]: If e ∈ [[T ]] then e

−→∗H

0

0

e uniquely such that resultH e .

Proof: Uniqueness is immediate by determinism(Lemma B.8). We show normalization by induction on T , observing
that blame inhabits every type.
(T = {x :B | e 00 }) By definition.
(T = T1 →T2 ) By Lemma B.11, we know that at least one result is in the domain type: ⇑l ∈ [[T1 ]]. So by
assumption, e ⇑l ∈ [[T2 ]]. By the IH, this term is strong normalizing—but that can only be so if e reduces to a
result.

B.13 Lemma [Cast congruence (single step)]: If
•

– e ∈ [[T1 ]] and |= S k T1 ⇒ T2 (and so ∅ `H hT1 ⇒T2 il e : T2 ),
– e −→H e1 (and so ∅ `H e1 : T1 ),
S

– hT1 ⇒T2 il e1 −→∗H e2 , and
– resultH e2
S

then hT1 ⇒T2 il e −→∗H ⇑l 0 if e2 = ⇑l or to e2 itself if valH e2 .
Proof: By cases on the step taken; the proof is as for forgetful λH (Lemma B.1), though we need to use strong
normalization to handle the reorderings. There are two groups of reductions: straightforward merge-free reductions
and merging reductions.
44

In these cases, we apply E CastInner and whatever rule derived e −→H e1 .

Merge-free reductions
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E

Beta) By E CastInner and E Beta.
Op) By E CastInner and E Op.
Unwrap) By E CastInner and E Unwrap.
TypeSet) By E CastInner and E TypeSet.
AppL) By E CastInner with E AppL.
AppR) By E CastInner with E AppR.
AppRaiseL) By E CastInner with E AppRaiseL; then by E CastRaise on both sides.
AppRaiseR) By E CastInner with E AppRaiseR; then by E CastRaise on both sides.
CheckOK) By E CastInner and E CheckOK.
CheckFail) By E CastInner and E CheckRaise.
CheckFail) By E CastInner and E CheckRaise.
OpInner) By E CastInner and E OpInner.
OpRaise) By E CastInner and E OpRaise.

Merging reductions In these cases, some cast in e reduces when we step e −→H e1 , but merges when we consider
S
S
hT1 ⇒T2 il e. We must show that the merged term and hT1 ⇒T2 il e1 eventually meet. After merging the cast in
e—and possibly some steps in e1 — the e and e1 terms reduce to a common term, which immediately gives us the
common reduction to results we need.
0

∅

(E CheckEmpty) We have e = (hT3 ⇒{x :B | e11 }il k ) where T1 = {x :B | e11 } and e1 = h{x :B | e11 }, e11 [k /x ], k il
S

S

and h{x :B | e11 }⇒T2 il e1 −→∗H e2 such that resultH e2 . We must show that h{x :B | e11 }⇒T2 il e −→∗H e20 such that
e2 = ⇑l and e20 = ⇑l 0 or valH e2 and e2 = e20 . We find that both terms go to blame (at possibly different labels), or
S

reduce to h{x :B | e11 }⇒T2 il k .
We step the e term:
S

0

•

h{x :B | e11 }⇒T2 il (hT3 ⇒{x :B | e11 }il k )
S∪{{x :B|e11 }}

−→H

hT3

−→H

h{x :B | e11 }

⇒

E CastMerge

l

T2 i k
S\{x :B|e11 }

E CheckSet

T2 il h{x :B | e11 }, e11 [k /x ], k il

⇒

0

S

0
such that
Knowing that h{x :B | e11 }⇒T2 il h{x :B | e11 }, e11 [k /x ], k il −→∗H e2 , we know that e11 [k /x ] −→∗H e11
0
00
resultH e11 . If it goes to ⇑l , so do both the e1 and e terms by E CheckRaise. If it goes to false, the e1 term
goes to ⇑l 0 while the e term goes to ⇑l , both by E CheckFail. Finally, if it goes to true, then we know that
0
S
S
S
h{x :B | e11 }⇒T2 il e1 = h{x :B | e11 }⇒T2 il h{x :B | e11 }, e11 [k /x ], k il −→∗H hT1 ⇒T2 il k . If {x :B | e11 } 6∈ S, then
we are already done—we say that the e term stepped to this.
S\{x :B|e11 }

If, on the other hand, {x :B | e11 } ∈ S, then the e term stepped to h{x :B | e11 }
S

⇒

T2 il k while the e1 term

l

stepped to h{x :B | e11 }⇒T2 i k . We can apply reflexivity of casts (Lemma B.9) to see that these terms reduce to
the same results.
S2
l0
(E CheckSet) This case is quite similar to E CheckEmpty. We have e = (hT3 ⇒T
1 i k ) where choose(S2 ) =
S2 \{x :B|e11 }

0

0

S

{x :B | e11 } and e1 = h{x :B | e11 }
⇒
T1 il h{x :B | e11 }, e11 [k /x ], k il and h{x :B | e11 }⇒T2 il e1 −→∗H e2
such that resultH e2 . We find that both sides reduce to blame (at possibly different labels) or the common term
(S1 ∪S2 ∪{T1 })\{x :B|e11 }

T2 il k .

h{x :B | e11 }
⇒
We step the e term:

S

0

S

1
2
l
l
hT1 ⇒T
2 i (hT3 ⇒T1 i k )

−→H

hT3

S1 ∪S2 ∪{T1 }

⇒

T 2 il k

E CastMerge
E CheckSet

Similarly, we know that the e1 term must step by E CastMerge as well:
S

1
l
hT1 ⇒T
2 i (h{x :B | e11 }

h{x :B | e11 }

S2 \{x :B|e11 }

0

T1 il h{x :B | e11 }, e11 [k /x ], k il ) −→H

⇒

(S1 ∪S2 ∪{T1 })\{x :B|e11 }

⇒

T2 il h{x :B | e11 }, e11 [k /x ], k il

S2 \{x :B|e11 }

0

0

0
Knowing that h{x :B | e11 }
⇒
T2 il h{x :B | e11 }, e11 [k /x ], k il −→∗H e2 , we know that e11 [k /x ] −→∗H e11
0
00
such that resultH e11 . If it goes to ⇑l , so does the e1 and by E CheckRaise followed by E CastRaise. The e

45

0

term, depending on what choose selects, produces either a different blame label (because the types it checks first
fail) or it eventually chooses {x :B | e11 } and raises blame, too. Note that here we are relying critically on strong
normalization, Lemma B.12 and WF TypeSet, to see that all checks reduce to results on both sides. A similar
case adheres when the check goes to false. Finally, if it goes to true, then we know that the e1 term reduces
(S1 ∪S2 ∪{T1 })\{x :B|e11 }

(S1 ∪S2 ∪{T1 })\{x :B|e11 }

0

h{x :B | e11 }
⇒
T2 il h{x :B | e11 }, e11 [k /x ], k il −→∗H h{x :B | e11 }
⇒
T2 il k on its
way to the result e2 We can then reduce the two terms together as new types are chosen (from S1 ∪S2 ∪{T1 }\{x :B | e11 }
and from S1 ∪ S2 ∪ {T1 }) until {x :B | e11 } is eliminated from the e-term’s type set, and the two terms are the same.
0

S

0

S

2
2
l
l
(E CastInner) We have e = hT3 ⇒T
e11 −→H hT3 ⇒T
e12 = e1 , with e11 −→H e12 and e11 6=
1i
1i

•

hT4 ⇒T3 il

00

e200 . We reduce both to the common term hT3

S1 ∪S2 ∪{T1 }

T2 il e12 .

⇒

S1

S

0

2
l
In the original derivation with e1 , the only step we can take is hT1 ⇒T2 il (hT3 ⇒T
1 i e12 ) −→H hT3
E CastMerge. We find a new derivation with e as follows:

−→H
−→H

hT3
hT3

⇒

•

E CastInner since e11 6= hT4 ⇒T3 il

S1 ∪S2 ∪{T1 }

T2 il e12
0

S

00

e200

(assumption)
S

3
2
l
l
(E CastMerge) We have e = hT3 ⇒T
1 i (hT4 ⇒T3 i

00

e11 ) −→H hT4

S2 ∪S3 ∪{T3 }

⇒

S

0

T1 il e11 = e1 .

1
l
In the original derivation with e1 , the only step we can take is hT1 ⇒T
2 i (hT4

hT4

T2 il e12

E CastMerge

l

T2 i e11

⇒

⇒

0

S

S

2
1
l
l
hT1 ⇒T
2 i (hT3 ⇒T1 i e11 )

S1 ∪S2 ∪{T1 }

S1 ∪S2 ∪{T1 }

S2 ∪S3 ∪{T3 }

⇒

0

T1 il e11 ) −→H

S1 ∪S2 ∪S3 ∪{T1 }∪{T3 }

⇒

T2 il e11 . We can build a new derivation with e as follows:
0

S

S

S

3
2
1
l
l
l
hT1 ⇒T
2 i (hT3 ⇒T1 i (hT4 ⇒T3 i

−→H

hT3

−→H

hT4

S1 ∪S2 ∪{T1 }

S3

l

l

00

⇒
T2 i (hT4 ⇒T3 i
S1 ∪S2 ∪S3 ∪{T1 }∪{T3 }
⇒
T2 il e11

00

e11 ))

e11 )

E CastMerge
E CastMerge
(assumption)

S

S

(E CastRaise) By E CastMerge, we can reduce e to hT1 ⇒T2 il ⇑l 0 , which is just the same term as hT1 ⇒T2 il e1 .

B.14 Lemma [Cast congruence]: If
S

– ∅ |= e : T1 and |= S k T1 ⇒ T2 (and so ∅ `H hT1 ⇒T2 il e : T2 ),
– e −→∗H e1 (and so ∅ `H e1 : T1 ),
S

– hT1 ⇒T2 il e1 −→∗H e2 , and
– resultH e2
S

then hT1 ⇒T2 il e −→∗H ⇑l 0 if e2 = ⇑l or to e2 itself if valH e2 . Diagrammatically:
Heedful λH
e1

H e2

⇓
•

•

l

hT1 ⇒T2 il e2

hT1 ⇒T2 i e1

∗
H

∗
H

resultH e10

=

valH e
Proof:

resultH e20

∼

=

By induction on the derivation e −→∗H e1 , using the single-step cast congruence (Lemma B.13).
S

B.15 Lemma [Strong normalization of casts]: If |= S k T1 ⇒ T2 and e ∈ [[T1 ]] then hT1 ⇒T2 il e ∈ [[T2 ]].
Proof:

By induction on the sum of the heights of T1 and T2 . We go by cases on the shape of the types.

46



(Ti = {x :B | ei }) We know that e goes to blame or a constant. In the former case, the entire term goes to blame
by E CastRaise. Otherwise, we go by E CheckSet and the normalization assumptions in WF TypeSet until we
run out of types in S, at which time we apply E CheckNone and the normalization assumption in |= T2 .
(Ti = Ti 1 →Ti 2 ) We know that e ∈ [[T1 →T2 ]], so it normalizes to some e 0 . By cast congruence (Lemma B.14),
S

S

we know that hT1 ⇒T2 il e and hT1 ⇒T2 il e 0 terminate together. We go by cases on the shape of the result e 0 ∈ [[T1 ]].
(e 0 = ⇑l 0 ) We are done by E CastRaise and Lemma B.11.
S

(e 0 = λx :T11 . e1 ) We have a value. We must show that hT11 →T12 ⇒T21 →T22 il λx :T11 . e1 ∈ [[T21 →T22 ]]. Let
e2 ∈ [[T21 ]] be a heedful λH result. We can step by E Unwrap and then apply the IH on the smaller domain and
codomain types.
S0

0

(e 0 = hT31 →T32 ⇒T11 →T12 il λx :T31 . e1 ) We step by E CastMerge to:
hT31 →T32

S 0 ∪S∪{T11 →T12 }

T21 →T22 il λx :T31 . e1

⇒

Let e2 ∈ [[T21 ]]. We step by E Unwrap, observing that we can use cast congruence (Lemma B.14) to factor the
domain and codomain casts, using the IH to handle S and T21 →T22 and the assumptions about e 0 to handle the
rest.

To be able to use our semantic cast congruence lemma, we must show that all well typed heedful λH terms are in
the relation we define; this proof is standard.
B.16 Lemma [Strong normalization of heedful terms]:
– Γ `H e : T implies Γ |= e : T ,
– `H T implies |= T , and
– `H S k T1 ⇒ T2 implies |= S k T1 ⇒ T2 .
Proof:

By mutual induction on the typing derivations.

Term typing Γ `H e : T
T Var We know by assumption that σ(x ) ∈ [[T ]].
T Const Evaluation is by reflexivity; we find ty(k ) = B by assumption.
T Abs Let Γ |= σ. We must show that λx :T1 . σ(e1 ) ∈ [[T1 →T2 ]]. Let e2 ∈ [[T1 ]]. We must show that applying
the abstraction to the result yields related values. If e2 is blame we are done; if not, we step by E Beta, to σ(e1 )[e2 /x ].
But Γ, x :T1 |= σ[e2 /x ], so we can apply IH (B.16) on e1 .
T Op By IH (B.16) on each argument, either one of the arguments goes to blame, we are done by E OpRaise,
or, all of the arguments normalize. We then reduce by E Op on to have [[op]] (k1 , . . . , kn ). We have assumed that
the denotations of operations agree with their typings in all modes, so then [[op]] (k1 , . . . , kn ) produces a constant of
appropriate base type (and, in fact, refinement) for −→H in particular, and we are done.
T App Let Γ |= σ. We must show that σ(e1 ) σ(e2 ) ∈ [[T2 ]]. But by IH (B.16) on e1 and e2 , we are done directly.
T Cast By Lemma B.15, using IH (B.16) on the type set and IH (B.16) on the term.
T Blame By Lemma B.11.
T Check By IH (B.16), we know that the active check reduces to a boolean or blame, which then reduces to
blame or the appropriate constant k .
Type well formedness `H T
WF Base We can immediately see true[k /x ] ∈ [[{x :Bool | true}]] by reflexivity and definition of constants.
WF Refine By inversion, we know that x :{x :B | true} `H e : {x :Bool | true}; by IH (B.16), we find that
σ(e) ∈ [[{x :Bool | true}]], i.e., that e[e2 /x ] ∈ [[{x :Bool | true}]] for all e2 ∈ [[{x :B | true}]]—which is what we needed
to know.
WF Fun By IH (B.16) on each of the types.

47

Type set well formedness `H S k T1 ⇒ T2
WF TypeSet By IH (B.16) on each of the types.

We define the logical relation in Figure 12. The main difference is that this relation is symmetric: classic and
heedful λH yield blame or values iff the other one does, thought the blame labels may be different. The formulations
are otherwise the same, and the proof proceeds similarly—though heedful λH ’s more complicated cast merging leads
to some more intricate stepping in the cast lemma.
B.17 Lemma [Value relation relates only values]: If e1 ∼H e2 : T then valC e1 and valH e2 .
Proof: By induction on T . We have e1 = e2 = k when T = {x :B | e} (and so we are done by V Const). When
T = T1 →T2 , we have the value derivations as assumptions.

B.18 Lemma [Relation implies similarity]: If T1 ∼H T2 then ` T1 k T2 .
Proof:

By induction on T1 , using S Refine and S Fun.



B.19 Lemma [Relating classic and heedful casts]: If T11 ∼H T21 and T12 ∼H T22 and ` T11 k T12 , then forall
0
•
•
e1 ∼H e2 : T21 , we have hT11 ⇒T12 il e1 'H hT21 ⇒T22 il e2 : T22 .
Proof: By induction on the sum of the heights of T21 and T22 . By Lemma B.18, we know that ` T11 k T21 and
` T12 k T22 ; by Lemma A.7, we know that ` T21 k T22 . We go by cases on T22 . The heedful term first steps by
E TypeSet, replacing its • annotation with an empty set.
(T22 = {x :B | e22 }) It must be the case (by similarity) that all of the other types are also refinements. Moreover,
it must be that case that e1 = e2 = k .
Classic steps by E CheckNone, while heedful steps by E CheckEmpty. Since e1 ∼H e2 : T21 = {x :B | e21 }, we
can find that e1 ∼H e2 : {x :B | true} trivially. Then, since {x :B | e12 } ∼H {x :B | e22 }, we know that e12 [k /x ] 'H
e22 [k /x ] : {x :Bool | true}.
If e12 [k /x ] −→∗C ⇑l 0 , then e22 [k /x ] −→∗H ⇑l 00 , and both terms reduce to blame by E CheckInner and E CheckRaise—
this completes the proof. If not, then both predicates reduce to a boolean together. If they reduce to false, then both
terms eventually reduces to ⇑l via E CheckInner and E CheckFail, and we are done. If they both go to true, then
both sides step by E CheckInner and E CheckOK to yield k , and we can find k ∼H k : {x :B | e22 } easily—we
have a derivation for e22 [k /x ] −→∗H true handy.
(T22 = T221 →T222 ) By Lemma B.17, we know that valC e1 and valH e2 . So the classic side is a value e11 (by
V ProxyC), while the heedful side either steps by E CastMerge to produce a function proxy e21 , or immediately
has one, depending on the shape of e2 : an abstraction immediately yields a value by V ProxyH, or E CastMerge
for a function proxy (again yielding a value by V ProxyF).
We must now show that e11 ∼H e21 : T221 →T222 , knowing that e1 ∼H e2 : T211 →T212 . Let e12 ∼H e22 : T221 be
•
•
given. On the classic side, we step by E Unwrap to find hT112 ⇒T122 il (e1 (hT121 ⇒T111 il e12 )). (Recall that the
annotations are all empty.)
We now go by cases on whether or not e2 had to take a step to become a value:
∅

(V ProxyH) We have e21 = hT211 →T212 ⇒T221 →T222 il λx :T211 . e20 since e2 = λx :T211 . e20 . We must show that:
•

•

∅

hT112 ⇒T122 il (e1 (hT121 ⇒T111 il e12 )) 'H (hT211 →T212 ⇒T221 →T222 il λx :T211 . e20 ) e22 : T222
•

•

The heedful side steps by E Unwrap with an empty type set, yielding hT212 ⇒T222 il ((λx :T211 . e20 ) (hT221 ⇒T211 il e22 )).
•
•
By the IH, we know that hT121 ⇒T111 il e12 'H hT221 ⇒T211 il e22 : T211 . If we get blame on both sides, we are done
0
0
∼H e22
: T211 . We know by assumption
immediately by the appropriate E ...Raise rules. If not, we get values e12
0
0
00
00
that e1 e12 'H e2 e22 : T212 ; again, blame on finishes this case. So suppose both sides go to values e12
∼H e22
: T212 .
•
•
l
00
l
00
By the IH, we know that hT112 ⇒T122 i e12 'H hT212 ⇒T222 i e22 : T222 , and we are done.
(E CastMerge) We have e21 = hT31 →T32
We must show that:
•

S∪{T211 →T212 }

S

0

T221 →T222 il λx :T31 . e20 since e2 = hT31 →T32 ⇒T211 →T212 il λx :T31 . e20 .

⇒

•

hT112 ⇒T122 il (e1 (hT121 ⇒T111 il e12 )) 'F (hT31 →T32

48

S∪{T211 →T212 }

⇒

T221 →T222 il λx :T31 . e20 ) e22 : T222

dom(S)∪{T211 }

cod(S)∪{T212 }

⇒
T31 il e22 )).
⇒
T222 il ((λx :T31 . e20 ) (hT221
The right hand steps by E Unwrap, yielding hT32
•
•
l
l
We must show that this heedful term is related to the classic term hT112 ⇒T122 i (e1 (hT121 ⇒T111 i e12 )).
We must now make a brief digression to examine the behavior of the cast that was eliminated by E CastMerge.
•
•
We know by the IH that hT121 ⇒T111 il e12 'H hT221 ⇒T211 il e22 : T211 , so both sides go to blame or to values
•
0
0
0
00
e12 ∼H e22 : T211 . By Lemma B.14 with dom(S) as the type set, we can find that hT211 ⇒T31 il e22
−→∗H e22
implies
dom(S)

•

S

•

00
. But then we have that hT211 ⇒T31 il (hT221 ⇒T211 il e22 ) −→H
hT211 ⇒ T31 il (hT221 ⇒T211 il e22 ) −→∗H e22
dom(S)∪{T221 }

dom(S)∪{T221 }

00
⇒
T31 il e22 −→∗H e22
, just as if it were applied to
⇒
T31 il e22 , so we then know that hT221
hT211
0
e22 .
•
Now we can return to the meat of our proof. If hT121 ⇒T111 il e12 −→∗H ⇑l 0 , we are done—so must the heedful
0
side (albeit possibly at a different blame label). If it reduces to a value e12
, then we are left considering the term
•
l
0
hT112 ⇒T122 i (e1 e12 ) on the classic side. We know that e1 ∼H e2 : T21 . Unfolding the definition of e2 , this means
•
•
0
0
that e1 e12
'F hT32 ⇒T212 il ((λx :T31 . e20 ) (hT211 ⇒T31 il e22
)) : T212 . If the classic side produces blame, so must the
heedful side and we are done, as indicated in the digression above. If not, then both sides produce values. For these
terms to produce values, it must be the case that (a) the domain cast on the heedful side produces a value, (b) the
heedful function produces a value given that input, and (c) the heedful codomain cast produces a value. Now, we
dom(S)

dom(S)

0
and hT211 ⇒ T31 il e22 reduce to the exact same value,
know from our digression above that hT211 ⇒ T31 il e22
dom(S)

cod(S)

0
00
00
)) −→∗H e22
then we can also see
e22
. So if hT32 ⇒ T212 il ((λx :T31 . e20 ) (hT211 ⇒ T31 il e22
cod(S)

dom(S)

•

00
.
hT32 ⇒ T212 il ((λx :T31 . e20 ) (hT211 ⇒ T31 il e22 )) −→∗H hT32 ⇒T212 il e32 −→∗H e22

We have shown that the domains and then the applied inner functions are equivalent. It now remains to show
that
cod(S)∪{T212 }
•
•
00
hT112 ⇒T122 il e11
'H hT32
⇒
T222 il ((λx :T31 . e20 ) (hT221 ⇒T31 il e22 )) : T222
We write the entire heedful term to highlight the fact that we cannot freely apply congruence, but must instead
carefully apply cast congruence (Lemma B.14) as we go.
•
•
00
00
By the IH, we know that either hT112 ⇒T122 il e11
and hT212 ⇒T222 il e22
go to blame (perhaps with different labels)
cod(S)

00
,
or to values. In the former case we are done; in the latter case, we already know that hT32 ⇒ T212 il e32 −→∗H e22
•
l
00
∗
000
so we can apply cast congruence (Lemma B.14) with the empty type set to see that if hT212 ⇒T222 i e22 −→H e22
cod(S)

•

cod(S)

•

000
. But we know that hT212 ⇒T222 il (hT32 ⇒ T212 il e32 ) −→H
then hT212 ⇒T222 il (hT32 ⇒ T212 il e32 ) −→∗H e22

hT32

cod(S)∪{T212 }

⇒

T222 il e32 deterministically, so we then we know that hT32

cod(S)∪{T212 }

hT32
⇒
and heedful

•
T222 i ((λx :T31 . e20 ) (hT221 ⇒T31 il e22 ))
000
000
term reduce to values e12 ∼H e22 : T222 , and
l

−→∗H

•

cod(S)∪{T212 }

⇒

000
T222 il e32 −→∗H e22
. Since

l

hT32 ⇒T222 i e32 , we have shown that the classic term
we are done.


B.20 Lemma [Relating classic and heedful source programs]:
1. If Γ `C e : T as a source program then Γ ` e 'H e : T .
2. If `C T as a source program then T ∼H T .
Proof:

By mutual induction on the typing derivations.

Term typing Γ `C e : T
T Var We know by assumption that δ1 (x ) ∼H δ2 (x ) : T .
T Const Since we are dealing with a source program, T = {x :B | true}. We have immediately that ty(k ) = B
and true[k /x ] 'H true[k /x ] : {x :Bool | true}, so k 'H k : {x :B | true}.
T Abs Let Γ |=H δ. We must show that λx :T1 . δ1 (e1 ) ∼H λx :T1 . δ2 (e1 ) : T1 →T2 . Let e2 ∼H e20 : T1 . We must
show that applying the abstractions to these values yields related values. Both sides step by E Beta, to δ1 (e1 )[e2 /x ]
and δ2 (e1 )[e20 /x ], respectively. But Γ, x :T1 |=H δ[e2 , e20 /x ], so we can apply IH (1) on e1 showing the two sides reduce
to related results.

49

T Op By IH (1) on each argument, either one of the arguments goes to blame (in both calculi), and we are done
by E OpRaise, or all of the arguments reduce to related values. Since ty(op) is first order, these values must be
related at refined base types, which means that they are in fact all equal constants. We then reduce by E Op on
both sides to have [[op]] (k1 , . . . , kn ). We have assumed that the denotations of operations agree with their typings in
all modes, so then [[op]] (k1 , . . . , kn ) satisfies the refinement for −→H in particular, and we are done.
T App Let Γ |=H δ. We must show that δ1 (e1 ) δ1 (e2 ) 'H δ2 (e1 ) δ2 (e2 ) : T2 . But by IH (1) on e1 and e2 , we are
done directly.
T Cast We know that the annotation is •, since we are dealing with a source term. Let Γ |=H δ. By IH
(1) on e 0 , we know that δ1 (e 0 ) 'H δ2 (e 0 ) : T1 , either δ1 (e 0 ) −→∗C ⇑l 0 and δ2 (e 0 ) −→∗H ⇑l 00 (and we are done)
or δ1 (e 0 ) and δ2 (e 0 ) reduce to values e1 ∼H e2 : T1 . By Lemma B.19 (using IH (2) on the types), we know that
•
•
hT1 ⇒T2 il e1 ∼H hT1 ⇒T2 il e2 : T2 , so each side must reduce to a result e10 ∼H e20 : T2 . We have cast congruence on
the classic side straightforwardly, finding:
•

•

hT1 ⇒T2 il δ1 (e 0 ) −→∗C hT1 ⇒T2 il e1 −→∗C e10
•

On the heedful side, we can apply our derived cast congruence (Lemma B.14) to find that hT1 ⇒T2 il e2 −→∗H e20 and
•
δ2 (e 0 ) −→∗H e2 imply that hT1 ⇒T2 il δ2 (e 0 ) −→∗H e20 .
T Blame Contradiction—doesn’t appear in source programs. Though in fact it is in the relation, since ⇑l 'H
⇑l 0 : T for any l , l 0 , and T .
T Check Contradiction—doesn’t appear in source programs.
Type well formedness `C T
WF Base We can immediately see true[k /x ] 'H true[k /x ] : {x :Bool | true} for any k ∼H k : {x :B | true}, i.e., any
k such that ty(k ) = B .
WF Refine By inversion, we know that x :{x :B | true} `C e : {x :Bool | true}; by IH (1), we find that δ1 (e) 'H
δ2 (e) : {x :Bool | true}, i.e., that e[e1 /x ] 'H e[e2 /x ] : {x :Bool | true} for all e1 ∼H e2 : {x :B | true}—which is what we
needed to know.
WF Fun By IH (2) on each of the types.

We have investigated two alternatives to the formulation here: type set optimization and invariants that clarify
the role of type sets.
S
First, we can imagine a system that optimizes the type set of hT1 ⇒T2 il such that T1 and T2 don’t appear in
S—taking advantage of idempotence not only for the source type (Lemma B.9) but also for the target type. This
change complicates the theory but doesn’t give any stronger theorems. Nevertheless, such an optimization would be
a sensible addition to an implementation.
Second, our proof relates source programs, which start with empty annotations. In fact, all of the reasoning about
type sets is encapsulated in our proof cast congruence(Lemma B.14). We could define a function from heedful λH to
classic λH that unrolls type sets according to the choose function. While this proof would offer a direct understanding
of heedful λH type sets in terms of the classic semantics, it wouldn’t give us a strong property—it degenerates to our
proof in the empty type set case.

B.3

Relating classic and eidetic manifest contracts

B.21 Lemma [Idempotence of coercions]: If ∅ `E k : {x :B | e1 } and `E join(r1 , r2 ) k {x :B | e1 } ⇒ {x :B | e2 },
then for all resultE e, we have h{x :B | e1 }
e2 }i• k −→∗E e.

join(r1 ,drop (r2 ,{x :B|e1 }))

{x :B | e2 }i• k −→∗E e iff h{x :B | e1 }

⇒

join(r1 ,r2 )

⇒

{x :B |

Proof: By induction on their evaluation derivations: the only difference is that the latter derivation performs some
extra checks that are implied by e1 [k /x ] −→∗E true—which we already know to hold.

As before, cast congruence is the key lemma in our proof—in this case, the strongest property we have: reduction
to identical results.
B.22 Lemma [Cast congruence (single step)]: If
c

– ∅ `E e1 : T1 and `E c k T1 ⇒ T2 (and so ∅ `E hT1 ⇒T2 i• e1 : T2 ),
50

– e1 −→E e2 (and so ∅ `E e2 : T1 ),
c

c

then for all resultE e, we have hT1 ⇒T2 i• e1 −→∗E e iff hT1 ⇒T2 i• e2 −→∗E e.
Proof: By cases on the step taken to find e1 −→E e2 .
There are two groups of reductions: straightforward merge-free reductions and merging reductions. In many
cases, we simply show confluence, which implies the cotermination at identical values in our deterministic semantics
(Lemma A.28).
Merge-free reductions In these cases, we apply E CoerceInner and whatever rule derived e1 −→E e2 to find
c
c
c
that hT1 ⇒T2 i• e1 −→E hT1 ⇒T2 i• e2 , i.e., e = hT1 ⇒T2 i• e2 .
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E
(E

Beta) By E CoerceInner and E Beta.
Op) By E CoerceInner and E Op.
Unwrap) By E CoerceInner and E Unwrap.
AppL) By E CoerceInner with E AppL.
AppR) By E CoerceInner with E AppR.
AppRaiseL) By E CoerceInner with E AppRaiseL; then by E CastRaise on both sides.
AppRaiseR) By E CoerceInner with E AppRaiseR; then by E CastRaise on both sides.
Coerce) By E CoerceInner and E Coerce.
StackDone) By E CoerceInner and E StackDone.
StackPop) By E CoerceInner and E StackRaise.
StackInner) By E CoerceInner and E StackRaise.
StackRaise) By E CoerceInner and E StackRaise.
CheckOK) By E CoerceInner and E CheckOK.
CheckFail) By E CoerceInner and E CheckRaise.
CheckFail) By E CoerceInner and E CheckRaise.
OpInner) By E CoerceInner and E OpInner.
OpRaise) By E CoerceInner and E OpRaise.

Merging reductions In these cases, some coercion in e1 reduces when we step e1 −→E e2 , but merges when we
c
c
consider hT1 ⇒T2 i• e1 . We must show that the merged term and hT1 ⇒T2 i• e2 eventually meet at some common term
c2
c1
•
•
e. It’s convenient to renumber the types and coercions, so we consider hT2 ⇒T
3 i e1 where e1 = hT1 ⇒T2 i e −→E e2
for some e.
r

1
•
•
(E CoerceStack) We have e1 = hT1 ⇒T
2 i k and e2 = hT2 , ?, r1 , k , k i . Since our term is well typed, we know

join(r1 ,r2 )

that c2 is some r2 . In the original, unreduced term with e1 , we step to hT1 ⇒ T3 i• k by E CastMerge; we then
step by E CoerceStack to hT3 , ?, join(r1 , r2 ), k , k i• . Call this term e10 .
r2
•
•
0
In the reduced term with e2 , we have hT2 ⇒T
3 i hT2 , ?, r1 , k , k i . Call this term e2 .
0
0
We must show that e1 reduces to a given result iff e2 does.
The term e10 evaluates by running through the checks in join(r1 , r2 ), raising blame if a check fails or returning k
if they all succeed.
The term e20 evaluates by running through the checks in r1 , raising blame if a check fails or returning k if they all
succeed, eventually reducing to hT3 , ?, r2 , k , k i• in that case. This term, similarly, reduces to k or ⇑l if a given check
fails. Note that types are preserved by join left-to-right, so if there is a type that fails in r1 , it fails in join(r1 , r2 ), as
well. So e20 fails in the first set of checks iff e10 fails in the first half of join(r1 , r2 ).
Now we must consider those checks in r2 . It may be that there are types in r2 that were subsumed by a check in
r1 : these types are re-checked in e20 but not in e10 , since the latter merges coercions while the former doesn’t. We can
show that these second checks are redundant by idempotence (Lemma B.21), allowing us to conclude that e10 and e20
also behave the same on the second half of the checks, and therefore the two terms both go to the same blame label
or to the same constant.
c1
c1
• 0
• 00
00
(E CoerceInner) e1 = hT1 ⇒T
2 i e1 and e2 = hT1 ⇒T2 i e1 such that e1 −→E e1 and e1 isn’t a coercion term.
Both sides reduce to the common term hT1

join(c1 ,c2 )

⇒

c

c

2
1
•
• 0
T3 i• e100 . We step hT2 ⇒T
3 i (hT1 ⇒T2 i e1 ) first by E CastMerge

join(c1 ,c2 )

c

c

2
1
•
• 00
to hT1 ⇒ T3 i• e 0 , after which we can apply E CoerceInner. We step hT2 ⇒T
3 i (hT1 ⇒T2 i e1 ) directly to e
by E CastMerge.

c

c

1
0
•
•
0
(E CastMerge) e1 = hT1 ⇒T
2 i (hT0 ⇒T1 i e ) and e2 = hT0

hT0

join(join(c0 ,c1 ),c2 )

⇒

join(c0 ,c1 )

⇒

T2 i• e 0 . The common term here is

T3 i• e 0 : we step the left-hand side by E CastMerge twice, and e2 only once.
51

c

1
•
(E CoerceRaise) We have e1 = hT1 ⇒T
2 i ⇑l and e2 = ⇑l . Both reduce to the common term ⇑l . The former
first steps by E CastMerge, and then both step by E CoerceRaise.


B.23 Lemma [Cast congruence]: If
c

– ∅ `E e1 : T1 and `E c k T1 ⇒ T2 (and so ∅ `E hT1 ⇒T2 i• e1 : T2 ),
– e1 −→∗E e2 (and so ∅ `E e2 : T1 ),
c

c

then there exists an e such that hT1 ⇒T2 i• e1 −→∗E e and hT1 ⇒T2 i• e2 −→∗E e. Diagrammatically:
e1

E e2

⇓
•

•

l

hT1 ⇒T2 il e2

hT1 ⇒T2 i e1

E

E

∗

∗

Proof:

resultE e

By induction on the derivation e −→∗E e1 , using the single-step cast congruence (Lemma B.22).



Our proof strategy is as follows: we show that the casts between related types are applicative, and then we
show that well typed source programs in classic λH are logically related to their translation. Our definitions are in
Figure 12. Our logical relation is blame-exact. Like our proofs relating forgetful and heedful λH to classic λH , we use
the space-efficient semantics in the refinement case and use space-efficient type indices.
B.24 Lemma [Similar casts are logically related]: If T1 ∼E T10 and T2 ∼E T20 and e1 ∼E e2 : T1 , then
•
•
hT1 ⇒T2 il e1 'E hT10 ⇒T20 il e2 : T2 .
Proof:

By induction on the invariant relation, using coercion congruence in the function case when e2 is a function

proxy. We always step first by E Coerce on the right to hT10

coerce(T10 ,T20 ,l)

⇒

T20 i• e2 .

(A Refine) Let e10 ∼E e20 : {x :B | e10 }, we know that e10 = e20 = k such that e10 [k /x ] −→∗E true. In classic λH , we
step by E CheckNone to h{x :B | e2 }, e2 [k /x ], k il ; in eidetic λH , we step by E Coerce and then E CoerceStack
to h{x :B | e20 }, ?, {x :B | e20 }l , k , k i• , and then by E StackPop to
h{x :B | e20 }, X, nil, k , h{x :B | e20 }, e20 [k /x ], k il i•
Since k ∼E k : {x :B | true} by definition and reflexivity of −→∗E , we know that e2 [k /x ] 'E e20 [k /x ] : {x :Bool | true}. If
the predicates step to a blame label (the same one!), then both terms raise that label (by E CheckRaise, with an
added E StackRaise on the right). Similarly, if the predicates go to false, then both sides raise ⇑l by E CheckFail
(followed by the same steps as for inner blame). Finally, if the predicates both go to true, then both checks return k .
After stepping by E StackDone on the right, we find that both terms reduce to k and that e20 [k /x ] −→∗E true.
0
0
0
0
0
0
(A Fun) We have T11 →T12 ∼E T11
→T12
and T21 →T22 ∼E T21
→T22
. Let e1 ∼E e2 : T11
→T12
. The classic side
is a value, by V ProxyC. The eidetic λH term is:
c 7→c

0
0 1
0
0 •
hT11
→T12
⇒ 2 T21
→T22
i e2

How this term steps depends on the shape of the value e2 : either e2 is an abstraction λx :T . e and we have a value
c 0 7→c 0

0
0 •
by V ProxyE, or it is a function proxy hT01 →T02 1⇒ 2 T11
→T12
i λx :T01 . e and we step by E CastMerge.
c 7→c

0
0 1
0
0 •
0
(V ProxyE) We step to hT11
→T12
⇒ 2 T21
→T22
i e2 . Let e10 ∼E e20 : T21
be given. Both sides unwrap,
•
•
l
l
0
0 c2
0 •
0 c1
0 •
giving us hT12 ⇒T22 i (e1 (hT21 ⇒T11 i e1 )) on the classic side and hT12 ⇒T22 i (e2 (hT21
⇒T12
i e20 )). By the
IH, the arguments are related and reduce to related results (by expansion via E Coerce and the observation that
0
0
coerce(T21
, T11
, l ) = c1 ). Blame (at the same label!) aborts the computation. If the arguments produce values, then
0
0
0
we apply our assumption that e1 ∼E e2 : T11
→T12
, so e1 e10 'E e2 e20 : T12
. Again, blame (at the same label!) aborts
early. A value flows to the related codomain casts, and we are done by the IH and E Coerce-expansion (observing
0
0
coerce(T12
, T22
, l ) = c2 ).

52

join(c1 ,c 0 )7→join(c 0 ,c2 )

2
1
0
0 •
0
0
0
0
⇒
T21
→T22
i λx :T01
. e. Let e10 ∼E e20 : T21
be given.
(E CastMerge) We step to hT01
→T02
•
•
l
Both sides unwrap as above. On the classic side, we have the same term as before: hT12 ⇒T22 i (e1 (hT21 ⇒T11 il e10 )).

join(c 0 ,c2 )

2
0
0 •
0
0
On the eidetic side, we have some extra coercions: hT02
⇒
T22
i ((λx :T01
. e) (hT21
coercion congruence to resolve these, and see that both terms behave the same.

c0

0
join(c1 ,c1
)

0 • 0
T01
i e1 )). We use

⇒

c

0 1
0 •
0 1
0 •
Considering the argument, we can factor it out to the term hT11
⇒T01
i (hT21
⇒T11
i e20 ). We know that
•
l
0
0 c1
0 • 0
0
0
0
hT21 ⇒T11 i e1 'E hT21 ⇒T11 i e2 : T11 by the IH (with E Coerce-expansion, observing that coerce(T21
, T11
, l) =
00
00
0
c1 ), so they reduce to related results e1 'E e2 : T11 . By coercion congruence (Lemma B.23), we know that
c0

c0

c

0 1
0 •
0 1
0 •
0 1
0 •
hT11
⇒T01
i e200 and hT11
⇒T01
i (hT21
⇒T11
i e20 ) behave identically. We can make a similar observation in the
c0

c

c0

c

0 2
0 •
0 2
0 •
0
0 1
0 •
0 1
0 • 0
codomain: factoring out to hT12
⇒T22
i (hT02
⇒T12
i ((λx :T01
. e) (hT11
⇒T01
i (hT21
⇒T11
i e2 )))), we know that
0
0
0 •
0 •
0
0 c1
0 •
0 c2
0 c2
⇒T01
i e200 ))); by assumption, we know
⇒T12
i ((λx :T01
. e) (hT11
⇒T22
i (hT02
this term is equivalent to hT12
0
0
c
c
0 •
0 •
0
0 1
0 2
⇒T01
i e200 )) is equivalent to e1 e100 , so they both reduce to related results
⇒T22
i ((λx :T01
. e) (hT11
that hT12
000
000
0
e1 'E e2 : T12 . Now, by the IH on the codomain (along with E Coerce expansion and the observation that
•
0 • 000
0
0 c2
0
0
⇒T22
i e2 : T22
. We can apply coercion congruence
coerce(T12
, T22
, l ) = c2 ), we know that hT12 ⇒T22 il e1000 'E hT12
000
again (Lemma B.23) to see that the behavior on e2 is the same as the behavior on the unreduced term.


B.25 Lemma [Relating classic and eidetic source programs]:
1. If Γ `C e : T as a source program then Γ ` e 'E e : T .
2. If `C T as a source program then T ∼E T .
Proof:

By mutual induction on the typing derivations.

Term typing Γ `C e : T
T Var We have x = x . We know by assumption that δ1 (x ) ∼E δ2 (x ) : T .
T Const We have k = k . Since we are dealing with a source program, T = {x :B | true}. We have immediately
that ty(k ) = B and true[k /x ] 'E true[k /x ] : {x :Bool | true} by reflexivity of −→∗C , so k 'E k : {x :B | true}.
T Abs Let Γ |=E δ. We must show that λx :T1 . δ1 (e1 ) ∼E λx :T1 . δ2 (e1 ) : T1 →T2 . Let e2 ∼E e20 : T1 . We must
show that applying the abstractions to these values yields related values. Both sides step by E Beta, to δ1 (e1 )[e2 /x ]
and δ2 (e1 )[e20 /x ], respectively. But Γ, x :T1 |=E δ[e2 , e20 /x ], so we can apply IH (1) on e1 and e1 to show the two sides
reduce to related results.
T Op By IH (1) on each argument, either one of the arguments goes to blame (in both calculi), and we are done
by E OpRaise, or all of the arguments reduce to related values. Since ty(op) is first order, these values must be
related at refined base types, which means that they are in fact all equal constants. We then reduce by E Op on
both sides to have [[op]] (k1 , . . . , kn ). We have assumed that the denotations of operations agree with their typings in
all modes, so then [[op]] (k1 , . . . , kn ) satisfies the refinement for −→C in particular, and we are done.
T App Let Γ |=E δ. We must show that δ1 (e1 ) δ1 (e2 ) 'E δ2 (e1 ) δ2 (e2 ) : T2 . But by IH (1) on e1 and e2 , we are
done directly.
T Cast Let Γ |=E δ. By IH (1) on e, we know that δ1 (e) 'E δ2 (e) : T1 , either δ1 (e) −→∗C ⇑l 0 and δ2 (e) −→∗E ⇑l 0
(and we are done) or δ1 (e 0 ) and δ2 (e 0 ) reduce to values e1 ∼E e2 : T1 . By Lemma B.24 (using IH (2) on the types),
•
•
we know that hT1 ⇒T2 il e1 ∼E hT1 ⇒T2 il e2 : T2 , so each side must reduce to a result e10 ∼E e20 : T2 . We have cast
congruence on the classic side straightforwardly, finding:
•

•

hT1 ⇒T2 il δ1 (e 0 ) −→∗C hT1 ⇒T2 il e1 −→∗C e10
•

On the heedful side, we can apply our derived cast congruence (Lemma B.23) to find that hT1 ⇒T2 il e2 −→∗E e20 and
•
δ2 (e) −→∗E e2 imply that hT1 ⇒T2 il δ2 (e) −→∗E e20 .
T Blame Contradiction—doesn’t appear in source programs. Though in fact it is in the relation, since ⇑l 'E
⇑l : T for any l and T .
T Check Contradiction—doesn’t appear in source programs.

53

Term type extraction

types(e) : P(T )
∅
∅
types(T ) ∪ types(e)
types(T1 ) ∪ types(T2 ) ∪
types(a) ∪ types(e)
types(e1 e2 ) = types(e
1 ) ∪ types(e2 )
S
types(op(e1 , . . . , en )) = 1≤i≤n types(ei )
types(h{x :B | e1 }, e2 , k il ) = types({x :B | e1 }) ∪ types(e2 )
types(h{x :B | e1 }, s, r , k , ei• ) =
types({x :B | e1 }) ∪ types(r ) ∪ types(e)
types(⇑l) = ∅
types(x )
types(k )
types(λx :T . e)
a
types(hT1 ⇒T2 il e)

=
=
=
=

Type, type set, and coercion type extraction
types(T ) : P(T )
types({x :B | e})
types(T1 →T2 )

=
=

{{x :B | e}} ∪ types(e)
{T1 →T2 } ∪
types(T1 ) ∪ types(T2 )

types(•)
types(S)

=
=

∅
S

types(nil)
types({x :B | e}l , r )
types(c1 7→ c2 )

=
=
=

∅
{{x :B | e}} ∪ types(r )
types(c1 ) ∪ types(c2 )

types(a) : P(T )

Type height

T ∈S

types(T )

height(T )
height({x :B | e})
height(T1 →T2 )

=
=

1
1 + maxi∈{1,2} height(Ti )

Figure 14: Type extraction and type height
Type well formedness `C T
WF Base We can immediately see true[k /x ] 'E true[k /x ] : {x :Bool | true} for any k ∼E k : {x :B | true}, i.e., any
k such that ty(k ) = B , since −→∗C is reflexive.
WF Refine By inversion, we know that x :{x :B | true} `C e : {x :Bool | true}; by IH (1), we find that δ1 (e) 'E
δ2 (e) : {x :Bool | true}, i.e., that e[e1 /x ] 'E e[e2 /x ] : {x :Bool | true} for all e1 ∼E e2 : {x :B | true}—which is what we
needed to know.
WF Fun By IH (2) on each of the types.


C

Proofs of bounds for space-efficiency

This section contains our definitions for collecting types in a program and the corresponding proof of bounded space
consumption (for all modes at once).
We define a function collecting all of the distinct types that appear in a program in Figure 14. If the type
T = {x :Int | x ≥ 0}→{y:Int | y 6= 0} appears in the program e, then types(e) includes the type T itself along with
its subparts {x :Int | x ≥ 0} and {y:Int | y 6= 0}.
C.1 Lemma: types(e[e 0 /x ]) ⊆ types(e) ∪ types(e 0 )
Proof:

By induction on e.

54

(e = y) types(y) = ∅, so we must show that types(y[e 0 /x ]) ⊆ types(e 0 ). If x 6= y, then types(y[e 0 /x ]) = types(y) =
∅, which is a subset of everything. If x = y, then types(x [e 0 /x ]) = types(e 0 ).
(e = k ) Immediate, since k is closed and types(k ) = ∅.
(e = λy:T . e) By the IH on e and the closure of T .
a
(e = hT1 ⇒T2 il e) By the IH on e and the closure of the types and annotations.
(e = e1 e2 ) By the IHs on e1 and e2 .
(e = op(e1 , . . . , en )) By the IHs on each ei .
(e = h{x :B | e1 }, e2 , k il ) By the IH on e2 and the closure of {x :B | e1 }—noting that e2 is in fact closed in well
typed terms.
(e = h{x :B | e1 }, s, r , k , ei• ) By the IH on e—though all of the terms are closed.
(e = ⇑l ) Immediate since ⇑l is closed and types(⇑l ) = ∅.

C.2 Lemma: types(T1 )∪types(mergem (T1 , a1 , T2 , a2 , T3 ))∪types(T3 ) ⊆ types(T1 )∪types(a1 )∪types(T2 )∪types(a2 )∪
types(T3 )
Proof: By cases on each, but observing that the merged annotation is always no bigger than the original, and that
the type T2 may or may not vanish.

C.3 Lemma: types(dom(a)) ⊆ types(a)
Proof: This property is trivial when a = •.
When the annotation is a type set, for dom(S) to be defined, every type in S must be a function type. So:
S
types(S) = ST ∈S types(T )
types(T1 →T2 )
=
ST1 →T2 ∈S
=
{T
1 →T2 } ∪
T1 →T2 ∈S
types(T
1 ) ∪ types(T2 )
S
types(T1 )
⊇
ST1 →T2 ∈S
=
T ∈types(dom(S)) types(T )
= types(dom(S))
Immediate when a = c1 7→ c2 .



C.4 Lemma: types(cod(a)) ⊆ types(a)
Proof: This property is trivial when a = •.
When the annotation is a type set, for cod(a) to be defined, every type in a must be a function type. So:
S
types(S) = ST ∈S types(T )
types(T1 →T2 )
=
ST1 →T2 ∈S
=
{T1 →T2 } ∪ types(T1 ) ∪ types(T2 )
ST1 →T2 ∈S
types(T2 )
⊇
ST1 →T2 ∈S
=
T ∈types(cod(S)) types(T )
= types(cod(S))
Immediate when a = c1 7→ c2 .



C.5 Lemma [Coercing types doesn’t introduce types]:
types(coerce(T1 , T2 , l )) ⊆ types(T1 ) ∪ types(T2 )
Proof: By induction on T1 and T2 . When they are refinements, we have the coercion just being {x :B | e2 }l . When
they are functions, by the IH.

C.6 Lemma [Dropping types doesn’t introduce types]:
types(drop (r , {x :B | e})) ⊆ types(r )
Proof:

By induction on r .

(r = nil) The two sides are immediately equal.

55

(r = {x :B | e 0 }l , r 0 ) If {x :B | e 0 } 6⊃ {x :B | e}, then the two are identical. If not, then we have types(r 0 ) ⊆ types(r )
by the IH.

C.7 Lemma [Coercion merges don’t introduce types]:
types(join(r1 , r2 )) ⊆ types(r1 ) ∪ types(r2 )
Proof:

By induction on r1 .

(r1 = nil) The two sides are immediately equal.
(r1 = {x :B | e}l , r10 ) Using Lemma C.6, we find:
types(join(r1 , r2 )) = {{x :B | e}} ∪
types(join(r10 , drop (r2 , {x :B | e})))
⊆ {{x :B | e}} ∪ types(r10 ) ∪
types(drop (r2 , {x :B | e}))
⊆ {{x :B | e}} ∪ types(r10 ) ∪ types(r2 )
= types(r1 ) ∪ types(r2 )

C.8 Lemma [Reduction doesn’t introduce types]: If e −→m e 0 then types(e 0 ) ⊆ types(e).
Proof:

By induction on the step taken.

Shared rules
(E Beta)
types((λx :T . e12 ) e2 )

types(T ) ∪ types(e12 ) ∪ types(e2 )
types(e12 ) ∪ types(e2 )
types(e12 [e2 /x ])

=
⊇
=

(Lemma C.1)

(E Op)
types(op(e1 , ... , en ))

=
⊇
=
=

S

1≤i≤n types(ei )
∅
types(k )
types([[op]] (e1 , ... , en ))

(operations are first order)

(E Unwrap)
a

types(hT11 →T12 ⇒T21 →T22 il e1 e2 )
= types(T11 →T12 ) ∪ types(T21 →T22 ) ∪ types(a) ∪ types(e1 ) ∪ types(e2 )
= {T11 →T12 } ∪ types(T11 ) ∪ types(T12 ) ∪ {T21 →T22 } ∪ types(T21 ) ∪ types(T22 ) ∪ types(a) ∪ types(e1 ) ∪ types(e2 )
⊇ types(T11 ) ∪ types(T12 ) ∪ types(T21 ) ∪ types(T22 ) ∪ types(a) ∪ types(e1 ) ∪ types(e2 )
⊇ types(T11 ) ∪ types(T12 ) ∪ types(T21 ) ∪ types(T22 ) ∪ types(dom(a)) ∪ types(cod(a)) ∪ types(e1 ) ∪ types(e2 )
(Lemmas C.3 and C.4)
=

cod(a)

dom(a)

types(hT12 ⇒ T22 il (e1 (hT21 ⇒ T11 il e2 )))
(E CheckNone)
•

types(h{x :B | e1 }⇒{x :B | e2 }il k )

=
⊇
=
=
⊇
=
=

types({x :B | e1 }) ∪ types(•) ∪ types({x :B | e2 }) ∪ types(k )
types({x :B | e2 }) ∪ types(k )
{{x :B | e2 }} ∪ types(e2 ) ∪ types(k )
types({x :B | e2 }) ∪ types(e2 ) ∪ types(k )
types({x :B | e2 }) ∪ types(e2 [k /x ])
types({x :B | e2 })
types(h{x :B | e2 }, e2 [k /x ], k il )

56

(Lemma C.1)
since types(k ) = •

(E CheckOK)
types(h{x :B | e}, true, k il )

=
⊇
=

types({x :B | e}) ∪ types(true)
∅
types(k )

types(h{x :B | e}, false, k il )

=
⊇
=

types({x :B | e}) ∪ types(false)
∅
types(⇑l )

(E CheckFail)

(E AppL)
types(e1 e2 )

=
⊇
=

types(e1 ) ∪ types(e2 )
types(e10 ) ∪ types(e2 )
types(e10 e2 )

(IH)

=
⊇
=

types(e1 ) ∪ types(e2 )
types(e1 ) ∪ types(e20 )
types(e1 e20 )

(IH)

(E AppR)
types(e1 e2 )

(E OpInner)
types(op(e1 , . . . , ei−1 , ei , . . . , en ))

S
types(ei )
S
S1≤i≤n
0
types(e
j ) ∪ types(ei ) ∪
i+1≤j≤n types(ej )
1≤j≤i
types(op(e1 , . . . , ei−1 , ei0 , . . . , en ))

=
⊇
=

(IH)

(E CheckInner)
types(h{x :B | e1 }, e2 , k il )

=
⊇
=

types({x :B | e1 }) ∪ types(e2 )
types({x :B | e1 }) ∪ types(e20 )
types(h{x :B | e1 }, e20 , k il )

types(⇑l e2 )

=
⊇
=

types(⇑l ) ∪ types(e2 )
∅
types(⇑l )

types(e1 ⇑l )

=
⊇
=

types(e1 ) ∪ types(⇑l )
∅
types(⇑l )

(IH)

(E AppRaiseL)

(E AppRaiseR)

(E CastRaise)
S

types(hT1 ⇒T2 il ⇑l 0 )

=
⊇
=

types(T1 ) ∪ types(T2 ) ∪ types(S) ∪ types(⇑l 0 )
∅
types(⇑l 0 )

(E OpRaise)
types(op(e1 , . . . , ei−1 , ⇑l , . . . , en ))

S

=
⊇
=

1≤j≤i

types(ej ) ∪ types(⇑l ) ∪

S

i+1≤j≤n

∅
types(⇑l )

(E CheckRaise)
0

types(h{x :B | e}, ⇑l , k il )

=
⊇
=

types({x :B | e}) ∪ types(⇑l )
∅
types(⇑l )

57

types(ej )

Classic λH rules
(E CastInnerC)
•

types(hT1 ⇒T2 il e)

=
⊇
=

types(T1 ) ∪ types(T2 ) ∪ types(•) ∪ types(e)
types(T1 ) ∪ types(T2 ) ∪ types(•) ∪ types(e 0 )
•
types(hT1 ⇒T2 il e 0 )

(IH)

=
⊇
=

types(T2 ) ∪ types(T3 ) ∪ types(a) ∪ types(e2 )
types(T2 ) ∪ types(T3 ) ∪ types(a) ∪ types(e20 )
a
types(hT2 ⇒T3 il e20 )

(IH)

Efficient λH rules (m 6= C)
(E CastInner)
a

types(hT2 ⇒T3 il e2 )

(E CastMerge)
a

0

a

2
1
l
l
types(hT2 ⇒T
3 i (hT1 ⇒T2 i e2 ))

=
⊇
=

types(T2 ) ∪ types(T3 ) ∪ types(a2 ) ∪
types(T1 ) ∪ types(T2 ) ∪ types(a1 ) ∪ types(e2 )
types(T1 ) ∪ types(T3 ) ∪
types(mergem (T1 , a1 , T2 , a2 , T3 )) ∪ types(e2 )
types(hT1

mergem (T1 ,a1 ,T2 ,a2 ,T3 )

⇒

(Lemma C.2))

l

T3 i e2 )

Heedful λH rules
(E TypeSet)

•

types(hT1 ⇒T2 il e)

=

types(T1 ) ∪ types(T2 ) ∪ types(e)
∅

= types(hT1 ⇒T2 il e)
(E CheckEmpty)
∅

types(h{x :B | e1 }⇒{x :B | e2 }il k )

=
⊇
=
=
⊇
=
=

types({x :B | e1 }) ∪ types(∅) ∪ types({x :B | e2 }) ∪ types(k )
types({x :B | e2 }) ∪ types(k )
{{x :B | e2 }} ∪ types(e2 ) ∪ types(k )
types({x :B | e2 }) ∪ types(e2 ) ∪ types(k )
types({x :B | e2 }) ∪ types(e2 [k /x ])
types({x :B | e2 })
types(h{x :B | e2 }, e2 [k /x ], k il )

(Lemma C.1)
since types(k ) = ∅

(E CheckSet)
S

types(h{x :B | e1 }⇒{x :B | e3 }il k )

=
=
=

⊇

=

types({x :B | e1 }) ∪ types({x :B | e3 }) ∪ types(S) ∪ types(k )
types({x :B | e1 }) ∪ types({x :B | e3 }) ∪ types(S)
types({x :B | e1 }) ∪ types({x :B | e3 }) ∪
types(S \ {x :B | e2 }) ∪ types({x :B | e2 })
({x :B | e2 } ∈ S)
types({x :B | e1 }) ∪ types({x :B | e3 }) ∪
types(S \ {x :B | e2 }) ∪ types({x :B | e2 }) ∪ types(e2 [k /x ])
(Lemma C.1 and types(k ) = ∅)
S\{x :B|e2 }

types(h{x :B | e2 }

⇒

{x :B | e3 }il h{x :B | e2 }, e2 [k /x ], k il )

Eidetic λH rules
(E Coerce)
•

types(hT1 ⇒T2 il e)

=
=

types(T1 ) ∪ types(T2 ) ∪ types(e)
types(coerce(T1 , T2 , l )) ∪ types(T1 ) ∪ types(T2 ) ∪ types(e)

=

types(hT1

coerce(T1 ,T2 ,l)

⇒

T2 i• e)
58

(Lemma C.5)

(E CoerceStack)
r

types(h{x :B | e1 }⇒{x :B | e2 }i• k )

(E StackDone)

=
⊇
=

types({x :B | e1 }) ∪ types({x :B | e2 }) ∪ types(r )
types({x :B | e2 }) ∪ types(r )
h{x :B | e2 }, ?, r , k , k i•

types(h{x :B | e}, X, nil, k , k i• )

=
⊇
=

types({x :B | e})
∅
types(k )

(E StackPop)
types(h{x :B | e}, s, ({x :B | e 0 }l , r ), k , k i• )

=
=
=
=

types({x :B | e}) ∪ types({x :B | e 0 }l , r )
types({x :B | e}) ∪ types({x :B | e 0 }) ∪ types(r ) ∪ types(e 0 )
types({x :B | e}) ∪ types({x :B | e 0 }) ∪ types(r ) ∪ types(e 0 [k /x ])
types(h{x :B | e}, s ∨ (e = e 0 ), r , k , h{x :B | e 0 }, e 0 [k /x ], k il i• )

(Lemma C.1)

(E StackInner)
types(h{x :B | e}, s, r , k , e 0 i• )

(E StackRaise)

=
⊇
=

types({x :B | e}) ∪ types(r ) ∪ types(e 0 )
types({x :B | e}) ∪ types(r ) ∪ types(e 00 )
types(h{x :B | e}, s, r , k , e 00 i• )

types(h{x :B | e}, X, nil, k , k i• )

=
⊇
=

(IH)

types({x :B | e})
∅
types(k )


59

