[Prev][Next][Index][Thread]

monad transformer papers




Although I wrote these papers on monad transformers a while ago, I
forgot to announce them in a sufficiently public forum.  Both are
available (and code also) from

	swiss-ftp.ai.mit.edu : pub/users/dae

My thesis presents this work more clearly and should be available
within the next month.

David Espinosa
Columbia University and
MIT Artificial Intelligence Lab


Semantic Lego
(written December 1993)
-----------------------

This paper describes an approach to monad transformers based on
lifting.  A monad may have several operators defined on it besides
unit and bind.  When we transform the monad, we lift the operators
through the transformer and also add new operators.  This approach
comes almost directly from Moggi's 1989 notes, which are also
available from the above ftp site.  We present examples in Scheme and
work in terms of functional programming rather than denotational
semantics.


Stratified Monads
(written June 1994)
-------------------

We improve on the above by formalizing an intermediate interface
between the basic denotational semantics and the language constructs,
called a stratified monad.  Using stratified monads, we can split
semantics into two parts, a semantic algebra, implemented by a
stratified monad, and a language algebra, implemented by a set of
constructs definitions over the semantic algebra.  The advantages are:

  * We can build semantic algebras from component parts.

  * We can reuse language constructs over multiple semantic algebras.

  * We can define a large class of language constructs at a high level
    of abstraction.

  * We can cleanly define language constructs that involve multiple
    semantic layers (such as environments and continuations).

  * Semantic algebras explicitly represent the layered structure of
    denotational models.

This approach differs from Mosses's action semantics because we form
specialized semantic algebras from component modules.  That is, we are
no longer limited to a single, fixed semantic algebra.  Furthermore,
we can reason equationally over the algebra in a disciplined way using
the stratified monad laws (these are presented in my thesis).