Lifting of operations in modular monadic semantics

Jaskelioff, Mauro Javier (2009) Lifting of operations in modular monadic semantics. PhD thesis, University of Nottingham.

PDF (PhD Thesis)


Monads have become a fundamental tool for structuring denotational semantics and programs by abstracting a wide variety of computational features such as side-effects, input/output, exceptions, continuations and non-determinism. In this setting, the notion of a monad is equipped with operations that allow programmers to manipulate these computational effects. For example, a monad for side-effects is equipped with operations for setting and reading the state, and a monad for exceptions is equipped with operations for throwing and handling exceptions.

When several effects are involved, one can employ the incremental approach to mod- ular monadic semantics, which uses monad transformers to build up the desired monad one effect at a time. However, a limitation of this approach is that the effect-manipulating operations need to be manually lifted to the resulting monad, and consequently, the lifted operations are non-uniform. Moreover, the number of liftings needed in a system grows as the product of the number of monad transformers and operations involved.

This dissertation proposes a theory of uniform lifting of operations that extends the incremental approach to modular monadic semantics with a principled technique for lifting operations. Moreover the theory is generalized from monads to monoids in a monoidal category, making it possible to apply it to structures other than monads.

The extended theory is taken to practice with the implementation of a new extensible monad transformer library in Haskell, and with the use of modular monadic semantics to obtain modular operational semantics.

Item Type:Thesis (PhD)
Supervisors:Hutton, G.M.
Ghani, N.
Uncontrolled Keywords:monadic semantics, monads, programming, computers, computer science
Faculties/Schools:UK Campuses > Faculty of Science > School of Computer Science
ID Code:1226
Deposited By:Dr. Mauro Jaskelioff
Deposited On:23 Apr 2010 09:12
Last Modified:02 Jun 2010 11:49

Archive Staff Only: item control page