6 ms·

Implementing Algebraic Effects in C

150 points by necrodome 9y ago

ambulancechaser 9y ago
the authors cite Matija Pretnar who has an introduction on [algebraic effects](http://www.eff-lang.org/handlers-tutorial.pdf http://www.eff-lang.org/handlers-tutorial.pdf). I'm reading through it now as I have no idea what is going on :)
- gbrown_ 9y ago
  Thanks for the link! I'm in the same boat.
rraval 9y ago
This is super interesting and I'm still going through the paper. For folks with a "Cool, but why" reaction, the introduction elaborates: For example, the P language [10] is a language for describing verifiable asyn- chronous state machines, and used for example to implement and verify the core of the USB device driver stack that ships with Microsoft Windows 8. Compiling to C involves a complex CPS-style transformation [19, 26] to enable async/await style programming [5] with a receive statement – using the effects library this transformation is no longer necessary and we can generate straightforward C code instead. Similarly, we hope to integrate this library with libuv [29] (the asynchronous C library underlying Node [43]) and improve programming with libuv directly from C or C++ using async/await style abstractions [12, 27] Since the linked abstract doesn't actually mention this practical application, consider this comment as a goad to encourage more people to click through to the paper :)
- zengid 9y ago
  It should be noted that the previous sentence before your quote is: "For now, we mainly see the library as a target for library writers or compilers."
  - mannykannot 9y ago
    Your caveat is well-taken, but you can learn a lot from what is done in these fields.
- Matthias247 9y ago
  Couldn't these kind of goals also be reached with the upcoming C++ coroutines (also pioneered by Microsoft)? I remember some presentation that those (or at the least the LLVM implementation underneath it) could also be used for C.
deleted 9y ago
[deleted]
frankpf 9y ago
A little off-topic, but the author of this paper (Daan Leijen) is also the author of Koka[1], a programming language with algebraic effects. IMO, Koka (or something similar) has more potential to become a mainstream language than "traditional" FP languages (Haskell, OCaml, Idris, etc.). Effects seem to be easier to understand than monads (at least on a superficial level) and more modular (I don't have a lot of experience with Haskell, so take that with a grain of salt). Its syntax is also very close to C-like languages. Taken from the Koka book[2]: fun square1(x : int) : total int { return x*x } fun square2(x : int) : io int { println( "a not so secret side-effect" ) return x*x } `square1` is a pure mathematical function, so its effect is `total`. `square2` has a side-effect because of `println`, so its effect is `io`. This means that `square2` can raise exceptions, not terminate, be non-deterministic, read and write to the heap, and do any input/output operations. Note that Koka can infer effects, so these annotations are optional. [1]: https://www.microsoft.com/en-us/research/project/koka/?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fprojects%2Fkoka https://www.microsoft.com/en-us/research/project/koka/?from=... [2]: https://koka-lang.github.io/koka/doc/kokaspec.html#sec-effect-types https://koka-lang.github.io/koka/doc/kokaspec.html#sec-effec...
- chenglou 9y ago
  Fwiw, OCaml algebraic effects are being implemented: http://kcsrk.info/ocaml/multicore/2015/05/20/effects-multicore/ http://kcsrk.info/ocaml/multicore/2015/05/20/effects-multico... (And then there's https://reasonml.github.io https://reasonml.github.io, which I work on)
  - frankpf 9y ago
    Hey there, Reason is a great project! Thanks for working on it! I actually tried to use it very recently in a new project at my workplace, but unfortunately I decided not to. I found some fundamental things were lacking. I didn't find documentation about how to interact with npm libraries (e.g. how do I use a websockets library in Reason? Do I have to create my own bindings? If so, how?). There also seemed to be nothing similar to async/await in Reason/Bucklescript yet and I couldn't find out how to use promises. I'll definitely reevaluate it in the future. I think it is an awesome project with great potential (along with Bucklescript which is awesome too).
deleted 9y ago
[deleted]
lindig 9y ago
Algebraic effects are a hot topic. The name sounds fancy but maybe this intuition helps: an effect is like an exception where the exception handler receives enough information to resume the computation from where it was called. Just like exceptions, effects are dynamically scoped: the handler is always found up in the call stack.
- larsbrinkhoff 9y ago
  Cue smug lispers.
daanx 9y ago
Hi, I am the author of this report -- thank you for the interest :-) Just wanted to add that you can find the library at: https://github.com/koka-lang/libhandler https://github.com/koka-lang/libhandler The `dev` branch contains a sample of `libuv` integration. There is still a lot to be done in terms of creating a better interface and providing implementations of standard effects but the core is working quite well by now. Enjoy!
cryptonector 9y ago
If all you want is generators and co-routines, then there's a lot of literature on this for C. The original Icon compiler compiled to CPS C. That was pretty cool. One can do much of what Icon did using GCC local functions and computed gotos to get something much closer to not-CPS. There's Simon Tatham's PuTTY, which uses his co-routine macros, which are an extravagant meta-programming macros around a Duff's device. He also has an extensive set of meta-programming macros as well, not related to co-routines. Some Schemes compile to C code where all functions always return immediately, but what they return is a continuation, and the top-level is a for(;;) { next = next(); }. EDIT: I'm particularly fond of PuTTY. Its SSHv2 implementation all the way up to the end of authentication is a single, huge function. It looks completely synchronous, but it's not, because it's actually a co-routine. As a result, and in spite of being a single huge function, it's actually quite readable.
- daanx 9y ago
  I tried to cite much related work on co-routines and threading libraries in C -- including Simon Tatham's page on co-routines in C [1] -- But I was not yet aware of the work on Icon nor did I know co-routines were used in PuTTY -- thanks! Although now that I reread Simon's page I see he actually mentions PuTTY explicitly :-) As an aside, I feel algebraic effect handlers are safer to use than most coroutine or shift/reset implementations because they offer more structure. As put by others: "Algebraic Effects+Handlers" are to "delimited continuations" as "while" is to "goto" [1]: https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

150 points by necrodome 9y ago

the authors cite Matija Pretnar who has an introduction on [algebraic effects](http://www.eff-lang.org/handlers-tutorial.pdf http://www.eff-lang.org/handlers-tutorial.pdf). I'm reading through it now as I have no idea what is going on :)

gbrown_ 9y ago
Thanks for the link! I'm in the same boat.

rraval 9y ago

This is super interesting and I'm still going through the paper. For folks with a "Cool, but why" reaction, the introduction elaborates: For example, the P language [10] is a language for describing verifiable asyn- chronous state machines, and used for example to implement and verify the core of the USB device driver stack that ships with Microsoft Windows 8. Compiling to C involves a complex CPS-style transformation [19, 26] to enable async/await style programming [5] with a receive statement – using the effects library this transformation is no longer necessary and we can generate straightforward C code instead. Similarly, we hope to integrate this library with libuv [29] (the asynchronous C library underlying Node [43]) and improve programming with libuv directly from C or C++ using async/await style abstractions [12, 27] Since the linked abstract doesn't actually mention this practical application, consider this comment as a goad to encourage more people to click through to the paper :)

zengid 9y ago
It should be noted that the previous sentence before your quote is: "For now, we mainly see the library as a target for library writers or compilers."
- mannykannot 9y ago
  Your caveat is well-taken, but you can learn a lot from what is done in these fields.
Matthias247 9y ago
Couldn't these kind of goals also be reached with the upcoming C++ coroutines (also pioneered by Microsoft)? I remember some presentation that those (or at the least the LLVM implementation underneath it) could also be used for C.

deleted 9y ago

[deleted]

frankpf 9y ago

A little off-topic, but the author of this paper (Daan Leijen) is also the author of Koka[1], a programming language with algebraic effects. IMO, Koka (or something similar) has more potential to become a mainstream language than "traditional" FP languages (Haskell, OCaml, Idris, etc.). Effects seem to be easier to understand than monads (at least on a superficial level) and more modular (I don't have a lot of experience with Haskell, so take that with a grain of salt). Its syntax is also very close to C-like languages. Taken from the Koka book[2]: fun square1(x : int) : total int { return x*x } fun square2(x : int) : io int { println( "a not so secret side-effect" ) return x*x } `square1` is a pure mathematical function, so its effect is `total`. `square2` has a side-effect because of `println`, so its effect is `io`. This means that `square2` can raise exceptions, not terminate, be non-deterministic, read and write to the heap, and do any input/output operations. Note that Koka can infer effects, so these annotations are optional. [1]: https://www.microsoft.com/en-us/research/project/koka/?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fprojects%2Fkoka https://www.microsoft.com/en-us/research/project/koka/?from=... [2]: https://koka-lang.github.io/koka/doc/kokaspec.html#sec-effect-types https://koka-lang.github.io/koka/doc/kokaspec.html#sec-effec...

chenglou 9y ago
Fwiw, OCaml algebraic effects are being implemented: http://kcsrk.info/ocaml/multicore/2015/05/20/effects-multicore/ http://kcsrk.info/ocaml/multicore/2015/05/20/effects-multico... (And then there's https://reasonml.github.io https://reasonml.github.io, which I work on)
- frankpf 9y ago
  Hey there, Reason is a great project! Thanks for working on it! I actually tried to use it very recently in a new project at my workplace, but unfortunately I decided not to. I found some fundamental things were lacking. I didn't find documentation about how to interact with npm libraries (e.g. how do I use a websockets library in Reason? Do I have to create my own bindings? If so, how?). There also seemed to be nothing similar to async/await in Reason/Bucklescript yet and I couldn't find out how to use promises. I'll definitely reevaluate it in the future. I think it is an awesome project with great potential (along with Bucklescript which is awesome too).

deleted 9y ago

[deleted]

lindig 9y ago

Algebraic effects are a hot topic. The name sounds fancy but maybe this intuition helps: an effect is like an exception where the exception handler receives enough information to resume the computation from where it was called. Just like exceptions, effects are dynamically scoped: the handler is always found up in the call stack.

larsbrinkhoff 9y ago
Cue smug lispers.

daanx 9y ago

Hi, I am the author of this report -- thank you for the interest :-) Just wanted to add that you can find the library at: https://github.com/koka-lang/libhandler https://github.com/koka-lang/libhandler The `dev` branch contains a sample of `libuv` integration. There is still a lot to be done in terms of creating a better interface and providing implementations of standard effects but the core is working quite well by now. Enjoy!

cryptonector 9y ago

If all you want is generators and co-routines, then there's a lot of literature on this for C. The original Icon compiler compiled to CPS C. That was pretty cool. One can do much of what Icon did using GCC local functions and computed gotos to get something much closer to not-CPS. There's Simon Tatham's PuTTY, which uses his co-routine macros, which are an extravagant meta-programming macros around a Duff's device. He also has an extensive set of meta-programming macros as well, not related to co-routines. Some Schemes compile to C code where all functions always return immediately, but what they return is a continuation, and the top-level is a for(;;) { next = next(); }. EDIT: I'm particularly fond of PuTTY. Its SSHv2 implementation all the way up to the end of authentication is a single, huge function. It looks completely synchronous, but it's not, because it's actually a co-routine. As a result, and in spite of being a single huge function, it's actually quite readable.

daanx 9y ago
I tried to cite much related work on co-routines and threading libraries in C -- including Simon Tatham's page on co-routines in C [1] -- But I was not yet aware of the work on Icon nor did I know co-routines were used in PuTTY -- thanks! Although now that I reread Simon's page I see he actually mentions PuTTY explicitly :-) As an aside, I feel algebraic effect handlers are safer to use than most coroutine or shift/reset implementations because they offer more structure. As put by others: "Algebraic Effects+Handlers" are to "delimited continuations" as "while" is to "goto" [1]: https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html