13 ms·
Effective Concurrency with Algebraic Effects in Multicore OCaml
- xvilka 5y agoSee also the actual roadmap[1] to the OCaml 5.0 - the first version of OCaml with Multicore upstreamed. [1] https://discuss.ocaml.org/t/the-road-to-ocaml-5-0/8584 https://discuss.ocaml.org/t/the-road-to-ocaml-5-0/8584
- jhoechtl 5y ago> Note that OCaml 5.0 focuses on minimal (solid) support for the multicore runtime system, and will not provide stable user-facing concurrency and parallelism libraries. Wouldn't hold my breath
- mirekrusin 5y agoProgress + report on OCaml multicore has been exceptionally well done for many months [0]? Quite big piece of work, impressive to see it materialising as general public availablity. I wouldn't be worried about higher level abstrations at this stage. Well done runtime part is the most important now. [0] https://discuss.ocaml.org/search?q=Multicore https://discuss.ocaml.org/search?q=Multicore
- square_usual 5y agoEffectful concurrency feels so different from the async/await model I'm used to, but I'm really looking forward to playing around with it when OCaml 5 drops. Does anybody here have a more "ELI5" tier guide to it?
- sadiq 5y agoThomas Leonard did a great talk on our experiences with effects at the OCaml Workshop this year: https://watch.ocaml.org/videos/watch/74ece0a8-380f-4e2a-bef5-c6bb9092be89 https://watch.ocaml.org/videos/watch/74ece0a8-380f-4e2a-bef5... Also you can start playing with effects today using the 4.12+domains branch on https://github.com/ocaml-multicore/ocaml-multicore https://github.com/ocaml-multicore/ocaml-multicore
- d3nj4l 5y agoThanks for the links, that was a very succinct talk and made me excited to try it out. Just one follow-up question: the 4.12+domains branch doesn't include support for the try syntax for handling effects, correct?
- sadiq 5y agoCorrect. The 4.12+domains branch has effect handlers without syntactic support (which is what will be in 5.0), the 4.12+domains+effects has the syntax.
- rstarast 5y ago(2015)
- deleted 5y ago[deleted]
- johnnycerberus 5y agoIsn't Java capable of the same thing now that it has algebraic data types with records + sealed classes + pattern matching? Given that Java already has a fine concurrency story, isn't OCaml a hard sell to someone that's not into compiler development to depend on its rich ecosystem?
- wtetzner 5y agoAlgebraic data types are not the same as an algebraic effects system.
- johnnycerberus 5y agoJava's checked exceptions can be considered an effect system and coupled with ADTs I suppose we can call it an algebraic effects system. I mean the domino effect in which the exception has to be handled in each method that calls that is what seems to me the effect/handler counterpart that is present in Java. In the end an algebraic effect is just an extension of a type system that supports ADT, or is my memory from university failing me now.
- deleted 5y ago[deleted]
- octachron 5y agoYou cannot resume a computation with exceptions. At most, exceptions are a subset of effects. Similarly, a lot of the issues with checked exceptions in Java come from the lack of exception polymorphism in the checked exception type system. Adding the two points, you cannot really call checked exceptions an effect system.
- nsonha 5y agonot to mention that exceptions as flow control is frowned upon in java, so while there are similarities, they are different in designation.
- 5y ago
- saltmeister 5y agouseless
- dgan 5y agoWow Algebraic Effects are a totally new thing i never seen mentionned so far I always thought that async /await was the best known way to handle resumable computation Totally blew my mind
- Smaug123 5y agoFor more mind-blowing stuff, try learning F#, where async/await as a language feature is something you could implement entirely in user-space (though of course you need to access the .NET APIs if you want to implement parallelism). F# has "computation expressions", which allow you to define syntax for fully-general "monad-like things", and the built-in `async` computation expression is just a part of the standard library and is defined using that mechanism. I imagine exposure to algebraic-effects systems must make one feel the same way: like it's such an awful hack when a language has to have async support baked into its syntax!
- yawaramin 5y agoFYI, OCaml also has library-level async/await implementations (e.g. Lwt), and something similar to computation expressions (let-operators).
- infogulch 5y agoI first encountered Algebraic Effects in Unison where they're called "abilities" [0] via the strangeloop talk from 2 years ago [1]. Just from the little I've seen of it I feel like AE is a fundamental abstraction tool that's been missing in programming language design. "Fundamental" as in the same level as function arguments. So many problems that were solved with myriad complex programming language constructs are just absorbed as a trivial user-implementation with an effect system: exceptions, sync vs async, dependency injection, cancellation tokens, dynamic contexts... all of these problems where the essential complexity is a need to have an effect that cuts through the function call stack. I'm not saying that all our problems are solved and the programming world will now be rainbows and butterflies, I'm just saying that this feature is the correct framing and abstraction for issues we've run into many times in the past, and it has the potential to greatly simplify and unify the hacky, bespoke, situational solutions we've found. [0]: https://www.unisonweb.org/docs/abilities https://www.unisonweb.org/docs/abilities [1]: https://youtu.be/gCWtkvDQ2ZI https://youtu.be/gCWtkvDQ2ZI
- thesz 5y agoAs I keep saying, what is a language feature in other languages, is a library in Haskell: https://hackage.haskell.org/package/effect-handlers https://hackage.haskell.org/package/effect-handlers And this is how it should be. Not a language feature, but library. Dealing with language feature you deal with compiler and may affect more people than needed, with library you can use (and extend) it as you wish.
- resoluteteeth 5y agoHaskell is probably going to need to get some language features for extensible effects to have acceptable performance (e.g. the unmerged work on eff).
- georgehm 5y agoAdding some more related articles. this was mostly a result of me trying to find some more useful articles to better understand and it was lost in my browsing history. https://overreacted.io/algebraic-effects-for-the-rest-of-us/ https://overreacted.io/algebraic-effects-for-the-rest-of-us/ https://users.scala-lang.org/t/from-scala-monadic-effects-to-unison-algebraic-effects/5882 https://users.scala-lang.org/t/from-scala-monadic-effects-to... https://dl.acm.org/doi/pdf/10.1145/3122975.3122977 https://dl.acm.org/doi/pdf/10.1145/3122975.3122977
- kwhitefoot 5y agoIt would be handy to have a bit of explanation about what the term algebraic effect means.
- iamwil 5y agoYou weren't the target audience of the post. But I found this helpful: https://www.youtube.com/watch?v=hrBq8R_kxI0 https://www.youtube.com/watch?v=hrBq8R_kxI0 As well as this post, which relates react hooks to algebraic effects. https://overreacted.io/algebraic-effects-for-the-rest-of-us/ https://overreacted.io/algebraic-effects-for-the-rest-of-us/
- kwhitefoot 5y agoThanks.
- flyingchipmann 5y agoIs this what Dan talked about in react hooks origins? https://overreacted.io/algebraic-effects-for-the-rest-of-us/ https://overreacted.io/algebraic-effects-for-the-rest-of-us/
- devmunchies 5y agothanks for posting this. It helped me understand ocaml algebraic effects by comparing it to React hooks and React context.
- brundolf 5y ago> allowing the programmer to separate the expression of an effectful computation from its implementation How does this compare with IO monads? Seems like they accomplish roughly the same goal
- petalmind 5y agoMonads are too specific, a lot of things that they are used for could be represented by weaker constructs such as Applicative. See e.g.: https://www.microsoft.com/en-us/research/publication/desugaring-haskells-do-notation-into-applicative-operations/ https://www.microsoft.com/en-us/research/publication/desugar... "Furthermore, 10,899 (28.0%) were fully desugared into Applicative and Functor combinators and thus would not require a Monad constraint." б) "The Haxl codebase at Facebook. [...] and 7,600 (26.9%) were fully desugared into Applicative and/or Functor."
- brundolf 5y agoThat doesn't really explain how they relate to the OP
- T-R 5y agoDoing things in an IO monad, you don't distinguish much between types of effect, everything's just in IO, and you just execute the action when you run into it, which means that you don't have, e.g., lookahead to see if you can do one batch request instead of 10 individual requests. There have been a few attempts to address these - Monad transformers allow you to separate types of effects (so you can specify e.g., "this code only needs environment variables, not database access"), and, at least at compile time, select a different implementation for each effect. In Haskell, at least, though, they have a drawback of needing to define typeclass instances (interpreters) for every concrete monad stack (basically explicitly describe how they interact with each other - the n-squared instances problem. In practice, there's a bunch of template code to help mitigate the boilerplate). Somewhat relatedly, Haxl, in an attempt to optimize effects, introduced a compiler change to identify less dynamic code (code that only needed Applicative), and Selective Functors, to allow for more optimization based on what's coming next. Algebraic Effects (assuming I'm not incorrect to conflate them a bit with free effects/extensible effects) make things more dynamic, so you're instead effectively building the AST you want, and separately interpreting it at runtime. This should let you look at more of the call tree to decide on an execution plan. Since you'd also not be relying solely on the typeclass mechanism to pick an interpretation strategy, you should also be able to more easily describe how the interpreters compose, saving you from all the boilerplate of the transformers approach.
- brundolf 5y agoI've actually been playing with a similar idea in JavaScript, having pure functions generate "Plans" for async actions which are then executed later by other code. They can be thought of as Promises that haven't happened yet. A neat side-effect (no pun intended) of doing things this way is that, unlike Promises, Plans can be stored as constants (or cached) and re-used multiple times. I'm sure it's nowhere near as advanced or flexible as the OP, but it seems to be in the same general spirit
- mirekrusin 5y agoYes, you "can" somehow emulate it with async generators everywhere but your js code will look more like brainfuck than js. It really requires language construct, similar to how yield, try/catch or pattern matching can be simulated without those constructs but it's going to be total disaster with no language support.
- gpderetta 5y agoThanks for the article. OCaml has long been on my short list of languages to learn, and continuations are an hobby of mine. I'll have to dig into this deeper. If someone has experience with algebraic effects, I have a question to ask. Why are they needed at all as a type system extension and why can't they just be represented with function types? (excuse my Haskell pseudocode, I'm just a filthy C++ programmer abusing the notation I don't really know the language, also don't assume lazy semantics): newtype Effect a = Effect (a -> Effect a) newtype EffectHandler a = EffectHandler (() -> (a, EffectHandler a)) A function with an effect would have an explicit Effect parameter, while an effect handler would take an EffectHandler as a parameter (and return it as well). You could also add phantom types if you really need to distinguish different effects beyond 'a. The only magic would be in the function that creates the continuation: typed_callcc1 :: (Effect a -> Effect a) -> EffectHandler a Of course you could generalize Effect and EffectHandler into a bidirectional typed continuation: newtype Cont a b = Cont (a -> (b, Cont a b)) I don't pretend to fully understand algebraic effects but from what I see they are pretty much equivalent, except that there is no explicit effect parameter, just the type (so the continuation is not exactly first class and it is logically passed implicitly). For similar reasons, I think you can't hide them in a closure. What is the gain? What am I missing?
- dan-robertson 5y agoI think I don’t understand your types. The Effect type you define appears to be, essentially, a function that takes infinitely many arguments of type a. Let’s imagine two simple effects. One prints a string (I’ll call this ‘printer’) and one reads an int entered by the user (let’s call it ‘reader’) In this case, how would those effects be modelled with the types you wrote?
- dan-robertson 5y agoI think I have a slightly better idea: the type you call Effect is like a continuation not an effect and so to print a string you have print :: String -> Effect () -> Effect () hello () = fst (typed_callcc1 (print “Hello”) ()) And I guess the type of reading an int is: input_int :: () -> Effect Int -> Effect Int But it still isn’t obvious to me. If you want that IO to be asynchronous then how will you return the Effect Int (by calling the argument with the input) from input_int? I suppose the answer is that you implement a scheduler but I can’t work out how you want the details for yielding to work.
- nextaccountic 5y agoSomething I rarely see addressed: why was multicore ocaml blocked on having full-fledged effects? Couldn't multicore have landed years ago, and then gradually insert effects in the language?
- pjmlp 5y agoI guess to avoid nuking the ecosystem Python 3 style.
- LeonidasXIV 5y agoWhich also didn't add multicore support, it still has a GIL. But it has been an extremely valuable lesson for other systems, so there's tha.
- sadiq 5y agoMulticore upstreaming wasn't blocked on having fully-fledged effects. If you look at the diff between multicore 5.00 and trunk OCaml, the changes required for fibers is pretty small relative to the multicore GC and making the rest of the runtime thread-safe. The original plan was to upstream only the multicore GC. This was sped up on the suggestion of the core developers and now 5.0 will bring parallelism and effect handlers (though without syntactic support for the latter). https://discuss.ocaml.org/t/multicore-ocaml-september-2021-effect-handlers-will-be-in-ocaml-5-0/8554 https://discuss.ocaml.org/t/multicore-ocaml-september-2021-e... has a good explanation of effect handlers, syntax and what will be available in 5.0.
- solmag 5y agoSeems to me this multicore journey was quite a barn burner; might as well have gone all the way to linear types as your GC.