 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Niklas Matthies
Guest
|
 Posted: Thu Sep 22, 2005 9:11 am Post subject: Using operator-> for TMP recursion |
 |
|
I wonder whether somebody already thought about using operator-> to
implement TMP recursion, since nested template instantiation limits
don't seem to apply there. Here's a simple example:
// determine sum of natural numbers from 1 to N
template <int N, int S = 0>
struct Sum {
Sum<N-1, S+N> operator -> () const { return Sum<N-1, S+N>(); }
};
template <int S>
struct Sum<0, S> {
struct Result { int result() const { return S; } } result;
Result const * operator -> () const { return &result; }
};
int main()
{
std::cout << Sum<100>()->result() << std::endl; // prints 5050
return 0;
}
-- Niklas Matthies
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
David Abrahams
Guest
|
| Posted: Thu Sep 22, 2005 11:28 am Post subject: Re: Using operator-> for TMP recursion |
|
|
Niklas Matthies <usenet-nospam (AT) nmhq (DOT) net> writes:
| Quote: | I wonder whether somebody already thought about using operator-> to
implement TMP recursion, since nested template instantiation limits
don't seem to apply there. Here's a simple example:
// determine sum of natural numbers from 1 to N
template <int N, int S = 0
struct Sum {
Sum () const { return Sum<N-1, S+N>(); }
};
template <int S
struct Sum<0, S> {
struct Result { int result() const { return S; } } result;
Result const * operator -> () const { return &result; }
};
int main()
{
std::cout << Sum<100>()->result() << std::endl; // prints 5050
return 0;
}
|
Very cute! Unfortunately, until we have decltype it isn't very
general: you can't compute new types this way unless you're prepared
to use them immediately in a runtime context.
Have you done any tests to see if it consumes fewer compiler resources,
or can do more computation before blowing up, than the usual methods?
I'd like to see those results!
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Niklas Matthies
Guest
|
| Posted: Thu Sep 22, 2005 2:27 pm Post subject: Re: Using operator-> for TMP recursion |
|
|
On 2005-09-22 11:28, David Abrahams wrote:
| Quote: | Niklas Matthies <usenet-nospam (AT) nmhq (DOT) net> writes:
I wonder whether somebody already thought about using operator-> to
implement TMP recursion, since nested template instantiation limits
don't seem to apply there. Here's a simple example:
// determine sum of natural numbers from 1 to N
template <int N, int S = 0
struct Sum {
Sum () const { return Sum<N-1, S+N>(); }
};
template <int S
struct Sum<0, S> {
struct Result { int result() const { return S; } } result;
Result const * operator -> () const { return &result; }
};
int main()
{
std::cout << Sum<100>()->result() << std::endl; // prints 5050
return 0;
}
Very cute! Unfortunately, until we have decltype it isn't very
general: you can't compute new types this way unless you're prepared
to use them immediately in a runtime context.
|
That's right. You also can't compute compile-time constants.
To be true, the above isn't really TMP at all, since the chain
of operator->() invocations, which means the actual iteration,
conceptually happens at runtime.
My original idea was indeed to use a typeof facility, and then
I tried to make as much of it as possible without it.
| Quote: | Have you done any tests to see if it consumes fewer compiler resources,
or can do more computation before blowing up, than the usual methods?
|
Not really. Since the templates have still to be instantiated, I don't
think that it will make a significant difference in terms of resources.
My aim was mainly to get rid of the hard limit on instantiation depth.
-- Niklas Matthies
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Kodt
Guest
|
| Posted: Thu Sep 22, 2005 2:28 pm Post subject: Re: Using operator-> for TMP recursion |
|
|
| Quote: | Very cute! Unfortunately, until we have decltype it isn't very
general: you can't compute new types this way unless you're prepared
to use them immediately in a runtime context.
Have you done any tests to see if it consumes fewer compiler resources,
or can do more computation before blowing up, than the usual methods?
I'd like to see those results!
|
I compared this approach with a more common one,
template<int N, int S=0>
struct Sum
{
enum { value = Sum<N-1,S+N>::value };
};
template<int S>
struct Sum<0,S>
{
enum { value = S };
};
As we can see, both of them have linear recursion.
But operator-> makes a _tail_recursion_, so that compiler (Comeau Test
Drive) doesn't exceed its limits. And with my example, it does.
Pitily, the result of computation doesn't seem to be compile-time
constant. We cannot write
char buf[ Sum<100>()->value ];
even if it was defined
....
{
struct result { enum { value=S }; };
result* operator->() const { return NULL; }
}
----------
So, if we need a compile-time computations, we have to reduce the
algorithm's depth.
For instance,
template<int L, int C> // sum of [L..L+C) range
struct SumRange
{
enum { value = L +
SumRange<(L+1) ,(C-1)/2 >::value +
SumRange<(L+1)+(C-1)/2,(C-1)-(C-1)/2>::value
};
};
template<int L>
struct SumRange<L,0> // empty range
{
enum { value = 0 };
};
template<int N>
struct Sum
{
enum { value = SumRange<1,N>::value };
};
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Marco Jez
Guest
|
| Posted: Thu Sep 22, 2005 5:39 pm Post subject: Re: Using operator-> for TMP recursion |
|
|
"Niklas Matthies" <usenet-nospam (AT) nmhq (DOT) net> ha scritto nel messaggio
news:slrndj41ri.23cd.usenet-nospam (AT) nmhq (DOT) net...
| Quote: | I wonder whether somebody already thought about using operator-> to
implement TMP recursion, since nested template instantiation limits
don't seem to apply there. Here's a simple example:
|
Since you can only evaluate the result at run time (as opposite to usual TMP
recursion which takes place at compile time), what's the advantage of using
this code instead of a non-template function?
Marco
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Greg Herlihy
Guest
|
| Posted: Fri Sep 23, 2005 1:18 pm Post subject: Re: Using operator-> for TMP recursion |
|
|
Marco Jez wrote:
| Quote: | "Niklas Matthies" <usenet-nospam (AT) nmhq (DOT) net> ha scritto nel messaggio
news:slrndj41ri.23cd.usenet-nospam (AT) nmhq (DOT) net...
I wonder whether somebody already thought about using operator-> to
implement TMP recursion, since nested template instantiation limits
don't seem to apply there. Here's a simple example:
Since you can only evaluate the result at run time (as opposite to usual TMP
recursion which takes place at compile time), what's the advantage of using
this code instead of a non-template function?
Marco
|
There's no requirement that the expression be evaluated only at
runtime. The requirement is that the result of the evaluation cannot be
used in an expression requiring a compile-time constant. But a
compile-time evaluation can be used productively in other ways.
As an example, an optimizing compiler with sufficient inline recursion
depth resolution will realize that that this expression:
Sum<100>()->result()
is a constant expression evaluating to 5050. The optimizer will replace
this expression with the value 5050 and not invoke the ->() operator at
all. And no, I am not speculating here. I know from compiling and
disassembling the original example that there is at least one C++
compiler (I tested Metrowerks) that performs this optimization today.
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Harald van Dijk
Guest
|
| Posted: Fri Sep 23, 2005 1:20 pm Post subject: Re: Using operator-> for TMP recursion |
|
|
Niklas Matthies wrote:
| Quote: | I wonder whether somebody already thought about using operator-> to
implement TMP recursion, since nested template instantiation limits
don't seem to apply there. Here's a simple example:
|
Very interesting. Here's a modified version:
#include <iostream>
template <int N, int S = 0>
struct Sum { Sum<N-1, S+N> operator->(); };
template <int S>
struct Sum<0, S> {
struct Result { char result[S]; };
Result *operator->();
};
int main() {
std::cout << sizeof(Sum<100>()->result) << std::endl;
}
Is this still valid? And if so, can sizeof(Sum<100>()->result) be used
as any other constant?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Sat Sep 24, 2005 2:09 am Post subject: Re: Using operator-> for TMP recursion |
|
|
Niklas Matthies <usenet-nospam (AT) nmhq (DOT) net> writes:
| Quote: | Very cute! Unfortunately, until we have decltype it isn't very
general: you can't compute new types this way unless you're prepared
to use them immediately in a runtime context.
That's right. You also can't compute compile-time constants.
To be true, the above isn't really TMP at all, since the chain
of operator->() invocations, which means the actual iteration,
conceptually happens at runtime.
|
I don't know about that. The very first TMP was probably expression
templates, which look pretty runtime-ish in a very similar way.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Niklas Matthies
Guest
|
| Posted: Sat Sep 24, 2005 2:21 am Post subject: Re: Using operator-> for TMP recursion |
|
|
On 2005-09-23 13:20, Harald van D?k wrote:
| Quote: | Niklas Matthies wrote:
I wonder whether somebody already thought about using operator-> to
implement TMP recursion, since nested template instantiation limits
don't seem to apply there. Here's a simple example:
Very interesting. Here's a modified version:
#include <iostream
template
struct Sum { Sum(); };
template <int S
struct Sum<0, S> {
struct Result { char result[S]; };
Result *operator->();
};
int main() {
std::cout << sizeof(Sum<100>()->result) << std::endl;
}
|
Very nice!
| Quote: | Is this still valid? And if so, can sizeof(Sum<100>()->result) be
used as any other constant?
|
Yes and yes.
-- Niklas Matthies
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Przemyslaw Szymanski
Guest
|
| Posted: Sat Sep 24, 2005 2:22 am Post subject: Re: Using operator-> for TMP recursion |
|
|
Out of sheer curiosity - what do you think about this modification of
that common implementation?
#include <iostream>
template <int N, int S = 0>
struct sum
{
typedef typename sum<N - 1, S + N>::type type;
};
template <int S>
struct sum<0, S>
{
typedef sum type;
enum { value = S };
};
int main()
{
int a = sum<100>::type::value;
std::cout << a << std::endl;
return 0;
}
Still limited by the template recursion depth, though...
Przemek.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Niklas Matthies
Guest
|
| Posted: Sun Sep 25, 2005 1:39 am Post subject: Re: Using operator-> for TMP recursion |
|
|
On 2005-09-24 02:09, David Abrahams wrote:
| Quote: | Niklas Matthies <usenet-nospam (AT) nmhq (DOT) net> writes:
Very cute! Unfortunately, until we have decltype it isn't very
general: you can't compute new types this way unless you're prepared
to use them immediately in a runtime context.
That's right. You also can't compute compile-time constants.
To be true, the above isn't really TMP at all, since the chain
of operator->() invocations, which means the actual iteration,
conceptually happens at runtime.
I don't know about that. The very first TMP was probably expression
templates, which look pretty runtime-ish in a very similar way.
|
I guess you're right, since the generation of the invocation chain
is controlled by template logic.
On another note: Is there some intrinsic reason why compilers should
impose a fixed (if configurable) limit on the number of nested
template instantiations, while they don't on operator -> recursion?
-- Niklas Matthies
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Mon Sep 26, 2005 8:30 am Post subject: Re: Using operator-> for TMP recursion |
|
|
Niklas Matthies <usenet-nospam (AT) nmhq (DOT) net> writes:
| Quote: | On another note: Is there some intrinsic reason why compilers should
impose a fixed (if configurable) limit on the number of nested
template instantiations, while they don't on operator -> recursion?
|
The standard has a "recommended minimum" for the former; perhaps they
are trying to help you write portable code?
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Niklas Matthies
Guest
|
| Posted: Tue Sep 27, 2005 11:29 am Post subject: Re: Using operator-> for TMP recursion |
|
|
On 2005-09-26 08:30, David Abrahams wrote:
| Quote: | Niklas Matthies <usenet-nospam (AT) nmhq (DOT) net> writes:
On another note: Is there some intrinsic reason why compilers should
impose a fixed (if configurable) limit on the number of nested
template instantiations, while they don't on operator -> recursion?
The standard has a "recommended minimum" for the former;
|
Of course. To elaborate my question into a couple of related ones:
Since the standard doesn't bother to specify a recommended minimum
for the latter (and that doesn't seem to hurt), why does it for the
former?
Why is the specified recommended minimum so small compared to most
of the other recommended minima?
Why do compilers by default impose a pretty small limit; much smaller
than I would estimate the associated resource consumption to suggest?
| Quote: | perhaps they are trying to help you write portable code?
|
Perhaps. But in practice it appears to have the effect of compilers
accepting less programs than they would otherwise (judging from how
they behave for operator -> recursion), while on the theoretical side
it doesn't make code more portable in the strict sense, since the
minimum is only "recommended", which means it still remains a QoI
issue. If we relate the "Q" to the number of supported nested levels,
then the specified minimum appears to have the effect of a much lower
"Q" for template recursion than for operator -> recursion.
-- Niklas Matthies
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
