😍

This RFC does not go into nearly enough detail as to how CTFE is supposed to work to be actionable. What are the limitations? What subset of the language does it allow? How is it implemented? How do we extend it? What about allocation and I/O?

@pcwalton I thought much of your questions (e.g. about its limitations and what subset of the language it allows) were covered by this text:

The body of the function is checked as if it were a block inside a const:

const FOO: Foo = {
   // Currently, only item "statements" are allowed here.
   stmts;
   // The function's arguments and constant expressions can be freely combined.
   expr
}

E.g. do we allow allocation and IO in const expressions today?

I mean, yes, we haven't formally defined what the subset of the language is that const expressions allows (to my knowledge), but it seems reasonable for this RFC to be written in this delegating manner.

Update: I admit, the (sketch of a) definition quoted above leaves completely unspecified how const function calls themselves work; e.g. whether one is statically restricted to an acyclic call graph, or if recursion is allowed.

(whether we can afford to adopt this feature is an entirely separate question, of course.)

@eddyb I assume you allow recursion in your function calls (rather than restricting the call graph to be acyclic), though I have not verified that assumption via the implementation. Did you add a recursion limit for the function calls in the const evaluator?

I recommend the RFC allow the use of a recursion limit (or, if you prefer, allow the DAG restriction, though I suspect that is less palatable from both the implementation side and from the user's perspective).

(I hope @eddyb comments more on this detail later himself, here or in the RFC text, but over IRC, he just pointed out to me that attempting to write a useful recursive function in the scheme as proposed would probably be impossible, because we do not support if <expr> { <block> } else { <block> } in constant expressions today! that's big: that essentially forces ones const fn call graph to be acyclic, even if that isn't statically verified in the current implementation.)

Despite having myself submitted an RFC that punts on this question, I would like to see a description of what is/isn't allowed in a const function, even if it just documents what's allowed today.

For one, it should be specified whether or not const functions will follow the rules about references from RFC 246.

Other things that I could probably guess or easily test about the current implementation, but are not set down in any obvious location:

• Whether types implementing Drop are allowed.
• Whether types that don't implement Copy are allowed.
• Whether types that are not 'static are allowed.
• What about closures?
• Trait objects?
• What about pointer arithmetic in unsafe blocks?

A fairly important question, though one that can be deferred to a later RFC, is which library functions should be made const.

Then there are traits:

• Which existing implementations of ops traits are allowed? Primitives only (e.g. 4i32 5 but not Point1 Point2)?
• Can traits with no associated items (e.g. Copy or Sync) be used as bounds for generic const functions?
• What about traits with only associated types (and are there restrictions on those types)?
• Only associated consts (not yet implemented)? In particular, I'm concerned that even after associated consts are implemented, you won't be able to make use of constants like <T as Float>::pi in constant functions, until after some trait story is worked out.
• Less a question than a comment: the proposed alternative is very different from how I would picture interaction with traits, in that I would think of const-ness as being a property of a method, or a specific impl of a method, but not of an entire trait impl or bound.

I agree with @pcwalton that the details are too vague.

In general I feel like all the proposals in this vein are motivated by the desire to get "something" into the language as fast as possible without considering future design implications of coming up with an ad-hoc sub-language and baking it in before 1.0. Personally I think we should show restraint on picking a design for this too early. There are more interesting and powerful directions we could push the language in if we wait for some of the post-1.0 design to shape up.

As a language that borrows from many different sources I believe we should also consider more than a single design before adoption (and this feels way too much like C ), and there are many other ways to do this. We could for example move towards singleton types, a very interesting idea that is implemented as a library in Haskell, and has both a library implementation and a prototype in the compiler in Scala. This combined with a couple other features is much more powerful than the proposed extensions and doesn't require inventing a new sub-language with restricted semantics.

As a final point, regardless of what happens, the definition of the allowed sub-language is incredibly important. Unless you only allow a restricted subset like @pnkfelix describes above, we most likely need to require the sub-language to total and pure. If not the termination of type checking will cease to be a guarantee and personally I find this feature to be way less useful without recursion (arbitrary loops are probably out of the question). If we allow recursion I don't want to introduce non-termination into the type checking of my code by calling some one else's malicious "const" function.

Although probably just an academic exercise to many the dependent typing community has thought through these issues in depth, and many of the restrictions imposed by dependently typed languages are to enable the full relaxation of the phase distinction between terms, and types. Any design that gives us the ability to express constructs like CTFE moves us close in that direction and we shouldn't ignore years of thought, even if our final design is quite different.

You can get if-else even if you don't allow if cond { ... } else { ... }, like so:

const fn if_else<I, E, T>(cond: bool, iff: I, elsef: E) -> T
where I: FnOnce() -> T, E: FnOnce() -> T {
    // Haven't actually tried to compile this, but you get the idea.
    let index = cond as u8;
    [iff as &FnOnce() -> T, elsef as &FnOnce() -> T][index]()
}

so I think allowing recursion basically means we are promising we are going to add the rest of control flow, which leaves us with many of the questions brought up in this thread already.

@reem 👍 to the general point (even if we can't do virtual methods as @eddyb notes). I think that is a good point out that once you add general recursion all control flow is possible which is the problem. Since we can't solve the halting problem, if we want termination we must restrict ourselves to using only primitive recursion (i.e we can only recurse on syntactic sub terms).

An example is:

#![feature(box_syntax)]
enum List<A> {
    Cons(A, Box<List<A>>),
    Nil
}

fn map<F, A, B>(xs: List<A>, f: F) -> List<B> where F: Fn(A) -> B {
   match xs {
      List::Nil => List::Nil,
      List::Cons(x, tail) => {
         // This works because I can show that I'm moving towards termination
         List::Cons(f(x), box map(*tail, f))
      }
    }
}

fn main() {}

@reem You are calling a virtual method there, which is far from being allowed.

@eddyb true, but you get the idea.

If my understanding of this and a skim of the reference impl is correct, the RFC is to allow something similar to the below:

use foomod::Foo;

mod foomod {
    #[derive(Debug)]
    pub struct Foo { inner: u8 }

    // same module : access to private members
    pub const LOCAL_FOO : Foo = {
        const DEFAULT_VAL: u8 = 4;
        Foo { inner: DEFAULT_VAL }
    };
}

// Cannot do the below as `inner` is private
// The RFC would allow Foo::new(CUSTOM_VAL) instead
//const FOO : Foo = {
//    const CUSTOM_VAL: u8 = 23;
//    Foo { inner: CUSTOM_VAL }
//};

fn main() {
    println!("{:?}", foomod::LOCAL_FOO);
    //println!("{:?}", FOO);
}

Which would, as @eddyb points out, allow us to hide implementation details while still allowing users to use const/static. Most of this functionality is already in the lang other than the potential for recursion (except via macros?), which if a limit is added makes it akin to just copy pasting a load of expansions and doesn't really expand the scope of our CTFE abilities?

@Ryman that is entirely correct. I plan to properly update the RFC to reflect the main goal better, ASAP.
As for recursion, I am happy to disallow it for 1.0 - it's unnecessary for both abstractions like UnsafeCell and the potential exposure of intrinsics like size_of.

@jroesch
I think that your suggestion that the compile-time "sub-language" be pure (other than possibly static asserts) is fairly reasonable, if for no other reason than that there is no obviously appropriate time for side effects to occur.

However, I don't think that it's as obvious that it should be total. Rust does not guarantee that type inference will terminate today, nor do I expect that it ever will in the future (except in the most practical sense, via recursion limits). In fact it is pretty trivial to use associated types to generate an infinite type stack, which in practice leads to the compiler blowing past the stack size limit (or it did a few months ago when associated types were young; I should check on what happens now, and maybe file a bug report...). If type inference is not guaranteed to terminate, is it still beneficial to make a guarantee about const functions terminating?

@reem I did not think when I posted my message that a lambda-calculus style encoding of if/then/else was expressible in the const fn language as currently outlined, but I will admit that I could be wrong, and even if I am right, the details in this description are sufficiently sketchy that I cannot tell if I am right. :)

However, I don't think that it's as obvious that it should be total. Rust does not guarantee that type inference will terminate today, nor do I expect that it ever will in the future (except in the most practical sense, via recursion limits). In fact it is pretty trivial to use associated types to generate an infinite type stack, which in practice leads to the compiler blowing past the stack size limit (or it did a few months ago when associated types were young; I should check on what happens now, and maybe file a bug report...). If type inference is not guaranteed to terminate, is it still beneficial to make a guarantee about const functions terminating?

@quantheory It isn't very difficult in principle to fix the non-termination problem with type-level computations using associated types. Haskell's type classes with type families are similar but certain restrictions are enabled by default which limit instances to a decidable fragment unless you specifically opt out. See here. IIRC, the intention was to do something similar with Rust at some point.

const programming, on the other hand, is going to be very difficult to guarantee termination for without either severely limiting generality or forcing a very particular style of programming based around structural recursion or pre-supplied recursion operators.

@freebroccolo

IIRC, the intention was to do something similar with Rust at some point.

I was not aware that anyone intended to do this. If this is not already planned for 1.0 (by which I mean, someone has a design right now), I doubt that re-instituting a guarantee of termination will happen in the foreseeable future.

const programming, on the other hand, is going to be very difficult to guarantee termination for without either severely limiting generality or forcing a very particular style of programming based around structural recursion or pre-supplied recursion operators.

I agree.

As far as recursion is concerned, I don't see const fn as different from generics: The latter already is turing complete, and the non-termination issue is simply resolved with an recursion limit.

I see no reason why const fn could not just do the same.

In both cases, if the arbitrary limit is too low for a specific use case, there is or could be an attribute for increasing it locally.

One (perhaps minor) drawback of this approach is similar as with constexpr in C : quite a lot of fns are or will be eligible for being const, especially as the initial restrictions get loosened over time, and you end up in a situation where a substantial fraction of your functions are const fns, you get bug reports for fns which could be const but weren't declared as such, and so on. Basically const noise ends up infecting more and more code. That said, I'm not sure if there's a design that avoids this problem. (While I'm familiar with singletons from GHC, can anyone elaborate on how they would be applicable here?)

(Also, there is no scenario where it would be legal to run unsafe code at compile time, right? That sounds like a bad idea.)

@glaebhoerl Sadly, we need to mark this property in the API, to be able to abstract away the contents of the function.
It's entirely possible to modify the const-qualification system to find functions which could be const (even inductively, i.e. if Unique::new calls NonZero::new and the latter is not marked const, but could be, they could be both linted).

As for unsafe const fn, the intended usecase is for functions like NonZero::new or the pointer offset intrinsic, which return a value that can cause UB in safe code, for certain inputs.
There is no actual danger of running "unsafe code" in constants, as they are pure, with no code execution, just value-oriented evaluation.

Based on the discussion here, we are merging this RFC for now. Note that the feature is not intended to be stable for 1.0 or any particular release. This gives us room to experiment with const fn while exploring potential alternatives as well. Thanks @eddyb for your work in preparing the RFC and the PR.

According to the RFC, we will mark each implementation of a trait as const. Then is it correct that we will have, say, const AtomicPtr::default() but not const BTreeMap::default()?

@nodakai Quite the contrary, trait methods cannot be const, because that requires a more complicated system that has not been designed yet.

@eddyb Hmm, I must have misread something... It was clearly stated trait methods can't be const:

Traits, trait implementations and their methods cannot be const - this allows us to properly design a constness/CTFE system that interacts well with traits - for more details, see Alternatives.

const is sad. Why not assume constance until the fn explicitly performs a non-const action (i.e. IO or recursion) or calls a non-const function (i.e. one that performs IO or recursion)? The compiler can easily keep track of which functions are "tainted".

@alexchandel what happens if a function in some API I'm working on happens to be const for a while and then I change it in a way that makes it non-const? The const keyword allows you opt in to stating that this function is guaranteed to be const.

@alexchandel It's not that simple

1. consts need to be evaluated compile-time, which isn't trivial and even undesirable, because of the duplicate effort of compiling and interpreting. Check out this recent discussion: https://internals.rust-lang.org/t/mir-constant-evaluation/3143/19
2. Rust has - by design - the relevant info for type, borrow etc. checks in function signatures. This applies to constness too. If the compiler needs to scan the bodies to determine their constness, it's going to slow it down quite a lot.
3. How are you going to detect if the function recurses or not? That doesn't make sense in the general case.

@sfackler I'd rather see it treated like unsafe, where unsafe behavior must be opted into, rather than having to mark all your functions as safe. My c code is forever polluted with constexpr, because most things are constexpr. This RFC threatens a similar situation with const fn.

@golddranks 1) This is still possible, though it might be easier with a separate phase. 2) Not substantially. It might be done very easily by assuming functions are const until proven wrong. For example, Idris assumes totality until proven wrong, but doesn't require it. 3) Yes it does. It's addressable in the short term by marking constructs like loop/while as non-const, much the same as the const fn proposal specifies what forbidden in const. Though it's notable how far c 's constexprs have pushed this.

@maninalift Hmm; Was this a comment on RFC #2237 ?

Good point - I wasn't aware of that discussion - it looks like most of what I said has been said there. I will take the time to read it.