Live data from Hacker News

Effective Concurrency with Algebraic Effects in Multicore OCaml

kcsrk.info

41–50 of 63 posts

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#41

> 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

Monads 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/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."

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#42

> 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

Monads 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/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…

That doesn't really explain how they relate to the OP

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#43
post #31

Wow 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

For 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 lib…

FYI, OCaml also has library-level async/await implementations (e.g. Lwt), and something similar to computation expressions (let-operators).

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#44

I 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 j…

Adding 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://users.scala-lang.org/t/from-scala-monadic-effects-to...

https://dl.acm.org/doi/pdf/10.1145/3122975.3122977

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#45

I 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 j…

Java has always had checked exceptions, a weak form of type-checked effect. They were controversial because developers didn't like being forced to handle them, but I always thought they were a great idea. Algebraic effect handlers just generalise the idea of an exception, by providing a continuation that can be called to resume execution.

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#46

> 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

Doing 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.

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#47
Thanks 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?

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#48
post #46

> 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

Doing 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., "th…

Great context, thanks

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#49

Thanks 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…

I 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?

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#50

Thanks 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…

You wouldn't be able to use normal code, ie. loops, if statements, pattern matching etc. What you're trying to describe is monad'ish like promise or simply callbacks. Algebraic effects are much more general, code is normal sync like code, you can have async/await semantics without function coloring, you can customize code with dependency injection like behaviour ie. you can define logging effect in your library without specifying which logging library your user has to use as caller can customize it etc. It's not as much type system extension as new language construct – it's simply try/catch'ish yield burrito :)
Post reply on HN