Implement closure traits on `&T` when `T` implements them?

[CloudiDust]

When discussing RFC 883, I found the following problem:

Currently in Rust, a plain function is callable, and any level of references to a plain function is also callable, but only the plain function itself is passable as a closure:

fn echo(val: &str) { println!("{}", val); }
fn add_one(val: i32) -> i32 { val + 1 }

fn main() {
   let ref_ref_ref_echo = &&&echo;
   let ref_add_one = &add_one;
   ref_ref_ref_echo("Hello"); // Okay.
   vec![1i32, 2, 3].into_iter().map(ref_add_one); // Error.
}

Currently, there are no transitive closure trait implementations on references to closures, which brings us such inconsistencies, should those implementations be added?

[theme]

There is one little problem though: It can sometimes change or hide the asymptotic complexity of a function.

For example, this function calls f(0), f(1), f(2), ... f(n):

fn foo<F: Fn(u32)>(f: &F, n: u32) {
    if n != 0 { foo(f, n-1); }
    f(n);
}

This function runs in O(n).

However, if your proposal is allowed, then it is possible to write this:

fn foo<F: Fn(u32)>(f: F, n: u32) {
    if n != 0 { foo(&f, n); }
    f(n);
}

Which, unfortunately, runs in O(n^2). It might not be so obvious, so here is the explanation:

When calling f(n), f doesn't have to be dereferenced. When calling f(n-1), f has to be dereferenced once. When calling f(n-2), f has to be dereferenced 2 times. ... When calling f(0), f has to be be dereferenced n times Thus, there must be a total of n*(n+1)/2 dereferences.

For non-recursive functions (i.e. most of the higher-order functions), it is possible to write |x| foo(x) to convert from &Fn(T) to Fn(T). Most code use closure literals directly anyway, so this workaround is rare.

For recursive functions, I think that explicit &F's in the function signature is OK.

Note that I realized this when I was writing actual code and I wrote something similar to this:

fn foo<F: Fn(u32)>(f: F, n: u32) {
    if n != 0 { foo(|x| f(x), n); }
    f(n);
}

fn main() {
    foo(|_| {}, 10);
}

playpen

The result was: error: reached the recursion limit during monomorphization, which made me notice that O(n^2) blow up.

[reem]

This is really a special case of the general issue that &T (and &mut T, and Rc<T>, and Box<T>) doesn’t implement the traits of T in the general case, even if only the forms of self which are needed by those traits is available on that pointer type.

[CloudiDust]

@theme, I don’t think the playpen snippet blew up because O(n^2), but because the recursive calling of foo(|x| f(x), n); caused a monomorphization infinite loop.

The following snippet would also fail to compile:

fn foo<F: Fn(u32)>(f: F, n: u32) {
    if n != 0 { foo(|x| f(x), n - 1); }
    f(n);
}

fn main() {
    foo(|_| {}, 0);
}

[Diggsey]

Actually, that’s not correct. You’ll get the recursion limit error for any value, just try putting in 2. The problem is that each monomorphisation of “foo” will generate a new unboxed closure type, which will in turn cause the compiler to try to monomorphise one more version of “foo”: foo<unboxed_closure_1> => foo<unboxed_closure_2> => foo<unboxed_closure_3> => etc.

To get this to work you need to use type erasure, so that there’s only ever single monomorphism of “foo”.

@CloudiDust Ah, you beat me to it…

[CloudiDust]

@Diggsey, Yes, the actual problem is the |x| f(x) closure in foo(|x| f(x), n - 1);

But type erasure is not the only way to avoid the infinite loop. By passing f directly, we can avoid all the extra monomorphisations.

The following code will compile (did some modifications to f(n) to avoid the “use-after-move” issue):

fn foo<F: Fn(u32)>(f: F, n: u32) {
    if n != 0 { foo(f, n - 1); }
    else { f(n); }
}

fn main() {
    foo(|_| {}, 10000000);
}

The above snippet would blow the (runtime) stack in -O0 but run very quickly in -O2. (All hail tail call optimizations!)

[CloudiDust]

FWIW, I don’t believe we should do very aggressive auto-dereferencing by implementing all implementable traits transitively on reference types (and smart pointers). But I think a balance should be found. (We already have deref-coercions and . to do a lot of auto-dereferencing.)

Here, the fact references to functions are callable but not usable as closures is surprising. I think either “only functions are callable and usable as closures” or “functions and references/pointers to them are all callable and usable as closures” would be a more consistent choice. I lean towards the latter.

[theme]

@CloudiDust This is what I mean by the O(n^2) thing:

trait NewFn {
    fn call(&self, u32);
}
impl<F: Fn(u32)> NewFn for F {
    fn call(&self, x: u32) { self(x); }
}
impl<'a, F: NewFn + ?Sized> NewFn for &'a F {
    fn call(&self, x: u32) { (**self).call(x); }
}

fn foo(f: &NewFn, n: u32) {
    if n != 0 { foo(&f, n - 1); }
    f.call(n);
}

fn main() {
    foo(&|_| {}, 40000);
}

playpen

This triggers a timeout on playpen even with -O2

[CloudiDust]

@Theme, yes, I see the problem now.

However I think this is a problem that can happen for any transitively implemented trait methods. (There is nothing special about the NewFn trait.) Am I right?

If so, as long as people don’t use unnessary &s this shouldn’t matter much in practice.

Then again, do we want to add possibility of misuse just for the sake of consistency?

[CloudiDust]

I realized, another way to look at this would be:

Only a function itself is callable and passable as a closure, but the function calling operator () does auto-dereferencing. (Just like the field accessing/method calling operator . does auto-dereferencing.)

EDIT: and the following snippet prints “Hello!”, which shows that references to closure literals are “callable” without implementing the closure traits, and can be seen as a proof of the above interpretation.

fn main() {
    (&&&(|| { println!("Hello!"); }))();
}