It's my belief that all effects can be done with dependency injection in some form, at least, I'm not familiar with ones that can't. Even arbitrary delimited continuations can be implemented by injecting a reference to the continuation prompt on the stack.
That's very interesting, thanks! It gave me a brainwave and I wondered I could implement that in Bluefin. I'm pretty sure Bluefin's Request[1] is a second class stackful coroutine, and sure enough it turns out to be possible, so I'm pleased about that.
-- ghci> example
-- Hello
-- World
-- Timed out
example = runEff $ \io -> awaitYield (receiver io) sender
receiver ::
(e1 <: es, e2 <: es) =>
IOE e1 ->
Await String e2 ->
Eff es ()
receiver io a = do
r1 <- await a
effIO io (putStrLn r1)
r2 <- await a
effIO io (putStrLn r2)
mr3 <- timeout io 0 (await a)
effIO io $ case mr3 of
Nothing -> putStrLn "Timed out"
Just r3 -> putStrLn r3
sender ::
e1 <: es =>
Yield String e1 ->
Eff es ()
sender y = do
yield y "Hello"
yield y "World"
yield y "More"
timeout ::
e1 <: es =>
IOE e1 ->
Int ->
Eff es r ->
Eff es (Maybe r)
timeout io t m = withEffToIO
(\effToIO -> System.Timeout.timeout t (effToIO (\_ -> useImpl m)))
io
> I dislike the concept of having a second, hidden, control flow that might get sprung up upon function callers, because it has side effects buried in the implementation of a callee that are not defined in the parameters or the returns
You might like my capability-based effect system for Haskell, Bluefin[1], then. If a Bluefin effectful function throws you can see it in the type system. If you want to have the capability to throw, you need to pass in an argument of type Throw. For example here "workWithThrow" can only throw an exception because it is passed the Throw capability.
workWithThrow ::
(e1 :> es) =>
Throw String e1 ->
Int ->
Int ->
Eff es Int
workWithThrow t x y = do
let result = x + y
when (result > 10) $ do
throw t "Too big"
pure result
-- ghci> example
-- Left "Too big"
example :: Either String Int
example = runPureEff $ try $ \t -> do
workWithThrow t 5 7
Not sure why people are saying "you can't" when it seems to me the whole point of algebraic effects that you can. You can define g so that it has no ability to do "general IO", all it can do is yield log messages. Then f can call g in a way that turns the log messages into writes to stdout. For example, here's how you would do it in Bluefin:
type Log = Yield String
-- workWithLogging cannot do arbitrary IO!
-- All it can do is yield log messages, which
-- must be processed elsewhere.
workWithLogging ::
(e1 :> es) =>
Log e1 ->
Int ->
Int ->
Eff es Int
workWithLogging l x y = do
yield l ("x was " <> show x)
yield l ("y was " <> show y)
let result = x + y
yield l ("result was " <> show result)
pure result
-- ghci> example
-- x was 5
-- y was 7
-- result was 12
-- 12
example :: IO Int
example = runEff $ \io -> do
-- forEach determines how each log message
-- should be handled.
forEach
(\l-> workWithLogging l 5 7)
(\logMsg -> effIO io (putStrLn logMsg))
I've never understood what's meant by "algebraic" in that sense, or what this algebra of combining effect is. Could you say more, or maybe share a link to a useful reference?
Here is an article by Andrej Bauer answering the exact question, "What is algebraic about algebraic effects and handlers?": https://arxiv.org/abs/1807.05923v2
Contrary to the claim from the comment you are replying to, according to Andrej Bauer, "algebraic" does not refer to the composition of different algebraic effects via composing their handlers.
When you see "algebra," think "algebraic structure," i.e., a set of operations and a set of equational laws on those operations.
An algebraic effect consists of a set of effectful operations. In that sense, each algebraic effect (reader, state, etc.) defines its own algebraic structure. In theory, the operations of an effect should also be related to each other by laws. Here is an example for the state effect from Andrej Bauer's paper:
Therefore, the state effect has an algebraic structure.
However, monads that cannot be defined in this equational style cannot be translated to algebraic effects. An example is the continuation monad: https://old.reddit.com/r/haskell/comments/44q2xr/is_it_possi... (I think you are involved in the Reddit comment chain that I'm linking to...)
AFAIK, another example is the "exception" monad, because the way that you interact with it is through the handler itself. I once saw a thread on r/Haskell discussing this, but can't find it.
Ah, thanks, maybe this holds a clue! (Clearly I have been interested in getting to the bottom of this for a while.)
So maybe an "algebraic effect" is one that's isomorphic to a free monad of a functor that itself is an algebraic data type. That seems to give an unambiguous specification for what it means to handle an effect (a natural transformation) and to take a "free product" of effects (sum the functors).
On the other hand I think it would mean that things like Future and general IO wouldn't be algebraic effects.
- An algebraic theory consists of a "signature" (specifying a set of operation symbols with their arities) and a set of equations about those operations. An algebraic theory is purely syntactic, and does not give meaning to the operations or equations.
- An interpretation of an algebraic theory maps each operation symbol to a concrete mathematical object. It maps syntax to semantics.
- A model is an interpretation in which the algebraic theory's equations hold.
- A free model of an algebraic theory, generated by a set, is basically a model that can be mapped to any other model of the theory generated by the set.
So, an example of an algebraic theory is a group (as in the algebraic structure itself, not the various instances of a group). Its signature consists of the binary operation of combining, the unary operation of inverse, and the nullary operation of identity. The models of a group are its instances, such as the integers under additions and subtraction, or permutation functions on a set. The integers are the free group (that is, the free model of the group) generated by the set {1}.
Algebraic theories can also describe the effects of a programming language (e.g. reader, writer, or state). The free model of an algebraic effect is given by the syntax trees describing its effectful computations. Effect handlers are maps from syntax trees, transforming computations into other computations within the programming language.
> On the other hand I think it would mean that things like Future and general IO wouldn't be algebraic effects.
For what it's worth, Example 2.3 in the paper states that IO is an algebraic effect, albeit one with no equations. What might be confusing is that the handler of the IO effect cannot have the level of concreteness to actually implement the IO operations. Effect handlers only map computations to computations within the "pure" programming language. From the paper:
> What we still lack is a mathematical model of computational effects at the level of the external environment in which the program runs. There is always a barrier between the program and its external environment, be it a virtual machine, the operating system, or the underlying hardware. The actual computational effects cross the barrier, and cannot be modeled as handlers. A handler gets access to the continuation, but when a real computational effects happens, the continuation is not available. If it were, then after having launched missiles, the program could change its mind, restart the continuation, and establish world peace.
> Example 2.3 in the paper states that IO is an algebraic effect
Oh, I meant what Haskell calls `IO`, which includes the ability to launch threads, use delimited continuation primops, abort the program, communicate with the FFI, and all sorts of other things that I would guess don't have an algebraic presentation.
I show it when I teach Haskell, and it's what usually makes it "click" for students. Probably because motivating examples are in normal imperative pseudocode.
Your linked article hints at the advantages of using Monads and therefor ADTs (Algebraic Data Types), and does it really well.
The wiki entry on effect systems[0] tells me that a focus of an effect system is something different from a focus of monads. "The term algebraic effect follows from the type system", where an effect system is effectively a type and effect system. It links to Monadic encapsulation of effects[1] and mentions the runST monad when it mentions support in Haskell, as that one seem to "simulate a type and effect system".
One thing this page makes clear is that do-syntax could mean all kinds of things, which seems like a disadvantage for readability. Assuming you know the specialized syntax, elvis operators looking different from async code or a nested for loop seems like an advantage? The performance implications are entirely different.
The problem with monads is their composition. Ie. questions like how is the do notation supposed to work if I want to return:
* an Option<Async> or Async<Option>?
* both an Option and an Async (a product, or tuple type)?
* either an Option or an Async (a sum, or tagged union type)?
Monad transformers can be written for wrapping monads into other monads (as a simple example, an Option is equivalent a List with exactly zero or one elements), but they're something of an ad hoc solution and do not generalize well.
This is fundamentally an issue similar to the "function color" problem, or the fact that exceptions in most languages are a limited, ad hoc effect system and do not compose well. Java gave checked exceptions a bad name largely because of their lack of compositionality, but it's more that the particular implementation is poor.
To be fair, that was in 1994 and nobody had worked out these things yet even in the academia. Algebraic effects are the attempt to do just that.
Right, I understand the history (although I'm not sure I'd say that exception don't compose well) and I understand that "algebraic effects" are an attempt at something better. But I don't understand whether they're something that can be precisely defined or just informal terminology for "a better sort thing for dealing with effects".
You can precisely define any particular model, but not all work in the area shares the same model. I think you know about the capability-passing model, which is quite different to the algebraic effects (e.g. row types) models.
The general ideas are:
* effects are handled by handlers (called capabilities in the capability-passing model)
* function signatures describe the effects that are used
* effectful code is written in direct style, not monadic style
OK, and in the general case a handler allows its body to "perform" an action, and when the action is performed it has the ability to "respond" to it in (in some cases) a very flexible way, running it never, or multiple times, or in a modified environment, or possibly even passing it out of the scope of the handler entirely.
> function signatures describe the effects that are used
Would you say this is not possible in an untyped language then?
> effectful code is written in direct style, not monadic style
> OK, and in the general case a handler allows its body to "perform" an action...
Yes, although not all systems allow this, as implementing full continuations is involved and can hurt performance.
> Would you say this is not possible in an untyped language then?
You can definitely implement the ideas of algebraic effects in an untyped language, but you lose one of the benefits.
> I don't understand the distinction here
Monadic code is code where the order of evaluation is specified by bind / flatMap. Direct-style just uses the language's built-in control flow. See https://noelwelsh.com/posts/direct-style/ for more
> Algebraic effects & handlers use a free monad and an interpreter to separate the syntax of effects from their semantics
I'm pretty sure not everybody who works with algebraic effects would say they have to be based on a free monad, so I'm skeptical how definitive this definition is.
I was completely baffled by "algebraic effects" for years. They looked far too confusing for me to want to spend my time on them, and took the "Don’t feel like you have to [get curious about them]" approach.
But then at some point it struck me: underlying all these effect systems is just passing stuff in. So I developed my own effect system for Haskell, Bluefin[1], based on capabilities, which means the "capability to perform some effect" is represented by just passing stuff in (that is, a function can do some effect as long as it has been passed the capability to do it).
From this point of view it's hard to understand the excitement over "resume with" and "the part you can’t do with try / catch. It lets us jump back to where we performed the effect, and pass something back to it from the handler". Programming languages have had that feature since forever: a "resumable exception" is a "function call". A dynamically chosen "resumable exception" is the call of a dynamically chosen function, i.e. the argument to a higher order function.
So I don't know why people love the complexity around "algebraic effects". Maybe the mystique has a certain allure. But if you want the most straightforward possible approach I can recommend you try out Bluefin. I'm happy to answer questions on the issue tracker[2].
(Caveat: Bluefin is able to simplify things dramatically by dropping support for "multi-shot" continuations. But mostly you don't want multi-shot continuations.)
A real effect system allows you to do things like NOT continue execution after using the effect (like the error effect does - if you "implement" this by using Exceptions, you're not using effects at all, just using Exceptions with extra steps) or only continuing it after some asynchronous work happens (the Future effect), or even "continue" execution several times. That just cannot be done with "just passing stuff in". You still don't seem to have understood effects.
Thanks for your response. Perhaps I'm missing some fundamental things. Could you help?
> A real effect system allows you to do things like NOT continue execution after using the effect
Right, Bluefin's Request allows you to do that too. For example here is an example of handling the request by continuing or not, depending on what the value yielded to the Request is.
example :: Either String ()
example = runPureEff $ try $ \ex -> do
forEach
( \r -> do
request r True
request r True
request r False
request r True
request r True
)
( \case
True -> pure ()
False -> throw ex "Stopped"
)
> if you "implement" this by using Exceptions, you're not using effects at all, just using Exceptions with extra steps
Not sure I follow that. Above you can see I used an exception (Bluefin's Throw capability), but I couldn't have used only an exception because that would have aborted unconditionally. What am I missing here, that makes "using Exceptions" "not using effects at all"?
> only continuing it after some asynchronous work happens (the Future effect)
I'm not really sure what "a Future effect" is, but I don't see how it's not something that can be run as a function call, at least in Haskell.
> or even "continue" execution several times
Right, these are the multishot continuations which Bluefin doesn't support. I haven't discovered many particularly compelling use cases for multishot continuations but would be very interested in finding some. The developer of the Kyo effect system for Scala, Flavio Brasil, suggested parsing, with multiple parse results, which makes sense.
I'm also not entirely sure Bluefin couldn't simulate common use cases of multishot continuations with threads, but I haven't thought about it very hard.
> You still don't seem to have understood effects.
Possibly true, and part of my puzzlement! I'm always happy to try to improve my understanding. Can you help me see what I've missed?
I think the parent may be getting at the continuation aspect of effects? Effect systems make the stack a first class object you can reuse, I think a standard example is implementing a scheduler. I'm not familiar with your Bluefin library so maybe it already handles this:
effect Sched =
yield : unit -> unit
fork : (unit -> unit) -> unit
end
let mut run_queue = []
let enqueue t = run_queue := List.concat run_queue [t]
let dequeue () =
match run_queue with
| [] -> ()
| t :: rest ->
run_queue := rest;
t ()
let rec spawn task =
handle
task ()
with
| return _ -> dequeue ()
| yield () k ->
enqueue (fn () -> resume k ());
dequeue ()
| fork f k ->
enqueue (fn () -> resume k ());
spawn f
let run main = spawn main
let worker name steps =
let rec loop i =
if i > steps do ()
else do
print $"{name}: step {i}";
perform yield ();
loop (i + 1)
end
in
loop 1
let () =
run (fn () ->
print "main: starting";
perform fork (fn () -> worker "A" 3);
perform fork (fn () -> worker "B" 3);
print "main: forked workers, now yielding";
perform yield ();
print "main: done")
Ah yes, OK, I missed the point that the timeout is applied to the entire continuation, not just the part of the computation until the next await. Bluefin can't currently do that. I think I could make it do that, using the same implementation strategy as awaitYield (fork a thread, communicate through an MVar) but I wonder what the point is, given that Bluefin allows you to run the continuation at most once. Is the use case of "run the continuation in a modified environment (e.g. with a timeout)" really that compelling? Maybe it is! But I don't see it yet.
On the other hand, I don't see any difficulty with implementing a scheduler using Await/Yield. I don't think it needs access to the full continuation.
Equating "algebraic effects" with "continuations" is like saying "if" is just "goto" (which isn't even true, e.g., an if can turn into a cmov or whatever).
The only mystique around algebraic effects is the same mystique there is around monads. I don't know if people have started equating algebraic effects to burritos yet but that's a pretty good way to take something simple and turn it into something confusing.
> Equating "algebraic effects" with "continuations" is like saying "if" is just "goto"
Fair enough. But are you responding to something I said? I didn't make that equation.
> The only mystique around algebraic effects is the same mystique there is around monads. I don't know if people have started equating algebraic effects to burritos yet but that's a pretty good way to take something simple and turn it into something confusing.
Ah, are you saying that fundamentally there isn't really much to algebraic effects and they're much simpler than they're made out to be? If so then it perhaps we agree?
I don't think I said they're just continuations. In fact I'm trying to make the point that they're mostly just function calls (and I think in my career I've come across one case where I wanted something beyond function calls (for a constraint solver)). There are "multi-shot" continuations (whether you consider that interface or implementation I don't really mind), which have behaviour than function calls can't express, but I don't know of any algebraic effects beyond that.
What do you think algebraic effects are, if they're not continuations?
EDIT: Ah, based on your comment at https://news.ycombinator.com/item?id=48334737 you might say they're a feature of an intermediate language? So you might take a surface language and "compile to an intermediate language of lambda calculus + algebraic effects", without specifying how that intermediate language is implemented (because it may not even be implemented, per se).
They're really just a protocol. You can implement them in various ways. They will always be some sort of delimited continuations but a "function call" or continuation passing style or anything of the sort does not have to be involved at all.
For example, let us say I don't allow "multi-shot" continuations like in your library, and I'm implementing Algebraic Effects in my own interpreted language.
One way I can implement effects and handlers is to have a handlers get registered in a stack, then when an effect is triggered, save the IP and current stackframe, search for the right handler and jump to it. "resume" then just resets the stackframe, pushes a value into the stack, and sets the saved IP.
(Only saw your edit after posting, sorry, but yes)
Thanks, that clarifies where you're coming from. Is it possible to specify this protocol somehow, by defining an interface for it? Or by extending lambda calculus with the bits it needs?
(Maybe that's what the Koka folks do in their papers, and if so feel free to say, "yeah read their papers").
I'm thinking a less formally than that. Protocol in a very layman-y "perform is supposed to do this, resume is supposed to do this".
For example, Koka compiles handlers differently depending if they do multi-shot continuations or not. It can do this because all that matters is "perform is supposed to do this, resume is supposed to do this", not what they turn into (same as "if" turning into "cmov" in certain cases). I think it uses a continuation-passing style sort of implementation, but I can't quite remember.
Daan's libhandler implements effects for C in an entirely different manner. It captures the stack much like my example or a stackful coroutine library would.
I'm sure there a formal definitions in both the koka papers and the libhandler paper, but I just skim that stuff ;)
Yeah, there's three things you're supposed to implement: try/handle, perform, and resume. The names can vary (e.g., perform is often called "raise" or "do"). They have well defined interactions.
I don't actually know what the original paper describing what algebraic effects are supposed to do is, I just know them informally from Koka, Effekt, etc.
Interesting, then I wonder if anyone has distinguished them from continuation "protocols" such as shift/reset and prompt/control. Thanks!
Bringing it back to my original point, I guess I'd say that if you already have function calls, exceptions and threading built in to the language then you don't need perform/resume except in niche cases (multi-shot continuations being the only case I know of, but I don't even know of many applications of those).
It's debatable how much one is willing to describe historical solutions like MTL style to be a "good" solution to this problem (I explained the downsides in my talk "A History of Effect Systems"[1] at Zurihac 2025), but I certainly have no hesitation in describing my capability-based effect system Bluefin[2], as a good solution.
For the channels you describe above the type signature would look like this
Six different capabilities that give you access to six different channels of IO. A "Yield" to which you yield strings to stdout, an "Await" from which you can await strings from stdin, a "Yield" to which you yield log messages, and three abstract effects that allow you to do network, database and file system operations (abstract because I'm not sure exactly how you want them defined, but there's an example of the implementation of a file system effect at https://hackage-content.haskell.org/package/bluefin-0.6.0.0/...).
No problem with combining or untangling monads whatsoever. This is the natural conclusion of galaxyLogic's point: instead of dividing your program into two parts (IO and not IO) you divide it into six parts (or maybe 2^6 parts?) according to which fine grained effects you have in scope.
If you (or anyone) has any questions about Bluefin I'm happy to help. Please feel free to ask here or on the issue tracker[3].
Interesting. Those channels seem to all manage side-effects that persist after program execution. What about state-changes that are made and persist into the memory of the running program? Or is there any need for that?
Yes, there's a need for it, and Bluefin provides Modify which allows you to modify a reference to a value in a way that is not observable outside the scope of the capability.
An HN user time-transported in from 15 years ago would find it incomprehensible that there there are only two sceptical responses (both flag killed) on a post about a message from the supreme leader of a nearly 1.5 billion strong religion. Times have truly changed.
Times have changed in a lot of dimensions. To name 2: 1) we have an AI thing now, and 2) the pope is American and more trustworthy than all of our current top politicians of both parties.
It's not like people are longing for times of papal authority, they're just looking for anyone at all with common sense.
15 years ago it was Pope Benedict, who was a pretty different figure. I can speak only for myself, but I would have had more cynicism about him than I would for Francis or Leo.
Please don't post grandiose conspiracy theories like this on HN. All kinds of criticism of AI is posted all the time on HN. Comments are downvoted or flagged if users disagree with them or if they break the guidelines. If you see anything that's flagged unfairly, you can vouch for it or email us (hn@ycombinator.com) to point it out.
the only other haskell compiler is MicroHs. and it has no pragmas. it just enables the whole thing.
this is not a real problem in practice. even without the GHC20XX stuff (which is nice). it feels like a problem a novice would point at (and be totally wrong)
sorry your favorite language doesn't let you import language features according to your needs. half of them have trade-offs! like -XOverloadedLists. Useful, but hurts inference. Maybe you don't want it globally. But maybe in a few modules, it's perfect. {-# LANGUAGE OverloadedLists -#} is the answer that no other mainstream lang has.
-XPolyKinds is another great example of that sort of extension.
Preferably there would be more implementation. But if they only implement the "standard" language, it will be missing a lot of things. That is the point!
It's not Haskell anymore. It's Glasgow Haskell. It's its own language at this point.
reply