Const fn using iterators - a possible track to more powerful const functions

language design
#1

It seems like this could be a way to make const functions much more powerful. I've seen elsewhere that arbitrary loops aren't allowed in const functions, but I believe in principle the iterator HOFs should be much less likely to do bad things (e.g. map, fold, etc).

An example of what would be ideal to have as const, and in my view, there should be a way to make this const (if I am wrong, please correct me).

pub const fn double_them(xs: &Vec<i32>) -> Vec<i32> {
    xs.into_iter().map(|x| 2*x).collect()
}

Currently on a recent nightly this gives:

    error[E0015]: calls in constant functions are limited to constant functions, tuple structs and tuple variants
      --> src/sfwtools.rs:65:5
       |
    65 |     xs.into_iter().map(|x| 2*x).collect()
       |     ^^^^^^^^^^^^^^

    error[E0015]: calls in constant functions are limited to constant functions, tuple structs and tuple variants
      --> src/sfwtools.rs:65:5
       |
    65 |     xs.into_iter().map(|x| 2*x).collect()
       |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^

    error[E0015]: calls in constant functions are limited to constant functions, tuple structs and tuple variants
      --> src/sfwtools.rs:65:5
       |
    65 |     xs.into_iter().map(|x| 2*x).collect()
       |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

    error: aborting due to 3 previous errors; 2 warnings emitted

There may already be tracking issues for some of these, in which case - I'm sorry if I missed them.

2 Likes
#2

Related: https://github.com/rust-lang/rfcs/blob/master/text/2344-const-looping.md

#3

This may be predicated on whether or not it will be possible for Rust to tell if a particular Iterator is proven to be finite or not. I'm not sure if there's a way to do that currently.

#4

It looks like another major issue, perhaps the primary issue, is outlined in this RFC as a possible extension to the original const_fn RFC: https://github.com/rust-lang/rfcs/blob/master/text/0911-const-fn.md#alternatives

#5

Note though that loops are being implemented in const fns - while loops are already allowed.

5 Likes
#6

Those can all be legally overridden to do arbitrarily-silly things, so long as they're safe (and meet the type signatures). There's certainly never a good reason to override map (since it just constructs an adapter), but it's still possible. So the problem of calling arbitrary code in traits still remains.

(Which is the real problem here -- as bluss mentioned, loops are already allowed.)

#7

I don't think that's an issue. If the iterator is infinite then compilation can fail after a timeout, and I think that's ok.

The issue of overriding map and fold to do weird things can be addressed by "blessing" the built-in implementations in a way that custom impls cannot do. Then the "only" remaining thing is to require that all mapping and folding functions are const too. Whether or not that is practical to do is another matter!

1 Like
#8

Even if they do weird things, as long as those things are also const, is it an issue? I'm guessing the answer is yes, but I don't know what it is.

#9

It's the iterator impl itself that's the problem. Iterator::next() cannot be const because it takes &mut self. Some "weird" override of map could return an iterator, WeirdMap<I, F>, that breaks assumptions that the compiler needs to make about map.

1 Like
#10

Actually, Iterator::next could be const if the idea of const was extended to include mut methods that are guaranteed to mutate self deterministically.

ie. re-interpret a mut method:

const fn foo(&mut self, Args) -> Bar {}

as:

const fn foo(Self, Args) -> (Self, Bar)

and prove that it is a pure function.

#11

That's an interesting idea, though as it still breaks referential transparency, it isn't really pure, I think.

Perhaps an alternative is to keep the standard iterators as they are, define non-mutative operations on non-stateful collections (such as Vecs and arrays). I'm afraid, being fairly new to Rust, I don't know enough to know how to do this generically yet, and I probably won't try looking into it right away as I still have a lot on my list to read to that end.

#12

I know that the initial RFC for const functions was specifically about free functions (and methods it seems) but I don't see why an RFC couldn't be created for trait const functions.

(I even have some ideas, maybe I should start a new thread)

1 Like
#13

You'll want to see RFC 2632, and probably other things linked off of that tracking issue.

2 Likes
#14

Yes, I really think the lack of trait const fns hurts: for instance, it isn't even possible to perform a clone() in a const fn currently (though it is possible to dereference in some cases).

#15

Risking being naive.. Suppose

  • const fn-s were allowed to take &mut arguments
  • const fn-s were allowed to assign fields through &mut references
  • const fn-s were allowed to take &mut references to local variables

Wouldn't this bring Rust closer to being able to use iterators in const fn-s?

"Top level" `const` expressions would still be unable to produce `&mut`. Therefore the only `&mut`-s around would be to data on stack. So these `&mut` seem no more dangerous than `mut` local bindings which are already allowed.

Of course this conflicts with heap allocations ever becoming allowed in const contexts. But heap allocations are already a problem. Some mechanism would be needed to prevent them from escaping const fn-s. And the same mechanism could then potentially solve the conflict with &mut.

#16

I'm still a bit unnerved by the idea of const fn allowing &mut arguments, but it is a good point. Perhaps a different demarcation is worthwhile here, though I'm not sure of a good term. Let's call it mutconst for the three allowances you listed. Then, although mutconst function itself is not const, a function could still be const if it calls a mutconst function, which I believe opens up a range of possibilities. For instance, if the Iterator functions were mutconst, then although they couldn't directly be used in a const context (since the might be mutating things outside function scope), they could still be used when they consume/drop the mutated variable, such as in the original function example I listed:

pub const fn double_them(xs: &Vec<i32>) -> Vec<i32> {
    xs.into_iter().map(|x| 2*x).collect()
}

In this case, double_them could still be const, even though e.g. map and collect may only be mutconst.

#17

You should really look into what the const-eval working group is looking into, because I'm pretty sure they are in the process of solving these issues already.

1 Like
#18

Actually.. is it at all possible to call this meaningfully from a const expression?
Wouldn't creating a non-empty Vec require heap allocation which is presently not supported in const?