[L7] ================================================ AMAST Links 02 01

                        Papers on Monad transformers
 David Espinosa, Columbia University & MIT Artificial Intelligence Lab

   Both papers are available (and code also) by anonymous ftp at
URL: ftp://swiss-ftp.ai.mit.edu/pub/users/dae
  My thesis presents this work more clearly and should be available
within the next month.

  *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:
 o  We can build semantic algebras from component parts.
 o  We can reuse language constructs over multiple semantic algebras.
 o  We can define a large class of language constructs at a high level
    of abstraction.
 o  We can cleanly define language constructs that involve multiple
    semantic layers (such as environments and continuations).
 o  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).