4 ms·

(2019) It’s worth clarifying that for the most part, this article just discusses plain effects, ie. "reified side effects" or "resumable exceptions". Algebraic

by Sharlin 5mo ago

(2019) It’s worth clarifying that for the most part, this article just discusses plain effects, ie. "reified side effects" or "resumable exceptions". Algebraic effects are about the composition (ie. algebra) of effects, exactly like algebraic data types are about the composition of types. This part is generally not meaningful in an untyped language like Javascript because effects are all YOLO and you never know what’s going to happen, what effects a function might throw, or whether there’s any handler up-stack to catch your effect.

tome 5mo ago
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?
- matt_kantor 5mo ago
  I'm no expert, but perhaps https://arxiv.org/abs/2302.01415 https://arxiv.org/abs/2302.01415 (especially section 2.2, "Non-Algebraic Effects") will help.
  - tome 5mo ago
    Thanks. It says > Algebraic eﬀects & handlers use a free monad and an interpreter to separate the syntax of eﬀects 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.
- sodic 5mo ago
  This is my favorite one, short and understandable: https://philipnilsson.github.io/Badness10k/posts/2017-05-07-escaping-hell-with-monads.html https://philipnilsson.github.io/Badness10k/posts/2017-05-07-... 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.
  - tome 5mo ago
    Thanks, I definitely feel like I understand monads and their benefits, and even "effects", but I'm not sure what's "algebraic" in "algebraic effects".
    - Sharlin 5mo ago
      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.
      - tome 5mo ago
        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".
        noelwelsh 5mo ago
        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
- hutao 5mo ago
  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 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: lookup(ℓ,λs.lookup(ℓ,λt.κst)) = lookup(ℓ,λs.κss) lookup(ℓ,λs.update((ℓ,s),κ)) = κ() update((ℓ,s),λ_.lookup(ℓ,κ)) = update((ℓ,s),λ_.κs) update((ℓ,s),λ_.update((ℓ,t),κ)) = update((ℓ,t),κ) 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_possible_to_make_a_generic_handler_for_the/czs9ch8/ 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.
  - tome 5mo ago
    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.
    - hutao 5mo ago
      This is the gist of Andrej Bauer's paper: - 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.

by Sharlin 5mo ago

tome 5mo ago

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?

matt_kantor 5mo ago
I'm no expert, but perhaps https://arxiv.org/abs/2302.01415 https://arxiv.org/abs/2302.01415 (especially section 2.2, "Non-Algebraic Effects") will help.
- tome 5mo ago
  Thanks. It says > Algebraic eﬀects & handlers use a free monad and an interpreter to separate the syntax of eﬀects 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.
sodic 5mo ago
This is my favorite one, short and understandable: https://philipnilsson.github.io/Badness10k/posts/2017-05-07-escaping-hell-with-monads.html https://philipnilsson.github.io/Badness10k/posts/2017-05-07-... 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.
- tome 5mo ago
  Thanks, I definitely feel like I understand monads and their benefits, and even "effects", but I'm not sure what's "algebraic" in "algebraic effects".
  - Sharlin 5mo ago
    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.
    - tome 5mo ago
      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".
      - noelwelsh 5mo ago
        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
hutao 5mo ago
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 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: lookup(ℓ,λs.lookup(ℓ,λt.κst)) = lookup(ℓ,λs.κss) lookup(ℓ,λs.update((ℓ,s),κ)) = κ() update((ℓ,s),λ_.lookup(ℓ,κ)) = update((ℓ,s),λ_.κs) update((ℓ,s),λ_.update((ℓ,t),κ)) = update((ℓ,t),κ) 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_possible_to_make_a_generic_handler_for_the/czs9ch8/ 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.
- tome 5mo ago
  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.
  - hutao 5mo ago
    This is the gist of Andrej Bauer's paper: - 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.