Is `FnMut() + Clone + Send` strictly more expressive than `Fn() + Sync`?

1

The context is a feature request for the Paralight iterator library: Accept `FnMut() + Clone + Send` instead of `Fn() + Sync` in `ParallelIterator` and similar APIs · Issue #27 · gendx/paralight · GitHub.

For iterator combinators like .map(), the current API accepts functions that implement Fn() + Sync, for example: ParallelIteratorExt in paralight::iter - Rust. However, @discreaminant2809 pointed out that FnMut() + Clone + Send is more expressive, in that any f implementing Fn() + Sync can be transformed into a FnMut() + Clone + Send by taking a reference to it &f (Rust Playground).

However, this comes with tradeoffs in terms of ergonomics if users have to pass lambdas by reference. The API definitions may also appear more complex. So I'd like to know if there is an example of a FnMut() + Clone + Send function that cannot be transformed into a Fn() + Sync.

My reasoning so far is that:

  • Fn() captures immutable references only, while FnMut() also allows captures of mutable references.
  • However, mutable references are not Clone (due to aliasing rules), so a FnMut() + Clone can only capture by immutable reference and should therefore also implement Fn().
  • A function inherits the Send/Sync bounds of the state it captures. If a function captures an immutable reference &T, we know that &T will be both Send + Sync if and only if T is Sync (according to the documentation of the Sync trait Sync in std::marker - Rust). So Fn() + Sync and Fn() + Send are equivalent.

Is that correct? Or is there a function that implements FnMut() + Clone + Send but not Fn() + Sync (and cannot be generically transformed into a Fn() + Sync)?

2

If I understand the API correctly (that init is called for every worker) then their uscase is already possible using the Accum generic.

FnMut(Item) + Clone is equivalent to the init (which is the Clone part) and Fn(Accum, Item) . While the latter allows for more flexibility by not requiring Clone and instead allowing you to capture the env when preparing the workers.

More generally, I don't really see a FnMut where a Clone does something useful. A dedicated initializer function is always better.

3 
fn never_sync_and_never_fn() -> impl FnMut(u32) + Clone + Send {
    let mut x : Cell<u32> = Cell::new(0);
    move |k : u32| {
        *x.get_mut() = k
    }
}

there is no way to make this an Fn(), or make it Sync, unless you add something like a Mutex which would probably ruin the purpose

4

OK, so adding the move keyword allows creating a FnMut() + Clone by enclosing a mutable state (regardless of Cell). However, this state isn't captured but moved into the closure, meaning that Clone duplicates the state.

In the context of iterator APIs, when Clone happens would remain unspecified, so that'd likely not be desired from a user's perspective. Adaptors like .map_init() seem more suited for the purpose.

In your specific example, I don't see what the Cell brings as it's contained in a mutable variable (i.e. interior mutability is not needed), so arguably this specific lambda could be transformed to not have a Cell at all.

5

i think i answered the question that was given well.
but if you specifically want something "reasonable" (which is kinda subjective), here is

use std::collections::HashMap;
use std::cell::Cell;
fn never_sync_and_never_fn() -> impl FnMut(i32) -> i32 + Clone + Send {
    let mut reusable_scratch_space: HashMap<u32, Cell<u32>> = HashMap::new();
    move |k : i32| {
        reusable_scratch_space.clear();
        do_math_with_minimal_allocation(k, &mut reusable_scratch_space)
    }
}


fn do_math_with_minimal_allocation(_ : i32, scratch_space : &mut HashMap<u32, Cell<u32>>) -> i32;

optimization of scratch space is a common optimization trick, and Cell<u32> is a convenient element type that allows having multiple "mutable" references to the same value at the same time

6

It's not strictly more expressive, both have things they allow that the other disallows. An example for something that is !(Fn() + Sync) was already provided, here's an example for !(FnMut() + Clone + Send):

fn never_clone_and_never_send(mutex: &std::sync::Mutex<i32>) -> impl Fn() -> i32 + Sync {
    let guard = mutex.lock().unwrap();
    move || *guard
}
7

Along with the other examples of capturing by value, you can capture a &mut _ (e.g. by move) and still have an implementor of Fn() by only using the &mut _ in ways compatible with &&mut _.

More concretely, the Send Sync and Clone capabilities depend on what was captured, but the Fn() versus FnMut() capabilities depend on how the body of the closure needs to access the captures.

Think of captures as fields in a struct, and for the traits...

    // All closures implement `FnOnce(...) -> R`
    fn _fn_once(mut self, ...) -> R { ... }

    // If the closure body is compatible with this signature, the
    // closure can also implement `FnMut(...) -> R`
    fn _fn_mut(&mut self, ...) -> R { ... }

    // If the closure body is additionally compatible with this signature,
    // the closure can also implement `Fn(...) -> R`
    fn _fn(&self, ...) -> R { ... }

With that mindset, constructing something that is e.g. Fn() + Send but not Fn() + Sync is simply constructing a closure that captures something which is Send but not Sync with a body compatible with &Self.[1]

Revisiting your bullet points with this in mind, we have:

  • Fn() can capture by value (including &mut _s), not just &_s, so long as the body is compatible with &self
  • A FnMut() + Clone can't have captured a &mut _ directly,[2] but that doesn't mean the body is compatible with &self (nor that it only captured &_s), so it may still not implement Fn()
  • Fn() captures aren't limited to &_s so the reasoning here doesn't hold

  1. Additionally on unstable, you can implement Fn for your own ADTs. Which you could think of as closures "capturing" arbitrary types unrelated to the closure body. ↩︎

  2. in contrast with Arc<&mut _> or whatever ↩︎

8

you seem to have missed a part :

that is a fact.
because their code does not require 'static, a user can always write &f instead of f so FnMut() + Clone + Send is stricly more expressive :

fn never_clone_and_never_send() -> impl Fn() -> i32 + Sync {
    static M : std::sync::Mutex<i32> = Mutex::new(0);
    let guard = M.lock().unwrap();
    move || *guard
}

fn never_sync_and_never_fn() -> impl FnMut() -> i32 + Clone + Send {
    let mut reusable_scratch_space: HashMap<u32, Cell<u32>> = HashMap::new();
    move || {
        reusable_scratch_space.clear();
        0
    }
}


fn more_expressive(_ : impl FnMut() -> i32 + Clone + Send) {}
fn less_expressive(_ : impl Fn() -> i32 + Sync) {}


fn more_expressive_test() {
    more_expressive(&never_clone_and_never_send());
    more_expressive(never_sync_and_never_fn());
}

fn less_expressive_test() {
    less_expressive(never_clone_and_never_send());
    more_expressive(never_sync_and_never_fn());  // compiler error ! nothing can be done
}