An idea for TCP closures and rust's effect system

Brief summary of idea\proposal:

Allow closures and functions to capture control flow environment, with support for following effects: fallibility,asynchrony & multiplicity.

  • fallibility is achieved through introduction of a return-to-label (diverging) expression: return 'label val. It is terminating effect;
  • asynchrony is done by allowing closure to capture async context's implicit values and use them to await a future in a closure: || await(some_captured_fut). Resulting closure's state is stored in and polled by parent future;
  • multiplicity is provided via capturing generator's environment and yield'ing from (another) generator context.

Pain points:

  1. light weight syntax for providing labels to their consumers;
  2. inconsistent syntax of asynchrony;
  3. giving a labels for closure and generators contexts.

Solutions:

  1. Second class labels.
    We introduce labels as second class citizens. In input positions, by functionality:

    • fn gimme_label(lab: label(u64)) - is for terminating return effect;
    • fn gimme_gen(parent_scope: label(u64 -> bool)) - is for consuming labels of generators' scopes.

    Because of labels being second class citizens we impose restrictions:

    • No renaming other than at function boundary;
    • As a consequence, there is no bindings of type "label".

    Example:

    fn takes_a_label(a: label(u64 -> bool)) -> !  {
       let mut acc = 0; loop { acc += yield 'a (acc % 2 == 0) };
    }
    

    And btw, here I had to use yield as an expression approach - I have no access to what is actually being mutated.

  2. Possible use of async closure's syntax.
    Instead of trying to justify inconsistent use of await outside of async function/block(/closure),
    I opt to reuse async closure syntax for creating such TPC closures:
    Example:

    async mapper(iter: impl Iterator<Item=Struct>) -> Vec<Struct2>{
       iter
         .map(async |it|{ process(it).await }) //note, this creates iterator tied to local scope
         .collect();
       ...
    }
    
  3. A syntax is like 'label: |arg| {...}.
    Example (using previously defined takes_a_label):

    ...
    // has type: `impl Generator<u64,Yield = bool,Return = !>`
    let gen_cl = 'lab: |num: u64| {
       takes_a_label('lab) // diverges
    };
    ...
    

HOF.

Section which they deserve. Such cryptic syntax is not for no reason:
The primal goal was to allow HOF to write signatures like this:

  1. async fn hof(f: async fn(label(u64)) -> Struct );
  2. or this:
/// it will "fold" a coroutine
fn folder<T>(
init: T,
f: fn(label(Struct -> Struct2)),
fld: fn(T,Struct2)->(T,Option<Struct>),
)

Drawbacks:

  1. label is a keyword now.

Unresolved questions:

  • exact rules for async closure syntax: when it creates a TPC async closure?; when a plain async closure?;
  • real cost of second class labels.

Things to note:

  1. Given all of these one might think that this is a coroutines proposal, but it's not really one because of imposed restrictions on how labels flow between functions.
  2. To avoid unnecessary monomorphic copies of label taking code, we can give them an actual runtime representation. Then effectful code will receive pointers to where to store next yield value and whom to callback on next yield.

... meanwhile I was thinking about making non-local returns a new sort of panic:

// reserves space on stack for NonLocalReturnType
// keeps track of current stack frame so that we can return to it
let catcher = PanicCatcher<RegularReturnType, NonLocalReturnType>::new();

// pass it into the new catch_unwind
catch_unwind_nonlocal(&mut catcher, |nonLocalReturn : &PanicInvoker<NonLocalReturnType>| {
        ....
        let value : NonLocalReturnType = ...;
        nonLocalReturn.panic(value); // can be in another method, just pass nonLocalReturn to it
        ....
    });

if (catcher.isOk()) { ...} else {..}
2 Likes

Non-local returns also call destructors, It should had been written.

It could be nice, typed catch_unwind, but the last one is stable. Also, with this approach we can have library level exceptions, for catching NPE, IndexOutOfBounds, and other common error at runtime, safely(?).

Any ideas on improving asynchrony syntax?

I was already assuming that since normal returns also call destructors. However this should not be the case for async/generators because they can be resumed.

While syntax is important I don't think it should be the primary focus here. There are important questions that I think should come before them, for example:

  • how should this be implemented? For example kotlin requires the function accepting the lambda with non-local control flow to be inlined into the caller. Should we do something like that? This would e.g. limit the ability to turn these types of closures into trait objects. What are the alternatives?

  • Does this need to be something special or could it be modeled with a trait? For example just like we have the Future trait that can be .awaited we could add another trait that does a more generalized thing. Although at that point I suspect we would pretty much get syntax sugar for monads.

  • Can we let functions limit the kinds of effects they allow, but still being somewhat generic? For example I could see code definitely being unsound with async/generators, but that could somehow manage if destructors where guaranteed to run, so it could still allow non-local returns.

  • Can this be integrated in a backward compatible way? E.g. being able to change old functions that take closures in a way such that they still work with old closures but would also accept new one? I suspect type inference might make this harder or more complicated than it seems though.

I imagine giving labels factual reperesentation:

  • (*mut T,*const fn()) - the first is pointer to place for value; second is pointer to instruction to jump;
    Passed as an argument to consumer function, this makes non local returns not to require inlining.

  • (*mut T,*const fn(*mut U)) - pointer to place where effect consumer yields; pointer to instruction to jump, provide a pointer to resume arg. place for resume argument to be placed there.
    Such use of pointer implies that use of such functions result in a consumer's future to be !Unpin;
    Alternatively, we could store offsets of places in the state; adds one more pointer op, but lifting the restriction.

I see inlining as an optimization, not mandatory thing.

Personally I can't imagine such a trait, albeit I haven't thought deeply.

But given the amount of nuances, I doubt that such trait will be feasible at all.
Moreover, the need for such a trait seems to be absent: We introduced special traits when we either wanted to add flexibility for an otherwise special constructs (see Try trait) or desired a syntax to be a sugar (e.g. async & generator features) for impl Trait types production.

Could you show an example of such code?

I especially designed feature that consumers of effectuful functions say what they can support and will provide explicitly, they pass appropriate labels and an async context inside a functions, closures can capture these on demand.

One mechanism of limiting what a provided closure could do is to use traits like NoReturnEffect, NoGeneratorEffect, NoAsyncEffect (nameing is bikeschedable). They are implemented for closures without any usage of provided effect. This way traits carry their function and provided labels can play role of phantom data.

This is why I asked for another variant of acynchrony syntax - it clashes with async closures and I couldn't come up with a better one.

My design goal is to allow functions to accept TPC closures without any changes. In price of closure always having a local lifetime.

In the examples I've demonstrated use of existing map combinators - they accept plain closures, without any notion of effects.

Addition: TPC closures shouldn't capture non-local labels.

Those don't support calling destructors though, and I can't see how they would be used to implement generators/async since they require completly rewriting the function as a state machine.

Also, what happens when you mix generators/async and non-local returns?

Isn't this also a kind of sugar? async rewrites a function to a state machine that implements Future, this feature also kind of rewrites a function.

The replace_with crate for example uses a destructor to run code needed for soundness. Only as long as destructors are always run it would be sound to accept closures with effects.

...could non-local returns not share machinery with panics?

Assuming An idea for TCP closures and rust's effect system - #23 by atagunov you initiate a non-local return by invoking a method on a special object passed down the call stack; this object records some kind of tag or address.

Panic machinery would go up the stack unwinding until it finds a handler with a matching tag/address. This object also provides storage space to put return value into - a reference into the stack frame of the non-local-return-aka-panic handler.

If a regular panic handler is met while unwinding the stack it would be necessary to unwind past it until correct non-local return handler is found I guess.

... yinz realize you are literally in the process of reinventing the C++ exception unwinder, including the never-actually-resolved-people-just-got-sick-of-arguing-about-it question of how it should interact with thread cancellation panic.

1 Like

Share the exact same machinery with panics? Probably not, that's optimized for the "doesn't unwind" case, which is the opposite of what would happen with non-local returns.

This also doesn't handle generators/async.

In particular this feels very non-zero cost.

Shouldn't cost more than catch_unwind? On each step you compare frame pointer to the one on which you want to stop or something to the same effect.

And you know on which you want to stop because the &PanicInvoker<T> you passed down the call stack has the address of the base frame on which you want to stop. A bit different from C++.

Certainly

It probably costs a bit more than catch_unwind, but the problem is that catch_unwind is already expensive.

Important detail to notice.

We simply forbid non-local returns from async and gen fn's - closures are allowed to return to local fn's scope producing a value. Then rest of code in scope can do something reasonable with labels fn was provided with..

I see, we'll need to store these states inside of their callers states. Representation for labels was only to allow to not inline most of code (not state) to not duplicate it in monomorphic copies.

Now I see that it's smaller optimization than I originally thought.

Fundamentally there should be nothing preventing you to have non-local returns from generators/async, so this sounds like an artificial limitation that creates inconsistency.

Closures are pretty much inlined anyway, so does it change anything if you don't require closures with non-local control flow to be inlineable?

1 Like

Indeed, they can be safely allowed.

My initial concern was like "what if a future is spawned on an executor, and then, after being moved to another thread returns to a non-async code from a runtime's code" that would break runtime as of one of its threads terminated to sync scope.

However, my concerns were just overstatement, as of these futures cannot be spawned: they have local lifetime.

Generators also share this property.

Another point: TPC closures aren't Send nor Sync.

Now, interactions between Asynchrony and Multiplicity.

My view is that asynchrony dominates multiplicity, so consumer of async fn(gctx: label(u64->bool)) will use it like:

...
while let GeneratorState::Yielded(it) = gctx.resume(64).await {
   ...
}
...

Pretty syntaxes are not there yet.

And this brings us to their "full" counterparts. Probably, together they should result in stream literals... But that's outside of current topic.

Edit: what's about denoting asynchrony effect by label(async)?

1 Like

dyn safety and fn pointers:

There are no place for state, produced by asynchrony or multiplicity in case of fn pointers => cannot allow.

Thereof, fn pointers only can have non local returns.

In case of explicit boxed dyn Trait, we allow Fn trait to accept only non local return effect (it does not mutate anything); FnMut is allowed to have rest of effects as long as their state is Unpin. AFAIK boxed things have stable location in memory even in face of allocators API, Unpin here is actually not necessary.

This is also the case for a representation of labels:

The destructors should be run before returning (setting the value, then jumping).

The information passed in the second repr. is indeed insufficient, my bad, but... - what if we do it like that:

(
   *const fn(*mut ResumeTy), /*a callback for setting where to place resume arg*/
   (
   *mut YieldTy /*place for a value*/,
   *mut *const fn()->bool /*next resume address, also tells whether parent coroutine should yield*/
   ) //`yield`info
)

Then:

  1. When a consumer invokes an effectful function, the first thing function does, is set up resume argument address via callback. A place for a next resume argument is set up by via this callback on each (effectful) yield, if the address has changed;

  2. When effectful function yields, it sets up yield value, and a pointer to code where to pass control (it returns).

Effectively, this is "runtime place resolution" like thing.

Lifetimes:

for now, because of the rules, labels always have either lifetime of the caller, or local stack frame lifetime.

In case of lifting the rules and allowing full non local control flow...

In this case we treat them as a structs with references (what they in fact are), any label has one lifetime parameter which can be specified like label<'a>(...) when it's necessary.

Lifetime in signatures are elided, if they are not specified (elision failed => annotation needed).

asynchrony effect syntax:

As of syntax for capturing async env., but not producing a future, I would suggest smth. like fn<async>(...)... as a notation. I don't think we should allow an async fn or an async closure to accept this effect.

What if a function 1 passes a closure (that does a non-local return) to a function 2, which in turn passes it to a function 3. Now the moment the function is run and the return is triggered it needs to run the destructors of function 3's local variables, then function 2's local variables and the function 1's local variables. How can it know it?

I'm not entirely sure that would work (it probably does? not considering the destructors), but anyway this looks a bit too overhead for the average case where callee and closure can just be inlined.

Edit: I'm sorry, re-read the definition of label, I updated it (at least, will) - there were no way to tell when to yield from parent coroutine.

This is necessary for dyn Fn(label(A->B)) and fn<async> only. Any other use case is probably to be inlined.

As of usage, consider an example:

gen fn exmp4(data: impl Iterator<Item=char>) -> () -> [char;2] {
   data.map( //imagine that this takes box
      gen |_: char| loop {
         let ch1 = yield; let ch2 = yield; // here we accumulate 2 characters.
         yield 'fn [ch1,ch2]; //here we yield these right from original context.
      }
   )
}

Given the types from signature, the label type here is:

struct Label<'a>( fn(&'a mut char),(&'a mut [char;2],&'a mut fn() -> bool ) );

original generator uses it like following:

...
let mut r_place: &mut char;
let mut rp_upd = |ch: &mut char| r_place = ch;
let mut f: fn();
let mut yield_slot: [char;2]
//construct a label (all the variables from above),
// pass it into a (boxed) closure; 
//closure inits everything right
while let Some(ch) = data.next() {
   *r_place = ch; //pass data in;
   let should_yield = f(); //resume inner coroutine, at this point `yield_slot` may not be initialized;
   if should_yield  {yield yield_slot;} //else { continue; }
}
...

Non local returns

By example:

fn c(clo: fn()->u64) -> u64 {
   clo();
   unreachable!()
};
fn b(clo: fn()->u64) -> u64 {
   let t: DropType = ...;
   c(clo) + 1
}
fn a(){
   let res = 'lab: {
      let clo = || {return 'lab 10;};
      b(clo);
   };
}

The best solution I could come up with is magic, which is the following:

  1. The closure has captured a return label. => closure's struct has it as a field.
  2. The function b got this closure, sees* captured label, lets call it 'cap => we generate a new label 'replace inside of b, where we:
    1. store 'cap locally;
    2. run destructors;
    3. proceed up by the label 'cap.
  3. When the closure clo is passed down to c it's captured label 'cap is replaced by 'replace.

* Such insight is only possible if such closure comes as a generic parameter where (fn a<F: Fn(label(u64))>(f: &F)...) => no effects for function pointers at all :frowning_face:.

The example then becomes:

fn c<F: Fn()->u64>(clo: F) -> u64 {
   clo();
   unreachable!()
};
fn b<F: Fn()->u64>(clo: F) -> u64 {
   let t: DropType = ...;
   c(clo) + 1 //new, anonymous, label is created => closure is patched.
}
fn a(){
   let res = 'lab: {
      let clo = || {return 'lab 10;};
      b(Box::new(clo)); //original label
   };
}

The advantages of the approach:

  • it chains;
  • it's not (that) expensive;
  • it's transparent;
  • it's still possible to use with existing APIs like map<F: Fn...>.

The disadvantages of the approach:

  • it's transparent:
    We start to generate silent code, it's akin to drop glue, but feels fishy...
  • impossible to use with function pointer and trait objects (without a crazy additional implied trait, which I'll try to design). (I (still) want to allow dynamic use case, just for HOFs and (in future) dylib use trait objects) but the approach below is suitable for them.
  • special implicit(!) trait in trait object for extracting captured labels. only if we want to somehow abstract this magic.

In case of trait objects, I would like to use unwinding machinery for this.

Generator effects

Around a design of label representation I came up with few important points:

  1. how code which is only resumed\called by an fn() can know where the actual state of effectful function\closure is stored?
  2. the consuming coroutine should itself be responsible for providing effects (redirecting resumes) to an effectful code.

So because of these I have to (once again) alter the representation of label:

(
   //Same
   *const fn(*mut ResumeTy), /*a callback for setting where to place resume arg*/
   (
   //Same
   *mut YieldTy /*place for a value*/,
   //Changed
   *mut *const fn(*mut State)/*next resume address, takes state, returning from this indicates readiness to yield*/
   ) //`yield`info
)

So by the logic, now, calling a "resume" function pointer logically borrows corresponding effect. This borrow lasts until effectful function\closure doesn't return.
This mean that having two closures capturing the same label in the same time is not possible.

Now an interesting case:

gen fn a() -> u32 -> u32 {
	let genu = 'upper: gen |u64| -> u64 {
		let geni = |inp: usize| -> usize {
			loop {
				let b32 = yield 'fn 0u32;
				let b64 = yield 'upper 0u64;
				println!("{} and {}",b32,b64);
				if (b64 + b32) >= 200 {return inp};
			}
		}
		//use geni somehow
	}
	//use genu somehow
}

How geni would be implemented?\

  1. geni has captured two effects ('fn and 'upper), thus borrowed two scopes, these borrows are activated only by calling the closure, and last until it returns.
  2. geni, because of coroutine transform, has got its State, which is stored inside of surrounding state (if we were to box genu, this state would reside in an allocation).
  3. on each generator's yield-resume pass geni is resumed with a pointer to its State, resume argument is passed implicitly.
  4. by the time geni returns, scopes it has captured are released, and are again available for use.
    This means that the next user will have to call the callback with pointer to a place it wants the resume argument to be placed, so that consuming coroutine will be able to redirect resumes there.
    The price is one function call and one memory assignment.

Hey, I've totally lost the plot I'm afraid..

So this gets converted into some sort of enum? Like async fn? What trait does the resulting enum implement? How do you use it?

P.S. This is an interesting way to spell the "type", with an extra -> ..