@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c<Technical Report 1996>",
center "@c<Computer Science>",
right "@c<Carnegie Mellon>")
@heading(Controlling Effects)
@heading(CMU-CS-96-119)
@center(@b(Andrzej Filinski))
@center(May 1996 - Ph.D. Thesis)
@center(FTP: CMU-CS-96-119.ps)
@blankspace(1)
@begin(text)

Many computational effects, such as exceptions, state, or
nondeterminism, can be conveniently specified in terms of @i(monads).  We
investigate a technique for uniformly adding arbitrary such effects to
ML-like languages, without requiring any structural changes to the
programs themselves.  Instead, we use @i(monadic reflection), a new
language construct for explicitly converting back and forth between
representations of effects as @i(behavior) and as @i(data).

Using monadic reflection to characterize concisely all effects
expressible with a given monad, we can give a precise meaning to the
notion of @i(simulating) one effect by another, more general one. We
isolate a simple condition allowing such a simulation, and in
particular show that any monadic effect can be simulated by a
continuation monad.  In other words, under relatively mild assumptions
on the base language (allowing formation of a suitably large answer
type), control becomes a @i(universal effect).

Concluding the development, we show that this universal effect can
itself be explicitly implemented in terms of only standard first-class
continuations @t(call/cc) and a piece of global state.  This means that
we can specify an effect such as nondeterminism abstractly, in terms
of result lists, then directly obtain from this description a
nondeterministic-choice operator performing imperatively-implemented
backtracking.  We include a full realization of the general
construction in Standard ML of New Jersey, and give several
programming examples.

@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c<Monads, continuations, computational effects, monadic
reflection, logical relations, Scheme, ML>
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(148 pages)])