I would encourage anyone interested in this question to check out the paper "What is algebraic about algebraic effects and handlers?" (https://arxiv.org/abs/1807.05923) which is a write-up of the lecture series linked in the post above. I don't think the paper is too difficult to understand, but I know that if you're not familiar with the subject area it might be intimidating.
While I like the above blog post, I don't think that it will be very useful to people trying to understand algebraic effects. I see a lot of explainers like this one that shy away from some of the more gnarly-looking maths terms in an effort to appear more approachable, but as a result they can end up giving imprecise or vague definitions. When coupled with some subtle mistakes I think it can leave beginners more confused than helped (for instance, this author seems to conflate a few different notions of "composition", and they seem to think that the presence of equations makes an effect algebraic, which isn't really what the term "algebraic" is referring to in a technical sense).
The paper I linked above is not easy, and it would probably take at least a few hours to understand, but that's because it takes about that long to understand the material.
> they seem to think that the presence of equations makes an effect algebraic, which isn't really what the term "algebraic" is referring to in a technical sense
Author here! Open to learning. Can you expand on this? What is algebraic referring to in a technical sense?
Generally speaking, it means that the effect is derived from an algebraic theory (in a specific and structured way). While equations are definitely part of most theories, you can absolutely have a theory without equations, and furthermore you can define an effect with equations that isn't algebraic. The full definition of "algebraic theory" unfortunately doesn't really fit in a comment, but I did want to push back on the idea that "an effect becomes algebraic if you add equations to it".
In the effects literature, you often also see the definition that an operation (of an effect) is "algebraic" if the operation commutes with `>>=`. This definition is actually the same as the one above, just stated in a different way.
Trying to be helpful here, sorry if it doesn’t map to your field of which I am not familiar.
The _algebra_ you learn in school is elementary algebra, using variables.
In modern math, _algebra_ or _modern_ algebra or _abstract_algebra, is the study of structures over sets with defined operations on the elements of that set.
ADTs are an example of an algebraic structure, specifically called one that converts non-trivial semantic (runtime) properties to trivial ones (T/F).
This post is dealing with the structure in another way.
If you understand magmas, monoids, etc.. that can be helpful.
But the lay description I find useful is the algebra is what _arises_ from that defined set domain and operations.
The key point is studying the structure, which is the algebraic structure, or the algebra. It is basically what pops out, not what you start with, although that is flawed.
Almost all modern math will use that _modern_ meaning of algebra.
> In modern math, _algebra_ or _modern_ algebra or _abstract_algebra, is the study of structures over sets with defined operations on the elements of that set.
To add to/extend this there's a very famous quote from Poincaré that I think is helpful:
> Math is not the study of numbers, but the relationships between them.
I'd say more modern math has replaced the word "numbers" with the more abstract concept of "objects". This makes math truly the study of abstraction.
I actually wish we taught more of this math early on[0]. Children seem to be quick to grasp many of the fundamentals of important structures like groups, fields, and algebras. I find that many of these concepts have fundamentally shifted how I think and can be used on a daily basis, without the need of writing formulas or using formal semantics.
It's odd that it takes getting up upper division undergraduate education in math (or sometimes from neighboring fields) to learn what the field is even fundamentally about. It's akin to teaching people that programming by teaching people how to use a word editor. It's such a narrow aspect and no surprise so many are so fundamentally confused.
[0] I'm unconvinced the "new maths" programs were a complete failure. Just because we didn't get it right on the first attempt doesn't mean we should have thrown the baby out with the bath water.
Just to clarify, are you saying that you recommend that writeup over the lecture, or just linking the writeup for people who'd prefer it over watching a video?
I'm just recommending the writeup, but only because I haven't watched the lecture series myself (although I'm sure it's good, I've seen other lectures by the lecturer that were excellent). As far as I know, they cover basically the same material.
That was a very approachable explanation. Makes a lot of sense. Essentially by encoding the program algebraically you can prove that it is invariant under the action of the semi-lattice. Very neat! Maybe lean is worth a look.
That is interesting, I hadn't really given it much thought but my first instinct would be to assume the algebra in algebraic effect was not about having algebra like definitions but was in fact a direct reference to an algebra of a monad (though that might be the same thing).
At least the monad algeba gives a nice hint on how to view algbraic effects. Instead of using a monad so you can raise an exception
f :: a -> E b
You use an E-algebra (h :: E a -> a) instead to create a function that takes both an input and an exception handler to produce an output
g :: (a, E b -> b) -> b
The canonical example being something like
g x h = h (f x)
And a simple example of a handler being something like a default value
h :: Maybe a -> a
h Some x = x
h None = default_value
With the advantage of course that given a handler you can be much more flexible in how you handle exceptions and where. You're not limited to just returning early, you can handle the exception and carry on.
I started a thread last time Algebraic Datatypes were discussed that hit a similar vein. I assert most programmers know the middle school version of "algebra" and think of it in terms of what they can do with the values they are working with.
This is in contrast to doing operations on either the "types" or the "effects" that are happening during code. So, you have to show people what are the equivalent of + and * in types and effects to show them how these can be thought of algebraically.
I still think this would be easier if a type system was made that let you use + and * in defining something. It would give an obvious path to seeing how things relate to algebra. Would almost certainly make some things harder, of course. Maybe it would be a good worksheet asking questions about stuff?
The big underline, though, is getting people to realize what algebra there is is not on the values that your code represents. It is treating something else as the value for the algebra.
The "algebraic" in "algebraic effects" is not really related to algebraic data types, or sum or product types. I mean, I suppose they're related, since they both refer to algebra in the general sense, but there's no type-level algebra in a description of algebraic effects. (and, I suppose, you could do some type-level algebra with effects, like taking the "sum" of two effects, but again that's not what the "algebra" in "algebraic effects" is referring to)
> The big underline, though, is getting people to realize what algebra there is is not on the values that your code represents.
This is not correct. In the case of algebraic effects, the algebra is absolutely value-level.
I'm not sure I follow? For one, if algebraic isn't aiming at the ideas in an algebra, then they absolutely should be using a different name.
For two, though, the whole idea is how to compose the "value" of different effects together? My point is that the "value" is not the written value of a variable in ways that people are used to working with in their program. It will be a meta-value about some state represented by the program.
Is that not the case? If my use of the word "value" there is confusing things, I'm open to using some other words. My point is largely that the "value" of concern in effect systems is not the same as the value of a variable as people are used to reasoning. You are specifically meta-reasoning about the state of the program in ways that may not be represented by an explicit value of the program.
Not that that alone is unheard of. If you asked people to tell you the program counter of a function, they would largely get what you mean. Even if it is not something that is represented in the values of the program, itself.
> For one, if algebraic isn't aiming at the ideas in an algebra, then they absolutely should be using a different name.
Algebraic effects are certainly algebraic, they're just not directly related to algebraic data types. Both ideas are using "algebraic" at different levels, and I think trying to understand algebraic effects by referencing algebraic data types will be more confusing than helpful.
> My point is that the "value" is not the written value of a variable in ways that people are used to working with in their program.
I'm saying that (in algebraic effects) the "value" in question is precisely a normal variable that people are used to working with in programming languages. It is not a type-level value, which is the kind of value in question when we're talking about algebraic data types.
For example, if we take Groups (the algebra referenced in the post), we have a binary operation (that we might call +) along with a few other operations. We could write a piece of code like the following:
x = y + z
The "group" in question here could absolutely be an algebraic effect. And the line of code above could be implemented using algebraic effects, and interpreted using an algebraic effect handler. You don't even need types, if you didn't want them.
> For two, though, the whole idea is how to compose the "value" of different effects together?
No, not really.
Yes, algebraic effects compose well. But so do other effects systems and abstractions (applicatives, etc.). The fact that the effects compose is not what makes them algebraic, it's a consequence of it.
I don't think I can give a proper explanation in a comment, but I would point you to the paper I linked in another comment (https://arxiv.org/abs/1807.05923).
I'm not positive on what you are aiming at. I'd assume "algebraic effects" are to talk about performing algebra on the effects. That is, you are specifically going to talk about how different things combine effects, preferably in ways that honor + and * that we are used to.
If you are just pointing out that this is not, necessarily, "type" related. Agreed. Apologies if I mislead there. I was highlighting that algebraic data types has a similar problem. I did not mean to imply that these were the same topic.
My point is simply that there is no value in the program that says an effect has or has not completed. This is why I compare it to stepping through the program. The "line of code" that is active in executing code is not a first class value in your program. It is very much there, of course. But it is not a value of the program.
> I'd assume "algebraic effects" are to talk about performing algebra on the effects. That is, you are specifically going to talk about how different things combine effects
This is a misconception. The "algebra" does not refer to an algebra of effects, or combining effects in any way.
It's more like it's the other way around: "algebraic effects" are effects generated from algebras. These algebras are precisely-defined mathematical objects (like groups, monoids, etc.), so you have an "effect" that corresponds to monoids, an "effect" that corresponds to groups, and so on.
> My point is simply that there is no value in the program that says an effect has or has not completed. This is why I compare it to stepping through the program. The "line of code" that is active in executing code is not a first class value in your program.
I know: I'm trying to say that the "algebra" of "algebraic effects" do refer to first-class values. The + and * from other algebraic operations are the algebraic operations you might use for an algebraic effect.
I mean, the program snippet that I gave above contains 3 first-class values. If you write `x = y + z + 0`, or any other statement that uses the group algebra (or any other algebra), you can use algebraic effects to describe the semantics. The “first-class values” here are the x, y, and z: there’s nothing fancy going on. You can even use the group laws to show that the statement is equivalent to `x = y + z` (or whatever). It’s just normal, value-level algebra.
Right, but this is just explaining algebra. Which, I get that. Connect this to effects, for me. (And fair that just because I assert that I get it, I would wager I don't have as strong of a handle as I should have.)
My understanding for effects was more like "writes to stdout" and such. Probably better to have "opens a stream," "writes to an open stream," and "closes a stream." The algebra that I typically see is to show that you can combine some of these in such a way to either highlight a bug, or to help prevent them.
I got this because many effects typically go through hurdles to find a way to let you log to stderr without it polluting your entire effects system.
For an algebra, you have some operations and some equations. The group algebra has the + operation, and 0 and -, and all the relevant equations.
You can also form an algebra from logging. One operation might be “write to stdout”. And then a law might be `write x; write y = write (x ++ y)` where ++ is string concatenation.
This is the algebra, the algebra isn’t for combining effects at all. (Yes, you can combine algebraic effects, and the fact that they’re algebraic does help, but that’s for technical reasons that aren’t relevant)
The paper I linked in another comment has a good overview of the topic. It’s really not the kind of thing you can understand from reading a few comments, and the paper is well-written and goes over all of the main points from a pretty basic starting point.
I looked over the paper, but I confess I don't understand how it is helping. Would help a ton to have an example effect that didn't dive into distinguishing "Values", "Computations", "Value types," and "Computation types."
In fact, that it distinguishes values, computations, and the types of both seems more inline with my point? That what most "effect systems" are trying to capture are things that are not typically defined in programs?
So, again, give me some examples of effects and how you would model them. That will go a long way to demonstrate what you mean, here. Even better if you can show how this is already modeled in some code. (Note that I'm not trying to ask you to give this in a post. If you have some more things like that paper to look into, I don't mind looking there. I do plan on spending more time with the paper, already.)
Well, I gave the example of a logging effect above. In the post there’s also an example of a key-value store effect. What’s missing from these examples exactly?
All of these effects have simple operations (get and put for store, the `write` operation for the logging effect, etc.) These are all normal operations in your language: they just return values, like normal, and the laws that govern them are equivalent to the laws of any other algebra.
Elsewhere you mentioned Boolean algebra, and that people shouldn’t confuse that with algebraic effects: Boolean algebra can absolutely be another example of an algebraic effect! The operations are the Boolean operations (call them whatever you like, + or * or whatever), and the laws are the usual laws.
The point of algebraic effects is in noticing that traditional effects (logging, state, exceptions) can be thought of as algebraic the same way as Boolean algebras or monoids.
If you’re looking for an implementation, there are lots of implementations available in Haskell and other languages. However, to understand those you’d really already have to have a good understanding of the topic first, and then you’d also need to be comfortable with Haskell syntax (and probably free monads as well). I think that the paper really gives the best introduction to the topic, unfortunately there’s no way to simplify it much further.
I don't think I mentioned boolean algebra? I responded to someone else mentioning it. My problem there is still that you are going to be taught how to operate over boolean values using an algebraic construction. (Looking, I think that is accurate. Apologies if I am the one that brought it up somewhere, I don't remember that.)
Which, fair that may help some people. I just feel that this is akin to asking for people to understand algebraic effects using basic algebra from middle school. In basic algebra practices, you lean heavily on the basic operations applied to reals and see how to manipulate equations to discover both solutions and other statements about the equations. (Advanced students will eventually extend to imaginary numbers, but I don't think that changes this statement?)
Similarly, with algebraic datatypes, you learn what it means to combine the domains of types together. Since it is an algebra, you learn this in terms of the basic operations. Hence SumTypes and ProductTypes. My assertion there is that this is hard for people because they don't actually do the algebra on the domains. And, by "they" I largely mean the software that they write.
So, with algebraic effects, I would expect that this is about the ways that effects can be combined using basic algebra tools. But what is it that you are combining? In the types, you were combining domains for analysis. In effects, I'd expect that you are combining whatever it is an effect is. You seem to be saying that an effect is a standard value? But, that seems at odds with the definitions that distinguish "pure" functions from those that have "effects" being defined by things that they cause to happen.
It doesn't help that we typically talk about things that we want to preserve some property on. It isn't enough to say "writes to stderr", we want to know that it does so without clobbering someone else currently writing to the same spot. At the least, we probably want to know that it line buffers output in such a way that that is preserved.
So, when asking for an example, I'm hunting for something to meet me somewhere in the middle. Sucks that this commonly comes down to "writes to a logger."
I'm afraid I don't think I'm making progress here.
My overall point was that I felt your original comment was a little confused about algebraic effects. You seemed to think that the "algebra" in "algebraic effects" didn't refer to algebraic operations on normal values, which is incorrect. The basic middle-school algebra of a ring (+, *, etc., with all of the normal laws) does indeed give rise to an algebraic effect, and code that uses that effect can just be normal code like `x = 2 * y`. The "effect" here is the "ring" effect.
However, I don't think that this discussion is that productive. If you want to understand algebraic effects, unfortunately there is no substitute for just reading through the fundamental literature (like the paper I linked). I would love to be able to give you a short, easy-to-understand example that explains all the ideas in a few lines, but the concept just isn't that simple.
I see this a lot on this forum in particular: people like to develop a vague intuition for something rather than really understanding the concept properly, but almost always their "intuition" is very inaccurate, and they understand the thing less well than they think they do. Then, they try and teach others the concept, and those learners are even more misled.
I will try and point out some misconceptions in your last comment here, but again I will caution that I don't think you will be able to fully understand the topic just by reading these comments.
> So, with algebraic effects, I would expect that this is about the ways that effects can be combined using basic algebra tools.
I understand, but that is not what algebraic effects is about.
The "algebra" in algebraic effects doesn't refer to an algebra for combining effects, it refers to algebras like monoid etc., and you get an effect for any particular algebra.
> In effects, I'd expect that you are combining whatever it is an effect is.
This is incorrect. First, there are algebras that have no "combining" at all, and second, the algebras involved are just the normal algebras you're already familiar with, like the boolean algebra etc.
> You seem to be saying that an effect is a standard value? But, that seems at odds with the definitions that distinguish "pure" functions from those that have "effects" being defined by things that they cause to happen.
Yes, an effect is a standard value. And yes, we often want to distinguish pure functions from effectful ones.
(By the way, this does not mean that effectful functions are somehow not standard values)
However, in an algebraic effect the algebra does not combine effects.
> It isn't enough to say "writes to stderr", we want to know that it does so without clobbering someone else currently writing to the same spot.
I mean, obviously if the write is going to be performed concurrently you'll need more guarantees.
I included one law that might be important, but you could easily add more. That doesn't change the core concept.
> So, when asking for an example, I'm hunting for something to meet me somewhere in the middle. Sucks that this commonly comes down to "writes to a logger."
I'm not sure what you mean by the "middle"—middle between what two extremes? I picked the writing to a logger example because it was simple, and showed a simple law. The key-value store in the post is a little more complex, and involves a few more laws. In the paper there's even more examples: I/O etc. You have a lot of examples available to you!
If algebraic effects is not about how to manipulate effects using algebra, then I will flat out say that it is poorly named. Which, fair that that is already established and I don't expect some rando on the internet's objection to matter on that.
The paper you linked confuses me on this stance, as it explicitly goes through the effort of defining operations as distinct from the values they produce. And it then shows how they can be manipulated using operations. To quote: "Think of a value as an inert datum that needs no further computation, such as a boolean constant, a numeral, or a λ-abstraction. An operation takes a parameter p, for instance the memory location to be read, or the string to be printed, and a continuation κ, which is a suspended computation expecting the result of the operation, for instance the contents of the memory location that has been read" I read that as explicitly setting up how to use algebraic constructs on operations. You are taking the stance that that is not what they are doing?
That all said, I fully sympathize that you are likely hitting a blind spot of mine. I'm already fine reading up more on this paper later, so I'm not wanting to burden you on trying to cover it again.
OCaml (and its relatives I think) use * for type products. It's a lot trickier with sum types though because the variant tags realistically have to show up in the syntax, and that's going to really stretch any syntax that tries to use +... I guess it would sort of work if you made Variant(foo, bar) types of things usable standalone types, but that's either a product without a * or another non-algebraic level between + and *.
Yeah, I think I agree? It did amuse me how quickly this got annoying from the existence of String and how people use it. :D
That is, I think this is what you are saying? That it wouldn't be hard to show that an Optional<String> is the same as a variable that is (String + None) or some such. But having Either<String, String> kills this, since there is no way to distinguish the left and right String types, there. Now, if you forced it to be Either<ErrorString, ResponseString>, that can work. And that nicely explains why you have to tag the types to be distinguishable from each other.
Type sum is more like XOR though, in that it excludes overlap. I think of | for types as a set-like union type, with overlap allowed. At least that's how Typescript uses that operator (which makes sense for modeling JS APIs, but does not bring the joy of algebraic sums).
It'd be good to start with a preamble "what is algebraic about boolean algebra" since most coders should be familiar with the concept. That helps clarify what is even meant by the term "algebra" in abstract contexts. Then you could show how these things relate to ADTs and effects.
The problem with this is still that you are sticking with the algebra over the boolean values. And you are going to use + and * in doing so.
Then, you are going to move to discussing the algebra over types and effects. In such a way that you don't actually use + or * to represent the operations.
where | is another spelling of + (which is pretty standard if you look at boolean algebra) and the product is the usual tuple constructor. The is a simple algebraic data type which defines 'an effect' ... it doesn't define the semantics (that's defined by a handler), but it's an 'api' for an effect of some sort.
Obviously, the above definition is a bit contrived, but that's my understanding of why these things are called 'algebraic' effects. It's not that ConsoleOutput and ConsoleInput (however you define that using + or *) are magically 'composable' just because they're both algebraic... for that composition you need extra rules (however you specify that) because effects don't (in general) compose.
> that's my understanding of why these things are called 'algebraic' effects.
This is a misconception. Algebraic effects are not algebraic because they come from algebraic data types, the two features are completely independent (you can have algebraic effects without algebraic data types and vice versa).
> It's not that ConsoleOutput and ConsoleInput (however you define that using + or *) are magically 'composable' just because they're both algebraic... for that composition you need extra rules (however you specify that) because effects don't (in general) compose.
Actually, if you have two algebraic effects they can automatically compose. And this is a consequence of them both being algebraic. It's just that an algebraic effect is unrelated to an algebraic data type.
I have this mental block that keeps me forgetting which is which when discussing sum and product types. I have to go back to thinking of them as operations on sets.
Almost certainly a lack of formal education in maths higher level than simple calculus, but "unions" and "interface" or whatever the latter might be called in the language of choice is just so much easier to remember.
It's usually described as tagged unions and records, and the easy way to remember it by thinking about how many different values they can contain. Given that each type represents some number of possible values, the number of values for the unions is the sum of values for each allowable type and for records its the product of each field type.
* is and, + is or. This agrees with Boolean algebra, so you can think in terms of a single bit. If you can also remember that functions A->B are exponentials B^A, then you can do a quick check that everything lines up: C^(A+B) = C^A*C^B. A function that handles A or B is the same as a function that handles A and a function that handles B.
I would encourage anyone interested in this question to check out the paper "What is algebraic about algebraic effects and handlers?" (https://arxiv.org/abs/1807.05923) which is a write-up of the lecture series linked in the post above. I don't think the paper is too difficult to understand, but I know that if you're not familiar with the subject area it might be intimidating.
While I like the above blog post, I don't think that it will be very useful to people trying to understand algebraic effects. I see a lot of explainers like this one that shy away from some of the more gnarly-looking maths terms in an effort to appear more approachable, but as a result they can end up giving imprecise or vague definitions. When coupled with some subtle mistakes I think it can leave beginners more confused than helped (for instance, this author seems to conflate a few different notions of "composition", and they seem to think that the presence of equations makes an effect algebraic, which isn't really what the term "algebraic" is referring to in a technical sense).
The paper I linked above is not easy, and it would probably take at least a few hours to understand, but that's because it takes about that long to understand the material.
> they seem to think that the presence of equations makes an effect algebraic, which isn't really what the term "algebraic" is referring to in a technical sense
Author here! Open to learning. Can you expand on this? What is algebraic referring to in a technical sense?
Generally speaking, it means that the effect is derived from an algebraic theory (in a specific and structured way). While equations are definitely part of most theories, you can absolutely have a theory without equations, and furthermore you can define an effect with equations that isn't algebraic. The full definition of "algebraic theory" unfortunately doesn't really fit in a comment, but I did want to push back on the idea that "an effect becomes algebraic if you add equations to it".
In the effects literature, you often also see the definition that an operation (of an effect) is "algebraic" if the operation commutes with `>>=`. This definition is actually the same as the one above, just stated in a different way.
Trying to be helpful here, sorry if it doesn’t map to your field of which I am not familiar.
The _algebra_ you learn in school is elementary algebra, using variables.
In modern math, _algebra_ or _modern_ algebra or _abstract_algebra, is the study of structures over sets with defined operations on the elements of that set.
ADTs are an example of an algebraic structure, specifically called one that converts non-trivial semantic (runtime) properties to trivial ones (T/F).
This post is dealing with the structure in another way.
If you understand magmas, monoids, etc.. that can be helpful.
But the lay description I find useful is the algebra is what _arises_ from that defined set domain and operations.
The key point is studying the structure, which is the algebraic structure, or the algebra. It is basically what pops out, not what you start with, although that is flawed.
Almost all modern math will use that _modern_ meaning of algebra.
I actually wish we taught more of this math early on[0]. Children seem to be quick to grasp many of the fundamentals of important structures like groups, fields, and algebras. I find that many of these concepts have fundamentally shifted how I think and can be used on a daily basis, without the need of writing formulas or using formal semantics.
It's odd that it takes getting up upper division undergraduate education in math (or sometimes from neighboring fields) to learn what the field is even fundamentally about. It's akin to teaching people that programming by teaching people how to use a word editor. It's such a narrow aspect and no surprise so many are so fundamentally confused.
[0] I'm unconvinced the "new maths" programs were a complete failure. Just because we didn't get it right on the first attempt doesn't mean we should have thrown the baby out with the bath water.
are you address me, or oisdk? I did mean algebra in terms of structure, and I tried to say that in the post.
Just to clarify, are you saying that you recommend that writeup over the lecture, or just linking the writeup for people who'd prefer it over watching a video?
I'm just recommending the writeup, but only because I haven't watched the lecture series myself (although I'm sure it's good, I've seen other lectures by the lecturer that were excellent). As far as I know, they cover basically the same material.
That was a very approachable explanation. Makes a lot of sense. Essentially by encoding the program algebraically you can prove that it is invariant under the action of the semi-lattice. Very neat! Maybe lean is worth a look.
That is interesting, I hadn't really given it much thought but my first instinct would be to assume the algebra in algebraic effect was not about having algebra like definitions but was in fact a direct reference to an algebra of a monad (though that might be the same thing).
At least the monad algeba gives a nice hint on how to view algbraic effects. Instead of using a monad so you can raise an exception
You use an E-algebra (h :: E a -> a) instead to create a function that takes both an input and an exception handler to produce an output The canonical example being something like And a simple example of a handler being something like a default value With the advantage of course that given a handler you can be much more flexible in how you handle exceptions and where. You're not limited to just returning early, you can handle the exception and carry on.I started a thread last time Algebraic Datatypes were discussed that hit a similar vein. I assert most programmers know the middle school version of "algebra" and think of it in terms of what they can do with the values they are working with.
This is in contrast to doing operations on either the "types" or the "effects" that are happening during code. So, you have to show people what are the equivalent of + and * in types and effects to show them how these can be thought of algebraically.
I still think this would be easier if a type system was made that let you use + and * in defining something. It would give an obvious path to seeing how things relate to algebra. Would almost certainly make some things harder, of course. Maybe it would be a good worksheet asking questions about stuff?
The big underline, though, is getting people to realize what algebra there is is not on the values that your code represents. It is treating something else as the value for the algebra.
The "algebraic" in "algebraic effects" is not really related to algebraic data types, or sum or product types. I mean, I suppose they're related, since they both refer to algebra in the general sense, but there's no type-level algebra in a description of algebraic effects. (and, I suppose, you could do some type-level algebra with effects, like taking the "sum" of two effects, but again that's not what the "algebra" in "algebraic effects" is referring to)
> The big underline, though, is getting people to realize what algebra there is is not on the values that your code represents.
This is not correct. In the case of algebraic effects, the algebra is absolutely value-level.
I'm not sure I follow? For one, if algebraic isn't aiming at the ideas in an algebra, then they absolutely should be using a different name.
For two, though, the whole idea is how to compose the "value" of different effects together? My point is that the "value" is not the written value of a variable in ways that people are used to working with in their program. It will be a meta-value about some state represented by the program.
Is that not the case? If my use of the word "value" there is confusing things, I'm open to using some other words. My point is largely that the "value" of concern in effect systems is not the same as the value of a variable as people are used to reasoning. You are specifically meta-reasoning about the state of the program in ways that may not be represented by an explicit value of the program.
Not that that alone is unheard of. If you asked people to tell you the program counter of a function, they would largely get what you mean. Even if it is not something that is represented in the values of the program, itself.
> For one, if algebraic isn't aiming at the ideas in an algebra, then they absolutely should be using a different name.
Algebraic effects are certainly algebraic, they're just not directly related to algebraic data types. Both ideas are using "algebraic" at different levels, and I think trying to understand algebraic effects by referencing algebraic data types will be more confusing than helpful.
> My point is that the "value" is not the written value of a variable in ways that people are used to working with in their program.
I'm saying that (in algebraic effects) the "value" in question is precisely a normal variable that people are used to working with in programming languages. It is not a type-level value, which is the kind of value in question when we're talking about algebraic data types.
For example, if we take Groups (the algebra referenced in the post), we have a binary operation (that we might call +) along with a few other operations. We could write a piece of code like the following:
The "group" in question here could absolutely be an algebraic effect. And the line of code above could be implemented using algebraic effects, and interpreted using an algebraic effect handler. You don't even need types, if you didn't want them.> For two, though, the whole idea is how to compose the "value" of different effects together?
No, not really.
Yes, algebraic effects compose well. But so do other effects systems and abstractions (applicatives, etc.). The fact that the effects compose is not what makes them algebraic, it's a consequence of it.
I don't think I can give a proper explanation in a comment, but I would point you to the paper I linked in another comment (https://arxiv.org/abs/1807.05923).
I'm not positive on what you are aiming at. I'd assume "algebraic effects" are to talk about performing algebra on the effects. That is, you are specifically going to talk about how different things combine effects, preferably in ways that honor + and * that we are used to.
If you are just pointing out that this is not, necessarily, "type" related. Agreed. Apologies if I mislead there. I was highlighting that algebraic data types has a similar problem. I did not mean to imply that these were the same topic.
My point is simply that there is no value in the program that says an effect has or has not completed. This is why I compare it to stepping through the program. The "line of code" that is active in executing code is not a first class value in your program. It is very much there, of course. But it is not a value of the program.
> I'd assume "algebraic effects" are to talk about performing algebra on the effects. That is, you are specifically going to talk about how different things combine effects
This is a misconception. The "algebra" does not refer to an algebra of effects, or combining effects in any way.
It's more like it's the other way around: "algebraic effects" are effects generated from algebras. These algebras are precisely-defined mathematical objects (like groups, monoids, etc.), so you have an "effect" that corresponds to monoids, an "effect" that corresponds to groups, and so on.
> My point is simply that there is no value in the program that says an effect has or has not completed. This is why I compare it to stepping through the program. The "line of code" that is active in executing code is not a first class value in your program.
I know: I'm trying to say that the "algebra" of "algebraic effects" do refer to first-class values. The + and * from other algebraic operations are the algebraic operations you might use for an algebraic effect.
I feel that you just spelled potato and then pronounced it differently. :D
If you have examples you recommend, I'd be game to look over them.
What is a first class "value" that is referenced in algebraic effects?
I mean, the program snippet that I gave above contains 3 first-class values. If you write `x = y + z + 0`, or any other statement that uses the group algebra (or any other algebra), you can use algebraic effects to describe the semantics. The “first-class values” here are the x, y, and z: there’s nothing fancy going on. You can even use the group laws to show that the statement is equivalent to `x = y + z` (or whatever). It’s just normal, value-level algebra.
Right, but this is just explaining algebra. Which, I get that. Connect this to effects, for me. (And fair that just because I assert that I get it, I would wager I don't have as strong of a handle as I should have.)
My understanding for effects was more like "writes to stdout" and such. Probably better to have "opens a stream," "writes to an open stream," and "closes a stream." The algebra that I typically see is to show that you can combine some of these in such a way to either highlight a bug, or to help prevent them.
I got this because many effects typically go through hurdles to find a way to let you log to stderr without it polluting your entire effects system.
For an algebra, you have some operations and some equations. The group algebra has the + operation, and 0 and -, and all the relevant equations.
You can also form an algebra from logging. One operation might be “write to stdout”. And then a law might be `write x; write y = write (x ++ y)` where ++ is string concatenation.
This is the algebra, the algebra isn’t for combining effects at all. (Yes, you can combine algebraic effects, and the fact that they’re algebraic does help, but that’s for technical reasons that aren’t relevant)
The paper I linked in another comment has a good overview of the topic. It’s really not the kind of thing you can understand from reading a few comments, and the paper is well-written and goes over all of the main points from a pretty basic starting point.
I looked over the paper, but I confess I don't understand how it is helping. Would help a ton to have an example effect that didn't dive into distinguishing "Values", "Computations", "Value types," and "Computation types."
In fact, that it distinguishes values, computations, and the types of both seems more inline with my point? That what most "effect systems" are trying to capture are things that are not typically defined in programs?
So, again, give me some examples of effects and how you would model them. That will go a long way to demonstrate what you mean, here. Even better if you can show how this is already modeled in some code. (Note that I'm not trying to ask you to give this in a post. If you have some more things like that paper to look into, I don't mind looking there. I do plan on spending more time with the paper, already.)
Well, I gave the example of a logging effect above. In the post there’s also an example of a key-value store effect. What’s missing from these examples exactly?
All of these effects have simple operations (get and put for store, the `write` operation for the logging effect, etc.) These are all normal operations in your language: they just return values, like normal, and the laws that govern them are equivalent to the laws of any other algebra.
Elsewhere you mentioned Boolean algebra, and that people shouldn’t confuse that with algebraic effects: Boolean algebra can absolutely be another example of an algebraic effect! The operations are the Boolean operations (call them whatever you like, + or * or whatever), and the laws are the usual laws.
The point of algebraic effects is in noticing that traditional effects (logging, state, exceptions) can be thought of as algebraic the same way as Boolean algebras or monoids.
If you’re looking for an implementation, there are lots of implementations available in Haskell and other languages. However, to understand those you’d really already have to have a good understanding of the topic first, and then you’d also need to be comfortable with Haskell syntax (and probably free monads as well). I think that the paper really gives the best introduction to the topic, unfortunately there’s no way to simplify it much further.
I don't think I mentioned boolean algebra? I responded to someone else mentioning it. My problem there is still that you are going to be taught how to operate over boolean values using an algebraic construction. (Looking, I think that is accurate. Apologies if I am the one that brought it up somewhere, I don't remember that.)
Which, fair that may help some people. I just feel that this is akin to asking for people to understand algebraic effects using basic algebra from middle school. In basic algebra practices, you lean heavily on the basic operations applied to reals and see how to manipulate equations to discover both solutions and other statements about the equations. (Advanced students will eventually extend to imaginary numbers, but I don't think that changes this statement?)
Similarly, with algebraic datatypes, you learn what it means to combine the domains of types together. Since it is an algebra, you learn this in terms of the basic operations. Hence SumTypes and ProductTypes. My assertion there is that this is hard for people because they don't actually do the algebra on the domains. And, by "they" I largely mean the software that they write.
So, with algebraic effects, I would expect that this is about the ways that effects can be combined using basic algebra tools. But what is it that you are combining? In the types, you were combining domains for analysis. In effects, I'd expect that you are combining whatever it is an effect is. You seem to be saying that an effect is a standard value? But, that seems at odds with the definitions that distinguish "pure" functions from those that have "effects" being defined by things that they cause to happen.
It doesn't help that we typically talk about things that we want to preserve some property on. It isn't enough to say "writes to stderr", we want to know that it does so without clobbering someone else currently writing to the same spot. At the least, we probably want to know that it line buffers output in such a way that that is preserved.
So, when asking for an example, I'm hunting for something to meet me somewhere in the middle. Sucks that this commonly comes down to "writes to a logger."
I'm afraid I don't think I'm making progress here.
My overall point was that I felt your original comment was a little confused about algebraic effects. You seemed to think that the "algebra" in "algebraic effects" didn't refer to algebraic operations on normal values, which is incorrect. The basic middle-school algebra of a ring (+, *, etc., with all of the normal laws) does indeed give rise to an algebraic effect, and code that uses that effect can just be normal code like `x = 2 * y`. The "effect" here is the "ring" effect.
However, I don't think that this discussion is that productive. If you want to understand algebraic effects, unfortunately there is no substitute for just reading through the fundamental literature (like the paper I linked). I would love to be able to give you a short, easy-to-understand example that explains all the ideas in a few lines, but the concept just isn't that simple.
I see this a lot on this forum in particular: people like to develop a vague intuition for something rather than really understanding the concept properly, but almost always their "intuition" is very inaccurate, and they understand the thing less well than they think they do. Then, they try and teach others the concept, and those learners are even more misled.
----------------------------------------------------------------------
I will try and point out some misconceptions in your last comment here, but again I will caution that I don't think you will be able to fully understand the topic just by reading these comments.
> So, with algebraic effects, I would expect that this is about the ways that effects can be combined using basic algebra tools.
I understand, but that is not what algebraic effects is about.
The "algebra" in algebraic effects doesn't refer to an algebra for combining effects, it refers to algebras like monoid etc., and you get an effect for any particular algebra.
> In effects, I'd expect that you are combining whatever it is an effect is.
This is incorrect. First, there are algebras that have no "combining" at all, and second, the algebras involved are just the normal algebras you're already familiar with, like the boolean algebra etc.
> You seem to be saying that an effect is a standard value? But, that seems at odds with the definitions that distinguish "pure" functions from those that have "effects" being defined by things that they cause to happen.
Yes, an effect is a standard value. And yes, we often want to distinguish pure functions from effectful ones. (By the way, this does not mean that effectful functions are somehow not standard values)
However, in an algebraic effect the algebra does not combine effects.
> It isn't enough to say "writes to stderr", we want to know that it does so without clobbering someone else currently writing to the same spot.
I mean, obviously if the write is going to be performed concurrently you'll need more guarantees.
I included one law that might be important, but you could easily add more. That doesn't change the core concept.
> So, when asking for an example, I'm hunting for something to meet me somewhere in the middle. Sucks that this commonly comes down to "writes to a logger."
I'm not sure what you mean by the "middle"—middle between what two extremes? I picked the writing to a logger example because it was simple, and showed a simple law. The key-value store in the post is a little more complex, and involves a few more laws. In the paper there's even more examples: I/O etc. You have a lot of examples available to you!
If algebraic effects is not about how to manipulate effects using algebra, then I will flat out say that it is poorly named. Which, fair that that is already established and I don't expect some rando on the internet's objection to matter on that.
The paper you linked confuses me on this stance, as it explicitly goes through the effort of defining operations as distinct from the values they produce. And it then shows how they can be manipulated using operations. To quote: "Think of a value as an inert datum that needs no further computation, such as a boolean constant, a numeral, or a λ-abstraction. An operation takes a parameter p, for instance the memory location to be read, or the string to be printed, and a continuation κ, which is a suspended computation expecting the result of the operation, for instance the contents of the memory location that has been read" I read that as explicitly setting up how to use algebraic constructs on operations. You are taking the stance that that is not what they are doing?
That all said, I fully sympathize that you are likely hitting a blind spot of mine. I'm already fine reading up more on this paper later, so I'm not wanting to burden you on trying to cover it again.
OCaml (and its relatives I think) use * for type products. It's a lot trickier with sum types though because the variant tags realistically have to show up in the syntax, and that's going to really stretch any syntax that tries to use +... I guess it would sort of work if you made Variant(foo, bar) types of things usable standalone types, but that's either a product without a * or another non-algebraic level between + and *.
Yeah, I think I agree? It did amuse me how quickly this got annoying from the existence of String and how people use it. :D
That is, I think this is what you are saying? That it wouldn't be hard to show that an Optional<String> is the same as a variable that is (String + None) or some such. But having Either<String, String> kills this, since there is no way to distinguish the left and right String types, there. Now, if you forced it to be Either<ErrorString, ResponseString>, that can work. And that nicely explains why you have to tag the types to be distinguishable from each other.
It's not +, but it's |, like OR which is the + of logical operators.
Type sum is more like XOR though, in that it excludes overlap. I think of | for types as a set-like union type, with overlap allowed. At least that's how Typescript uses that operator (which makes sense for modeling JS APIs, but does not bring the joy of algebraic sums).
It'd be good to start with a preamble "what is algebraic about boolean algebra" since most coders should be familiar with the concept. That helps clarify what is even meant by the term "algebra" in abstract contexts. Then you could show how these things relate to ADTs and effects.
The problem with this is still that you are sticking with the algebra over the boolean values. And you are going to use + and * in doing so.
Then, you are going to move to discussing the algebra over types and effects. In such a way that you don't actually use + or * to represent the operations.
I'm not if sure if this is what you're asking for, but to make it very explicit, e.g. Console Output might be modeled as
where | is another spelling of + (which is pretty standard if you look at boolean algebra) and the product is the usual tuple constructor. The is a simple algebraic data type which defines 'an effect' ... it doesn't define the semantics (that's defined by a handler), but it's an 'api' for an effect of some sort.Obviously, the above definition is a bit contrived, but that's my understanding of why these things are called 'algebraic' effects. It's not that ConsoleOutput and ConsoleInput (however you define that using + or *) are magically 'composable' just because they're both algebraic... for that composition you need extra rules (however you specify that) because effects don't (in general) compose.
> that's my understanding of why these things are called 'algebraic' effects.
This is a misconception. Algebraic effects are not algebraic because they come from algebraic data types, the two features are completely independent (you can have algebraic effects without algebraic data types and vice versa).
> It's not that ConsoleOutput and ConsoleInput (however you define that using + or *) are magically 'composable' just because they're both algebraic... for that composition you need extra rules (however you specify that) because effects don't (in general) compose.
Actually, if you have two algebraic effects they can automatically compose. And this is a consequence of them both being algebraic. It's just that an algebraic effect is unrelated to an algebraic data type.
The Algebra of Graphics package for Julia[0] has a interesting ('tangible') use-case for algebraic operators here.
[0]: https://aog.makie.org/stable/#Example
I have this mental block that keeps me forgetting which is which when discussing sum and product types. I have to go back to thinking of them as operations on sets.
Almost certainly a lack of formal education in maths higher level than simple calculus, but "unions" and "interface" or whatever the latter might be called in the language of choice is just so much easier to remember.
It's usually described as tagged unions and records, and the easy way to remember it by thinking about how many different values they can contain. Given that each type represents some number of possible values, the number of values for the unions is the sum of values for each allowable type and for records its the product of each field type.
* is and, + is or. This agrees with Boolean algebra, so you can think in terms of a single bit. If you can also remember that functions A->B are exponentials B^A, then you can do a quick check that everything lines up: C^(A+B) = C^A*C^B. A function that handles A or B is the same as a function that handles A and a function that handles B.