views:

211

answers:

5

According to Generalized Constant Expressions—Revision 5 the following is illegal.

constexpr int g(int n) // error: body not just ‘‘return expr’’
{
    int r = n;
    while (--n > 1) r *= n;
    return r;
}

This is because all 'constexpr' functions are required to be of the form { return expression; }. I can't see any reason that this needs to be so.

In my mind, the only thing that would really be necessary is that no external state information is read/written and the parameters being passed in are also 'constexpr' statements. This would mean that any call to the function with the same parameters would return the same result, thus it is possible to "know" at compile time.

My main problem with this is that it just seems to force you to do really roundabout forms of looping and hoping that the compiler optimises it so that its just as fast for non-constexpr calls.

To write a valid constexpr for the above example you could do:

constexpr int g(int n) // error: body not just ‘‘return expr’’
{
    return (n <= 1) ? n : (n * g(n-1));
}

But this is a lot harder to understand and you have to hope that the compiler takes care of the tail recursion when you call with parameters that violate the requirements for const-expr.

A: 

It's probably ill-formed because it's too hard to implement. A similar decision was made in the first version of the standard with regard to member function closures (i.e., being able to pass off obj.func as a callable function). Maybe a later revision of the standard will offer more latitude.

Marcelo Cantos
Though seeing how the function has to be well formed c++ anyway, the compiler could compile the functions and then just run them and use the value returned (doesn't have to link into final executable, just a dummy block of memory along with the other functions constexpr it calls)
Grant Peters
@Grant: that's easier said than done. It's generally pretty tricky to compile small snippets of C++ code into a working program. The code might depend on some global state, or a macro, or... There are a lot of corner cases to consider to do it robustly
jalf
@Grant: The halting problem will bite you on the bum. Also, see my other answer.
Marcelo Cantos
@jalf: Due to the restrictions on constexpr, running small snippets of code would be particularly onerous for a compiler. The real problem is that recursion is explicitly disallowed in constexpr functions.
Marcelo Cantos
+2  A: 

As I understand it they kept it as simple as possible so as not to complicate the language (in fact I seem to remember a time in which recursive calls weren't allowed but that is no longer the case). The rationale being that it's much easier to relax rules in future standards than it is to restrict them.

Motti
Thats a good point, see how it goes and add more features if it isn't too complex and if no other problems are found after release. Just annoying to have to hack around it.
Grant Peters
+5  A: 

Just in case there's any confusion here, you are aware that constexpr functions/expressions are evaluated at compile-time. There's no runtime performance concern involved.

Knowing this, the reason that they only allow single return statements in constexpr functions is so that compiler implementors don't need to write a virtual machine to calculate the constant value.

I am concerned about QoI issues with this though. I wonder if the compiler implementors will be clever enough to perform memoization?

constexpr fib(int n) { return < 2 ? 1 : fib(n-1) + fib(n-2); }

Without memoization, the above function has O(2n) complexity, which is certainly not something I'd like to feel, even at compile time.

Peter Alexander
Runtime performance is concerned if you call it with a non const expression. Correct me if I'm wrong, but constexpr functions can also be called as if they were a normal function.
Grant Peters
@Grant Peters Peters point is if you look at the time complexity of this version of Fibonacci your builds times are potentially going to explode but in reality constexpr functions will have the same (or similliar) recursion depth limit as templates.if you call a constexpr function with argument that isn't a constant expression then the function will be evaluated at runtime instead of compile-time.I'm just wondering but I think constexpr would benefit form being lazily evaluated like what boost mpl tries to do with templates to reduce builds times and support lazy (meta)programs in general.
snk_kid
Agreed, consider `template<int N> struct Fib { const int value = Fib<N-1>::value + Fib<N-2>::value; };` . The introduction of `constexpr` doesn't create a new desire for memoization.
MSalters
+4  A: 

The reason is that the compiler has plenty to do already, without also being a full-fledged interpreter, able to evaluate arbitrary C++ code.

If they stick with single expressions, they limit the number of cases to consider dramatically. Loosely speaking, it simplifies things a lot that there are no semicolons in particular.

Every time a ; is encountered, it means the compiler has to deal with side effects. It means that some local state was changed in the previous statement, which the following statement is going to rely on. It means that the code being evaluated is no longer just a series of simple operations each taking as its inputs the previous operation's output, but require access to memory as well, which is much harder to reason about.

In a nutshell, this:

7 * 2 + 4 * 3

is simple to compute. You can build a syntax tree which looks like this:

   +
  /\
 /  \
 *   *
/\  /\
7 2 4 3

and the compiler can simply traverse this tree performing these primitive operations at each node, and the root node is implicitly the return value of the expression.

If we were to write the same computation using multiple lines we could do it like this:

int i0 = 7;
int i1 = 2;
int i2 = 4;
int i3 = 3;

int i4 = i0 * i1;
int i5 = i2 * i3;
int i6 = i4 + i5;
return i6;

which is much harder to interpret. We need to handle memory reads and writes, and we have to handle return statements. Our syntax tree just became a lot more complex. We need to handle variable declarations. We need to handle statements which have no return value (say, a loop, or a memory write), but which simply modify some memory somewhere. Which memory? Where? What if it accidentally overwrites some of the compiler's own memory? What if it segfaults?

Even without all the nasty 'what-if's, the code the compiler has to interpret just got a lot more complex. The syntax tree might now look something like this: (LD and ST are load and store operations respectively)

    ;    
    /\
   ST \
   /\  \
  i0 3  \
        ;
       /\
      ST \
      /\  \
     i1 4  \
           ;
          /\
         ST \
         / \ \
       i2  2  \
              ;
             /\
            ST \
            /\  \
           i3 7  \
                 ;
                /\
               ST \
               /\  \
              i4 *  \
                 /\  \
               LD LD  \
                |  |   \
                i0 i1   \
                        ;
                       /\
                      ST \
                      /\  \
                     i5 *  \
                        /\  \
                       LD LD \
                        |  |  \
                        i2 i3  \
                               ;
                              /\
                             ST \
                             /\  \
                            i6 +  \
                               /\  \
                              LD LD \
                               |  |  \
                               i4 i5  \
                                      LD
                                       |
                                       i6

Not only does it look a lot more complex, it also now requires state. Before, each subtree could be interpreted in isolation. Now, they all depend on the rest of the program. One of the LD leaf operations doesn't make sense unless it is placed in the tree so that a ST operation has been executed on the same location previously.

jalf
+2  A: 

EDIT: Ignore this answer. The referenced paper is out of date. The standard will allow limited recursion (see the comments).

Both forms are illegal. Recursion isn't allowed in constexpr functions, due to the restriction that a constexpr function cannot be called until it is defined. The link the OP provided states this explicitly:

constexpr int twice(int x);
enum { bufsz = twice(256) }; // error: twice() isn’t (yet) defined

constexpr int fac(int x)
{ return x > 2 ? x * fac(x - 1) : 1; } // error: fac() not defined
                                       // before use

A few lines further down:

The requirement that a constant-expression function can only call previously defined constant-expression functions ensures that we don’t get into any problems related to recursion.

...

We (still) prohibit recursion in all its form in constant expressions.

Without these restrictions you become embroiled in the halting problem (thanks @Grant for jogging my memory with your comment on my other answer). Rather than impose arbitrary recursion limits, the designers considered it simpler to just say, "No".

Marcelo Cantos
Ahh, missed that bit. Well that certainly drops my enthusiasm for constexpr a lot. Was hoping I'd be able to do hashing algorithms for strings, but seeing how they all involve some sort of loop, it seems impossible for a general compile time solution.
Grant Peters
"Recursion isn't allowed in constexpr functions". That's false. The paper linked is from 2007 and in the meantime constexpr have been allowed to be recursive. In the current working draft (n3092) we can see in "Annex B (informative) Implementation quantities [implimits]" that a compiler must allow at least 512 nested recursive constrexpr function invokation.
Thomas Petit
D'oh! I even checked the Wikipedia entry to confirm and it also indicates that the function has to be defined before it can be called, which I took to mean no recursion.
Marcelo Cantos
I asked this on comp.std.c++ last month http://groups.google.com/group/comp.std.c++/browse_thread/thread/87b5cb8b8dabec2d/26dcbe7bb2b0c269?lnk=raotYes recursion is allowed :)
snk_kid