I've been trying to learn more about algebraic effects and I want to use them for practical things. However it has been hard because although I understand at some level the theoretic reasons for using them, the actual day-to-day experience of using them is something else. I think the most popular effect library for a mainstream language is effect.ts, it is a nice library and it also uses coroutines but using it in some practical way isn't actually productive. I think a lot in the functional programming community get stuck on the f . g trap. As if function composition is the one thing you would want to do all day (even though you can), from a super practicle perspective it is often very little work to also write f' and g'.
If anyone is interested, we are leveraging delimited continuations as the foundational paradigm for structured concurrency and async flow control in the browser.
If you check out the linked paper you'll see the title is "One-shot Algebraic Effects as Coroutines" - the keyword being "one-shot".
In general every Monad can be expressed "interpreting" the free monad. This relaxes the "one-shot" restriction, and can be implemented using delimited control. One-shot means faster performance though and is still useful for many things - and that can be implemented using coroutines.
If you acquire some understanding of what this means then you'll have a very good idea about the expressive power of what you can use coroutines (with nothing more) for, so it's very interesting.
It's been a while since I was steeped enough in this to answer comprehensively, but per memory, up to performance concerns, they're equivalent in inductive settings.
Haskell ends up being a bad place to talk about this (or a great place, depending on your goals) because due to laziness you get to write a lot of structures which look inductive but end up being able to express coinductive structures.
From memory and intuition, if you're working in a strict language (or better yet, something like Agda where the distinction becomes very sharp) then you end up finding that continuations make for good coinductive "free" structures and the free monad (and its ilk) make for good inductive free structures.
The distinction between inductive and coinductive types is fairly subtle and hard to see in most languages where those distinctions are blurred, but broadly you can think of inductive structures as ones that are, in principle, finite and coinductive structures as being those which may be, in principle, infinite.
For example, a linked list is inductive. If you're looking at one cons cell of it you can't prove that, you may have to chase pointers for longer than your patience allows, but at least in principle there is an end. A stream is coinductive, because it instead suggests a generative process.
In a sense, inductive types are "naturally strict" whereas co-inductive types are "naturally lazy". Though there are some types, such as products/tuples and arrays, that come in both strict and lazy varieties. Ultimately, this would allow one to equally account for both strict and lazy evaluation in a very natural way - quite unlike languages like ML or Haskell, where only one form is natural and idiomatic whereas the other has to be added as an afterthought.
I was playing with Haskell years ago and remembered a cheap trick. Just make a typeclass with all the IO ops you want and also make it a monad. You now have your own custom IO monad with only the bits you want to “give access to”. It is easier to understand than free
monads (which I never truly grokked but could happily copy/paste adapt and get em to work, sans understanding!)
I used to argue that lazy evaluation and coroutines were kind of two sides of the same coin. That in a way, partially evaluated haskell functions were equivalent to concurrent execution.
It's just the way we force the results to appear that differs.
IO Monad, if you squint, is extremely similar.
Continuations are a different way to "store a procedure and state" (like a partially evaluated function in a lazy sense).
It's not totally obvious, but it's a lot of fun to think about how these things are all related.
Exceptions are merely the record of the programmer's mistake. Essentially an error, except an error that could have been caught at compile time given a sufficiently advanced compiler.
Exception handlers provide a control flow for dealing with exceptions, which may include unwinding.
Exception handlers, while primarily intended for use by exceptions, are not necessarily restricted to exceptions. Often programmers use them to move other things around, most notably errors.
Most places where exceptions are thrown do not want to handle the case of resumption. Being usefully-resumable requires careful design at the site where the exception occurs, it isn’t something you can just throw in (no pun intended) as a general feature of all exceptions.
From an interface-contract point of view, exceptions model the case that an operation cannot complete normally. Any mechanism that enables an operation to complete normally after all upon encountering an error condition, should better be modeled with a separate language feature, for example with callbacks specific to the concrete error condition.
A handler for a resumable exception is passed down the call stack, rather than an object being passed up the call stack to the handler.
In some languages the handler can conditionally decide whether to resume back into or restart the block that raised the exception, or to cause an unwinding of the stack. In other languages, the action is fixed per exception type. (`try ... rescue`)
Comments
Not everything, but if by “coroutine” we mean a delimited continuation, then we get: exceptions, async/await, generators, and even the IO monad.
http://logic.cs.tsukuba.ac.jp/~sat/pdf/tfp2020.pdf
In short: algebraic effects.
Here’s a whole thesis on the cool things that can do done with this one simple trick: https://publikationen.uni-tuebingen.de/xmlui/bitstream/handl...
"Professors HATE HIM"
I've been trying to learn more about algebraic effects and I want to use them for practical things. However it has been hard because although I understand at some level the theoretic reasons for using them, the actual day-to-day experience of using them is something else. I think the most popular effect library for a mainstream language is effect.ts, it is a nice library and it also uses coroutines but using it in some practical way isn't actually productive. I think a lot in the functional programming community get stuck on the f . g trap. As if function composition is the one thing you would want to do all day (even though you can), from a super practicle perspective it is often very little work to also write f' and g'.
If you want to look at a very mature and used in industry effect system take a look at Cats Effect 3 in Scala.
If anyone is interested, we are leveraging delimited continuations as the foundational paradigm for structured concurrency and async flow control in the browser.
I gave a talk about it recently at Michigan Typescript: https://www.youtube.com/watch?si=Mok0J8Wp0Z-ahFrN&v=uRbqLGj_...
https://github.com/thefrontside/effection
https://github.com/neurosnap/starfx
With delimited continuations, we are able to express any async flow control, it is an incredibly powerful paradigm.
I get the first three but what is the connection to the IO monad?
I guess every monad can be expressed as the continuation monad; and that includes the IO monad?
If you check out the linked paper you'll see the title is "One-shot Algebraic Effects as Coroutines" - the keyword being "one-shot".
In general every Monad can be expressed "interpreting" the free monad. This relaxes the "one-shot" restriction, and can be implemented using delimited control. One-shot means faster performance though and is still useful for many things - and that can be implemented using coroutines.
If you acquire some understanding of what this means then you'll have a very good idea about the expressive power of what you can use coroutines (with nothing more) for, so it's very interesting.
I'm not quite sure if the free monad (or the 'freer' monad) can simulate the continuation monad? See https://stackoverflow.com/questions/25827271/how-can-the-con...
It's been a while since I was steeped enough in this to answer comprehensively, but per memory, up to performance concerns, they're equivalent in inductive settings.
Haskell ends up being a bad place to talk about this (or a great place, depending on your goals) because due to laziness you get to write a lot of structures which look inductive but end up being able to express coinductive structures.
From memory and intuition, if you're working in a strict language (or better yet, something like Agda where the distinction becomes very sharp) then you end up finding that continuations make for good coinductive "free" structures and the free monad (and its ilk) make for good inductive free structures.
The distinction between inductive and coinductive types is fairly subtle and hard to see in most languages where those distinctions are blurred, but broadly you can think of inductive structures as ones that are, in principle, finite and coinductive structures as being those which may be, in principle, infinite.
For example, a linked list is inductive. If you're looking at one cons cell of it you can't prove that, you may have to chase pointers for longer than your patience allows, but at least in principle there is an end. A stream is coinductive, because it instead suggests a generative process.
In a sense, inductive types are "naturally strict" whereas co-inductive types are "naturally lazy". Though there are some types, such as products/tuples and arrays, that come in both strict and lazy varieties. Ultimately, this would allow one to equally account for both strict and lazy evaluation in a very natural way - quite unlike languages like ML or Haskell, where only one form is natural and idiomatic whereas the other has to be added as an afterthought.
After reading that, I think freer can in fact encode the continuation monad.
https://www.reddit.com/r/haskell/comments/7yll62/comment/duh... also suggests that.
A quick scan of https://okmij.org/ftp/Haskell/extensible/more.pdf doesn't yield much one way or another.
I was playing with Haskell years ago and remembered a cheap trick. Just make a typeclass with all the IO ops you want and also make it a monad. You now have your own custom IO monad with only the bits you want to “give access to”. It is easier to understand than free monads (which I never truly grokked but could happily copy/paste adapt and get em to work, sans understanding!)
I used to argue that lazy evaluation and coroutines were kind of two sides of the same coin. That in a way, partially evaluated haskell functions were equivalent to concurrent execution.
It's just the way we force the results to appear that differs.
IO Monad, if you squint, is extremely similar.
Continuations are a different way to "store a procedure and state" (like a partially evaluated function in a lazy sense).
It's not totally obvious, but it's a lot of fun to think about how these things are all related.
I'd prefer to separate the concepts of "exception" and "unwinding".
In languages such as C++ and Java, raising an exception defaults to an unwinding only if not handled within the same function that raised it.
Then there are languages with resumable exceptions, and languages wherein unwinding is considered normal control flow as "shortcut returns".
Also, "exceptions" and "exception handlers".
Exceptions are merely the record of the programmer's mistake. Essentially an error, except an error that could have been caught at compile time given a sufficiently advanced compiler.
Exception handlers provide a control flow for dealing with exceptions, which may include unwinding.
Exception handlers, while primarily intended for use by exceptions, are not necessarily restricted to exceptions. Often programmers use them to move other things around, most notably errors.
Most places where exceptions are thrown do not want to handle the case of resumption. Being usefully-resumable requires careful design at the site where the exception occurs, it isn’t something you can just throw in (no pun intended) as a general feature of all exceptions.
From an interface-contract point of view, exceptions model the case that an operation cannot complete normally. Any mechanism that enables an operation to complete normally after all upon encountering an error condition, should better be modeled with a separate language feature, for example with callbacks specific to the concrete error condition.
Can you give an example of languages with resumable exceptions (just want to check it out)?
Common Lisp, Smalltalk, Ruby, Elixir, ...
A handler for a resumable exception is passed down the call stack, rather than an object being passed up the call stack to the handler. In some languages the handler can conditionally decide whether to resume back into or restart the block that raised the exception, or to cause an unwinding of the stack. In other languages, the action is fixed per exception type. (`try ... rescue`)
Racket
it is an infectious disease when not being careful, i.e. anything now is an algebraic effect.
Instead, define effects that are actually relevant to your particular app. DB reads/writes, I/O to third party systems.
Model those as data-driven effects. Keep the rest pure.