Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algebraic Effects for the Rest of Us

overreacted.io

Post reply on HN
Print view View original

61–70 of 106 posts

Re: Algebraic Effects for the Rest of Us

#61

Post by codebje »

pjc50 wrote: post #39
phoe-krk wrote: post #19

> The best we can do is to recover from a failure and maybe somehow retry what we were doing, but we can’t magically “go back” to where we were, and do something different. But with algebraic effects, we can. This is literally Common Lisp's condition system which a) decouples signaling conditions from handling conditions, b) allows you to execute arbitrary code in the place that signals, c) allows you to stack indepe…

The origin of "algebraic effects" appears to be this paper (Plotkin and Power): https://link.springer.com/article/10.1023%2FA%3A102306490896... Unfortunately I don't speak monad.

That paper has another paper on algebraic effects in its list of references, so it's highly unlikely to be the origin :-)

Re: Algebraic Effects for the Rest of Us

#62

Post by amboo7 »

pwpwp wrote: post #37

Algebraic effects are similar to Common Lisp restart handlers, but in addition, they also receive the continuation of the invoker. This means, you can use algebraic effect handlers to implement higher-order control features like coroutines, probabilistic programming, and nondeterminism (which you can't in Common Lisp). However, what most people get wrong: you do not need higher-order control if you just want to resum…

As CL is programmable, I would not claim "which you can't in Common Lisp".

Re: Algebraic Effects for the Rest of Us

#63

Post by fjfaase »

dan-robertson wrote: post #11
fjfaase wrote: post #6

I doubt if you need any new language construct to introduce this. Could you not simply pass an error handling function/object with all your functions/methods, which is called when an error occurs? This function/object could then resolve the error or throw an exception if it cannot resolve the error. It is possible, and relatively easy, to chain such error handling functions/methods to implement complex error handling…

The article only gives a limited example of algebraic effects. The thing that is required for a condition system (ie good resumable exceptions) is lexical non-local transfer of control and doesn’t need algebraic effects (Common Lisp had a condition system but not algebraic effects in the late 1980s). Lexical non-local transfer of control is effectively the ability to write code which looks like (made up JS like synta…

One type of refactoring is to replace recursion with iteration. You could replace iterate_big_datastructure with an iteration class. I know, it will require dynamic memory allocation. But do not forget, that you can also run out of stack if you allow unlimited recursion. Usually, the heap is much bigger than the stack, especially if you are working with a lot of threads that all require their own stack. In a sense it would be like allocating one chunk of memory and use this for the 'recursive' invocations inside your iterator. An iterator like implementation would also allow you to 'jump' around and restart at a different location.

Re: Algebraic Effects for the Rest of Us

#64

Post by pwpwp »

amboo7 wrote: post #62
pwpwp wrote: post #37

Algebraic effects are similar to Common Lisp restart handlers, but in addition, they also receive the continuation of the invoker. This means, you can use algebraic effect handlers to implement higher-order control features like coroutines, probabilistic programming, and nondeterminism (which you can't in Common Lisp). However, what most people get wrong: you do not need higher-order control if you just want to resum…

As CL is programmable, I would not claim "which you can't in Common Lisp".

The only way to get higher-order control in CL is through whole-program rewriting, e.g. SCREAMER https://www.cliki.net/screamer so I think this qualifies as "can't".

Re: Algebraic Effects for the Rest of Us

#65

Post by codebje »

phoe-krk wrote: post #19

> The best we can do is to recover from a failure and maybe somehow retry what we were doing, but we can’t magically “go back” to where we were, and do something different. But with algebraic effects, we can. This is literally Common Lisp's condition system which a) decouples signaling conditions from handling conditions, b) allows you to execute arbitrary code in the place that signals, c) allows you to stack indepe…

Common Lisp's condition system was first described in '83 for the Lisp Machine in a technical report that's hard to get one's hands on these days. It was described in an MIT AI Labs working paper a few years later by Pitman (https://dspace.mit.edu/handle/1721.1/41474).

Algebraic effects were introduced by Plotkin in 2001 (https://link.springer.com/chapter/10.1007/3-540-45315-6_1) as an extension of Moggi's 1991 work on monads (https://www.sciencedirect.com/science/article/pii/0890540191...), which in turn built on work from the 70s and 80s on understanding computing from the perspective of category theory.

The chief difference, IMO, is that Pitman defined terminology for a language feature in some LISP dialects, while Plotkin showed operational semantics for algebraic effects that are compatible with the denotational semantics (ie, adequacy). Pitman wrote his paper using the AI Labs' practical experience with LISP for the benefit of other LISP practitioners. Plotkin wrote his paper using previous work on lambda calculus and category theory for the benefit of programming language theorists.

Plotkin may have been unaware of CL's conditions system, but since conditions do not have formal semantics, and their behaviour is not particularly useful for probablistic non-determinism (the main thrust of Plotkin's effects article), I doubt that being aware of it would have made him any less motivated or likely to do the work he did.

Dolan et al (https://link.springer.com/chapter/10.1007/978-3-319-89719-6_...) discuss algebraic effects for concurrency in the setting of a dialect of OCaml, and reference CL conditions (amongst other things) as related work. It's a very brief mention observing only that conditions fail to convey the full continuation as a value to handlers, making them unsuited to the use case at hand.

TL;DR: no, conditions aren't the same thing, and if they were, they lack the rigour to be useful without the work that went into algebraic effects.

Re: Algebraic Effects for the Rest of Us

#66

Post by codebje »

phoe-krk wrote: post #41
tiborsaas wrote: post #40

Earlier quoted context omitted.

That's a much nicer, forward pointing comment and it's good to know there's previous act. I've read some bitterness between the lines.

Probably just bitterness from the general trend of reinventing everything in computer science, all the time. People who are unaware of former work on any given topic are forced to reinvent it, poorly. People who are aware of it are forced to watch everyone else reinvent them. Without any sarcasm, communication is a hard and unsolved problem in general.

The irony here is that you appear to be unaware of the former work on algebraic effects, to the point that this one lightweight blog post forms your entire understanding of it and you mistake it for a limited and ill-defined language construct...

Re: Algebraic Effects for the Rest of Us

#67

Post by pron »

I'm far from convinced of the utility of algebraic effects, but if you like them, implementing them in Java (or any Java platform language) would be possible soon thanks to Project Loom [1]. The scoped (ALA multi-prompt) delimited continuations provided by Loom are intended for other uses, but they could also be used to implement algebraic effects.

[1] https://wiki.openjdk.java.net/display/loom/

Re: Algebraic Effects for the Rest of Us

#68

Post by ernst_klim »

konstmonst wrote: post #51

Am I the only one, that thinks that that is not a good feature. Instead A calling B calling C and having a well defined hierarchy and encapsulating complexity you have A calling B calling C calling maybe B calling maybe C again. I mean I see real value in have unidirectional call graphs because they are some much more easier to reason about. I feel like this is another gimmick to break abstractions and increase archi…

Effects are not about calling hierarchy.

Effects are about doing a computation dependent on wider context: IO, thread scheduling, non-deterministic computations, mutable references.

Now, in your example `A calling B calling C and having a well defined hierarchy and encapsulating complexity` you already have effects: threads are being scheduled by OS/runtime, IO is performed, memory cells are written.

The only difference your avg. imperative language with A calling B have is that Effects are implicitly baked into the language, while algebraic effects let you define your own effects as well.

So instead of `async val` you could simply do `(perform Async val)`, which would return val in the context of fiber scheduler (aka will do the necessary scheduling for continuing the computation). With effects you could extend your language with new effectful semantics without descending into metaprogramming hell/fixing the language.

In fact, you could think of Effects as of Monads, but composable.

Re: Algebraic Effects for the Rest of Us

#69

Post by TeMPOraL »

TeMPOraL wrote: post #26
riffraff wrote: post #4

Earlier quoted context omitted.

Smalltalk also had resumable exceptions, and I remember implementing then in ruby too, with callcc, but I think algebraic effects are more general and by focusing on exceptions the author has sort of hidden that, even if he kept saying it's just an example.

Like reikonomusha said, CL's condition system is pretty general in itself. The naming choice isn't an accident - the thing that's being "raised" is a "condition" (of which "error" is just a subtype), and what you do with a condition is "signal" it. In CL, most of the time it's used for exception handling, but I've seen code using this system for tasks not related to errors. As a simple example, you can imagine data p…

I've expanded on this example and added some further thoughts in a blog post: http://jacek.zlydach.pl/blog/2019-07-24-algebraic-effects-yo....

Re: Algebraic Effects for the Rest of Us

#70

Post by dusted »

Interesting sideeffect of Dijkstras rant :)

"Imagine that you’re writing code with goto, and somebody shows you if and for statements."

10 for a = 0 to 10

20 if a = 5 then goto 40

30 next

40 end

50 print "5"

60 goto 30

I lack imagination.

That said, algebraic effects sounds interesting indeed.

Post reply on HN