Generic Effects

The notion of generic effects is encountered in Plotkin and Power's theory of algebraic effects.

The concept is best explained by example. It is possible to add the effect of nondeterminism to a functional language by adding a construct

\frac{
  \Gamma \vdash M : \sigma
  \quad
  \Gamma \vdash N : \sigma
}{
  \Gamma \vdash M \sqcup_\sigma N : \sigma
}

at every type \sigma. The operational semantics of this is nondeterministic, in the sense that M \sqcup_\sigma N can reduce to either M or N, effectively making a nondeterministic choice. This is the style of algebraic operations.

However, if we also have a type \textsf{Bool} of Boolean values, the same effect can be introduced by a single constant

\frac{}{
  \Gamma \vdash \textbf{arb} : \textsf{Bool}
}

which arbitrarily reduces to either \textbf{true} or \textbf{false}. This is the style of generic effects.

If we have nondeterminism as an algebraic effect (\sqcup_\sigma) then we can define the corresponding generic effect by

\textbf{arb} = \textbf{true} \sqcup_\textsf{Bool} \textbf{false}

Vice versa, if we have the generic effect we can define the algebraic operation by

M \sqcup_\sigma N = \textbf{if arb then } M \textbf{ else } N

Plotkin and Power 2003 have shown that, for an appropriate general definition of algebraic effect, the two presentations coincide.

References

• The notion of algebraic effect was introduced in a paper presented at MFPS 2001 (17th):

@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}
}

• There is a journal version of the same paper:

@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}
}