[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 .

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:

• 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).