How to tell if an effect is algebraic?
$begingroup$
I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic effects and handlers, people mention effects that are not algebraic, like backtracking. How does one can tell an algebraic effect apart from a non-algebraic one?
pl.programming-languages
asked Feb 24 at 15:24
Jesper DahlJesper Dahl
363
$endgroup$
add a comment |
$begingroup$
I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic effects and handlers, people mention effects that are not algebraic, like backtracking. How does one can tell an algebraic effect apart from a non-algebraic one?
pl.programming-languages
asked Feb 24 at 15:24
Jesper DahlJesper Dahl
363
$endgroup$
$begingroup$
Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims?
$endgroup$
– Andrej Bauer
Feb 24 at 18:32
$begingroup$
I was sloppy when writing that. Pretnar's An Introduction to Algebraic Effects and Handlers (on page 14) says backtracking do not respect equations and cannot receive a homomorphic interpretation, so I assumed it wasn't algebraic. Also, given that continuations aren't algebraic, I also assumed asynchrony would not be algebraic as well. Conversation "on the streets" about it often lead to "yeah, but the interesting effects aren't algebraic", hence my question.
$endgroup$
– Jesper Dahl
Feb 25 at 15:16
$begingroup$
Pretnar's point is that the expected equations are not satisfied. This means that by removing them we will get an algebraic effect.
$endgroup$
– Andrej Bauer
Feb 25 at 19:11
1
$begingroup$
Asynchronous execution is algebraic because the continuations are delimited, like in the example of multi-threading from the "Programming with algebraic effects and handlers". So let it be known in the street that perhaps one should think first.
$endgroup$
– Andrej Bauer
Feb 25 at 19:12
$begingroup$
One possible thing to note is that some of the things that are categorized as not algebraic in some papers on effects actually are algebraic in the sense that you can make sense of the operations in a (countable enriched) Lawvere theory. The example I know of is catching exceptions. So sometimes the classification is not made on a completely rigorous basis (perhaps because it predates the formalism).
$endgroup$
– Dan Doel
Mar 9 at 0:52
add a comment |
$begingroup$
I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic effects and handlers, people mention effects that are not algebraic, like backtracking. How does one can tell an algebraic effect apart from a non-algebraic one?
pl.programming-languages
asked Feb 24 at 15:24
Jesper DahlJesper Dahl
363
$endgroup$
I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic effects and handlers, people mention effects that are not algebraic, like backtracking. How does one can tell an algebraic effect apart from a non-algebraic one?
pl.programming-languages
pl.programming-languages
asked Feb 24 at 15:24
Jesper DahlJesper Dahl
363
asked Feb 24 at 15:24
Jesper DahlJesper Dahl
363
edited Feb 25 at 14:54
Jesper Dahl
asked Feb 24 at 15:24
Jesper DahlJesper Dahl
363
asked Feb 24 at 15:24
Jesper DahlJesper Dahl
363
asked Feb 24 at 15:24
Jesper DahlJesper Dahl
363
363
$begingroup$
Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims?
$endgroup$
– Andrej Bauer
Feb 24 at 18:32
$begingroup$
I was sloppy when writing that. Pretnar's An Introduction to Algebraic Effects and Handlers (on page 14) says backtracking do not respect equations and cannot receive a homomorphic interpretation, so I assumed it wasn't algebraic. Also, given that continuations aren't algebraic, I also assumed asynchrony would not be algebraic as well. Conversation "on the streets" about it often lead to "yeah, but the interesting effects aren't algebraic", hence my question.
$endgroup$
– Jesper Dahl
Feb 25 at 15:16
$begingroup$
Pretnar's point is that the expected equations are not satisfied. This means that by removing them we will get an algebraic effect.
$endgroup$
– Andrej Bauer
Feb 25 at 19:11
1
$begingroup$
Asynchronous execution is algebraic because the continuations are delimited, like in the example of multi-threading from the "Programming with algebraic effects and handlers". So let it be known in the street that perhaps one should think first.
$endgroup$
– Andrej Bauer
Feb 25 at 19:12
$begingroup$
One possible thing to note is that some of the things that are categorized as not algebraic in some papers on effects actually are algebraic in the sense that you can make sense of the operations in a (countable enriched) Lawvere theory. The example I know of is catching exceptions. So sometimes the classification is not made on a completely rigorous basis (perhaps because it predates the formalism).
$endgroup$
– Dan Doel
Mar 9 at 0:52
add a comment |
$begingroup$
Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims?
$endgroup$
– Andrej Bauer
Feb 24 at 18:32
$begingroup$
I was sloppy when writing that. Pretnar's An Introduction to Algebraic Effects and Handlers (on page 14) says backtracking do not respect equations and cannot receive a homomorphic interpretation, so I assumed it wasn't algebraic. Also, given that continuations aren't algebraic, I also assumed asynchrony would not be algebraic as well. Conversation "on the streets" about it often lead to "yeah, but the interesting effects aren't algebraic", hence my question.
$endgroup$
– Jesper Dahl
Feb 25 at 15:16
$begingroup$
Pretnar's point is that the expected equations are not satisfied. This means that by removing them we will get an algebraic effect.
$endgroup$
– Andrej Bauer
Feb 25 at 19:11
1
$begingroup$
Asynchronous execution is algebraic because the continuations are delimited, like in the example of multi-threading from the "Programming with algebraic effects and handlers". So let it be known in the street that perhaps one should think first.
$endgroup$
– Andrej Bauer
Feb 25 at 19:12
$begingroup$
One possible thing to note is that some of the things that are categorized as not algebraic in some papers on effects actually are algebraic in the sense that you can make sense of the operations in a (countable enriched) Lawvere theory. The example I know of is catching exceptions. So sometimes the classification is not made on a completely rigorous basis (perhaps because it predates the formalism).
$endgroup$
– Dan Doel
Mar 9 at 0:52
$begingroup$
Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims?
$endgroup$
– Andrej Bauer
Feb 24 at 18:32
$begingroup$
Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims?
$endgroup$
– Andrej Bauer
Feb 24 at 18:32
$begingroup$
I was sloppy when writing that. Pretnar's An Introduction to Algebraic Effects and Handlers (on page 14) says backtracking do not respect equations and cannot receive a homomorphic interpretation, so I assumed it wasn't algebraic. Also, given that continuations aren't algebraic, I also assumed asynchrony would not be algebraic as well. Conversation "on the streets" about it often lead to "yeah, but the interesting effects aren't algebraic", hence my question.
$endgroup$
– Jesper Dahl
Feb 25 at 15:16
$begingroup$
I was sloppy when writing that. Pretnar's An Introduction to Algebraic Effects and Handlers (on page 14) says backtracking do not respect equations and cannot receive a homomorphic interpretation, so I assumed it wasn't algebraic. Also, given that continuations aren't algebraic, I also assumed asynchrony would not be algebraic as well. Conversation "on the streets" about it often lead to "yeah, but the interesting effects aren't algebraic", hence my question.
$endgroup$
– Jesper Dahl
Feb 25 at 15:16
$begingroup$
Pretnar's point is that the expected equations are not satisfied. This means that by removing them we will get an algebraic effect.
$endgroup$
– Andrej Bauer
Feb 25 at 19:11
$begingroup$
Pretnar's point is that the expected equations are not satisfied. This means that by removing them we will get an algebraic effect.
$endgroup$
– Andrej Bauer
Feb 25 at 19:11
1
1
$begingroup$
Asynchronous execution is algebraic because the continuations are delimited, like in the example of multi-threading from the "Programming with algebraic effects and handlers". So let it be known in the street that perhaps one should think first.
$endgroup$
– Andrej Bauer
Feb 25 at 19:12
$begingroup$
Asynchronous execution is algebraic because the continuations are delimited, like in the example of multi-threading from the "Programming with algebraic effects and handlers". So let it be known in the street that perhaps one should think first.
$endgroup$
– Andrej Bauer
Feb 25 at 19:12
$begingroup$
One possible thing to note is that some of the things that are categorized as not algebraic in some papers on effects actually are algebraic in the sense that you can make sense of the operations in a (countable enriched) Lawvere theory. The example I know of is catching exceptions. So sometimes the classification is not made on a completely rigorous basis (perhaps because it predates the formalism).
$endgroup$
– Dan Doel
Mar 9 at 0:52
$begingroup$
One possible thing to note is that some of the things that are categorized as not algebraic in some papers on effects actually are algebraic in the sense that you can make sense of the operations in a (countable enriched) Lawvere theory. The example I know of is catching exceptions. So sometimes the classification is not made on a completely rigorous basis (perhaps because it predates the formalism).
$endgroup$
– Dan Doel
Mar 9 at 0:52
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The general answer which you do not want to hear is: an effect is algebraic if it can be described using operations and equations. The question is a bit open-ended and gives no hint as to what you're expecting, so perhaps you deserve such a useless answer.
Nevertheless, it's still good to know some typical examples, as they help you develop a feeling for things:
Continuations are not algebraic. That's important because there are effects that let you encode continuations, and so those are not aglebraic either. (But be careful about the meaning of "encode").
Delimited continuations are algebraic, see Section 6.11 of "Programming with algebraic effects and handlers". Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.
If your effect looks like you're passing around state of some sort, then it's likely algebraic.
Nondeterministic choice, search, etc., are typically algebraic.
Exception-like effects are algebraic (transactions of various sorts are included).
Anything that looks like communication (I/O, reader monad) is algebraic.
Probabilistic programming is algebraic.
Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.
answered Feb 24 at 18:39
Andrej BauerAndrej Bauer
22k54105
$endgroup$
$begingroup$
I updated the delimited continuations example to point out that threads and thread-like effects are algebraic.
$endgroup$
– Andrej Bauer
Feb 25 at 19:14
$begingroup$
What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation.
$endgroup$
– Max New
Feb 26 at 12:31
$begingroup$
Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had resources which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion.
$endgroup$
– Andrej Bauer
Feb 26 at 14:03
$begingroup$
I think a good answer to this question would be to say how to show effects are not algebraic. I think continuations are not because of size issues, but are there any other examples?
$endgroup$
– Max New
Feb 26 at 20:32
$begingroup$
What do you mean by "show effects"?
$endgroup$
– Jesper Dahl
Feb 27 at 19:03
|
show 1 more comment
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "114"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f42431%2fhow-to-tell-if-an-effect-is-algebraic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The general answer which you do not want to hear is: an effect is algebraic if it can be described using operations and equations. The question is a bit open-ended and gives no hint as to what you're expecting, so perhaps you deserve such a useless answer.
Nevertheless, it's still good to know some typical examples, as they help you develop a feeling for things:
Continuations are not algebraic. That's important because there are effects that let you encode continuations, and so those are not aglebraic either. (But be careful about the meaning of "encode").
Delimited continuations are algebraic, see Section 6.11 of "Programming with algebraic effects and handlers". Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.
If your effect looks like you're passing around state of some sort, then it's likely algebraic.
Nondeterministic choice, search, etc., are typically algebraic.
Exception-like effects are algebraic (transactions of various sorts are included).
Anything that looks like communication (I/O, reader monad) is algebraic.
Probabilistic programming is algebraic.
Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.
answered Feb 24 at 18:39
Andrej BauerAndrej Bauer
22k54105
$endgroup$
$begingroup$
I updated the delimited continuations example to point out that threads and thread-like effects are algebraic.
$endgroup$
– Andrej Bauer
Feb 25 at 19:14
$begingroup$
What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation.
$endgroup$
– Max New
Feb 26 at 12:31
$begingroup$
Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had resources which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion.
$endgroup$
– Andrej Bauer
Feb 26 at 14:03
$begingroup$
I think a good answer to this question would be to say how to show effects are not algebraic. I think continuations are not because of size issues, but are there any other examples?
$endgroup$
– Max New
Feb 26 at 20:32
$begingroup$
What do you mean by "show effects"?
$endgroup$
– Jesper Dahl
Feb 27 at 19:03
|
show 1 more comment
$begingroup$
The general answer which you do not want to hear is: an effect is algebraic if it can be described using operations and equations. The question is a bit open-ended and gives no hint as to what you're expecting, so perhaps you deserve such a useless answer.
Nevertheless, it's still good to know some typical examples, as they help you develop a feeling for things:
Continuations are not algebraic. That's important because there are effects that let you encode continuations, and so those are not aglebraic either. (But be careful about the meaning of "encode").
Delimited continuations are algebraic, see Section 6.11 of "Programming with algebraic effects and handlers". Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.
If your effect looks like you're passing around state of some sort, then it's likely algebraic.
Nondeterministic choice, search, etc., are typically algebraic.
Exception-like effects are algebraic (transactions of various sorts are included).
Anything that looks like communication (I/O, reader monad) is algebraic.
Probabilistic programming is algebraic.
Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.
answered Feb 24 at 18:39
Andrej BauerAndrej Bauer
22k54105
$endgroup$
$begingroup$
I updated the delimited continuations example to point out that threads and thread-like effects are algebraic.
$endgroup$
– Andrej Bauer
Feb 25 at 19:14
$begingroup$
What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation.
$endgroup$
– Max New
Feb 26 at 12:31
$begingroup$
Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had resources which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion.
$endgroup$
– Andrej Bauer
Feb 26 at 14:03
$begingroup$
I think a good answer to this question would be to say how to show effects are not algebraic. I think continuations are not because of size issues, but are there any other examples?
$endgroup$
– Max New
Feb 26 at 20:32
$begingroup$
What do you mean by "show effects"?
$endgroup$
– Jesper Dahl
Feb 27 at 19:03
|
show 1 more comment
$begingroup$
The general answer which you do not want to hear is: an effect is algebraic if it can be described using operations and equations. The question is a bit open-ended and gives no hint as to what you're expecting, so perhaps you deserve such a useless answer.
Nevertheless, it's still good to know some typical examples, as they help you develop a feeling for things:
Continuations are not algebraic. That's important because there are effects that let you encode continuations, and so those are not aglebraic either. (But be careful about the meaning of "encode").
Delimited continuations are algebraic, see Section 6.11 of "Programming with algebraic effects and handlers". Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.
If your effect looks like you're passing around state of some sort, then it's likely algebraic.
Nondeterministic choice, search, etc., are typically algebraic.
Exception-like effects are algebraic (transactions of various sorts are included).
Anything that looks like communication (I/O, reader monad) is algebraic.
Probabilistic programming is algebraic.
Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.
answered Feb 24 at 18:39
Andrej BauerAndrej Bauer
22k54105
$endgroup$
The general answer which you do not want to hear is: an effect is algebraic if it can be described using operations and equations. The question is a bit open-ended and gives no hint as to what you're expecting, so perhaps you deserve such a useless answer.
Nevertheless, it's still good to know some typical examples, as they help you develop a feeling for things:
Continuations are not algebraic. That's important because there are effects that let you encode continuations, and so those are not aglebraic either. (But be careful about the meaning of "encode").
Delimited continuations are algebraic, see Section 6.11 of "Programming with algebraic effects and handlers". Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.
If your effect looks like you're passing around state of some sort, then it's likely algebraic.
Nondeterministic choice, search, etc., are typically algebraic.
Exception-like effects are algebraic (transactions of various sorts are included).
Anything that looks like communication (I/O, reader monad) is algebraic.
Probabilistic programming is algebraic.
Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.
answered Feb 24 at 18:39
Andrej BauerAndrej Bauer
22k54105
edited Feb 25 at 19:14
answered Feb 24 at 18:39
Andrej BauerAndrej Bauer
22k54105
answered Feb 24 at 18:39
Andrej BauerAndrej Bauer
22k54105
answered Feb 24 at 18:39
Andrej BauerAndrej Bauer
22k54105
22k54105
$begingroup$
I updated the delimited continuations example to point out that threads and thread-like effects are algebraic.
$endgroup$
– Andrej Bauer
Feb 25 at 19:14
$begingroup$
What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation.
$endgroup$
– Max New
Feb 26 at 12:31
$begingroup$
Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had resources which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion.
$endgroup$
– Andrej Bauer
Feb 26 at 14:03
$begingroup$
I think a good answer to this question would be to say how to show effects are not algebraic. I think continuations are not because of size issues, but are there any other examples?
$endgroup$
– Max New
Feb 26 at 20:32
$begingroup$
What do you mean by "show effects"?
$endgroup$
– Jesper Dahl
Feb 27 at 19:03
|
show 1 more comment
$begingroup$
I updated the delimited continuations example to point out that threads and thread-like effects are algebraic.
$endgroup$
– Andrej Bauer
Feb 25 at 19:14
$begingroup$
What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation.
$endgroup$
– Max New
Feb 26 at 12:31
$begingroup$
Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had resources which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion.
$endgroup$
– Andrej Bauer
Feb 26 at 14:03
$begingroup$
I think a good answer to this question would be to say how to show effects are not algebraic. I think continuations are not because of size issues, but are there any other examples?
$endgroup$
– Max New
Feb 26 at 20:32
$begingroup$
What do you mean by "show effects"?
$endgroup$
– Jesper Dahl
Feb 27 at 19:03
$begingroup$
I updated the delimited continuations example to point out that threads and thread-like effects are algebraic.
$endgroup$
– Andrej Bauer
Feb 25 at 19:14
$begingroup$
I updated the delimited continuations example to point out that threads and thread-like effects are algebraic.
$endgroup$
– Andrej Bauer
Feb 25 at 19:14
$begingroup$
What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation.
$endgroup$
– Max New
Feb 26 at 12:31
$begingroup$
What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation.
$endgroup$
– Max New
Feb 26 at 12:31
$begingroup$
Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had resources which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion.
$endgroup$
– Andrej Bauer
Feb 26 at 14:03
$begingroup$
Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had resources which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion.
$endgroup$
– Andrej Bauer
Feb 26 at 14:03
$begingroup$
I think a good answer to this question would be to say how to show effects are not algebraic. I think continuations are not because of size issues, but are there any other examples?
$endgroup$
– Max New
Feb 26 at 20:32
$begingroup$
I think a good answer to this question would be to say how to show effects are not algebraic. I think continuations are not because of size issues, but are there any other examples?
$endgroup$
– Max New
Feb 26 at 20:32
$begingroup$
What do you mean by "show effects"?
$endgroup$
– Jesper Dahl
Feb 27 at 19:03
$begingroup$
What do you mean by "show effects"?
$endgroup$
– Jesper Dahl
Feb 27 at 19:03
|
show 1 more comment
Thanks for contributing an answer to Theoretical Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f42431%2fhow-to-tell-if-an-effect-is-algebraic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims?
$endgroup$
– Andrej Bauer
Feb 24 at 18:32
$begingroup$
I was sloppy when writing that. Pretnar's An Introduction to Algebraic Effects and Handlers (on page 14) says backtracking do not respect equations and cannot receive a homomorphic interpretation, so I assumed it wasn't algebraic. Also, given that continuations aren't algebraic, I also assumed asynchrony would not be algebraic as well. Conversation "on the streets" about it often lead to "yeah, but the interesting effects aren't algebraic", hence my question.
$endgroup$
– Jesper Dahl
Feb 25 at 15:16
$begingroup$
Pretnar's point is that the expected equations are not satisfied. This means that by removing them we will get an algebraic effect.
$endgroup$
– Andrej Bauer
Feb 25 at 19:11
1
$begingroup$
Asynchronous execution is algebraic because the continuations are delimited, like in the example of multi-threading from the "Programming with algebraic effects and handlers". So let it be known in the street that perhaps one should think first.
$endgroup$
– Andrej Bauer
Feb 25 at 19:12
$begingroup$
One possible thing to note is that some of the things that are categorized as not algebraic in some papers on effects actually are algebraic in the sense that you can make sense of the operations in a (countable enriched) Lawvere theory. The example I know of is catching exceptions. So sometimes the classification is not made on a completely rigorous basis (perhaps because it predates the formalism).
$endgroup$
– Dan Doel
Mar 9 at 0:52