Pre-RFC: Primitive Closure Type

language design
1
  • Feature Name: closure_primitive
  • Start Date: 2023-12-23

Summary

This is a way to allow closures to be primitives rather than traits. At some point this may be the default method, and the traits could be deprecated.

Motivation

This is to be done to allow for things that the trait system does not allow, as well as for greater readability and usability. For expample, the trait system does not allow something like nested impl traits, so something like:

impl Fn(impl Fn(T) -> T)

would not be allowed.

Guide-level explanation

In order to enable this feature, you will use:

#[feature(closure_primitive)]

This type can be used as (<parameters type a>, <parameter type b> -> <return type>). This is different then say:

impl Fn(<parameter type a>, <parameter type b>) -> <return type>

So a function that takes a string and returns a function that takes a function and manipulates the prior string would act like this:

fn manipulate(s: &str) -> ((&str -> &str) -> &str) {
    |f| {
        f(s)
    }
}

While this specific use-case is rare, there are many examples where people want to nest closures (in fact, that's how they're most commonly used, so people can nest closures within normal functions.

Reference-level explanation

Ths will be implemented similarly to how closures are implemented currently, simply with the syntax shown shown here, and without the trait system.

Drawbacks

If we deprecate closures-as-traits, this could create issues with backwards compatibility, but if we don't, and they remain used, this could mean that we have to support two systems infinitely.

Prior art

In many functional languages such as Haskell and Futhark, anonymous functions are not structures, traits, or the such, but primitive types.

Unresolved questions

None currently.

2

How would this type be represented in memory? If it can hold any function with that type, it seems like it'd have to be like a trait object, which likely involves a heap allocation; Rust prefers to make heap allocations explicit, rather than have syntax that allocates automatically.

Your function can already be implemented, if verbosely, as follows:

fn manipulate<'a>(s: &'a str) -> Box<dyn Fn(&'a (dyn Fn(&str) -> &str + 'a)) -> &'a str + 'a> {
    Box::new(|f: &dyn Fn(&str) -> &str| {
        f(s)
    })
}
4 Likes
3

It could be represented as instructions and pushed onto the stack, or it could be represented similarly to however normal functions are.

4

Normal functions are indeed represented as instructions, but those instructions are determined at compile time and included in the binary; a function that contained the runtime value of s could only be reduced to instructions by just-in-time compilation (JIT), which is very different than how Rust does things. (Or Haskell, for that matter. Haskell has an easier job here because it doesn't have the high performance goals that Rust does.) And you can't just put those instructions on the stack, because, for security reasons, the stack may not be executable memory.

3 Likes
5

Normal functions are represented by unique unnameable ZST types that implement the Fn* traits, exactly the same as closures are represented by unnameable potentially-ZST types that implement the Fn* traits. Both functions and ZST closures can be coerced into fn() references, state carrying closures cannot.

1 Like
6

The important question this needs to answer to be a good RFC is exactly how this problem is solved; how the these closure types are represented at run time, and what the features, restrictions, and performance characteristics that follow from that are.

1 Like
7

This is not a fundamental limitation, and could be lifted. But the sticking point is that this (probably) wants a GATified Fn, because the closure itself is expected to be generic.

Generic closures have their own can of worms independent of everything else. The way to handle this need right now is to define specific single-function-traits for whatever functionality you need and structs to implemented it manually, instead of relying on closures, or to make everything use dyn.

3 Likes
8

This is a way to allow closures to be primitives rather than traits.

This is already incorrect. Closures are not traits, closures are their own unique type (that happens to implement the function traits). Every closure gets its own unique type.

let a = || true;
let b = || false;

These two closures have different types. This is important, because it allows for very efficient monomorphization. If those closures were primitives and both had the type () -> bool, then Rust would be a lot less efficient.

let x = (0..10).filter(|_| true).count();
let y = (0..10).filter(|_| false).count();

The fact that the two closures are different types is important, as it guaratees that we get a unique monomorphization for both count functions. This ensures that both of these chains will optimize to 10 and 0 respectively, instead of actually having to do a loop. In this simple example, inlining may be enough to do it even if they were the same type, but for larger programs, the monomorphization is important.

This pre-RFC seems to misunderstand what closures actually are and why they are the way they are, which is very important for any RFC wanting to change how closures work.

6 Likes
9

a function that contained the runtime value of s could only be reduced to instructions by just-in-time compilation (JIT), which is very different than how Rust does things.

High-jacking the thread somewhat but this would be really nice to have and I think Rust could support it in principle (though in practice it'd be far too much work to implement).

Here's how I imagine it working: every closure type has an additional jit_recompile method which allocates some memory and generates new, optimized machine code with all the closure's captured data inlined into the code, then returns a pointer to the code as some kind of FnBox type.

So, for example, suppose I have this function:

fn make_divider(denominator: u32) -> impl Fn(u32) -> u32 {
    |numerator: u32| numerator / denominator
}

And suppose I'm using it like this:

fn divide_all(numerators: &mut [u32], denominator: u32) {
    let divider = make_divider(denominator);
    for numerator in numerators {
        *numerator = divider(*numerator);
    }
}

This divide_all function would be unnecessarily slow if numerators is a really big array and denominator is something like 1 or 2 where a div instruction could be avoided. So it'd be nice if I could instead implement divide_all as:

fn divide_all(numerators: &mut [u32], denominator: u32) {
    let divider = make_divider(denominator);
    // Make it go fast! vroom vroom!
    let divider = divider.jit_recompile();
    for numerator in numerators {
        *numerator = divider(*numerator);
    }
}

The jit_recompile method would look at the value of denominator and use the same logic that the codegen backend would use when dividing by a constant in order to replace the division with a nop or bitshift where possible. Note that, in principle, this wouldn't require linking LLVM into the user's binary since this jit_recomple method would just need to know how to apply this one specific optimization.

This is a toy example but this feature would really be useful when dealing with domain-specific languages. eg. if you've written a regex crate then you could add the ability to JIT-compile regexes with a single line of code.

To actually implement this we'd need a codegen backend which has reflection capabilities built-in. ie. rather than just "Here's a CFG, please generate optimized machine code for it", you'd need to be able to ask "Here's a two-stage CFG, please generate optimized machine code which generates optimized machine code for the second stage by treating the first-stage variables as constants", and I can't imagine LLVM adding that feature before the singularity next year.

(There's also a bunch of issues with allocating executable memory being awkward to support - or impossible for things like wasm - but this is all a fantasy anyway).

10

Yeah, it's a really cool idea! It's just that we need more cutting-edge research before it'll be viable, and it'll probably going to go in a new programming language, not Rust.

1 Like
11

How would this work in no-std? Rust doesn't require a runtime, your idea would.

Also, far from all targets let you even allocate executable code at runtime. Consider something like the AVR microcontroller family, that uses a Harvard architecture. You need to re-flash to change the code on at least some of those.

1 Like
12

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