`const fn` and generics

[RalfJung]

Now that I came to like const soundness, of course I had to start thinking about how to achieve const soundness in the presence of generics. The problem is that in a const fn foo<T: Trait>, when we call T::method, how can we know if that method is safe to call in const context? When type-checking the method body, we cannot know if that will later resolve to a const fn or not.

There was plenty of discussion on this that I did not follow closely, but it seems it mostly happened in chat so I don't know of a good summary. @Centril was involved, probably @eddyb and @oli-obk and I am not sure who else?

I propose to discuss this further here so that we have a place to look at. I see two fundamental approaches:

• Find some way to solve this and obtain a const sound generic type system, i.e., obtain a static guarantee that (safe) const code will not even attempt to call a non-const fn. (By "static" I mean that we detect this before even starting CTFE, just on the type system level. In our context here, "dynamic" means "during CTFE evaluation", i.e. when miri runs).
• Punt on this. We will detect this a CTFE evaluation time. Our type system would only be const sound for non-generic code. Not very satisfying, but it's worth keeping in mind that this is not a horrible alternative, which puts an upper bound on the amount of complexity we should pile up to avoid this outcome. :D

(I understand there are other open questions around const fn, like avoiding having to manually mark every single function as const. Things like const mod have been proposed. Feel free to open a separate issue for those concerns, but I consider such discussion to be off-topic in this issue.)

[RalfJung]

Here is the simplest possible thing I could come up with, and I hope @Centril et al will tell me why that is not sufficient. ;)

I propose that we have const impl Trait for Foo where all methods are checked in const context; and that, whenever we perform trait resolution in const context, we only consider const impl. We also freely allow using trait bounds that were introduced by where clauses, relying on the fact that whoever is satisfying those where clauses will take care to only use const impl. And I think that's already it.

So, for example, in

const fn ptr_eq<T>(x: &T, y: &T) -> bool {
    unsafe { x as *const _ == y as *const _ }
}

we check that we have a const impl PartialEq for *const T.

In

const fn foo<T: PartialOrd>(x: &T, y: &T) -> bool {
    x < y || y < x
}

we don't actually check anything locally, because the where clause is sufficient. We rely on the fact that when foo is called in const context, the caller will only use const impl to satisfy our where clause. That way, we should have an invariant that when a trait method is executed in const context, it always comes from a const impl.

---

I just realized one complication with this is default implementations and specialization. I suppose that we could let you write const fn when providing a default method, and when a const impl relies on a default method (by not overwriting that method), then the default method must be marked const. As for specialization; a const impl can only be specialized by a const impl.

What I am trying to avoid here is requiring annotations like where T: const PartialOrd, which directly lead us to const polymorphism and a whole bag of complexity that does not seem proportional to the problem we are solving. Essentially, we have implicit const polymorphism: const fn foo<T: Trait> is useable at run-time with all T: Trait, but in const context it requires T: const Trait. Similar, const impl<T> Trait for Foo<T> where T: Something is implicitly const polymorphic so that the resulting impl is const safe if we have T: const Something. This is not as powerful, but vastly simpler and requires hardly any new syntax.

Has such an idea already been discussed? Is there any reason why this does not work?

[Centril]

cc @alercah, @rpjohnst

Dumping stuff:

• Start here... RFC: const bounds and methods rfcs#2237
• https://github.com/Centril/rfcs/blob/rfc/const-everywhere/text/0000-const-everywhere.md
• https://github.com/Centril/rfc-effects

[Centril]

First, I infer from your setup that we have the following typing rule:

Δ ⊢ TheTrait trait
Δ ⊢ TheType type
Δ ⊢ Implemented(TheType, const TheTrait)
----------------------------------------
Δ ⊢ Implemented(TheType, TheTrait)

is that accurate? If not, the system is pretty unusable.

Our primary goal with const impl or impl const or whatever should be code reuse.
As such, I think it is important that you can let something be const if the dependents are const.
I also think that whatever we come up with should scale to other forms of restrictions such as statically preventing panics, etc.

The idea of implicitly bounding traits as const is not bad, and can hopefully be retrofitted onto various designs. But I think inventing ergonomic syntax is starting at the wrong end of things. At the moment, I'm less interested about surface syntax and more about core semantics, inference, coherence and the consequences for reuse. For example, consider the following trait in the standard library which we would like to retrofit for const contexts (also Iterator, ..):

pub trait Hash {
    fn hash<H>(&self, state: &mut H)
    where H: Hasher; // As defined today...
}

If we accept the typing rule above, then a const impl must be:

const impl Hash for Foo {
    fn hash<H>(&self, state: &mut H)
    where H: Hasher // this is **NOT** `H: const Hasher`
    {
        // can't use any methods of `H`!
    }
}

We can't write:

const impl Hash for Foo {
    const fn hash<H>(&self, state: &mut H)
    where H: const Hasher
    {
        ...
    }
}

If we did, then either the typing rule above can't hold, or it does hold and if we allow the impl, the system is unsound. It is unsound because we can write something like this:

trait Bar {
    fn bar() -> usize;
}

trait Foo {
    fn foo<T: Bar>() -> usize;
}

struct Wibble;
struct Wobble;

impl Bar for Wibble {
    fn bar() -> usize {
        read_usize_from_file()
    }
}

const impl Foo for Wobble {
    const fn foo<T: const Bar>() -> usize {
        T::bar()
    }
}

const ITEM: usize = Foo::foo::<Bar>();

So the contravariant position of type parameters is causing problems for us if we wish to support existing code.

Instead, if we encode things as (this is not the surface syntax, but rather a language we can desugar to...):

trait Hash<effect E = io> {
    E fn hash<H: E Hasher>(&self, state: &mut H);
}

then the definition is backwards compatible. Here, E is a parametric effect variable.
If we want a const version of Hash, we can then write T: Hash<const>.
We can then try to make the surface syntax more ergonomic by adding elision, various shorthands, etc.

...to be continued...

[RalfJung]

• Start here... RFC: const bounds and methods rfcs#2237
• https://github.com/Centril/rfcs/blob/rfc/const-everywhere/text/0000-const-everywhere.md
• https://github.com/Centril/rfc-effects

Ah, that's where all that stuff is. :)
TBH I feel this is beyond the level of complexity that is worth throwing at this problem... so really hope we can have something simpler that's getting us most of the way.

First, I infer from your setup that we have the following typing rule:

I can only guess what exactly that means, but every const impl also acts as a normal impl if that's what you mean?

The idea of implicitly bounding traits as const is not bad, and can hopefully be retrofitted onto various designs. But I think inventing ergonomic syntax is starting at the wrong end of things. At the moment, I'm less interested about surface syntax and more about core semantics, inference, coherence and the consequences for reuse.

I think restricting the type system to just what I described makes this discussion just so much simpler.

const impl Hash for Foo {
    fn hash<H>(&self, state: &mut H)
    where H: Hasher // this is **NOT** `H: const Hasher`
    {
        // can't use any methods of `H`!
    }
}

Under my proposal, this can use the methods of H because they come from a where clause.

I can try to express this using fancy syntax as well: Let's say we have "const mode variables \c" that we can quantify over, that can be either const or, eh, let's say runtime for the normal type system concerned with run-time safety. Then the above impl Hash would translate to something like

for<\c> \c impl Hash for Foo {
    fn hash<H>(&self, state: &mut H)
    where H: \c Hasher
    {
        // *can* use all methods of `H`!
    }
}

So, when you need a const impl you get one where the bound is const Hasher, but when you need a normal impl you just get a normal bound.

EDIT: Looking at some of your work, it seems you would write that using ?const instead of \c. However, one important point is that it must be the same constness in both places, which ?const cannot express.

[RalfJung]

One thing I should may more explicit: I claim that every program accepted by the const type system would also be accepted by the "normal" type system. This is interesting because const-safety of a function does not imply safety (because const-safety only talks about what happens when you use the function with const-valid inputs).
So, we only have to typecheck the const impl Hash with the const type system (effectively typechecking the variant where \c is const) and will automatically know that the normal type system would also accept it (the variant where \c is runtime).

IOW, I am not taking an effect system point-of-view here. Instead I think of there being two separate type systems, but they have this useful relationship. I think that means we can avoid all the usual complexity that effect systems bring.

[RalfJung]

Reading over https://github.com/Centril/rfcs/blob/rfc/const-everywhere/text/0000-const-everywhere.md, I realized I did not talk about what to do with fn pointers. I think we can carry over the same idea:

const fn iter<T>(x: usize, f: fn(T) -> T) -> T

iter can be called with any const fn in const context, but called with any fn at run-time. Just like we only allow const impl in const context (and probably need an invariant that all trait objects have a vtable which is a const impl), we also only allow using const fn pointers.

IOW, it is sugar for

for<\c> \c fn iter<T>(x: usize, f: \c fn(T) -> T) -> T

which I think you would write

?const fn iter<T>(x: usize, f: ?const fn(T) -> T) -> T

but I think this lacks the crucial information that the two ?const are tied together.

The trouble with this is that we already allow creating fn pointers on stable... :/

[Centril]

TBH I feel this is beyond the level of complexity that is worth throwing at this problem... so really hope we can have something simpler that's getting us most of the way.

I want to reuse the same mechanism for other forms of restrictions such as "this can't panic" and "this will always terminate" as well as adding more abilities such as "this can use RandomIntelExtension" or "this can use async", so I'd like a system that is composable, flexible, expressive, and ergonomic to use.

I can only guess what exactly that means, but every const impl also acts as a normal impl if that's what you mean?

The rule says that if T: const Trait holds, then T: Trait also holds, so it is a subtyping rule.

I think restricting the type system to just what I described makes this discussion just so much simpler.

Sure, but then you lose out on a bunch of interesting things you might want to encode :)
For example, it is not possible in your system to encode the following:

fn foo<F: const Fn() -> usize>(fun: F) {
    write_to_file("bar", fun()); // `fun` may not cause side-effects.
}

for<\c> \c impl Hash for Foo {
    fn hash<H>(&self, state: &mut H)
    where H: \c Hasher
    {
        // *can* use all methods of `H`!
    }
}

So, when you need a const impl you get one where the bound is const Hasher, but when you need a normal impl you just get a normal bound.

Yeah, this is much clearer wrt. what you mean, which is totally different from what I inferred (subtyping) at first :)
Being even more clear about what this means, I'd write:

for<effect C> C impl Hash for Foo {
    fn hash<H>(&self, state: &mut H) where H: C Hasher {
        ...
    }
}

where the possible effect is io (what we have today) as well as the absence of it. However, it seems to me that \c or C is possibly unconstrained because it is not mentioned by either Hash or Foo.

Also note that if you have some existing trait (as defined today) with provided methods where their definitions have side effects, then you'd need to require the const impl to redefine those methods.

EDIT: Looking at some of your work, it seems you would write that using ?const instead of \c. However, one important point is that it must be the same constness in both places, which ?const cannot express.

Well, you could use ?const for "possibly const" the way you've used const in your syntax and const for "must be const". Speaking of which, with the setup of having const mean "possibly const", then there's no way to use type parameter T with T: Foo where Foo has some function bar as T::bar() in a const generics context because we can't know before T is instantiated whether it is safe to use it in such a context.

IOW, I am not taking an effect system point-of-view here. Instead I think of there being two separate type systems, but they have this useful relationship. I think that means we can avoid all the usual complexity that effect systems bring.

Right; but it amounts to an effect-polymorphic system, albeit a limited and implicit one.
I also don't think it scales well to take that POV when you want to add more effects / restrictions.
In particular, I'd like to encode:

pub fn replace_with<T, F>(val: &mut T, closure: F)
where
    F: no_panic FnOnce(T) -> T
{
    unsafe {
        let old = ptr::read(val);
        let new = closure(old);
        ptr::write(val, new);
    }
}

Since we've guaranteed that closure(old) can't panic, it's safe. But if we let no_panic be "maybe don't panic", it doesn't work.

Just like we only allow const impl in const context (and probably need an invariant that all trait objects have a vtable which is a const impl), we also only allow using const fn pointers.

Yes; this is one of the major problems with the "exposed body" approach.
In my first system, I had contemplated Box<dyn const Foo> and impl const Foo as saying explicitly that existentials. If you don't have such an annotation, then Box<dyn Foo> or impl Foo need to be different types in an fn context and in a const fn context. I'm concerned that this could be hard to understand for users.

So what am I currently contemplating instead?

We can use lightweight quantification:

pub trait Hash<#E = io> { // #E  denotes an effect variable... We could possibly elide `io` here
    fn hash<H>(&self, state: &mut H)
    where H: #E Hasher; // As defined today...
}

(We can totally bikeshed the sigil #, multicore OCaml uses ! instead)

We can use implicit quantification on functions:

pub trait Iterator<#A> { // = io elided
    type Item;

    #A fn next(&mut self) -> Option<Self::Item>;

    ...

    #A fn chain<U>(self, other: U) -> Chain<Self, <U as IntoIterator<#B>>::IntoIter>
    where U: IntoIterator<#B, Item = Self::Item>,
    { ... }

    #A fn zip<U>(self, other: U) -> Zip<Self, <U as IntoIterator<#B>>::IntoIter>
    where U: IntoIterator<#B>,
    { ... }

    #A fn map<B, F: FnMut<#C>(Self::Item) -> B>(self, f: F) -> Map<Self, F> { ... }

    #A #B fn for_each<F: FnMut<#B>(Self::Item)>(self, f: F) { ... }

    #A fn filter<P>(self, predicate: P) -> Filter<Self, P>
    where P: FnMut<#B>(&Self::Item) -> bool,
    { ... }

    #A fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F>
    where F: FnMut<#B>(Self::Item) -> Option<B>,
    { ... }

    ...

    #A fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
    where
        F: FnMut<#B>(Self::Item) -> U,
        U: IntoIterator<#C>,
    { ... }

    #A fn flatten(self) -> Flatten<Self> where Self::Item: IntoIterator<#B> { ... }
    // Same as:
    #A fn flatten<#B>(self) -> Flatten<Self> where Self::Item: IntoIterator<#B> { ... }

    ...

    #A #C #D fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
    where
        F: FnMut<#C>(B, Self::Item) -> R,
        R: Try<#D, Ok = B>,
    { ... }

    ...
}

I don't think this is too bad. It is backwards compatible and also scales to more effects and restrictions.
The trait is also fully in on it, so all provided definitions in the trait are also as a consequence.

We can regain the syntax T: const Trait by saying that #E Trait means "find all quantified effect variables in the trait and require that they are #E".

If writing #A becomes repetitive, we can have some sort of syntax for "apply the variable to all functions" or something.

Of course, all of this is more complex, but also more flexible and expressive.
I also think it is understandable, because we already have 2 different things we can quantify over today:

• lifetimes
• types

with one more on the way:

• const values

so people will already be used to quantify over a bunch of stuff.

@alercah had more ideas so I'll let them fill in...

[alercah]

I had also thought about some level of inference: e.g. by default, traits are considered to be fully effect-polymorphic (by adding an implicit effect parameter and applying it to all functions). This would only be done where it was safe (e.g. no higher-order functions involved? or perhaps only in limited cases of higher-order functions), but would help make effect-polymorphism usable on existing traits without having to add it explicitly, creating a giant migration headache.

[rpjohnst]

It seems to me that @RalfJung's syntax is both forward-compatible with an effect system, and eminently reasonable as an actual syntax. Even if we ever get an effect system, I strongly suspect we would want such a shorthand anyway.

It also seems to me that the sorts of things @Centril wants to add are... well beyond the complexity budget. Fun to think about, perhaps useful as a tool to make const sound and usable, but not a real argument against considering @RalfJung's model, especially if it really is forward-compatible.

[RalfJung]

Sure, but then you lose out on a bunch of interesting things you might want to encode :)
For example, it is not possible in your system to encode the following:

fn foo<F: const Fn() -> usize>(fun: F) {
    write_to_file("bar", fun()); // `fun` may not cause side-effects.
}

Notice that const, a priori, has nothing to do with side-effects. const is about const-safety. I think const-safety is a term where we can all agree on what it means, whereas side-effects are much harder to define.

Yes, my system is deliberately restricted. I don't see Rust getting a full effect system any time soon, and I wouldn't want to wait with const fn until we found a design that's both expressive and ergonomic (probably that would be the first such effect system ever?). As you know, Rust used to have an effect system and it got removed (from what I read), amongst other reasons, because the complexity budget of the language is already "used by" by lifetimes and borrowing.

I agree, though, that terminology from a power powerful system can be useful in this discussion.

the possible effect is io (what we have today) as well as the absence of it.

Again, I'd like to separate const from "not io". Saying that io is the effect we have currently is rather arbitrary, i.e. we also have non-termination and panics -- and it may be useful to split io into different effects. (Memory and file system are a priory unrelated effects, for example. Just Haskell decided to lump it all together...)

Also note that if you have some existing trait (as defined today) with provided methods where their definitions have side effects, then you'd need to require the const impl to redefine those methods.

I do not understand what you are saying here.

Well, you could use ?const for "possibly const" the way you've used const in your syntax and const for "must be const". Speaking of which, with the setup of having const mean "possibly const", then there's no way to use type parameter T with T: Foo where Foo has some function bar as T::bar() in a const generics context because we can't know before T is instantiated whether it is safe to use it in such a context.

The key difference between your ?const and my const is that I am expressing "this function is const if you are using const impl to satisfy trait bounds".

[RalfJung]

I talked with @nikomatsakis about this and realized that what I proposed for trait objects doesn't work, for the not-very-surprising reason that they are a lot like function pointers. The following works in stable today:

const X : &'static std::fmt::Debug = &();

So, I came up with a different variant for run-time function pointers (i.e., fn and dyn). For example:

const fn twice<T>(arg: T, fun: const fn(T) -> T) -> T {
    fun(fun(arg)) // OK. We know that `fun` respects the rules of `const`.
}

This function signature means that when twice is called in const context, the argument must be a const fn. When twice is called outside of const context, you can use any function. Essentially, the type const fn is only different from fn when are are in const-context, and is otherwise considered the same type.

With some kind of quantification, that would translate to

for<\c> \c fn twice<T>(arg: T, fun: \c fn(T) -> T) -> T {
    fun(fun(arg)) // OK. We know that `fun` respects the rules of `const`.
}

So, essentially, all const are really "const-mode variables" that are scoped on the function level, except that this also works when the \c appears inside a struct:

struct Foo<T> {
  x: usize,
  f: const fn(T) -> T,
}

const fn twice<T>(arg: T, fun: Foo<T>) -> T {
    fun.f(fun.f(arg)) // OK. We know that `fun` respects the rules of `const`.
}

Again, Foo in const context promises to contain a const fn, but in "run-time" context it can contain any fn.

We would need something similar for dyn, i.e., we would need dyn const to be a thing.

I don't like how this is getting more complicated, but I can't think of anything that is simpler and backwards-compatible.

---

One possible concern with this proposal is the asymmetry between trait bounds (where a "const-context only const" is added automatically) and trait objects/fn pointers. However, we already often require more annotation on trait objects (think: marker traits, lifetimes), and I cannot think of a case where one would not want the trait bound to be const. Whereas for function pointers one can think e.g. of a function that initializes a data structure, and just puts a function pointer into it without ever calling that function -- that's perfectly safe to do in const context even when the function is not const-safe.

[Ixrec]

Essentially, the type const fn is only different from fn when are are in const-context, and is otherwise considered the same type.

What meaningful work could a const fn do with a non-const function argument? I'm not sure we need the extra const and its typing implications for function arguments.

[RalfJung]

@Ixrec I have an example in my post

for function pointers one can think e.g. of a function that initializes a data structure, and just puts a function pointer into it without ever calling that function -- that's perfectly safe to do in const context even when the function is not const-safe.

Also, we have no other choice if we want to remain backwards compaible. Safe const code can already create references to fn.

[alexreg]

Let's not less this stagnate yet. :-)

[RalfJung]

Summarizing today's discussion of @oli-obk, @Centril and me on Discord:

We all agreed that whatever proposal we come up with should be able to desugar into a full-blown effect system. That helps for discussion, for future addition of such a system (if that ever happens), and to check the design. The first implementation will likely not use that desugaring though but implement the rules directly, as that is much simpler.

@Centril's main point of contention with my proposal are (1) handling of provided methods in traits (i.e. those where the trait definition provides a default implementation), and (2) uniformity issues around explicit const dyn/const fn types, but implicit const Trait bounds. (And something about parametricity that I did not understand.^^)

As for (2), we can easily decide to make people write const Trait bounds in const fn. I do not think that that is worth it, but it'd be an okay outcome -- so I propose we experiment with that during stabilization.

For (1), we realized that my proposal had a problem: I imagined that when you write const impl, if the provided method was not a const fn, you habe to implement it yourself. That would work, however, it makes adding a non-const provided method to a trait a breaking change! If we do not want that, we can alternative say that traits must be marked as const trait if they want to permit a const impl. Then all provided methods would implicitly be const fn. Personally I am not decided yet which of these two is preferrable; @oli-obk and @Centril are tending towards const trait.

I think that's it? Please amend if I missed anything.