5 ms·

Of course! When I said "it can't be implemented" I meant the logic that the continuation monad itself encapsulates, not async computations in general. For those

by pka 9y ago

Of course! When I said "it can't be implemented" I meant the logic that the continuation monad itself encapsulates, not async computations in general. For those you wouldn't even need promises, you could just use callbacks: fetchUser("url", (user) => { fetchAddress(user.address, (address) => { ... }); }); But this repetetive plumbing is exactly what the continuation monad abstracts away: do user <- fetchUser "url" address <- fetchAddress user.address ... So the point is that you can write your async code in the same way you'd write normal, sequential code (which is what the async extensions of JS/C# allow you to do).

rbehrends 9y ago
This is a syntax thing only. You can do the same in Smalltalk with an array of blocks (which are closures). { [ user := url fetchUser ]. [ address := user fetchAddress ]. } and pass that array as an argument to whatever evaluation strategy you want. You can also do with with proper macros, e.g. in Nim (fictitious example, there's no actual `usingContinuations` macro): usingContinuations do: user = fetchUser("url") address = user.fetchAddress This is all a matter of syntax allowing you to write a sequence of code fragments in a readable fashion while allowing transformations on the underlying sequence. That said, outside of Haskell (or other functional languages emulating the approach) you'll encounter them fairly rarely in this particular form, because just allowing for a sequence of code fragments is a bit limiting if you can combine them in more general ways. For example, Smalltalk builds pretty much all control flow in what we'd call combinators (on closures and values) now and allows you to pretty much extend that arbitrarily. Not because Smalltalk does anything super-special here, but because it has a nice, concise syntax for expressing executable code fragments as values.
- marcosdumay 9y ago
  Every difference between Turing complete languages is a "syntax only thing". A monad is basically an abstraction that encapsulates an evaluation strategy. You can certainly reimplement it on most functional languages with a syntax that is only a bit more verbose and error prone. That's not a win. Also, macros are an all powerful construction, with heavy implementation and maintainability costs. They certainly can be used as monads. That's also not a win.
  - rbehrends 9y ago
    > Every difference between Turing complete languages is a "syntax only thing". I'm pretty sure you can't ignore language semantics here. > You can certainly reimplement it on most functional languages with a syntax that is only a bit more verbose and error prone. That's not a win. Note that I was giving examples from imperative languages; Haskell has the additional problem that it has to transform the do notation into what's essentially function composition; but function composition is already the natural denotational semantics of imperative code [1]. [1] https://en.wikipedia.org/wiki/Denotational_semantics#Denotational_semantics_of_state https://en.wikipedia.org/wiki/Denotational_semantics#Denotat...
    - marcosdumay 9y ago
      > I'm pretty sure you can't ignore language semantics here. As long as the languages operate on the same virtual computer (same IO capacities), you can create the same semantics on any language. At the worst case, you can write an interpreter for any language on any other language. > but function composition is already the natural denotational semantics of imperative code Most high-level languages got some influence by Lisp-style functional programing, so they transform into function reduction/composition with some amount of naturality. The imperative languages are the ones with the less straight-forward transformation, while Lisp is basically alone at the other extreme. Pure function reduction/composition is a great representation for computer. It's simple to analyze, and cheap to represent. But I don't think it is that great for human consumption. Do notation is a bit more complex to represent, but often a lot more legible.
      - rbehrends 9y ago
        > As long as the languages operate on the same virtual computer (same IO capacities), you can create the same semantics on any language. At the worst case, you can write an interpreter for any language on any other language. This is fairly tautological and would make semantics meaningless. I'm not talking about the universality of Turing-complete languages, but about the semantics of language constructs. > Most high-level languages got some influence by Lisp-style functional programing, so they transform into function reduction/composition with some amount of naturality. The imperative languages are the ones with the less straight-forward transformation, while Lisp is basically alone at the other extreme. This has nothing to do with what I said, so I'm not sure what your point is?
- KirinDave 9y ago
  "Do notation" is a syntax thing. What's more fundamental is modeling every computation in your language with these chainable algebraic constructs in such a way that they're always composable (when of the same computation type) and combinable (albeit with complexity, as in mtl). Monads are just a modeling technique for this, and when laid bare without do notation, they're neither impressive nor surprising. However, it's worth noting that there are some very neat properties with generic monads (something that Haskell does very well because of how typeclasses can model constraints). It allows for reuse across surprising axes. Let's extend the prior example: loadUser :: (MonadIO m) => UserRef -> m User loadUser url = do userRecord <- liftIO $ fetchAndParseUser url -- One function for compactness emailAddress <- validateEmailAddress userRecord pure $ User (publicName userRecord) emailAddress This simplified, but what's really nice about this specific construction is that we've placed a constraint on how we load UserRefs (we need to pull data from a url). In most cases I'd expect that this would be some variant of ExceptT IO * or MaybeT *. But it also could be something more sophisticated. I've had a case where I realized that I was using a dowdy 2008 approach to software assuming users would have only one identity record, but I wrote a load function a lot like this. I needed to change how I loaded users since users would often have multiple user records (i.e., they created and linked accounts to one another). I had to change my fetch and parsers (naturally, I chose a new endpoint). However, I started calling my load user function with ListT IO [1]. I barely had to change logic (mostly pattern matching on the edges) to cope with this change. But you might also imagine that the computation includes async properties, or validating properties, or whatever. Because we can generically address ALL kinds of computations and even combinations of computations, we can freely swap them around as we see fit without substantial modification. That kind of flexibility is fundamental to how these languages work in tandem with monadic computation, and it's very powerful. P.S., I recognize that you might argue a value encoding could capture this in Smalltalk, and I agree. That's often how people implement this under the covers before they optimize it. What's worth noting is that without good type checking, interlocking more than a few of these constraints correctly is very difficult, which is why this is much more feasible to do in Haskell. [1]: As an aside, I don't use ExceptT for runtime exceptions. IO already covers that and I think it's a bit of a fantasy to pretend I can do better. Also, I'm aware that ListT is a slightly troubled cousin in the world of monad transformers, but I was happy to use it here, none of its downsides really came into play.
- tathougies 9y ago
  Can you extend this approach to delimited continuations?
  - rbehrends 9y ago
    Depends on what you mean precisely by "extend to", but generally this is mostly a question of whether the underlying execution model supports them. "Code as values" is not exactly a particularly complicated thing (though arriving at an efficient implementation can be).
    - tathougies 9y ago
      But Haskell’s execution model has no underlying support for continuations, and yet there are perfectly efficient implementations. You actually can not implement delimited continuations in languages like c++, javascript, or go, unless you write your own execution environment at which point Id argue you’ve left the realm of the language. In c++ at least, such an implementation would certainly use undefined behavior
      - rbehrends 9y ago
        > But Haskell’s execution model has no underlying support for continuations, and yet there are perfectly efficient implementations. What you need is a way to capture and manipulate stack frames at a very basic level. Haskell cannot magically avoid that. As I recall (though it has been a while), Control.Monad.CC reifies stack frames explicitly. Monads function in this context as a very basic metaprogramming technique (or as some sort of AOP, if you want to look at it this way). > In c++ at least, such an implementation would certainly use undefined behavior This is what I mean by support in the execution model. You do need to have access to stack frames, and C++ doesn't permit that. There are workarounds [1], but they generally require non-trivial metaprogamming, due to the insane complexity of C++. You don't have that problem with, say, Smalltalk, as most Smalltalk VMs gives you the necessary functionality. For example, one of the original continuation-based web frame works, Seaside, was all Smalltalk [2]. [1] http://www.filpizlo.com/papers/baker-ccpe09-accurate.pdf; http://www.filpizlo.com/papers/baker-ccpe09-accurate.pdf; the context here is GC, but the underlying problem is similar, access to stack frames (in this context, for root scanning). [2] http://seaside.st/about/examples http://seaside.st/about/examples
lojack 9y ago
Eliminating the repetitive plumbing is a feature of haskell, not a feature of the monad. What the continuation monad gets you is a pipeline of asynchronous and synchronous operations. Whether or not something is asynchronous is abstracted away. Your example could be rewritten as: composeAsync([ fetchUser("url"), function(user) { return user.address }, fetchAddress, function(address) { return address.zipcode } ]).then(function(output) { document.write("Zipcode: " + output); }); In this example you don't need to care if fetchAddress is synchronous or asynchronous, it'll work either way. Its at least worth noting that one thing Haskell gives you is the ability to perform assignment within the async functions. This is also possible with Javascript, but a bit more intuitive in Haskell. Again, this is a feature of haskell, not a feature of monads. var outputs = {}; composeAsync([ fetchUser("url"), function(output) { outputs['user'] = output }, function() { return outputs.user.address }, fetchAddress, function(output) { outputs['address'] = output } ]).then(function(output) { ... }); composeAsync could also be rewritten to store this in an accumulator, making it look a little nicer.
- pka 9y ago
  This is not as general as a monad though, it's just feeding the output of one function into the next. I'm sure you know this, but the thing that makes monads a more general solution is that (because bind depends on a value produced at runtime) one can dynamically alter control flow, i.e: fetch = do user <- fetchUser "url" if userEmpty user then do fetchUserDetails "details" fetch -- recurse else fetchAddress user For that to work, your functions inside the `composeAsync` array would need to able to return nested promises and at that point you've just reimplemented the continuation monad :)
  - lojack 9y ago
    Yeah, I guess I may have not completely implemented the continuation monad, but my point was precisely what you just said. That is, it's totally possible to implement continuation monads in vanilla javascript. It's not only possible, but its reasonably easy to do without heavy lifting.
Rusky 9y ago
The reason async/await is implemented as a language extension in JS/C#/Kotlin/etc. is not because they're not powerful enough for a promise library, but because the language extension version composes with imperative control flow. Haskell has exactly the same problem- do-notation is nice, but not very different from just any of the sibling comments' tricks with things like arrays of closures. It doesn't let you write things like this: while some_condition() { let result = await some_async_operation() await something_else_async(result) } Instead you just use recursion and (lifted) higher order functions like elsewhere in Haskell. This is not very unusual there but it would be a pain in JS/C#/Kotlin/etc. which do use imperative control flow in idiomatic code.
- pka 9y ago
  Yes, they more or less had to lift while/for/if/switch etc into the continuation monad :)
  - Rusky 9y ago
    IMO the builtin version is much nicer than the equivalent Haskell, and thinking in terms of composing continuations rather than composing monads makes more sense for imperative languages.

by pka 9y ago

rbehrends 9y ago

This is a syntax thing only. You can do the same in Smalltalk with an array of blocks (which are closures). { [ user := url fetchUser ]. [ address := user fetchAddress ]. } and pass that array as an argument to whatever evaluation strategy you want. You can also do with with proper macros, e.g. in Nim (fictitious example, there's no actual `usingContinuations` macro): usingContinuations do: user = fetchUser("url") address = user.fetchAddress This is all a matter of syntax allowing you to write a sequence of code fragments in a readable fashion while allowing transformations on the underlying sequence. That said, outside of Haskell (or other functional languages emulating the approach) you'll encounter them fairly rarely in this particular form, because just allowing for a sequence of code fragments is a bit limiting if you can combine them in more general ways. For example, Smalltalk builds pretty much all control flow in what we'd call combinators (on closures and values) now and allows you to pretty much extend that arbitrarily. Not because Smalltalk does anything super-special here, but because it has a nice, concise syntax for expressing executable code fragments as values.

marcosdumay 9y ago
Every difference between Turing complete languages is a "syntax only thing". A monad is basically an abstraction that encapsulates an evaluation strategy. You can certainly reimplement it on most functional languages with a syntax that is only a bit more verbose and error prone. That's not a win. Also, macros are an all powerful construction, with heavy implementation and maintainability costs. They certainly can be used as monads. That's also not a win.
- rbehrends 9y ago
  > Every difference between Turing complete languages is a "syntax only thing". I'm pretty sure you can't ignore language semantics here. > You can certainly reimplement it on most functional languages with a syntax that is only a bit more verbose and error prone. That's not a win. Note that I was giving examples from imperative languages; Haskell has the additional problem that it has to transform the do notation into what's essentially function composition; but function composition is already the natural denotational semantics of imperative code [1]. [1] https://en.wikipedia.org/wiki/Denotational_semantics#Denotational_semantics_of_state https://en.wikipedia.org/wiki/Denotational_semantics#Denotat...
  - marcosdumay 9y ago
    > I'm pretty sure you can't ignore language semantics here. As long as the languages operate on the same virtual computer (same IO capacities), you can create the same semantics on any language. At the worst case, you can write an interpreter for any language on any other language. > but function composition is already the natural denotational semantics of imperative code Most high-level languages got some influence by Lisp-style functional programing, so they transform into function reduction/composition with some amount of naturality. The imperative languages are the ones with the less straight-forward transformation, while Lisp is basically alone at the other extreme. Pure function reduction/composition is a great representation for computer. It's simple to analyze, and cheap to represent. But I don't think it is that great for human consumption. Do notation is a bit more complex to represent, but often a lot more legible.
    - rbehrends 9y ago
      > As long as the languages operate on the same virtual computer (same IO capacities), you can create the same semantics on any language. At the worst case, you can write an interpreter for any language on any other language. This is fairly tautological and would make semantics meaningless. I'm not talking about the universality of Turing-complete languages, but about the semantics of language constructs. > Most high-level languages got some influence by Lisp-style functional programing, so they transform into function reduction/composition with some amount of naturality. The imperative languages are the ones with the less straight-forward transformation, while Lisp is basically alone at the other extreme. This has nothing to do with what I said, so I'm not sure what your point is?
KirinDave 9y ago
"Do notation" is a syntax thing. What's more fundamental is modeling every computation in your language with these chainable algebraic constructs in such a way that they're always composable (when of the same computation type) and combinable (albeit with complexity, as in mtl). Monads are just a modeling technique for this, and when laid bare without do notation, they're neither impressive nor surprising. However, it's worth noting that there are some very neat properties with generic monads (something that Haskell does very well because of how typeclasses can model constraints). It allows for reuse across surprising axes. Let's extend the prior example: loadUser :: (MonadIO m) => UserRef -> m User loadUser url = do userRecord <- liftIO $ fetchAndParseUser url -- One function for compactness emailAddress <- validateEmailAddress userRecord pure $ User (publicName userRecord) emailAddress This simplified, but what's really nice about this specific construction is that we've placed a constraint on how we load UserRefs (we need to pull data from a url). In most cases I'd expect that this would be some variant of ExceptT IO * or MaybeT *. But it also could be something more sophisticated. I've had a case where I realized that I was using a dowdy 2008 approach to software assuming users would have only one identity record, but I wrote a load function a lot like this. I needed to change how I loaded users since users would often have multiple user records (i.e., they created and linked accounts to one another). I had to change my fetch and parsers (naturally, I chose a new endpoint). However, I started calling my load user function with ListT IO [1]. I barely had to change logic (mostly pattern matching on the edges) to cope with this change. But you might also imagine that the computation includes async properties, or validating properties, or whatever. Because we can generically address ALL kinds of computations and even combinations of computations, we can freely swap them around as we see fit without substantial modification. That kind of flexibility is fundamental to how these languages work in tandem with monadic computation, and it's very powerful. P.S., I recognize that you might argue a value encoding could capture this in Smalltalk, and I agree. That's often how people implement this under the covers before they optimize it. What's worth noting is that without good type checking, interlocking more than a few of these constraints correctly is very difficult, which is why this is much more feasible to do in Haskell. [1]: As an aside, I don't use ExceptT for runtime exceptions. IO already covers that and I think it's a bit of a fantasy to pretend I can do better. Also, I'm aware that ListT is a slightly troubled cousin in the world of monad transformers, but I was happy to use it here, none of its downsides really came into play.
tathougies 9y ago
Can you extend this approach to delimited continuations?
- rbehrends 9y ago
  Depends on what you mean precisely by "extend to", but generally this is mostly a question of whether the underlying execution model supports them. "Code as values" is not exactly a particularly complicated thing (though arriving at an efficient implementation can be).
  - tathougies 9y ago
    But Haskell’s execution model has no underlying support for continuations, and yet there are perfectly efficient implementations. You actually can not implement delimited continuations in languages like c++, javascript, or go, unless you write your own execution environment at which point Id argue you’ve left the realm of the language. In c++ at least, such an implementation would certainly use undefined behavior
    - rbehrends 9y ago
      > But Haskell’s execution model has no underlying support for continuations, and yet there are perfectly efficient implementations. What you need is a way to capture and manipulate stack frames at a very basic level. Haskell cannot magically avoid that. As I recall (though it has been a while), Control.Monad.CC reifies stack frames explicitly. Monads function in this context as a very basic metaprogramming technique (or as some sort of AOP, if you want to look at it this way). > In c++ at least, such an implementation would certainly use undefined behavior This is what I mean by support in the execution model. You do need to have access to stack frames, and C++ doesn't permit that. There are workarounds [1], but they generally require non-trivial metaprogamming, due to the insane complexity of C++. You don't have that problem with, say, Smalltalk, as most Smalltalk VMs gives you the necessary functionality. For example, one of the original continuation-based web frame works, Seaside, was all Smalltalk [2]. [1] http://www.filpizlo.com/papers/baker-ccpe09-accurate.pdf; http://www.filpizlo.com/papers/baker-ccpe09-accurate.pdf; the context here is GC, but the underlying problem is similar, access to stack frames (in this context, for root scanning). [2] http://seaside.st/about/examples http://seaside.st/about/examples

lojack 9y ago

Eliminating the repetitive plumbing is a feature of haskell, not a feature of the monad. What the continuation monad gets you is a pipeline of asynchronous and synchronous operations. Whether or not something is asynchronous is abstracted away. Your example could be rewritten as: composeAsync([ fetchUser("url"), function(user) { return user.address }, fetchAddress, function(address) { return address.zipcode } ]).then(function(output) { document.write("Zipcode: " + output); }); In this example you don't need to care if fetchAddress is synchronous or asynchronous, it'll work either way. Its at least worth noting that one thing Haskell gives you is the ability to perform assignment within the async functions. This is also possible with Javascript, but a bit more intuitive in Haskell. Again, this is a feature of haskell, not a feature of monads. var outputs = {}; composeAsync([ fetchUser("url"), function(output) { outputs['user'] = output }, function() { return outputs.user.address }, fetchAddress, function(output) { outputs['address'] = output } ]).then(function(output) { ... }); composeAsync could also be rewritten to store this in an accumulator, making it look a little nicer.

pka 9y ago
This is not as general as a monad though, it's just feeding the output of one function into the next. I'm sure you know this, but the thing that makes monads a more general solution is that (because bind depends on a value produced at runtime) one can dynamically alter control flow, i.e: fetch = do user <- fetchUser "url" if userEmpty user then do fetchUserDetails "details" fetch -- recurse else fetchAddress user For that to work, your functions inside the `composeAsync` array would need to able to return nested promises and at that point you've just reimplemented the continuation monad :)
- lojack 9y ago
  Yeah, I guess I may have not completely implemented the continuation monad, but my point was precisely what you just said. That is, it's totally possible to implement continuation monads in vanilla javascript. It's not only possible, but its reasonably easy to do without heavy lifting.

Rusky 9y ago

The reason async/await is implemented as a language extension in JS/C#/Kotlin/etc. is not because they're not powerful enough for a promise library, but because the language extension version composes with imperative control flow. Haskell has exactly the same problem- do-notation is nice, but not very different from just any of the sibling comments' tricks with things like arrays of closures. It doesn't let you write things like this: while some_condition() { let result = await some_async_operation() await something_else_async(result) } Instead you just use recursion and (lifted) higher order functions like elsewhere in Haskell. This is not very unusual there but it would be a pain in JS/C#/Kotlin/etc. which do use imperative control flow in idiomatic code.

pka 9y ago
Yes, they more or less had to lift while/for/if/switch etc into the continuation monad :)
- Rusky 9y ago
  IMO the builtin version is much nicer than the equivalent Haskell, and thinking in terms of composing continuations rather than composing monads makes more sense for imperative languages.