That would require pretty aggressive inlining, or at least inter-function compilation.
It would be aggressive. I donât think the âinter-functionâ part is as bad as that label usually implies because this fancy pipeline is opt-in per function, so other uses of called functions would proceed as normalâextra cost for the caller, not extra cost for the callee.
This is a good point.
I think there are two key questions to answer. The first is whether these new TCP-preserving closures should use the same syntax on the caller side, and the second is whether they should use the same traits and types on the callee side.
As for the first question: one could imagine that we might use the same closure syntax (|| xyz), and try to infer (somehow) whether the closure ought to be TCP-preserving or not. Even if we could make this work, it seems like this is a recipe for confusion, since if you have something like foo(|| return 22) you won't know, without examining the signature of foo, where the return will return to. So let's say instead that the syntax for a TCP-preserving closure is different, as you suggested -- perhaps do || ....
Now we have to wonder about the callee side. If you have a TCP-preserving closure that returns type T in the normal (non-break, non-continue, etc) case, does it implement the trait FnOnce() -> T? (or FnMut, whatever). On the one hand, if it were to do so, that would mean that TCP-preserving closures could be used with all existing APIs, which is pretty cool.
On the other hand, it would imply an implementation based on unwinding, which implies some amount of implementation cost (and starts to chip away at the idea that unwinding paths can be expensive, since they won't be used in the common case). It also makes me worried because it introduces "non-local" reasoning: when you call a closure, it's possible that the closure will never return (in the normal sense) and instead unwinding will take you to some outer scope (but without a panic). This implies that functions like this:
fn wrap<F,R>(f: F) -> R where F: FnOnce() -> R {
do_something();
let r = f();
undo_something();
r
}
are potentially broken, since undo_something may never execute. Put another way, it means that all Rust code will have to be exception-safe, even in the non-unwinding case. Experience with C++ suggests this will not work out well in practice. (Moreover, this will chip away at the benefits of -C panic=abort, since we may need landing pads anyhow.)
An alternative is that a TCP-preserving closure either implements new closure traits or has some special return value (e.g., FnOnce() -> Control<T> instead of just T). A return value is appealing both because three closure traits are enough for any language and because it means that wrapper functions like the one above "just work" in the way intended, though I guess there might be other functions that maybe do not work as you might expect (e.g., the motivating example, I think, of foo.iter().map(do || x?).collect().
Anyway, I know we talked about this a while back -- just sketching out the possibilities as I see them currently.
In terms of implementation⌠I think that if you restrict this to closures which are borrowed (canât escape upwards from the creation scope, which would turn this into full-blown continuations instead of just nonlocal return), and to ones which are statically known (F: Fn*, no trait objects)⌠that might be sufficient to ensure that it can always be inlined into the call site, and unwinding doesnât have to be involved? (Or whatâs a failure case?)
I think that if you restrict this to closures where are:
- borrowed (can't escape upwards ...)...
I rather have have the closure environment contain some struct NoEscape<'a>(PhantomData<&'a>); perhaps alternate closure syntax could do this with a function body lifetime?
- might be sufficient
The callee could still not be inlineable due to e.g. recursion.
Hmm, right. With recursion that would require nonlocally-returning out of an arbitrarily deep call stack.
Even if that were the case, my bigger concern is the âuser modelâ â that is, if we use something âautomaticâ, weâve re-introduced exn safety as a major concern. If we use something explicit, weâve (potentially) split the API space.
Examples like iterators are actually quite apt and interesting because they donât actually fit naturally into the âTCP-preservingâ closure world, since the closure you pass to map is not executed immediately.
Your example reminded me why monads and effects are better than the ruby wayâwhatever else one might say about them they do solve those problems.
To be more precise, especially for those less familiar with either:
-
Effects perfectly account for early return: early return is an effect, and function- (including closure-) bodies by default only include the âearly return from this (the innermost) functionâ effect. Bigger returns would require âcoming cleanâ about the effect in the function type (âthis is an extra thing which you need to handle / be aware ofâ). While the caller of such a âTCP closureâ doesnât need to do anything âhandleâ the effect, the handling-of-the-effect rule be be used to stop the closure from escaping upwards. This is a pretty hefty change to the type system however.
-
âMonads with closuresâ is less invasive. Instead of having âbackdoorsâ operators like early return, callc, and other such things, everything is implemented âvirtuallyâ on top of normal control flow with closures. This is good for keeping the language simple, but all those closures can make runtime / complication difficult and reduce expressiveness because of it. [HKT on the other hand, assuming we still monomorphize everything, doesnât affect the runtime at all.]
The advantage of my âpervasive inliningâ approach is it keeps the surface language and runtime simpleâwe (ab)use closures and enum/structs implementing Monad for their denotational propertiesâbut then inline everything to also keep the runtime simple. The disadvantage is inlining is slow, and failures are hard to predict a priori, but unless we want to embrace unwinding for regular control flow (please no!!!), weâll have that problem anyways.
Can you do RAII with monads?
C++-style scope-based control flow is more expressive than the standard CPS translation would imply - calls to the destructors are automatically added when you exit a scope.
For example, this code:
fn foo() {
let x = create();
if !is_ok(x) {
return None;
}
Some(x)
}
translates into
foo = bb0 where
bb0 = create >>= \x -> bb1 where
bb1 = is_ok >>= bb2 where
bb2 = \cond -> if !cond then cleanup3 else bb4
cleanup3 = drop x >> bb3
bb3 = return None
bb4 = return $ Some $ x
Here cleanup3 appears nowhere in the source code.
Can you do RAII with monads?
I'm a bit confused exactly what you are asking about. As I envision it, do-notation->closures and closures->Thorin->Mir are disjoint parts of the pipeline, and thus independent problems. Perhaps I wasn't so clear on that.
For example, here is some do-notation. ? is generalized to "bind-current-continuation", something only valid in do notation.
let x = do {
loop {
let x = monadic_action()?;
if !is_ok(x) {
break Monad::return(None);
}
normal_action();
}
};
This gets desugared to
let x = {
let edge0 = |()| monadic_action().bind(edge1);
let edge1 = |temp0| {
let x = temp0;
if !is_ok(x) {
drop(x);
Monad::return(None)
} else {
normal_action();
drop(x);
Monad::return(()).bind(edge0)
}
};
edge0(())
};
So yes we do no need to elaborate drops since scopes are mangled, but since neither normal_action nor drop is monadic, we don't need need to introduce more binds/closures. only ? and "native control flow" have a monadic meaning. Furthermore, had the user written closures to begin with, their would be no need to introduce drops at this stage, because the closures scopes are still there (they would instead be made explicit during the lowering to thorin).
From here on, we do a CPS transform more like what you wrote, but that's for Thorin. Furthermore, from here on "Monad" is just another trait and not special in anyway, closures are all optimized alike. I suppose do notation, and the extra Thorin stage, can be opted into orthogonally too, but of course without a lot of inlining the above closures have no hope of passing the borrow checker.
For anyone not familiar with thorins, monads, etc, the crucial aspect is ? and control flow is only "magical" inside the do { .. }. This allows users to opt into "things not acting like they normally do", so as to prevent the exception safety problems @nikomatsakis mentioned.
1 Like
Thinking about TCP closures again in the context of for loops and the several âiterator alikeâ types that are appearing. Letâs look at some of these iteratorish traits:
// std Iterator. I've added a for_each method to it to show what its
// signature would be.
trait Iterator {
type Item;
fn for_each(self, F) -> () where F: FnMut(Self::Item) -> ():
}
// hypothetical higher kinded StreamingIterator, with non-overlapping
// item lifetimes.
trait StreamingIterator {
type Item<'a>;
fn for_each(self, F) -> ()
where F: for<'a> FnMut(Self::Item<'a>) -> ();
}
// rayon's ParallelIterator, which runs each task in parallel.
trait ParallelIterator {
type Item;
fn for_each(self, F) -> () where F: Fn(Self::Item) -> () + Sync;
}
// future-rs's Stream, which iterates over futures.
trait Stream {
type Item;
type Error;
fn for_each(self, F) -> impl Future<Item=(), Error=Self::Error>
where F: FnMut(Self::Item) -> Result<(), Self::Error>;
}
In principal, it would be a huge ergonomic and accessibility advantage if I could use consume types of all of these traits with a for loop. But only Iterator has a next method with the signature the current for loop sugar requires. We would need the sugar to be something else.
If we had TCP closures, the sugar could instead expand like this:
for x in iter { block } ==> iter.into_iter().for_each(|x| block)
They need to be TCP because in the block, return needs to refer to the outer function. This also presumes that TCP closures can use break (possibly carrying a value) and continue in the way that for loops do, essentially having behavior analogous to Ruby blocks.
This leads to another question - would this have to be duck typed (which I at least donât like), or could we define a trait abstraction for the for_each method, shared between all of the iteratorish traits? This seems quite challenging. In particular, the trait bound on each higher order function differs significantly. Could we build the language features needed to have the block called as a different Fn trait in each iteratorish trait (some kind of associated trait ?)
I haven't thought through whether/how it would apply here, but GHC's ConstraintKinds is basically this.
Isnât that a trait as a type parameter rather than as an associated item, or does it do both?
It does both. Besides being generic over constraints you can also make type aliases of kind Constraint (or * -> Constraint or Constraint -> * or whatever), which extends to type families and associated types. But the associated constraint case was in fact most of the original motivation.
2 Likes
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.