Evaluation strategies for monadic computations
In Proceedings of MSFP 2012
Monads have become a powerful tool for structuring effectful computations in functional programming, because they make the order of effects explicit. When translating pure code to a monadic version, we need to specify evaluation order explicitly. Two standard translations give call-by-value and call-by-name semantics. The resulting programs have different structure and types, which makes revisiting the choice difficult.
In this paper, we translate pure code to monadic using an additional operation
malias that abstracts out the evaluation strategy. The
malias operation is
based on computational comonads; we use a categorical
framework to specify the laws that are required to hold about the operation.
For any monad, we show implementations of
malias that give call-by-value
and call-by-name semantics. Although we do not give call-by-need semantics
for all monads, we show how to turn certain monads into an extended monad with
call-by-need semantics, which partly answers an open question.
Moreover, using our unified translation, it is possible to change the evaluation strategy
of functional code translated to the monadic form without changing its structure or types.
Paper and more information
- Download the paper pre-print (PDF)
- Download the published paper (PDF), from arXiv
- View slides from MSFP 2012 (PDF)
- Download associated Haskell source code (ZIP)
malias abstraction has been partly inspired by the author's work on
joinads which add pattern matching support to monadic computations. Joinads
malias operation for a related reason - for more information see
also Extending monads with pattern matching.
If you want to cite the paper, you can use the following BibTeX information, or get full details from the paper page on arXiv.
1: 2: 3: 4: 5: 6: 7: 8:
Published: Saturday, 17 March 2012, 12:00 AM
Author: Tomas Petricek
Typos: Send me pull request!