Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

const fn and generics #1

Open
RalfJung opened this issue Jul 21, 2018 · 34 comments
Open

const fn and generics #1

RalfJung opened this issue Jul 21, 2018 · 34 comments

Comments

@RalfJung
Copy link
Member

RalfJung commented Jul 21, 2018

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
Copy link
Member Author

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
Copy link

Centril commented Jul 21, 2018

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
Copy link
Member Author

RalfJung commented Jul 21, 2018

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
Copy link
Member Author

RalfJung commented Jul 21, 2018

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
Copy link
Member Author

RalfJung commented Jul 21, 2018

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
Copy link

Centril commented Jul 21, 2018

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
Copy link

alercah commented Jul 21, 2018

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
Copy link

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
Copy link
Member Author

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
Copy link
Member Author

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
Copy link

Ixrec commented Jul 27, 2018

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
Copy link
Member Author

RalfJung commented Jul 27, 2018

@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
Copy link

alexreg commented Aug 15, 2018

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

@RalfJung
Copy link
Member Author

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.

@alexreg
Copy link

alexreg commented Aug 22, 2018

@RalfJung I'm undecided on the last point too, but I think it's quite permissible to leave that as an unresolved question for now. Do you feel we're at a point an RFC can be written for all this now?

@RalfJung
Copy link
Member Author

Maybe?

I plan to submit something on const safety and promotion to this repo within this month. I'd be happy for someone else to write up the generics stuff :D

@alexreg
Copy link

alexreg commented Aug 22, 2018

@RalfJung I think promotion is already sorted... I did that in a PR a few months back.

@RalfJung
Copy link
Member Author

I am not talking about implementation, but about https://github.com/rust-rfcs/const-eval/blob/master/promotion.md

@alexreg
Copy link

alexreg commented Aug 22, 2018

@RalfJung I thought point 2 was already disallowed, but it seems someone added a const_raw_ptr_to_usize_cast feature (why??).

@RalfJung
Copy link
Member Author

Why should unsafe const code not be able to do that?

It is needed, for example, to eventually make HashMap const-compatible.

@alexreg
Copy link

alexreg commented Aug 22, 2018

Because it causes non-determinism (and thus non-referential transparency)... I don't see why HashMap needs it.

@RalfJung
Copy link
Member Author

RalfJung commented Aug 23, 2018

Because it causes non-determinism

No, that is not the case.

Casting a pointer to a usize in miri does not actually create an integer. It keeps a pointer value at integer type. See this blog post and the definition of Scalar in the miri engine.

I don't see why HashMap needs it.

It stores a pointer and a boolean together in a single usize, exploiting the fact that the pointer is aligned and hence some bits at the end are always 0.

Also, maybe let's stop this off-topic discussion here? This issue is about generic,s not about pointers or usize. If you still have questions, feel free to open a new issue :)

@oli-obk
Copy link
Contributor

oli-obk commented Sep 6, 2018

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`.
}

Does this mean

fn foo<T>(t: T) -> T { t }
let x = Foo { x: 42, f: foo };

is not legal because foo is not const fn? Even in runtime code where the constness is irrelevant?

@glaebhoerl
Copy link

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

(Hmm. I thought an analogous case would be that you can create const MY_CONST: &T = &MY_STATIC, but it seems you cannot do that: "constants cannot refer to statics", as rustc says. I had been prepared to go on to observe that trait objects likewise (inherently) involve references, and to muse that the whole thing is vaguely reminiscent of validity invariants, where a reference to uninitialized (cf. non-const) data can be valid but not safe; and that perhaps we could have separate notions of bindings being const versus their types/contents being so, with the former implying the latter only shallowly (propagating through e.g. structs, but not through pointer-likes such as references and fns). But it appears that my premise was invalid...)

@RalfJung
Copy link
Member Author

Does this mean

fn foo<T>(t: T) -> T { t }
let x = Foo { x: 42, f: foo };

is not legal because foo is not const fn? Even in runtime code where the constness is irrelevant?

No; const fn and fn are the same type when typechecking runtime code.

I think of Rust as having two typesystems at this point, one used for typechecking code in const context and one for the rest. They are related by the fact that const-well-typed code is also runtime-well-typed. The const type system is the only one making any distinctions based on const fn vs. fn.

In rust-lang/rust#53972, you suggested almost the same scheme, except you planned to also allow const as qualifier in front of any type. I am a bit worried about what exactly that is even supposed to mean... in any case, I disagree with

struct Bar(const fn());
const fn bar(f: Bar) {
    (f.0)() // not allowed
}

This should be allowed, we said const fn explicitly after all!

@RalfJung
Copy link
Member Author

@glaebhoerl I do see a formulation in terms of validity/safety though -- in const context, a fn() is safe when it points to any function, but a const fn() is safe only when it points to a const-callable function. const fn() could still be valid when pointing to a non-const fn, but then calling it causes "UB" (it causes a CTFE engine error, to be more precise).

@oli-obk
Copy link
Contributor

oli-obk commented Sep 18, 2018

This should be allowed, we said const fn explicitly after all!

So when using Bar in a const fn, the field always needs to be const fn, even if we don't care about that because we'd just use the value "by move"

const fn foo(b: Bar) -> (Bar, i32) { (b, 42) }

Would be impossible to write for allowing non const fns for b's field, even though

fn bar(b: Bar) -> (Bar, i32) { (b, 42) }

Is ok without b's field being const fn ?

@RalfJung
Copy link
Member Author

RalfJung commented Sep 18, 2018

So when using Bar in a const fn, the field always needs to be const fn

Yes, you asked for const fn specifically. Bar is a newtype around const fn, the two should behave the same.

I could imagine it to be useful that one can write

struct Foo(fn());
fn foo(f: const Foo) {
  (f.0)(); // allowed because of `const Foo`
}

I.e., one could "add constness" -- though I'd really like to see a concrete usecase before considering this seriously. But once it is const, I'd find it very strange to have to repeat that on every level.

@oli-obk
Copy link
Contributor

oli-obk commented Sep 18, 2018

That kind of constness adding would then add constness to all function pointers inside the struct, even if that is not necessary due to only one of them being called inside the function

@RalfJung
Copy link
Member Author

Yeah, I'm not a fan either. But at least it keeps newtypes working, which I think is something we should absolutely not break.

What you are asking for is essentially types which are generic wrt. const-ness. I'd rather avoid such an effect system until we have a clearly demonstrated need.

@oli-obk
Copy link
Contributor

oli-obk commented Sep 18, 2018

Sgtm. I am for the simple version, since it covers the real use cases I can think of. artificial examples are easy to come up with but rarely useful in practice. I have just one more thing: I presume we can now transmute function pointers to const function pointers (unsafely) and call them and then either weird things happen (like half of full miri things working without feature gates and super useless errors for very nonconst things) or we error out with "tried to call non const fn". I personally am for the former, for the lulz, but I'm happy with either scheme. Unsafe is unsafe after all, and we kind of give the user a way around the guarantees of the language.

@RalfJung
Copy link
Member Author

What currently happens is the latter, I think -- I hope (should add a test once calling fn pointers is possible). And indeed I think we should error out immediately when calling a non-const fn, to avoid accidentally stabilizing whatever the heck happens then.^^

@oli-obk
Copy link
Contributor

oli-obk commented Sep 18, 2018

Yes that's the current behaviour. OK, let's keep it. it's way saner, even if less fun

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

8 participants