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

Effective Concurrency with Algebraic Effects in Multicore OCaml

kcsrk.info

Post reply on HN
Print view View original

51–60 of 63 posts

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#51

Post by infogulch »

grumpyprole wrote: post #45
infogulch wrote: post #32

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.

The problem with Java exceptions is that they are used to paper over the lack of multiple return values for totally mundane situations where there are genuinely multiple possible outcomes. "tried to open file that doesn't exist", "tried to open a socket to a domain that couldn't be resolved", "user doesn't have permission to perform that action", etc, are normal failures not exceptional. But all of these totally normal outcomes are mediated by the same language feature that also deals with indexing past the end of an array or dereferencing null, both of which are clearly program bugs. That's why checked exceptions were controversial: they were a noisy workaround for proper language tool to manage multiple outcomes. Go takes a small step towards fixing this by making packing and unpacking tuples easy and normalizing returning an error as the last tuple value; rust and other languages with discriminated unions and an integrated match actually solves this.

I guess if it helps you understand typed effects if you describe it as "java checked exceptions with an option to resume" then I'm glad that works for you, but for me, Java exceptions have so much other baggage surrounding their design that I would prefer describing it from the other direction: "typed effects would enable you to implement a host of cross-stack features, including a checked exception system like Java's".

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#52

Post by mirekrusin »

brundolf wrote: post #40

I'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 adv…

Yes, 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.

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#53

Post by devmunchies »

flyingchipmann wrote: post #37

Is this what Dan talked about in react hooks origins? https://overreacted.io/algebraic-effects-for-the-rest-of-us/

thanks for posting this. It helped me understand ocaml algebraic effects by comparing it to React hooks and React context.

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#54

Post by dan-robertson »

dan-robertson wrote: post #49
gpderetta wrote: post #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…

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?

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

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#55

Post by gpderetta »

dan-robertson wrote: post #54
dan-robertson wrote: post #49

Earlier quoted context omitted.

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?

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

It is not like a continuation, it is exactly a (typed) continuation, or better, an infinite list of continuations (invoking the continuation yields, in addition to a possible value, the next continuation in the stream).

In your example of reading an int the EffectHandler and Effect are simply switched (better names are sink and source). And yes, for IO you will need a scheduler, but streams are much more straightforward.

I have reached my limit of pure functional language knowledge, but I can offer you a working implementation [1] in an imperative language.

I've actually implemented these typed continuations in c++ years ago, and I'm trying to understand how they differ from effects (aside for the whole imperative thing).

In the C++ implementation, for convenience the continuation object is replaced with the next continuation when invoked, but internally actually invoking a continuation function returns the yielded value and the next continuation as for my EffectHandeler example.

https://github.com/gpderetta/libtask/blob/master/tests/conti...

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#56

Post by gpderetta »

mirekrusin wrote: post #50
gpderetta wrote: post #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…

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

See my reply to the siblings comment with the working c++ example. The call to the effect function is not a tail call: the effect function will eventually resume its caller, providing the next continuation to call. Definitely there is no colored function problem. So you will be able to yield from a for loop just fine.

As far as I understand effects are similar to delimited continuations in the way the effect handler is found via dynamic scoping, but in addition there is an extension to the type system to guarantee that at least one effect handler of the correct type handler is in place.

So I'm wondering if it wouldn't it be better, or at least equivalent , to simply pass the continuation around (i.e with lexical scope) as a first class value and attach the effect type to it, obviating the need for an ad hoc type system extension.

I'm must be missing something and there must be some use cases that can't be easily expressed this way.

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#57

Post by valenterry »

lilactown wrote: post #33
valenterry wrote: post #29

Earlier quoted context omitted.

This has nothing to do with the JVM. Scala for example is already capable of exactly what Erlang/Haskell do. This is merely about the language Java, which lacks support for to make such a programming style ergonomic. You either need a language with very powerful type-system or a dynamically typed language. (or specific support for it, like in Go, but even in Go you are limited to what the language designers forsaw) P…

Project Loom is both about the JVM and the language Java. Most of the work for Loom AFAICT is at the JVM level, and the benefits are that all Java code will Just Work(TM) with the new primitives underneath them at the end. Scala’s varied async/concurrency libraries are implemented in user land, and still use threads underneath. Mechanically, you must opt in to these and have to work to interop with code that might us…

Everything you say is correct, but it can create a misunderstanding, so I want to elaborate for other readers:

Concurrency is not mainly about threads or performance, it is about program behavior semantics. Loom does not do anything about that, it "merely" improves performance. Well, you could say it actually makes semantics worse (you used (TM) for good reasons).

In that sense, I believe that Scala or any language with good concurrency semantics will benefit from Loom more than Java, unfortunately. But Java can of course still catch up on a language level. Even after such a long time, there are still new and interesting libraries (e.g. looking at JOOQ).

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#58

Post by grumpyprole »

infogulch wrote: post #51
grumpyprole wrote: post #45

Earlier quoted context omitted.

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.

The problem with Java exceptions is that they are used to paper over the lack of multiple return values for totally mundane situations where there are genuinely multiple possible outcomes. "tried to open file that doesn't exist", "tried to open a socket to a domain that couldn't be resolved", "user doesn't have permission to perform that action", etc, are normal failures not exceptional . But all of these totally nor…

I am not advocating Java the language and it's shortcomings are really the topic of another thread. I am also not seeking to understand algebraic effects starting from Java, I've read the original Eff paper and would encourage others to do so. I raised them only as an example of a form of type checked effect that is already in widespread use.

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#59

Post by kwhitefoot »

iamwil wrote: post #38
kwhitefoot wrote: post #36

It would be handy to have a bit of explanation about what the term algebraic effect means.

You weren't the target audience of the post. But I found this helpful: 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/

Thanks.

Re: Effective Concurrency with Algebraic Effects in Multicore OCaml

#60

Post by scns »

gpderetta wrote: post #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…

Enjoyed your post, except that one superfluos, harsh self deprecating word.
Post reply on HN