@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c",
center "@c",
right "@c")
@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
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(148 pages)])