The notion of a computational effect refers to computational phenomena beyond purely functional computation. This may encompass:
In order to systematically structure the semantics of programming languages with effects, Eugenio Moggi proposed the use of the category-theoretic notion of monads.
Independently, Mike Spivey noticed that the concept of monads is useful for structuring functional programs with an effectful flavour (e.g. those that can throw exceptions). This was later developed into a remarkable array of techniques: see monads in functional programming.
For more information, see the main article.
At some point in the late 1990s it was noticed that the monadic framework of Moggi is perhaps "too crude."
One possible alternative is this: instead of writing down a monad, we specify an algebraic signature for the effect we are interested in. This consists of some operations (e.g. lookup
, update
, choose
), as well as some equations governing their behaviour. Then, in the spirit of categorical algebra, this specification induces a monad: see e.g. the relevant nLab page. Thus, we achieve a "decomposition" of each algebraic effect into more primitive operations, leading to a finer semantic analysis of effects.
For more information, see the main article.
While algebraic effects are a rich framework, they cannot do everything.
For example, exceptions can be modelled by including a construct in an algebraic theory. However, the corresponding notion of handling this expression that has been raised (which may contain more specific information about the exception that has been raised) is in some sense non-algebraic: it cannot be written down in the language of algebraic theories.
Thus, we are led to the concept of an algebraic effect handler.
For more information, see the main article.