3 ms·
> If doing that results in a stack overflow then that severely limits the utility of this approach. There is no stack overflow. A chaining of monads translate
by pron 11y ago
> If doing that results in a stack overflow then that severely limits the utility of this approach.
There is no stack overflow. A chaining of monads translate to a blocking of the continuation. The familiar imperative sequence of blocking operations is an instance of the continuation approach, and it isn't susceptible to stack overflows.
> I find threads really hard to reason about, so "it's as easy as threads" doesn't really appeal.
Let me make it clearer: it's not "threads", as in multiple threads, but "as easy as threads" as in the simple, familiar blocking thread. There is no concurrency involved. If you can understand:
a = read()
print("hello " + a)
you understand how to work with delimited continuations (that code is actually written as a continuation, which blocks on read()); there's nothing more to it. It is simply a formalization of what it means to block a thread, and a mathematical name for what we've always done.
When you block a kernel thread, the OS takes care of all the continuation stuff -- but it does exactly that (the OS does run your single-threaded program in a continuation). Just as the OS mechanics of continuations don't get in the way of your understanding of the above code, language-level implementation of continuations shouldn't either. It is completely transparent to you -- your thread blocks, some handler does something, and then your thread resumes.
> I've not seen the term "functional-imperative" used that way, and usually the two are contrasted - can you clarify what class of languages you're talking about?
Well, it's sort of my made-up term that I use because "functional" doesn't really have a definition (try to come up with a definition that encompasses all of: Lisp, ML, Haskell, and Erlang but none of Java, Ruby, Smalltalk, JS and you'll see why), so I use the term to denote languages which we call functional (whatever exactly that means) which aren't pure, so: the Lisps, MLs, Erlang.
- lmm 11y ago> There is no stack overflow. A chaining of monads translate to a blocking of the continuation. The familiar imperative sequence of blocking operations is an instance of the continuation approach, and it isn't susceptible to stack overflows. So wait, you are doing TCO? When my code "unblocks" it will look like it's continued directly from the previous line, when actually the previous line called into some other code which then called into a continuation for the "tail" of this method, right? > When you block a kernel thread, the OS takes care of all the continuation stuff -- but it does exactly that (the OS does run your single-threaded program in a continuation). Just as the OS mechanics of continuations don't get in the way of your understanding of the above code, language-level implementation of continuations shouldn't either. It is completely transparent to you -- your thread blocks, some handler does something, and then your thread resumes. If it's the kind of thing that can be implemented transparently then I don't think I'd want to be managing it at all (and automatic CPS-ization is a valid alternative to threading (indeed as you say threading can be viewed as just a crude form of it) that can have performance advantages, but if it looks the same at the code level then it's "just" a performance optimization). The point of the monadic style is for if I do want to manage the sequencing explicitly. More concretely I think the big advantage is that a monadic effect can be captured as a value. So if I want to e.g. perform some effectful operation on a list, and I don't know about traverse, I can just do the operation in the normal way with map, and then as long as I use those values in a way that makes sense according to the normal rules of the language then I'll do something that makes sense. You draw an analogy with checked exceptions in Java - but most Java developers avoid using them, regard them as a failure, and I think a big part of that is you can't safely factor out the result of a call to a possibly-exception-throwing method as a value. > Well, it's sort of my made-up term that I use because "functional" doesn't really have a definition (try to come up with a definition that encompasses all of: Lisp, ML, Haskell, and Erlang but none of Java, Ruby, Smalltalk, JS and you'll see why), so I use the term to denote languages which we call functional (whatever exactly that means) which aren't pure, so: the Lisps, MLs, Erlang. Do you just mean non-Haskell languages? I don't think "pure" is binary in that sense: all languages have some things that are managed implicitly by the compiler/runtime/infrastructure and some things that the developer is expected to manage implicitly. Haskell explicitly sequences I/O but the infrastructure manages laziness, whereas in most MLs it's the other way around. Which is more pure is a matter of perspective.
- pron 11y ago> So wait, you are doing TCO? When my code "unblocks" it will look like it's continued directly from the previous line, when actually the previous line called into some other code which then called into a continuation for the "tail" of this method, right? No TCO. Your code doesn't "unblock"; it unblocks (no quotes). The handler code doesn't "call into the continuation" (i.e., there is no stack-growing call), it just resumes the continuation. Like unparking a thread (or not "like"; unparking a thread is resuming a continuation). There is a relationship between continuations and TCO in that they both deal with stacks, but in this case it only serves to confuse. > The point of the monadic style is for if I do want to manage the sequencing explicitly. But how is `a = read(); print(a)` not explicit? > More concretely I think the big advantage is that a monadic effect can be captured as a value. Continuations are the same in that they are also a "value", except that it is a mutable value. A continuation has a state (it's current program counter). The calls to read and print trigger an OS handler. When working with continuations, those are programmable handlers, so their function is pluggable. You can run the continuation calling read and print with a handler that actually does IO, or with one that does something else -- just like with monads. > You draw an analogy with checked exceptions in Java That's only to explain the typing. Java's checked continuations are an effect system, and the list of thrown exceptions can be viewed as a list of effects a function may have. That's how you can ensure that a function calling read and print will only be called within a context that implements a handler for those effects. > most Java developers avoid using them, regard them as a failure Off-topic, but that is a myth (there was an unscientific poll about this in the last JavaOne conference). If there is a failure is not with the concept, but that the standard Java libraries overuse checked exceptions (this may be addressed). Most Java developers like the concept (according to the poll). > and I think a big part of that is you can't safely factor out the result of a call to a possibly-exception-throwing method as a value. Don't think of checked exceptions in this context as actual exceptions, but as a list of effects. The same "problem" applies to monads, and is actually a good thing -- as you said yourself -- to have the type system ensure that monadic methods are called within the appropriate monad only. This kind of effect system also ensures that a function with effects is only called when the needed handlers are in context. The difference between continuation-effects and monads is that a function making use of continuations can use multiple effects without requiring nasty monad-transformers (and that's exactly the problem Kiselyov wanted to solve with his handler system). > Do you just mean non-Haskell languages? Basically yes (but Idris, Agda and Coq are also pure). > I don't think "pure" is binary in that sense: all languages have some things that are managed implicitly by the compiler/runtime/infrastructure and some things that the developer is expected to manage implicitly. I certainly agree in theory: what constitutes an effect (except IO) is indeed up to the language to define, but those languages I listed allow all effects (including IO, which is an "absolute" effect) without declaring them explicitly, hence they are not pure. BTW, there is another absolute effect (i.e. an effect which is externally observable, and thus must be considered an effect regardless of the language's preferences) -- time. Haskell (and Idris etc.) don't have a good mechanism of handling that effect, which is one of the reasons I am not fond of the Haskell-style pure-FP. As a nice demonstration of that problem, there are two ways in Haskell to write a function that sleeps for a second: one that is effectful (monadic) and one that is pure. Also, many people believe that Haskell has only one function inhabiting the type forall a: a -> a (a notion that is at the core of Haskell's equationality myth), when in fact there are infinitely many, all different from one another.