Algebraic effects

We speak of algebraic effects when we use the language of algebraic theories to capture the notion of computational effect.

This approach was pioneered by John Power, beginning in the late 1990s. The objective was to replace the more coarse-grained use of monads to structure the semantics of effects. This led to a series of papers by Power, Plotkin, and others.

Categorical semantics

The categorical semantics of algebraic effects was presented at MFPS 2001, with the journal version appearing in 2003 Plotkin and Power 2003.

The adequacy of this semantics is proven in Plotkin and Power 2001.

References

Community-maintained effects bibliography on GitHub.
The pre-history of algebraic effects seem to begin with the notion of enriched Lawvere theories developed by John Power in

Power, John. 1999. ‘Enriched Lawvere Theories’. Theory And Applications Of Categories 6 (7): 83–93. link

@article{power_1999,
	title = {Enriched {Lawvere} {Theories}},
	volume = {6},
	number = {7},
	journal = {Theory And Applications Of Categories},
	author = {Power, John},
	year = {1999},
	pages = {83--93}
}

The first article that promotes their use and attempts to prove an adequacy theorem was published at FoSSaCS 2001:

Plotkin, Gordon, and John Power. 2001. ‘Adequacy for Algebraic Effects’. In Foundations of Software Science and Computation Structures, edited by Furio Honsell and Marino Miculan. Vol. 2030. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-45315-6_1. pdf

@inproceedings{power_2001,
	address = {Berlin, Heidelberg},
	series = {Lecture {Notes} in {Computer} {Science}},
	title = {Adequacy for {Algebraic} {Effects}},
	volume = {2030},
	doi = {10.1007/3-540-45315-6_1},
	booktitle = {Foundations of {Software} {Science} and {Computation} {Structures}},
	publisher = {Springer Berlin Heidelberg},
	author = {Plotkin, Gordon and Power, John},
	editor = {Honsell, Furio and Miculan, Marino},
	year = {2001}
}

The categorical semantics of algebraic effects was presented at an MFPS 2001 article, whose journal version was published in 2003 in Applied Categorical Structures:

Plotkin, Gordon, and John Power. 2001. ‘Semantics for Algebraic Operations’. Electronic Notes in Theoretical Computer Science 45: 332–45. https://doi.org/10.1016/S1571-0661(04)80970-8. pdf

@article{plotkin_2001,
	title = {Semantics for {Algebraic} {Operations}},
	volume = {45},
	issn = {15710661},
	doi = {10.1016/S1571-0661(04)80970-8},
	journal = {Electronic Notes in Theoretical Computer Science},
	author = {Plotkin, Gordon and Power, John},
	year = {2001},
	pages = {332--345}
}

Plotkin, Gordon, and John Power. 2003. ‘Algebraic Operations and Generic Effects’. Applied Categorical Structures 11 (1): 69–94. https://doi.org/10.1023/A:1023064908962. pdf

@article{plotkin_2003,
	title = {Algebraic operations and generic effects},
	volume = {11},
	doi = {10.1023/A:1023064908962},
	number = {1},
	journal = {Applied Categorical Structures},
	author = {Plotkin, Gordon and Power, John},
	year = {2003},
	pages = {69--94}
}

The connection to monads in an article at FoSSaCS 2002, which showed that a number of commonly-used monads are in fact free for an appropriate algebraic theory:

Plotkin, Gordon, and John Power. 2002. ‘Notions of Computation Determine Monads’. In Foundations of Software Science and Computation Structures. FoSSaCS 2002, edited by M. Nielsen and U. Engberg, 2303:342–56. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45931-6_24. pdf

@inproceedings{plotkin_2002,
	series = {Lecture {Notes} in {Computer} {Science}},
	title = {Notions of {Computation} {Determine} {Monads}},
	volume = {2303},
	doi = {10.1007/3-540-45931-6_24},
	booktitle = {Foundations of {Software} {Science} and {Computation} {Structures}. {FoSSaCS} 2002},
	publisher = {Springer, Berlin, Heidelberg},
	author = {Plotkin, Gordon and Power, John},
	editor = {Nielsen, M. and Engberg, U.},
	year = {2002},
	pages = {342--356}
}

An overview of the state of the art by 2004 is given in

Plotkin, Gordon, and John Power. 2004. ‘Computational Effects and Operations: An Overview’. Electronic Notes in Theoretical Computer Science 73: 149–63. https://doi.org/10.1016/j.entcs.2004.08.008.

@article{plotkin_2004,
	title = {Computational {Effects} and {Operations}: {An} {Overview}},
	volume = {73},
	doi = {10.1016/j.entcs.2004.08.008},
	journal = {Electronic Notes in Theoretical Computer Science},
	author = {Plotkin, Gordon and Power, John},
	year = {2004},
	pages = {149--163}
}