Rust rejects functions of the same type, when a Fn trait bound is used

(I am on nightly)

when impl Trait is used, it is fine :: https://github.com/xieyuheng/sicp-rs/blob/2d1a7cdae50eb1e7abfa8b01deaf1fa7a6b97072/sicp/src/ch_1_3.rs#L81

fn sum (
    term: impl Fn (f64) -> f64, a: f64,
    next: impl Fn (f64) -> f64, b: f64,
) -> f64 {
    if a > b {
        0.0
    } else {
        term (a) +
            sum (term, next (a),
                 next, b)
    }
}

but when trait bound is used :: https://github.com/xieyuheng/sicp-rs/blob/2d1a7cdae50eb1e7abfa8b01deaf1fa7a6b97072/sicp/src/ch_1_3.rs#L58

fn sum <F> (
    term: F, a: f64,
    next: F, b: f64,
) -> f64
where F: Fn (f64) -> f64 {
    if a > b {
        0.0
    } else {
        term (a) +
            sum (term, next (a),
                 next, b)
    }
}

I got the following error :: https://github.com/xieyuheng/sicp-rs/blob/2d1a7cdae50eb1e7abfa8b01deaf1fa7a6b97072/sicp/src/ch_1_3.rs#L72

error[E0308]: mismatched types
  --> sicp/src/ch_1_3.rs:90:23
   |
90 |         sum (cube, a, inc, b)
   |                       ^^^ expected fn item, found a different fn item
   |
   = note: expected type `fn(f64) -> f64 {ch_1_3::cube}`
              found type `fn(f64) -> f64 {ch_1_3::with_sum::inc}`
1 Like

I am asked to not use github issues for this question :: https://github.com/rust-lang/rust/issues/54579

The issue is that Rust functions/closures all have unique types - in your second function, you’re constraining term and next to both be the exact same type (represented by F), rather than two functions with the same signature. The only way you could call the second version of your function would be to pass the exact same function as both parameters!

To get that version to work, I think you’d have to define two type bounds:

fn sum<T, N>(term: T, a: f64, next: N, b: f64) -> f64
where
    T: Fn(f64) -> f64,
    N: Fn(f64) -> f64,
{
    if a > b {
        0.0
    } else {
        term(a) + sum(term, next(a), next, b)
    }
}

The impl Fn version in your original example is basically syntax sugar for doing exactly that :slight_smile:

6 Likes

Thank you 17cupsofcoffee

From the reference, This seems a feature indeed.

For now, It is only a syntax matter for me.
I can just use impl Fn everywhere.

But Fn(f64) -> f64 and Fn(f64) -> f64 are not handled as exact the same type,
seems wrong to me.
(i.e. a problem of the type syetem needed to be fixed)

It’s definitely an oddity - hopefully someone with more knowledge of the compiler than me can weigh in on exactly why it works that way!

There’s nothing to fix here - it’s how closures work: each closure is a unique type, and due to how generics work (monomorphization), this is the natural outcome.

4 Likes

In fact, AFAIK, it's not Fn(f64) -> f64 in any of cases. It's Fn(f64) -> f64 {function_full_name}, as stated in the link by 17cupsofcoffee. Two different functions will have different names (even if their local names are equivalent, they are differently scoped), so the types are different too. Please correct me if I understood it wrong.

1 Like

In general, there is no known way to calculate equality between function-like types (i.e. fns and closures), even if they have the same signature. You could do it in extremely constrained situations but that’s not enough to perform an equality check that one can depend on.
This is the underlying theoretical reason for each closure being of a unique type.

1 Like

If each closure uses its type signature as its type (instead of been uniquely typed),
can you give an example to demonstrate how monomorphization will go wrong ?

Using just the “type signature” is essentially what trait objects do in Rust. They “erase” the concrete type, and instead use dynamic dispatch. So it’s not that monomorphization “will go wrong”, but rather it’s not the purpose it serves.

If you wanted to use type erasure/trait objects, you could write your function as:

fn sum(term: &Fn(f64) -> f64, a: f64, next: &Fn(f64) -> f64, b: f64) -> f64 {
    if a > b {
        0.0
    } else {
        term(a) + sum(term, next(a), next, b)
    }
}
2 Likes

The problem on my side is (syntactically) can I do not repeat the long function type &Fn(f64) -> f64
and write the following instead ::

fn sum <F> (
    term: &F, a: f64,
    next: &F, b: f64,
) -> f64
where F: Fn (f64) -> f64 {
    if a > b {
        0.0
    } else {
        term (a) +
            sum (term, next (a),
                 next, b)
    }
}

Given

let a = 0.5;
let b = 7.0;
let f = |x| { x*a };
let g = |x| { x*a + b };

f and g cannot have the same concrete type because f captures one variable and g captures two. Closures are like structs, so the type of f and the type of g have different sizes and layouts. (Example) The only way you can unify the types is behind a pointer, which is what a trait object is.

2 Likes

If you want to trim down the syntax, you can use a type alias (the below is still using trait objects):

type F<'a> = &'a Fn(f64) -> f64;

fn sum(term: F, a: f64, next: F, b: f64) -> f64 {
    if a > b {
        0.0
    } else {
        term(a) + sum(term, next(a), next, b)
    }
}
1 Like

Fn is a (special) trait and closures are like structs impl the Fn trait.

trait Trait {}

struct Struct1;
struct Struct2;

impl Trait for Struct1 {}
impl Trait for Struct2 {}

fn sum <F> (
    term: &F,
    next: &F,
) where F: Trait {
}

fn main () {
    sum (&Struct1 {}, &Struct1 {});
    //   monomorphization ==>
    // fn sum_struct1 (term: &Struct1, next: &Struct1) { ... }

    sum (&Struct2 {}, &Struct2 {});
    //   monomorphization ==>
    // fn sum_struct2 (term: &Struct2, next: &Struct2) { ... }

    // fn sum <F> (term: &F, next: &F) where F: Trait { ... }
    //   makes the above two monomorphizations ok,
    //   but the following monomorphizations is not ok.

    // just like the error message of misuse of Fn

    // error[E0308]: mismatched types
    //   --> src/main.rs:16:23
    //    |
    // 16 |     sum (&Struct1 {}, &Struct2 {});
    //    |                       ^^^^^^^^^^^ expected struct `Struct1`, found struct `Struct2`
    //    |
    //    = note: expected type `&Struct1`
    //               found type `&Struct2`

    sum (&Struct1 {}, &Struct2 {});
    //   monomorphization =/=>
    // fn sum_struct1_struct2 (term: &Struct1, next: &Struct2) { ... }
}

The problem is function type is handled in two ways in rust

(1) fn – for non local functions

(2) Fn trait – for closure, and closure are handled as structs

I can view this as a feature now.

But this design of function type seems so horrible from type theorists’ point of view …

But this design of function type seems so horrible from type theorists’ point of view

Why?

This was mentioned before by @17cupsofcoffee but the trait bound F represents the same type everywhere in the function signature. IIUC, traits are not types themselves. A struct is a type, and two structs implementing the same trait are still two different types.

The main purpose of types is to distinguish between the different use-cases for data. Because closures can’t be neatly substituted for each other (even when they have the same function signature), we should not be surprised to see a type-based distinction made between them.

In effect, this is a consequence of using a ‘low-level’ closure model. You can always hide closures behind pointers to recover a high-level model that treats them uniformly, and that is what the closure trait objects do. There’s nothing horrible with the theory here; it’s just another application of using types to distinguish things that are semantically differentiated.

2 Likes

We’d better not say “traits are not types”, and say:

  • structs and (primitive types like f64) are concrete types
  • and traits are abstract types

The fact that Struct1 and Struct2 are two different concrete types
implementing the same trait – Trait, is intuitive.

But when I see the types of cube and inc,
I see fn (f64) -> f64,
it is also intuitive to view them as two equivalent concrete types,
implementing the same trait – Fn (f64) -> f64.

Now I learned although they are both explicitly written as fn (f64) -> f64,
they are not viewed by the compiler as equivalent,
implicitly, they are viewed as different unique function pointer types –
fn (f64) -> f64 {ch_1_3::cube} and fn (f64) -> f64 {ch_1_3::with_sum::inc}.


What I failed to understand (at the beginning of this thread)
is the fact that compiler is implicitly doing this for me.

Without knowing compiler is doing this for you,
don’t you think it is intuitive to view the types of cube and inc
(which are written as fn (f64) -> f64 in their type signature)
as equivalent ?

https://doc.rust-lang.org/reference/types.html#closure-types

A closure expression produces a closure value with a unique, anonymous type that cannot be written out.

Because the above treatment of function type is not noraml.

I do not know how I can convince you this.

Maybe it is purely subjective.
Maybe only the authority of some type theoy textbooks will convince you.

Yes, you are right.
I am just surprised by this ‘low-level’ closure model.
I learned a lot in this thread. Thanks ~

1 Like