Function Traits and Closures

help
1

Hi, I'm new to Rust, but an old hand with Haskell and C++. I am currently implementing the algorithms from the 'Iterators' chapter of Stepanov's "Elements of Programming" to see how well Rust copes with the kind of generic programming I want to do. I have two algorithms, and I am puzzled by the difference in behaviour. Here they are (note: this is using an iterator trait implemented like a C++ iterator, not the standard Rust one. At the moment I am interested in replicating the algorithms as they are, rather than implementing safe versions, and in any case I am interested in iterators with static safety guarantees, not runtime range checks).

pub fn for_each<I, P>(f : &I, l : &I, mut p : P) -> P
where I : Iterator + Readable, P : FnMut(&I::value_type) {
    let mut i = (*f).clone();
    while i != *l {
        p(i.source());
        i = i.successor();
    }
    p
}

pub fn reduce_nonempty<I, Op, F, D>(f : &I, l : &I, mut op : Op, mut fun : F) -> D
where I : Iterator + Readable, Op : FnMut(D, D) -> D, F : FnMut(&I) -> D {
    let mut i = (*f).clone();
    let mut r = fun(&i);
    while i != *l {
        r = op(r, fun(&i));
        i = i.successor();
    }
    r
}

Note: both 'P' in the first, and 'F' in the second example are function traits that borrow their argument. Now I try and test both of these (I can post extra code if necessary, but I am trying to keep this to just the relevant bits):

let mut s : i64 = 0;
for_each(&f, &l, |&v| s += v);
assert_eq!(s, 6);

(aside: I wonder if I should be cloning 'v' here as '+=' takes ownership of the rhs?, is there a silent copy because the value is an integer? Is there any way to disable all silent copying, so that everything, even integers, have to be explicitly cloned? Otherwise I may get weird move errors when using generic functions with uncopyable objects)

Note: we have to borrow 'v' in the closure or we get a type mismatch (as expected). However with "reduce_nonempty" borrowing the argument produces an error and I have to write:

let r1 = reduce_nonempty(&f, &l, |a, b| a + b, |a| a.source().clone());

Alternatively this works:

let r1 = reduce_nonempty(&f, &l, |a, b| a + b, |&ref a| a.source().clone());

Why do the closures/function traits behave differently in these two examples?

2

Well, you haven't given us much to work with, so I'll make some guesses.

The & in |&v| s += v is not borrowing v. It is, in fact, doing the complete opposite. Arguments are patterns, not expressions, so you're actually dereferencing the argument [1]. It's more-or-less the same as writing either of:

|v| { let &v = v; s += v }
|v| { let v = *v; s += v }

Guess: I::value_type, whatever that is, has a bound on Copy, which allows the compiler to implicitly copy the value of v out from the reference.

&ref a is basically dereferencing a, then binding to the value by-reference, effectively not doing anything.

Guess: the "error" is about not being able to move out of a reference. This would be because I does not have a bound on Copy.

[1]: &self and &mut self are exceptions to this because they're used so very often.

3

Sorry if there is not enough here, I didn't want to post lots of code, but I can post any definitions that will be helpful. However I would comment that these are supposed to be generic functions so all that is really missing is the definitions of Iterator and Readable, everything else should be irrelevant, we should not care about the type of collection being iterated over, nor the contents, so there is no need to post that. Also the particular implementation of Iterator and Readable in use should be irrelevant. Here's the missing definitions:

pub trait Regular : PartialEq + Clone {}

pub trait Readable : Regular {
    type value_type : Regular;
    fn source(&self) -> &Self::value_type;
}

pub trait Iterator : Regular {
    type distance_type : Integer;
    fn successor(&self) -> Self where Self : Sized;
}

So closure arguments behave differently to function arguments? That would explain why it seems odd. In fact as I am borrowing the contents of a collection I suspect it cannot be moved, and hence what I really need is:

|v| s += (*v).clone();

Which makes sense now.

4

Actually, closure arguments behave the same as function arguments. It's just &self and &mut self that are exceptions, so far as I can recall.

Also, you shouldn't need to do (*v).clone(); just v.clone() should suffice; method calls will auto-deref as necessary.

If you're not aware, there's http://play.rust-lang.org/ where you can post a minimal example of the problem. It helps a lot to have the complete code on hand.

Especially when you're redefining a standard trait to mean something completely different. :slight_smile:

5

Auto-deref seems problematic to me, I would rather know explicitly that a dereference is happening. I find the automatic insertion of dereferences and copies to be like auto-casting in C/C++ it makes you unsure of what is happening. Is there any way to get the compiler to disable auto-deref and auto-copy and return errors (or even warnings) when these things happen?

Edit: I realise now I was getting confused between the type signature of the value and the value itself in the function signatures.

6

Thinking about this, what I really want to say is something like (making up some syntax):

 |v : &V| s += (*v).clone();

Or for a closure that expects an iterator:

 |i : &I| i.source().clone()

Can I do something like that?

Edit: maybe I don't want to after all, as Rust should infer the correct types. I guess my main concern is that there may be some implementation of iterator for which it no longer works. For example if my test case is a vector of integers, the way I had it originally would work fine, as a copy will get inserted silently. However it would then fail if the array contents were not copyable (but obviously defined AddAssign).

7

Not that I know of. As someone who used Rust before it did this as widely as it does now... it was not fun. Honestly, I haven't noticed any issues with it.

8

The problem is the type of the closure becomes more polymorphic than I want. For example:

|v| s += v.clone()

Here 'v' could be a value or a pointer (and if it allows multiple auto-dereferences) a pointer to a pointer to a value. I may actually want to clone the reference and not the value referenced as well.

Edit: Or maybe linear typing means this is not an issue? It doesn't seem to be obvious to me that this is less of a problem than it would be in C++, but maybe its a more subtle consequence of linear types? Auto-copy seems more of a problem for writing generic code than auto-dereference perhaps.

9

Rust checks generics when they are defined, not when they are expanded. If a generic compiles at all, it'll work for any type that you can instantiate it with [1].

First of all, it won't auto-deref through type parameters. A &T will be auto-dereffed to T, but no further... unless you specifically state that you want T: Deref<Target=SomeOtherType>, which which case I believe the compiler will auto-deref through T to SomeOtherType if necessary.

Again, the compiler will only do things that are possible with the bounds you specifiy, nothing more.

As for cloning references, they're Copy so it's a bit of a moot point. You can always specify exactly which implementation of a trait you want, though: <&T as Clone>::clone(&v) [2].

[1]: There is one exception I'm aware of to this: there's a bug whereby function pointers implement Copy but don't implement Clone. This is impossible, and causes the compiler to completely lose its marbles if you try to clone a function pointer from inside a generic function. Presumably, that will be fixed at some point.

[2]: &v because Clone::clone takes &self, and in that expression, Self is &T, so the parameter should be of type &&T

10

Does that work if the generic function relies on an implicit copy operation, and you then use it with a non-copyable type? Does auto-copying create a whole in the definitional type checking of generics?

11

You don't get implicit copy unless the type in question has a Copy bound applied to it. If you have a Copy bound on a type, it is impossible to substitute in a non-Copy type.

1 Like
12

What about in closures, where the types and their constraints seem to be inferred?

13

They are inferred, but they still can't "see through" the generic parameters. They're no different to anything else inside a function. It doesn't matter if a generic type T is really i32: if you didn't specify T: Copy, nothing depending on T can exploit that.

14

Yes, I think i my case the problem comes from using a value with a concrete type from the environment, like this:

let mut v = [0, 1, 2, 3];
let f;
match v.first_mut() {
    Some(start) => {
        f = SliceIterator::new(start);
    },
    _ => unreachable!()
}
let l = f.clone() + v.len();
assert_eq!(v.len(), l.clone() - f.clone());

let r1 = reduce_nonempty(&f, &l, |a, b| a + b, |a| (*a.source()).clone());
assert_eq!(r1, 6);

However this also works:

let r1 = reduce_nonempty(&f, &l, |a, b| a + b, |a| (*a.source()));
assert_eq!(r1, 6);

*a.source will return the value that is acutually in the slice. As it is impossible to move out of a slice the clone should be required, however this works, presumably because it can silently copy. There are no copy bounds on 'reduce_nonempty', so it must be allowing it because it can infer the concrete type of the slice and its contents. In other words type inference knows it is an i32, and it is copyable, even though I have no Copy bounds on any functions.

15

Yes; the closure is compiled based on the context where it's defined, not where it's used. What I mean is that if the closure is inside a generic function or impl, and it uses generic types, it's subject to the same restrictions as everything else.

16

I can prevent that by putting the test itself into a generic function like this:

fn test_reduce(f : &I, l : &I, z : I::value_type)
where I : Iterator + Readable, I::value_type : ops::Add + fmt::Debug {
    let r2 = reduce(f, l, |a, b| a + b, |a| (*a.source()).clone(), z);
    assert_eq!(r2, z);
}

But I now have the opposite problem, I can't work out the correct bounds for the recursive addition. I get an error like this:

src/lib.rs:302:38: 302:43 error: mismatched types:
 expected `::value_type`,
    found `<::value_type as core::ops::Add>::Output`
(expected value_type,
    found Output) [E0308]
src/lib.rs:302         let r2 = reduce(f, l, |a, b| a + b, |a| (*a.source()).clone(), z);
                                                    ^~~~~

I am not sure how to fix this?

17

TLDR: I::value_type: ops::Add<Output=I::value_type>

expected `X`, found `Y`

Just follow the types. a + b is really Add::add(a, b). Add's definition is:

pub trait Add<RHS = Self> {
    type Output;
    fn add(self, rhs: RHS) -> Self::Output;
}

The type you're constraining is I::value_type, which means that's what Self is, so the actual bound is:

I::value_type: ops::Add<I::value_type>

i.e. RHS is also I::value_type. This means that you're invoking a function with signature fn(I::value_type, I::value_type) -> <I::value_type as Add>::Output [1]. So what's Output?

And there's your problem. The compiler is using that path because it doesn't know anything else about Output. It isn't constrained by anything, so it could be literally anything. In particular, it can't prove that it's the same type as I::value_type, but that's the return type reduce is expecting.

The solution is to just constrain Output:

I::value_type: ops::Add<Output=I::value_type>

(I'm leaning on the default assignment for RHS to avoid specifying it.)

One thing to note: X = Blah is used to define default assignments for type parameters when defining generics, but it's used to constrain associated types (like Output) when instantiating them. Yes, it's a bit confusing, but that's how it shook out.

[1]: <Self as Trait>::X is just the fully qualified way of referring to some associated item X of a trait Trait, as defined in the implementation of that trait for type Self.

18 
fn test_reduce(f : &I, l : &I, z : I::value_type)
where I : Iterator + Readable, I::value_type : ops::Add + fmt::Debug

Gives:

src/lib.rs:300:70: 300:83 error: unsupported cyclic reference between types/traits detected [E0391]
src/lib.rs:300     where I : Iterator + Readable, I::value_type : ops::Add + fmt::Debug
                                                                                    ^~~~~~~~~~~~~

Which seems problematic?

The associated types seem to behave a bit weirdly, as I would expect them to be functionally dependant on the type of the object.

Edit: Turns out I need to use the more explicit syntax: <I as Readable>::value_type : ops::Add<Output = I::value_type> Why does that make a difference?

19

No idea. Might be a false positive, might be that it just doesn't like I being restricted based on a cyclic non-specific associated type path.