Why there is no "function metaprogramming" in C++?

[skywalker]

For example, How to do if we want to define a bitset which size is
30th
fibonacci number?

Plan A:
#include<bitset>
#include<cstdio>

/* You can run this code in py3k to get the 30th fibonacci number.
* fib = [1, 1]
* while len(fib) != 30:
* fib += [fib[-1] + fib[-2]]
* print(fib[-1])
*/
const size_t FIB30 = 832040;

int main()
{
std::bitset< FIB30 > a;
std:rintf("%d\n", a.size());
}

This is the most common way. It works fine, but we have to run
another
program to get the number.

Plan B:
#include<bitset>
#include<cstdio>
template<size_t n> struct fib {
enum { ret = fib<n - 1>::ret + fib<n - 2>::ret };
};
template<> struct fib<1> { enum { ret = 1 }; };
template<> struct fib<2> { enum { ret = 1 }; };
int main()
{
std::bitset< fib<30> > a;
std:rintf("%d\n", a.size());
}

By using template metaprogramming technique, we can use compile to
calculate
for us. However, this syntax is weird. It doesn't looks like a C++
program.
The natural way is using c++ function.

Plan C:
#include<bitset>
#include<cstdio>
const size_t fib(const size_t n)
{
size_t f[2] = {1, 1};
for(size_t i = 3; i <= n; ++i)
f[i & 1] += f[(i - 1) & 1];
return f[n & 1];
}
int main()
{
std::bitset< fib(30) > a; // Compile error: Boom!
}

Oops, this code cannot be compiling successfully.
All we know fib(30) is a const number, it will not be changed in the
running time.
So I think the compile should treat it as a const integer,
instead of calculating it every time.
By the way, I think C++0x's new keyword constexpr doesn't work in
here.
Perhaps std::vector<bool> or boost::dynamic_bitset is a good choice,
but this is not in the range of discussion.

Why C++ standard doesn't allow this code?

 

[Jonathan Lee]

...
Oops, this code cannot be compiling successfully.
All we know fib(30) is a const number, it will not be changed in the
running time.
So I think the compile should treat it as a const integer,
instead of calculating it every time.
By the way, I think C++0x's new keyword constexpr doesn't work in
here.
Perhaps std::vector<bool> or boost::dynamic_bitset is a good choice,
but this is not in the range of discussion.

Why C++ standard doesn't allow this code?

As far as I can tell you are either asking
1) Why doesn't C++ allow types to be determined at run time? Or
2) Why doesn't C++ treat fib(30) as a constant integral expression

The answer to the first is, I think: "Because that's the way C++ is".
Types are compile-time entities. As you've pointed out, the run-time
"equivalent" is std::vector<bool>, or whatever variation you want to
write.

The answer to the second is that fib(30) may be constant, but fib(x)
isn't. How is the compiler to know that fib(30) will always be the
same? It might be obvious for something like the Fibonacci sequence,
but more generally it's not easy. Consider sin(3.0)? Or rand()?
Under what conditions should we expect the compiler to determine
constant expressions? And aren't those conditions handled by
template techniques?

 

[Miles Bader]

By the way, I think C++0x's new keyword constexpr doesn't work in
here.

It does given a suitable function, e.g.:

#include<bitset>
constexpr size_t fib(const size_t n)
{
return n < 2 ? 0 : n == 2 ? 1 : fib (n - 2) + fib (n - 1);
}
int main()
{
std::bitset< fib(30) > a;
}

works.

-miles

 

[skywalker]

There is a little bugs in Plan B, int main function,
//////////////////////////////////////////////////////
std::bitset< fib<30> > a;
//////////////////////////////////////////////////////
should be
//////////////////////////////////////////////////////
std::bitset< fib<30>::ret > a;
//////////////////////////////////////////////////////

The answer to the second is that fib(30) may be constant, but fib(x)
isn't. How is the compiler to know that fib(30) will always be the
same? It might be obvious for something like the Fibonacci sequence,
but more generally it's not easy. Consider sin(3.0)? Or rand()?
Under what conditions should we expect the compiler to determine
constant expressions? And aren't those conditions handled by
template techniques?

Isn't there a way to determine a function call is a constant
expressions?
I can provide some requirement:

1) This function mustn't use any global variant.
(rand() is not a constexpr because it likely used a global variant
called "Random Seed")

2) All function call in this function need to be a constant
expression.

3) All argument have to be a constant expression.

I think sin(3.0) is a constant expression, fib(x) is not unless x is a
constant expression.

 

[James Kanze]

As far as I can tell you are either asking
1) Why doesn't C++ allow types to be determined at run time? Or
2) Why doesn't C++ treat fib(30) as a constant integral expression

The answer to the first is, I think: "Because that's the way C++ is".
Types are compile-time entities. As you've pointed out, the run-time
"equivalent" is std::vector<bool>, or whatever variation you want to
write.

This is the classical question of compile time type checking vs.
run-time type checking. In other words, whether you want the
compiler to detect errors, or prefer letting them go until tests
or the customer encounters them.

The answer to the second is that fib(30) may be constant, but fib(x)
isn't. How is the compiler to know that fib(30) will always be the
same? It might be obvious for something like the Fibonacci sequence,
but more generally it's not easy.

C++0x allows functions to be declared constexpr, provided it
meets certain conditions. I think that fib could be written as
a constexpr, in which case it can be used as a constant,
provided it is called with a constant.

If your compiler supports C++0x (or some version of what it
thinks will be C++0x), you might try this:

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

Consider sin(3.0)? Or rand()?

The second clearly can't be a constexpr, since it depends on
global state. The first raises an interesting question: I don't
think you can implement sin in such a way that it would be a
legal constexpr function, but it certainly meets the logical
requirements. (If std::sin is meant, the standard doesn't
require it to be declared constexpr. Presumably, some
implementation could extend it to make it one, but at some
point, you have to stop. Would you expect sin(x)*sin(x) +
cos(x)*cos(x) to be treated as a constant, just because it
always returns 1.0?)

Under what conditions should we expect the compiler to determine
constant expressions?

When the programmer declares it as such.

And aren't those conditions handled by template techniques?

Hardly. And even when they are (as in the case of fib), the
syntax is incredibly hairy, and the compilation times are likely
to be outrageously long.

 

[James Kanze]

Isn't there a way to determine a function call is a constant
expressions?
I can provide some requirement:

1) This function mustn't use any global variant.
(rand() is not a constexpr because it likely used a global variant
called "Random Seed")

The C++0x draft I have access to goes further. It requires that
the function consist of a single return, and that the expression
in the return correspond to a constant expression, provided the
function parameters are considered constant expressions. (This
does allow accessing global variables, provided that the global
variables are const, and are initialized with a constant
expression visible either at the place where the function was
defined, or where it was used, I'm not sure which.)

Curiously enough, I can't find any requirement that the body of
the function be visible in the translation unit (inline function
or function template). I think that this is an oversight,
however; I'm sure that it is not the intention to require the
compiler to access other translation units when evaluating a
constexpr.

2) All function call in this function need to be a constant
expression.

3) All argument have to be a constant expression.

I think sin(3.0) is a constant expression, fib(x) is not unless x is a
constant expression.

I think sin(3.0) would be a logical candidate, but I don't think
you can implement sin in a way that it meets the standard's
requirements for constexpr. Presumably, a compiler could offer
extensisions which allowed it, say with a definition of sin as:

inline constexpr double sin(double x) { return __buildin_sin(x); }

 

[Marc]

The second clearly can't be a constexpr, since it depends on
global state. The first raises an interesting question: I don't
think you can implement sin in such a way that it would be a
legal constexpr function, but it certainly meets the logical
requirements.

I believe it is possible, just awfully inconvenient (and it won't set
errno or take into account some current rounding mode).

(If std::sin is meant, the standard doesn't
require it to be declared constexpr. Presumably, some
implementation could extend it to make it one, but at some
point, you have to stop. Would you expect sin(x)*sin(x) +
cos(x)*cos(x) to be treated as a constant, just because it
always returns 1.0?)

Does it (always return 1.0)? I would expect the rounding to break that
property. Might be the axiom proposal would have allowed (not forced)
the transformation.

 

[Jonathan Lee]

The second clearly can't be a constexpr, since it depends on
global state.

Still, every time I run

int main() {
std::cout << rand() << std::endl;
return 0;
}

I get the same value. At compile time (esp: before any code
runs), it _is_ a constant expression.

 The first raises an interesting question: I don't
think you can implement sin in such a way that it would be a
legal constexpr function, but it certainly meets the logical
requirements.  (If std::sin is meant, the standard doesn't
require it to be declared constexpr.  Presumably, some
implementation could extend it to make it one, but at some
point, you have to stop.  Would you expect sin(x)*sin(x) +
cos(x)*cos(x) to be treated as a constant, just because it
always returns 1.0?)

Exactly: at some point you have to stop. But we needn't go so
far as trigonometric identies. There are practical difficulties
to determining the results of floating point operations, ex:

bool is_one_third(double x) { return (x == 1./3.); }
...
is_one_third(1./3.);

What is is_one_third(1./3.)? It seems to be constant, but
what's the value? On what platform? With what compiler flags?

I think once you go through and eliminate all these problem
areas, you'll more or less end up with the functions that can
be calculated via templates.

--Jonathan

 

[itaj sherman]

For example, How to do if we want to define a bitset which size is
30th
fibonacci number?

Plan A:
#include<bitset>
#include<cstdio>

/* You can run this code in py3k to get the 30th fibonacci number.
* fib = [1, 1]
* while len(fib) != 30:
* fib += [fib[-1] + fib[-2]]
* print(fib[-1])
*/
const size_t FIB30 = 832040;

int main()
{
std::bitset< FIB30 > a;
std:rintf("%d\n", a.size());

}

This is the most common way. It works fine, but we have to run
another
program to get the number.

Plan B:
#include<bitset>
#include<cstdio>
template<size_t n> struct fib {
enum { ret = fib<n - 1>::ret + fib<n - 2>::ret };};

template<> struct fib<1> { enum { ret = 1 }; };
template<> struct fib<2> { enum { ret = 1 }; };
int main()
{
std::bitset< fib<30> > a;
std:rintf("%d\n", a.size());

}

By using template metaprogramming technique, we can use compile to
calculate
for us. However, this syntax is weird. It doesn't looks like a C++
program.
The natural way is using c++ function.

Isn't it possible to wrap it with a constexpr function:

constexpr size_t fib_func(const size_t n)
{
return fib<n>;
}

Then the "wierd" template implementation can be encapsulated.

I can see that template implementations for more complicated things
like sin() can become quite a bother. Also, because the template
evaluation can be much more verbose than regular function code, the
compilation might be longer than seems reasonable.

I don't know why std::sin shouldn't be constexpr because floating-
point precision is not restricted 5.19/4.
However, even though float itself cannot specialize a template, it is
possible to work-around using template meta to do that:

template< typename jDigitVector, typename jExponent > class FloatPoint
{
public: typepdef jDigitVector DigitVector;
public: typepdef jExponent Exponent;
};

template< typename T >
constexpr float floatPointValue()
{
return someRecursiveConstexprEvaluation< T::Exponent, T:igitVector

();

}


template< typename X1, typename X2 > class FloatPointAddition
{
public: typedef IntegerMin< X1::Exponent, X2::Exponent >::type
Exponent;
private: typedef
PrefixVecter< IntegerAbsolute< IntegerSubtract< X1::Exponent,
X2::Exponent >::type >::type, 0, X1 >
ExtendedDigitVector1;
private: typedef
PrefixVecter< IntegerAbsolute< IntegerSubtract< X1::Exponent,
X2::Exponent >::type >::type, 0, X2 >
ExtendedDigitVector2;
public: typedef boost::mpl::vector_transform< ExtendedDigitVector1,
ExtendedDigitVector2, IntegerAddition >::type
DigitVector;
}

I guess you see where it goes. By the time you finish the first course
of theoretical calculus and reach FloatPointSin< Value, Precision >
using tailor sequences, compilation might be slow.

itaj