[rixtox]

Does implementing algebraic effects requires stack switching support? If so, I wonder what runtime cost we must pay when heavily using algebraic effects. Is there any empirical study on the performance of algebraic effects implementations?

[kcsrk]

Not necessarily. You can implement them using a monad. See https://dl.acm.org/doi/10.1145/2804302.2804319. That said, in GHC Haskell the implementation on top of stack switching seems to outperform other implementation strategies. See https://github.com/ghc-proposals/ghc-proposals/blob/master/p....

In OCaml 5, we’ve made it quite fast: https://kcsrk.info/papers/drafts/retro-concurrency.pdf. For us, the goal is to implement concurrent programming, for which a stack switching implementation works well. If you use OCaml effect handlers to implement state effect, it is going to be slower than using mutable state directly. And that’s fine. We’re not aiming to simulate all effects using effect handlers, only non-local control flow primitives like concurrency, generators, etc.

[hansvm]

Kind of.

Suppose one of your effects is `read()`, and you want to be able to drop in an asynchronous implementation. Then you'll either require something equivalent to stack switching or you'll require one of the restrictions to asynchronicity allowing you to get away without stack shenanigans -- practical algorithms usually start requiring stack switching though.

You can get a lot of mileage out of algebraic effects without allowing such ideas though. Language constructs like allocation, logging, prng, database sessions, authorization, deteterministic multithreaded prng, etc, are all fairly naturally described as functions+data you would like to have in scope (runtime scope -- foo() called bar() -- as opposed to lexicographic scope), potentially refining or changing them for child scopes. That's a weaker effect system than you would get with the normal AE languages, but there are enough concepts you feasibly might want to build on such a system that it's still potentially worthwhile.