Haxl(-like "Monads") in terms of Delimited Continuations?

Haxl allows for IO operations to be batched by having Applicative operators that result in a "slightly unlawful" Monad instance -- rather than strictly having (<*>) = ap where ap f x = f >>= (<$> x), it's merely "morally equivalent," as it performs the IO operations in parallel rather than in serial as ap would do.

I'm wondering if it's possible to implement something similar in a language that implements effects in terms of delimited continuations rather than in terms of monads. It seems a lot less obvious how to do so, at least; when evaluating the arguments of an applicative-shaped function call (pure function, effectful arguments), the effect handler must process them one by one, and can't introspect on the continuation to see what future effects might be performed.

An unfortunate solution might be to have a domain-specific optimization pass, reliant on inlining and other optimizations, that notes an effect as having some "do these in parallel" operator and transforms a program that unconditionally performs multiple effects in sequence to a single effect that uses that operator. However, this is terribly unsatisfying, since it's a non-semantics-preserving optimization, rather than something that falls directly out of the user-written code.

By remexre at 2023年12月27日 00:22 | LtU Forum | previous forum topic | next forum topic | other blogs | 6737 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Delimited continuations don't parallelize well.

I have never seen a system with continuations that wasn't also single-threaded in all scopes where those continuations could be invoked.

As you say, it's hard to imagine how to take advantage of parallelism (of ANY kind, not just I/O) with that paradigm.

I'm working on something where procedures can "yield" flow of control back to the caller, giving the caller a re-entry point so that the caller can "re-enter" if the function ought to resume right after it yielded. This is a very restricted form of delimited continuation that I hope will parallelize a bit better, but it has some significant limitations.

First, the caller has to declare a "function environment" and pass it to the re-enterable function. That environment goes out of scope when the caller's environment goes out of scope. The reason for this is so that parallel users of the re-entrant function can use separate environments allowing access in parallel and guarantee that they get cleaned up when the program exits a scope where they could be called.

Second, the re-enterable function has to treat every "yeild" as though it might be "exit," meaning it never does stuff outside its own environment (which the caller is keeping for it) that would need cleaning up after "yeilding."

Third, Function environments can't be returned on the stack as they can in most languages with continuations. They can be (and are) passed down the stack as arguments to re-enterable functions (or to functions that call re-enterable functions), but they exist strictly within the call tree of whatever allocated them and whatever housekeeping they do when they go out of scope gets done when the environment where they were allocated goes out of scope.

This is so "delimited" that I don't even know if you can really refer them as continuations, but I think they will parallelize more easily than anything you really could refer to as continuations.

By Ray Dillinger at Tue, 2025年11月04日 02:39 | login or register to post comments

AltStyle によって変換されたページ (->オリジナル) /