Representing Monads
We show that any monad whose unit and extension operations are
expressible as purely functional terms can be embedded in a call-by-value
language with "composable continuations". As part of the
development, we extend Meyer and Wand's characterization of the
relationship between continuation-passing and direct style to one for
continuation-passing vs. general "monadic" style. We further show
that the composable-continuations construct can itself be represented
using ordinary, non-composable first-class continuations and a single
piece of state. Thus, in the presence of two specific computational
effects -- storage and escapes -- any expressible monadic structure
(e.g., nondeterminism as represented by the list monad) can be added as
a purely definitional extension, without requiring a reinterpretation
of the whole language. The paper includes an implementation of the
construction (in Standard ML with some New Jersey extensions) and
several examples.
Full document:
DVI or
PostScript.