19 ms·
Coroutines and effects
- nsm 3y agoI am not an expert on this either, although very interested. Note that delimited continuations, which are a superset of coroutines are identical to effects in the sense of yielding control to the handler, not the caller. In languages like Racket/Scheme which allows associating tags with handlers, you can also model the same function having multiple effects. In general, coroutines seem vastly easier to understand/type compared to effects unless your language can do a lot of effect inference.
- angiosperm 3y agoAfter scrutiny this seems to be "Coroutines and Effects" in, particularly, Rust.
- saghm 3y agoGiven that withoutboats is a long-time major contributor to Rust, I suspect they titled the blog post with the audience of regular readers of their blog in mind rather than a more general audience like Hacker News
- steveklabnik 3y agoIt's more than that: https://bsky.app/profile/without.boats/post/3kql3yr3goc23 https://bsky.app/profile/without.boats/post/3kql3yr3goc23 > Btw this is the beginning of me trying to shift away from blogging about rust to blogging about PL design in general. I find that I have very little to say about Rust that I haven’t already said.
- tialaramex 3y agoRight, this is a post which kinda assumes you know Rust, but AFAICT it isn't a post specifically about Rust. In 2014 that would be extremely presumptuous or targeted at a very niche audience, however in 2024 a lot of people know Rust and so it seems much more reasonable.
- bitwize 3y agoIndeed. Rust is the language that the smart kids are using to think about higher-order programming concepts. It has begun to supplant Lisp and Haskell in that regard.
- withoutboats3 3y agoMy reference point is Rust because I've worked on or in Rust for most of the past decade, but I think the relevance of Rust for programming language design more broadly is that it is the most well-typed widely deployed imperative programming language. In this way it has an advantage over Lisp or Haskell if you're trying to think about how we might statically analyze imperative programs, which is what I'm personally most interested in.
- saghm 3y agoInteresting, I hadn't seen that context!
- armchairhacker 3y agoWhat’s the difference between an effect and a “coroutine” where calls in the function body to other coroutines are implicitly yielded? Or is that not a real coroutine? That’s what Kotlin’s `suspend fun` does.
- Rusky 3y agoBoth effects and coroutines can (and typically do) work implicitly across calls like that. The version with forwarding operators like in this post is something of a Rust-ism, or more generally an async/await-ism, or a stackless coroutine-ism. The more fundamental difference between effects and coroutines is that a `yield` in a coroutine always goes to the one unique resumer, and carries a single type of value. On the other hand, an expression may have several effects, each of which may be handled in a different place, in the same way that distinct exception types may be caught in different places.
- rc_mob 3y agoI just upvoted this because I love the domain name.
- mrkeen 3y agoI'm not really understanding the comparison (or isomorphism) between coroutines and effects. Feels like comparing Lists with functions, or promises with interfaces.
- alephaleph 3y agoA coroutine is a computation that can `yield`, suspending itself and passing control back up to the caller. It can then be resumed at the caller's leisure. An function with an effect (in this sense) is a function which can ask a handler to `perform` some effect for it. This suspends the function and passes control to whichever handler is in scope for that call, allowing that handler to resume the function at its leisure. I suspect that you're misunderstanding what is meant by effect, because despite buzz about them and backend support for them in OCaml 5, they aren't yet implemented with syntax and type-level support in any mainstream languages I'm aware of.
- galaxyLogic 3y ago> An function with an effect (in this sense) is a function which can ask a handler to `perform` some effect for it. Why does it need to ask a "handler" to do something, why can't it just call a function that does the "action" for it?
- mrkeen 3y agoBy making effects explicit, you reap the benefit of being able to write non-effectful code. Depending on what your language tracked as an effect, you could make your business-logic always terminate, or perform no allocations, if you had effects for Mutation/GeneralRecursion/Allocation. But no, I certainly don't understand the function->handler control flow here. It has to be handler->function, otherwise you've got two handlers!
- reuben364 3y agoa function will return to it's call site (or diverge), a handler doesn't necessarily have to resume from where it was invoked. There is also (sort of) dynamic scoping, where you don't have to thread the handlers through calls.
- et1337 3y agoWow I’ve been thinking of something exactly like this! Sort of a super charged, statically typed version of Go’s context.Context. It would allow you to describe the capabilities (or effects) of every function, including IO, memory allocation, cancellation, deadlines, concurrency, and whatever application-specific stuff you need on there (like logging). Then you could implement something like Google capslock [0] just by looking at type signatures. 0. https://github.com/google/capslock https://github.com/google/capslock
- ordinaryradical 3y agoDo itttttt :)
- wahern 3y agoSee also aspect-oriented programming (AoP): https://en.wikipedia.org/wiki/Aspect-oriented_programming https://en.wikipedia.org/wiki/Aspect-oriented_programming Algebraic effects might be a little too strict and narrowly defined for something as generic as, e.g., injecting ad hoc logging. With algebraic effects you need to reify in the type system the specific control flow behaviors you care about, and then get code to use those types and operators accordingly. AoP seems like a higher-level (if looser) concept that isn't necessarily specifically bound to the particular details of the type system. That modeling freedom seems necessary unless you're creating a language from scratch or confining yourself to a very limited set of control effects that can be shoe-horned into the existing type system and control flow operators.
- valcron1000 3y agoYou already have something like this (production ready) through effect systems in Haskell (ex. https://hackage.haskell.org/package/effectful https://hackage.haskell.org/package/effectful)
- bandrami 3y agoLike clockwork, every few years, smart people will re-invent introspection.
- amluto 3y agoThis touches on something I’d like to see in more mainstream languages, but it doesn’t quite get there. > For example, Koka has a “diverging” effect, which means that an expression may diverge (that is to say, it may not finish evaluating). An expression containing a diverging expression is also diverging. So you can distinguish in the type system between a function that is guaranteed to finish and a function that may not finish (this is imperfect, of course, because of the undecidability of the halting problem; some functions that do not diverge will be marked diverging). As I think about it (and I’m not a programming language theorist, nor have I done much serious work in any language with any sort of effect system), there are two vague categories of effect: control-flow effects like exceptions, yields, async waits (Pending, sleep, or however you feel like modeling it) and non-control-flow effects (divergence, various forms of unsafety, nondeterminism, impurity, reads or writes of global state, syscalls in models that don’t treat IO in and of itself as an effect), etc. I would like to be able to run and write code that is definitely free of certain kinds of effects. Xz should not be unsafe or do IO, for example. Leftpad is an entirely pure, non-diverging function. And I should be able to ask my language to enforce that, ideally with trivial code. Maybe even by default. But mainstream languages seem to mostly limit their use of effect-like systems on the control flow part, like this: > Overall, coroutines strike me as the most promising way to handle many kinds of effectful functions because they seem to be in the design sweet spot: They are statically typed, lexically scoped, and unlayered.
- noelwelsh 3y agoThis is one of the motivations of algebraic effects: you can have fine grained control over which effects are allowed.
- Rusky 3y agoThere are two aspects to effects as a language feature- first there is the runtime behavior, and then there is the type system. Ruling out categories of effects is the job of the type system, and you don't have to commit to (or avoid) any particular runtime approach to use it that way. This is related to the vagueness of your two categories. While exceptions, yields, and awaits don't really make sense without a handler, all that matters to the type system is which operations an expression might perform in addition to producing a result of their primary type. Handlers only interact with the type system in the sense that they remove an effect from their handle-ee expression. So even in a language that committed to coroutines as its approach handling effects at runtime, the type system could still track and rule out effects like divergence or system calls. (For what it's worth, nondeterminism, state, etc. can all also be defined in terms of handlers. And at the same time, though, unsafety is not an effect because it is not entirely captured by "can this expression perform operation X.")
- Avi-D-coder 3y ago> understand when the effect occurs requires examining the type signature of every function that is called. Since this is meaningful control flow, it seems very valuable to be able to identify points at which an error occurs without examining the signatures of each function call. This is currently the case in rust. IO and other effects are frequently implicit. You don’t have to use ? or await they are *sugar. I have frequently seen reinventions of exceptions, unwind nonsense, adhoc interpreted tagged effects, etc.. Explicit syntax for effectfull calls should not be a goal. We don’t actually have that today.
- skavi 3y agoI think it’s incredibly useful today to have both of these annotations. I frequently scan for all instances of `?` or `.await` in functions (though, unfortunately, for various reasons this won’t show you everywhere these effects are produced). I would rather not have to rely on an IDE to get that functionality.
- jeffparsons 3y ago> The key difference between coroutines and effect handlers is that coroutines yield control to their caller, but effectful expressions yield control to their handler. The difference of affordance this implies is the materially significant advantage of coroutines over effect handlers. Should that last bit be: "advantage of effect handlers over coroutines"? EDIT: Oh, maybe I should have read the rest of the article first. It might be going the other way than that one example suggested. :)
- kodablah 3y ago> Overall, coroutines strike me as the most promising way to handle many kinds of effectful functions This is basically what we do at Temporal, which is essentially deterministic coroutines with externalized effects. This gives another nice property: using coroutines to wrap effects lets the non-effect logic replay/resume durably.
- orthoxerox 3y ago> as far as I understand it is not possible to meaningfully handle the diverging effect I don't know if that counts, but I think `call_with_timeout(duration, function_that_diverges, timeout_return_value, args...)` handles the diverging effect of its function argument.
- withoutboats3 3y agoThe difference of this and an effect handler fwiw is that it doesn't handle it totally - it handles the divergence effect but then produces a partial function.
- orthoxerox 3y agoWhy does it produce a partial function? If the argument is total other than divergence, call_with_timeout fills in all "holes" in the set of all possible returns with default values.
- withoutboats3 3y agoI'm assuming your language has types which don't have default values because default values for every type are a billion dollar mistake that no modern language should have.
- mitt_romney_12 3y agoI'm assuming `timeout_return_value` would be a user provided value that serves as the default. But most effect systems also support a `return` effect that lets change the return type of a function [1]. So you could make it return `Just<result>` when it succeeds or `Nothing` when it hits the timeout. [1] https://koka-lang.github.io/koka/doc/book.html#sec-return https://koka-lang.github.io/koka/doc/book.html#sec-return
- reuben364 3y agoThat'd almost be partial functions with extra steps. Take the Klesili category with the Maybe Monad,and you get partial functions. Unless you are manually matching on the the Maybe, and thus observing the timeout, then that isn't the case. You'd probably also want a nondetermism effect which cannot handle unless you specifically build your timeouts to be deterministic, which I think Lean 4 does, but you can't go from partial to total with it afaik.
- fire_lake 3y agoI’m personally betting big on OCaml due to the effect system work. I think this is one of the next big advances in industrial programming. - Lambdas (mainstream) - Static types (mainstream) - Pattern matching (getting there) - Sum types (getting there) - TCO (getting there) - Global type inference (future) - Functors (future) - Effect systems (future) - Expression orientated (future) With OCaml, I get all of this today. The future is here, it’s just not evenly distributed…
- dureuill 3y agoGlobal type inference is not a positive in my book. In my experience it becomes very hard to understand the types involved if they are not explicit at systems boundaries. I can also imagine that it must be hard to maintain, like sometimes the types must accidentally change
- fire_lake 3y agoThere’s a trade off - was the mistake here or there? The type checker cannot know. But for those few cases you can add an annotation. Then the situation is, in the worst case, as good as when types are mandatory.
- dureuill 3y ago> But for those few cases you can add an annotation. not in other people's code. My main concern is that gradual typing makes understanding other people's code more difficult. Idiomatic Haskell warns against missing signatures[1], Rust makes them mandatory. Rather than global inference, local inference stopping at function boundaries is the future, if you ask me. [1]: https://wiki.haskell.org/Type_signatures_as_good_style https://wiki.haskell.org/Type_signatures_as_good_style
- fire_lake 3y agoHuh? If you are consuming code you can’t change from someone else, then I presume this is a published package? Then the IDE will tell you the types.
- grumpyprole 3y ago> but he made me realize that effect systems (like that found in Koka) and coroutines (like Rust’s async functions or generators) are in some ways isomorphic to one another. It's a shame this was not explored before going down the Async route. I believe Effect handlers would have been a better fit for a systems language. IMHO a Monadic approach really needs something expressive like a functional language in order to work well.
- gpderetta 3y ago> what if it was dynamically scoped…. but statically typed…………..? That's the right insight. Just give me implicit parameters (i.e. the statically typed versions of dynamic scoping). I'll build my own effect system, coroutines, exception and what not as needed.
- solidninja 3y agoIndeed - I do not think it is a coincidence that a lot of production experiments in effect systems are happening in Scala right now - the language is very flexible to conduct them. https://github.com/getkyo/kyo https://github.com/getkyo/kyo in particular looks interesting as it explores a different space where the monadic nature is less exposed to the end user.
- ufo 3y agoThis classification seems somewhat Rust-centrict. The terminology I'm more used to seeing for coroutines is this: Symmetric vs assymetric coroutines: symmetric coroutines are the original style, where the currently executing coroutine decides who to transfer control to. Assymetric coroutines have a caller and a callee and the callee always yields control back to the caller. (This is much more common today) Stackful vs stackless coroutines: in a stackless setting the language distinguishes between synchronous and asynchronous functions. This is what Python and Rust generators do. In a stackless setting (such as Lua), every function can potentially yield or call a sub-function that yields. Exception handling is somewhat similar to stackless coroutines, specially in languages such as Common Lisp where the exception handler can choose to resume execution from the point that raised the exception, instead of unwinding the stack.
- samatman 3y ago> symmetric coroutines are the original style This isn't quite correct, but it's close. The original style were co-routines, as distinguished from subroutines, this was when programming was still heavily goto-oriented, these were little more than patterns used to structure go-to. Simula, if I recall correctly, was the first high-level language to have coroutines, and they were basically asymmetric. I say basically because there was a mechanism for a coroutine to replace itself with another coroutine, but it wasn't a general transfer mechanism. Not unlike a delimited continuation in fact. Good summary of how it all works however! I believe this is a typo: > In a stackless setting (such as Lua) Since Lua is stackful, and you're contrasting it with stackless generators.
- ufo 3y agoyup, was a typo >_<
- gpderetta 3y agoI don't see how exception handling is similar to stackless coroutine as it is very non local.
- 3y ago
- codethief 3y agoCan anyone explain what exactly the author means by "dynamically scoped" vs. "lexically scoped"?
- jbjohns 3y agohttps://github.com/Chalarangelo/30-seconds-of-interviews/blob/master/questions/lexical-vs-dynamic-scoping.md https://github.com/Chalarangelo/30-seconds-of-interviews/blo... Exception handling, for example, uses dynamic scoping since you don't know what will be handling your exception when you write code which throws it. Another way of thinking about it is, with dynamic scoping the value of the dynamic variable must always be on the stack and the closest one is the value that will be used. This is a really good behaviour for global variables since a common source of bugs is some global variables (and I'm considering class members "global" for this) getting changed unexpectedly. If the variable is lexical then it can be very hard to figure out what changed the value (especially when threads are involved) but if the variable is dynamic it's easy: the culprit is in the stack trace.
- codethief 3y agoJust noticed your comment now: Thanks so much for the explanation! However, my question was more about the blog post in particular, i.e. coroutines (async/await) vs. effect handlers: I still fail to see why coroutines are lexically scoped. async/await yield control back to the calling function which might or might not define an event loop or yield control to another function further up the stack. How is this different from handling effects or exceptions? Whose scope does "lexically scoped" refer to here? EDIT: Ah, reading this comment[0], > The more fundamental difference between effects and coroutines is that a `yield` in a coroutine always goes to the one unique resumer maybe I thought too much of Python where async/await are implemented via generators and, unless I'm mistaken, there need not be a unique resumer/event loop. [0]: https://news.ycombinator.com/item?id=40108636 https://news.ycombinator.com/item?id=40108636