7 ms·
From Imperative to Pure-Functional and Back: Monads vs. Scoped Continuations
- inglor 11y agoIt's pretty interesting that the author did not talk about async/await which gives us back the imperative coding style with futures, effectively solving the problem - it has been adopted by many languages like Python, C# and JavaScript and can be implemented with generators. Generators, are the generalization that gives you the expressiveness you need (not fibers) here. Where are they ineffective here?
- pron 11y agoasync/await are a form of stackless coroutines (or stackless delimited continuations although that term is rarely, if ever used). They're a limited form of delimited continuations, and are mostly used as a compromise when implementing full coroutines is hard (or not wanted for some reason). Clojure's core.async's go blocks are also stackless coroutines. Basically, they're delimited continuations that only allow suspension ("shift") at the topmost stack frame of the continuation, and don't allow suspending at deeper stack frames.
- Others 11y agoI think that most languages don't want the complexity of coroutines, as they are a unfamiliar concept to most programmers. It is a shame that they've never gained popularity as they are very general concept.
- mwcampbell 11y agoA different take on the merits of explicit yielding (whether by async/await or raw generators), and the perils of full coroutines, by Glyph Lefkowitz of Twisted Python fame: https://glyph.twistedmatrix.com/2014/02/unyielding.html https://glyph.twistedmatrix.com/2014/02/unyielding.html
- pron 11y agoI'd say that Lefkowitz's claims are mostly relevant when your runtime has no multicore support (like Python). If your runtime is single-threaded, explicit yields might (it's mostly a matter of taste), make explicit reasoning about state-change ordering easier. But then you're using shared-state concurrency again, and unsafe shared-state to boot. If your runtime has multicore support -- like Java or .NET -- all this doesn't matter, because those concurrent changes Lefkowitz is talking about may happen any time -- not just at yield points. The solution, of course, is not to use unsafe-shared-state-concurrency! Either use threads with messages (like Erlang), or threads with transactional shared-state, like Clojure, or both (in fact even Erlang has both actors and ETS, and Clojure has agents and channels as well as atoms and refs).
- Silhouette 11y agoHe does (briefly) mention that kind of variation and why it's a slightly different idea in the original presentation. It's around 28 minutes into the video.
- Verdex 11y agoThe interesting part of this whole thing to me is that you can get composition between your continuations without using something like Monad Transformers[1]. However, the part that I haven't been able to get past yet is that monads are not closed over composition (so there exist some monads that are no longer monads when you compose them). If it turns out that monads and delimited continuations are duals then it seems that there ought to be some continuations that compose only to yield invalid results. (With the alternative being that scoped continuations always compose which suggests something odd is going on.) I haven't worked through the math yet because it looks suspiciously dreadful, but if anyone knows why scoped continuation composition is closed I would appreciate your input. [1] - the most disappointing thing about monads to me.
- elcritch 11y agoInteresting, and disappointing in a way. I assumed that all Monadic compositions would be closed analogous to linear algebra operations and vector spaces. Out of curiosity, do you have a reference to read up on Monadic Composition not being closed? Particularly any lighter references (it's a Saturday after all).
- tel 11y agoHere's a simple counter-example. The state monad is the following functor St s a = s -> (a, s) if we compose it with itself (using `d` as the second state parameter) St s (St d a) = s -> (d -> (a, d), s) is `F a = St s (St d a)` a monad? The return operation is clear enough return a = \s -> (\d -> (a, d), s) but the join operation fails join :: F (F a) -> F a :: St s (St d (St s (St d a))) -> St s (St d a) :: s -> (d -> (s -> (d -> (a, d), s), d), s) -> s -> (d -> (a, d), s) join m0 = \s0 -> let (m1 :: St d (F a), s1) = m0 s0 in (\d0 -> let (m2 :: F a, d1) = m1 d0 (m3 :: St d a, s2) = m2 s1 (a, d2) = m3 d1 in (a, d2) , ??? ) The trouble is the ??? bit where we'd like to place the furthest advanced `s` state named `s2`, but it's not in scope to return at the top since we have to apply the d state to reach it. This however only means that St does not compose with itself as a functor. It composes just fine in another method. If we install the inner monad "wrapped around" the tuple StT s m a = s -> m (a, s) -- T for "transformer" then the composition of states looks like StT s (St d) a = s -> St d (a, s) = s -> d -> ((a, s), d) = (s, d) -> (a, (s, d)) = St (s, d) a which is obviously a monad.
- runT1ME 11y agoUh... What do you think monad transformers do?
- biggerbob 11y agoMonad transformers are the workaround for monads don't compose. Look at "Appendix I: Look Ma, No Transformers!" on the page to show benefit. Can compose and don't need the transformers.
- tel 11y agoI still honestly haven't given this enough time to digest—my Java-fu is quite rusty so I'm sort of reading between the lines on what I know about delimited continuations generally. First I want to state that delimited continuations form a monad and (I believe) that in order to get the Java implementation working you need to implement that monad in the "ambient monad" of Java. Second, I want to dissect the notion of "monad" as used here into two pieces. First, there is the "PFP Notion" of monad which tends to be represented as a data type and some associated operations. Actually, I mean this even more specifically as being aimed precisely at the standard library monads of Haskell. Secondly, there's the mathematical "monad" which is just a qualifier assigned to any structure which satisfies the monad laws. Delimited continuations are definitely a mathematical monad. They are represented by one PFP monad, but are generally eschewed as a style there. Why? Because delimited continuations are very "large" and PFP tends to favor the idea of having your data "forbid invalid state" so... large types are disfavored. So now, to the third point: I think this is all just "implementing a specific overlarge monad in Java and Clojure". It turns out that this is really convenient because overlarge things always are. They are of course more convenient in PFP, too. But this convenience has the price of making code difficult to treat as data, difficult to analyze statically. All that said, it doesn't mean at all that this isn't a useful technique for implementation of monads in Java/Clojure. Four, what about composability? (Specifically, here, we mean functor composition.) Turns out that delcont composes nicely compared to the PFP-style monads. The reason why is again because of lack of restrictions on state space. Non-composability of monads is a good thing because it relates to non-commutativity of certain effects. You can get better composability in three ways: throw out all the non-commutative effects, work with subsets of effects a particular ambient monad (see Purescript's impl of Eff), split the specification of effects from the implementation of effects and leave the decision of ordering up to the implementer (see Haskell's mtl). If you don't want any of the above, just realize that non-composition is telling you something and forcing you to make choices. One choice is to build a new kind of composition (monad transformer composition) which does work the way we want by being more sensitive to ordering. Fifth, and finally, all the above is not to say that there's any lack of merit to using delcont for effects. It's a great technique. It may fit the "algorithmic mind" better, too. I am trying to say, however, that it's not some grand trick that frees the user from thinking about monads. You still are, you just trade one set of implementation concerns for another. But since things are still monads then the same mathematical techniques will translate. Which is a great thing—it means there are more tools to think about, understand, and become confident in the application of this technique.
- mikekchar 11y agoIt's an interesting article and something I would like to think deeply about, but I hope the author will forgive me if it isn't immediately obvious to me. Especially the statement that "monads have no place in imperative languages". For example, I do a lot of Java/Coffee script lately. I don't have access to first class continuations. Don't get me wrong; I'd love to have them. I'm sick as the next person of blowing up in a callback and having my stack completely hosed. But in Coffee script, monads are nearly trivial to implement. The use of the Maybe monad makes doing repeated transformations and filtering incredibly nicer. It is not obvious to me that a continuation based implementation would be clearer at all. Perhaps the author is trying to make the case that first class continuations are more important than first class monads for imperative languages. If that's the case, then I tend to agree because, like I said, monads are not difficult to implement even if you don't have explicit support for them. Stack preserving continuations on the other hand... :-P I think the idea of using composable continuations is a very interesting one and I'd like investigate it further, but unless I'm being very dim-witted (a definite possibility) I don't think the matter is as clear as the author hopes.
- pron 11y agoAuthor here. I'm not trying to claim that nested scoped continuations (what the literature calls "delimited continuations with multiple prompts") are objectively easy, although I do think they're a lot easier than monad transformers, especially for imperative programmers. In fact, in the post I say that I'm not sure languages should expose this abstraction directly. It is merely discussed here to show that the theory behind the imperative style is not different from the one behind the PFP style, aimed for those who believe "PFP is just math, while imperative is 'not math'", or to those who are curious to see (as I was) if the imperative style has something like PFP's monad, namely an elegant abstraction that's at the heart of everything. In practice, however, most continuations should be used sparingly if at all, except one -- the thread (in particular, the lightweight thread). Lightweight threads make the most annoying problems of monads in an imperative language go away, and are easy for imperative programmers to use.
- mikekchar 11y ago
- dkarapetyan 11y agoI like this because it addresses part of the problem of why I've stopped paying any attention to PLT related topics like denotational semantics, monads, category theory, and higher-order/dependent static type systems in general. In my day to day work the programming language is never the problem because hacking around the limitations of the language to bridge the gap between the problem domain and the computational domain is never the bottleneck. The real problem is when these systems go into production and all static guarantees and beautiful abstractions become basically useless. What I want is something to help me reason about dynamic and evolving large scale software systems. What I get is PLT researchers and library authors bickering over dependent types, monads, and continuations. Here's a concrete and unsolved problem. How do you specify some kind of topology for your production environment and then have whatever system understands this specification reason about performance, error recovery, failover, and scaling issues. In fact the lower level components don't even matter because you could write it in Haskell or Python or Java or whatever is your favorite language. Right now there is nothing because everyone is arguing about continuations and monads. Basically everyone involved is thinking too small. The one person that I think comes close to approaching the problem from the right angle is http://www.cl.cam.ac.uk/~srk31/ http://www.cl.cam.ac.uk/~srk31/.
- zoul 11y agoDoesn’t an expressive and strong type system, as an example, help you reason about software systems?
- dkarapetyan 11y agoNope, my problem isn't reasoning about the lower level components. In fact you can assume I have correctness proofs for every piece of the infrastructure. What I don't have is the higher-level piece that can reason about the lower level components and do so when new pieces are added, old pieces removed, new guarantees enforced, old ones relaxed, etc. A static type system no matter how advanced doesn't help with any of it.
- pron 11y ago
- acjohnson55 11y agoVery interesting piece. It sounds a lot like how exceptions be used to implement non-error control flow [1]. The one bone I have to pick is the juxtaposition of PFP and imperative as opposites. Certainly it's the case that PFPers can and do implement imperative logic monadically, but it's also the case that imperative programmers often use frameworks that largely treat the business logic, where most of the programming is actually done, as more or less pure functions. Moreover, explicitly hybrid languages like JavaScript, Scala, Rust, Swift, etc. seem to be where a lot of the practical PL excitement is these days. I think the real debate is in the best patterns to use for particular generic problems. That's the core of the blog post of course, I'm just disagreeing with some of the rhetorical framing. Anyhow, the premise reminds me a lot of What Color Is Your Function [2] and its critique of async programming. I think monads are super useful and intuitive when representing data. Promises/futures blew my mind, once I finally understood them, but I think there are important points about how they can become extremely cumbersome within a large architecture. I have to admit that I'm starting to agree that they may be a dead end, no matter how much syntactic sugar you sprinkle on it. I think the big issue is that if you can't pull data out of a monad, you can't really encapsulate its logic. For containers, this isn't much of a problem, because the monadic data structure is either inherent to the data itself or you can fold your way down to something more primitive. In those cases, the monadic model seems completely reasonable and very nicely encapsulated to me. I'm not sure I buy the idea that scoped continuations should replace this monad usage. Connecting back with async programming, I wonder how this jives with the actor model, which has been so widely praised as a model of concurrency that is conceptually simple, easy to reason about, fault tolerant, and imperative. When the author mentioned the thread being the atom of imperative programming, actors immediately came to mind. Lastly, much like monads, futures and every other abstraction out there, the usefulness of scoped continuations may come down to how easily it can be expressed and comprehended within real programming languages. I found the examples in the original talk and the blog post to both be rather difficult to follow. The former, probably because of the use of = to select the scope and the latter because of the verbosity of Java. It would be interesting to see if there's a syntax that really captures the operation in an intuitive way. [1] http://stackoverflow.com/questions/2742719/how-do-i-break-out-of-a-loop-in-scala http://stackoverflow.com/questions/2742719/how-do-i-break-ou... [2] http://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/ http://journal.stuffwithstuff.com/2015/02/01/what-color-is-y...