5
$\begingroup$

I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic effects and handlers, people mention effects that are not algebraic, like backtracking. How does one can tell an algebraic effect apart from a non-algebraic one?

$\endgroup$
  • $\begingroup$ Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims? $\endgroup$ – Andrej Bauer Feb 24 at 18:32
  • $\begingroup$ I was sloppy when writing that. Pretnar's An Introduction to Algebraic Effects and Handlers (on page 14) says backtracking do not respect equations and cannot receive a homomorphic interpretation, so I assumed it wasn't algebraic. Also, given that continuations aren't algebraic, I also assumed asynchrony would not be algebraic as well. Conversation "on the streets" about it often lead to "yeah, but the interesting effects aren't algebraic", hence my question. $\endgroup$ – Jesper Dahl Feb 25 at 15:16
  • $\begingroup$ Pretnar's point is that the expected equations are not satisfied. This means that by removing them we will get an algebraic effect. $\endgroup$ – Andrej Bauer Feb 25 at 19:11
  • 1
    $\begingroup$ Asynchronous execution is algebraic because the continuations are delimited, like in the example of multi-threading from the "Programming with algebraic effects and handlers". So let it be known in the street that perhaps one should think first. $\endgroup$ – Andrej Bauer Feb 25 at 19:12
  • $\begingroup$ One possible thing to note is that some of the things that are categorized as not algebraic in some papers on effects actually are algebraic in the sense that you can make sense of the operations in a (countable enriched) Lawvere theory. The example I know of is catching exceptions. So sometimes the classification is not made on a completely rigorous basis (perhaps because it predates the formalism). $\endgroup$ – Dan Doel Mar 9 at 0:52
7
$\begingroup$

The general answer which you do not want to hear is: an effect is algebraic if it can be described using operations and equations. The question is a bit open-ended and gives no hint as to what you're expecting, so perhaps you deserve such a useless answer.

Nevertheless, it's still good to know some typical examples, as they help you develop a feeling for things:

  1. Continuations are not algebraic. That's important because there are effects that let you encode continuations, and so those are not aglebraic either. (But be careful about the meaning of "encode").

  2. Delimited continuations are algebraic, see Section 6.11 of "Programming with algebraic effects and handlers". Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.

  3. If your effect looks like you're passing around state of some sort, then it's likely algebraic.

  4. Nondeterministic choice, search, etc., are typically algebraic.

  5. Exception-like effects are algebraic (transactions of various sorts are included).

  6. Anything that looks like communication (I/O, reader monad) is algebraic.

  7. Probabilistic programming is algebraic.

Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.

$\endgroup$
  • $\begingroup$ I updated the delimited continuations example to point out that threads and thread-like effects are algebraic. $\endgroup$ – Andrej Bauer Feb 25 at 19:14
  • $\begingroup$ What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation. $\endgroup$ – Max New Feb 26 at 12:31
  • $\begingroup$ Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had resources which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion. $\endgroup$ – Andrej Bauer Feb 26 at 14:03
  • $\begingroup$ I think a good answer to this question would be to say how to show effects are not algebraic. I think continuations are not because of size issues, but are there any other examples? $\endgroup$ – Max New Feb 26 at 20:32
  • $\begingroup$ What do you mean by "show effects"? $\endgroup$ – Jesper Dahl Feb 27 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.