Function composition in the standard library

libs
1

Function composition is a major building block of functional programming. For instance (e.g. in Haskell f . g gives you the same function as h x = f (g x), in scala g.andThen(f) or f.compose(g) do the same).

It would be nice to have a way to do this in rust, and ideally a way that the compiler understands so that the composed function can be optimized as a single unit.

I posted this issue: https://github.com/rust-lang/rust/issues/28226

which contains a suggestion on how this could be done (which I did not write).

#![feature(unboxed_closures, core)]

fn succ(x: i32) -> i32 { x + 1 }
fn sq(x: i32) -> i32 { x * x }

struct Compose<F, G>(F, G); 
impl<R, M, A, F: FnOnce(M) -> R, G: FnOnce<A, Output=M>> FnOnce<A> for Compose<F, G> {
    type Output = R;
    extern "rust-call" fn call_once(self, args: A) -> R {
        let Compose(f, g) = self;
        f(g.call_once(args))
    }
}
impl<R, M, A, F: FnMut(M) -> R, G: FnMut<A, Output=M>> FnMut<A> for Compose<F, G> {
    extern "rust-call" fn call_mut(&mut self, args: A) -> R {
        self.0(self.1.call_mut(args))
    }
}
impl<R, M, A, F: Fn(M) -> R, G: Fn<A, Output=M>> Fn<A> for Compose<F, G> {
    extern "rust-call" fn call(&self, args: A) -> R {
        self.0(self.1.call(args))
    }
}

fn main() {
    let f = Compose(succ, sq);
    println!("{} {}", f(5), f(6));
}

It was suggested I post this here for pre-RFC discussion (although a pull request to add this seems pretty straightforward).

One thing the above does not address is composing Box<FnBox()>, Box<Fn()> which will likely come up in functional code where we have functions that return functions.

5 Likes
2

I was asked for a use-case for this on the github issue. The main reason is to be able to return an unboxed closure when composing functions and an example is given in the github issue.

1 Like
3

If anyone else was confused like me why |x| succ(sq(x)) isn’t sufficient: Compose<F, G> has a size that is known if you know what F and G are (since it doesn’t close over any other data), so you can use it as a return type or part of a return type for a function that’s generic over F and G. The concrete type of |x| succ(sq(x)) can’t be named, and Fn(A) -> R is just a trait so it can’t be a return type. @Posco wrote a nice example on the bug.

The ability to return unboxed closures in general (formerly RFC 105, currently… waiting on a better idea, as far as I can tell?) seems like it’d solve this in a more general way, but I can imagine a good argument for Compose being an important enough special case to have right now, especially since the ability to return unboxed closures doesn’t seem like it’ll happen imminently.

1 Like
4

If we believe that there is a better solution on the horizon, then I'm not quite sure what the argument is for adding this now. I don't sense a particularly pressing need for this in std specifically. It looks like you could define this in an external crate to hold you over.

1 Like
5

If it doesn’t need language level support, I’d like to keep it out of libstd until it’s baked awhile and for potential competitors to show up.

6

I actually don’t understand what that extern "rust-call" means in the code (which was given to me on IRC).

I assumed this was something that signified some kind of compiler code around closures. Is it perfectly legitimate to have that in library code outside of std?

As for a better solution on the horizon, can you send me the RFC for the better solution? The RFC mentioned above was closed and I didn’t see a replacement.

@havvy do you have any ideas what a competitor would look like? It’s a shame for everyone who wants function composition on unboxed closures to copy or take an extra dependency.

7

Yes. It works in the playpen on a nightly compiler, so it will work with yours too. (You won't be able to get this on a stable compiler though.)

I don't think it exists yet. I imagine it would be the RFC that provides abstract return types, which would enable you to return something like |x| f(g(x)) without paying the overhead of boxing.

std has a high bar for inclusion. Namely, it's not clear to me how much Rust code in the wild would benefit from a construct like Compose. A good way to answer this question is to put it in a crate and see what happens.

1 Like
8

I actually don't understand what that extern "rust-call" means in the code (which was given to me on IRC).

It's calling into a compiler intrinsic. This is the same code that's used for implementing mem::forget, for example.

Is it perfectly legitimate to have that in library code outside of std?

No, stabilizing the compiler intrinsics themselves sounds like a horrible idea.

As for a better solution on the horizon, can you send me the RFC for the better solution? The RFC mentioned above was closed and I didn't see a replacement.

That's because it hasn't been replaced. I think that the reason for this is that there are so many things people want added to the type system, including type constructors, type-level integers, abstract return types, and associated constants. Adding some of these would either allow people to fake the other (abstract return types could be used to fake type constructors) or would exacerbate the missing other (type constructors without type-level integers would make fixed-length arrays even worse than they already are). They're working on a way to solve all these problems with a small number of orthogonal, composable features. Look up Higher-Kinded Types.

@havvy do you have any ideas what a competitor would look like? It's a shame for everyone who wants function composition on unboxed closures to copy or take an extra dependency.

Dependencies are much cheaper than stabilization, especially with Cargo.

9

Abstract return types on its own wouldn’t completely replace this, or not as nicely, at least not without additional nontrivial extensions. You would have to write something like:

fn compose<A, B, C, F: Fn(A) -> B, G: Fn(B) -> C>(f: F, g: G) -> abstract Fn(A) -> C { move |a| g(f(a)) }

fn compose_mut<A, B, C, F: FnMut(A) -> B, G: FnMut(B) -> C>(f: F, g: G) -> abstract FnMut(A) -> C { move |a| g(f(a)) }

fn compose_once<A, B, C, F: FnOnce(A) -> B, G: FnOnce(B) -> C>(f: F, g: G) -> abstract FnOnce(A) -> C { move |a| g(f(a)) }

The issue is that there’s no way to say things like “the output abstract type is FnMut iff the input types are”. Off the top of my head, I don’t think the more-general formulation of named module-level abstract types would provide for this either. (And, for what it’s worth, my sense is that any extension enabling this would likely be too complex to be worthwhile, considering that you can just use structs with explicit impls for this instead.)

So I think that struct Compose is in fact the right way to do this, and will be for some time. Inclusion in std might be reasonable from my perspective.

11

I’m confused what is being suggested here.

When I ask: “Is it perfectly legitimate to have that in library code outside of std?”, the answer was: No due to the bad idea of stabilization of compiler intrinsics.

Then it is stated that adding dependencies via cargo is cheaper than stabilization (std library in this case, I presume).

So, is the your suggestion to do this in a library outside of std (at risk of changing compiler intrinsics) or not (unstable label on a new Compose struct)?

I’m surprised it would be this hard to get something as simple as this in. I feel like there is good evidence this is valuable and simple to add (function composition being very common, wanting it to be as fast as possible in a motivation to use Rust, and implementing it requires no changes to the language or compiler).

12

The cost, in order from most expensive to least expensive, is:

  1. Stabilizing a compiler intrinsic: this is the most costly because, right now, there are no stabilized compiler intrinsics. The closest things we have are stabilized functions that are direct re-exports of intrinsics (like mem::forget) and magic lang-items (like Box’s “Deref Move”). Committing to a compiler intrinsic means committing to having the feature directly inside the compiler itself, even if we could otherwise switch to implementing it in terms of other features later.

  2. Stabilizing a standard library feature based on an intrinsic: this requires us to maintain the interface forever, but we can change (aspects of) the underlying implementation. If we later add features that allow the feature to be implemented on top of the rest of the language, we can do that.

  3. Creating a library on Crates.IO: Seeing as cargo allows multiple versions of the same library in one project, changing the interface of a lib crate is as cheap as changing an API can get.

As for what I would like? Allow implementing the Fn* traits without having to mark the functions as extern "rust-call", the same way Drop already works. That allows us to use option #3.

13

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.