 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
leimy2k@gmail.com
Guest
|
 Posted: Fri Jul 29, 2005 11:06 am Post subject: template recursion "fun" |
 |
|
I wonder if code like this is expected to be supported by the template
evaluation code of standards conformant C++ compilers.
It's the old, how many ways are there to make change from a given
amount given a number of denominations of coins problem, done at
compile time using an arguably evil amount of template recursion.
I adapted it from some Scheme code from Structure and Interpretation of
Computer Programs and it has a good deal of recursion involved.
It doesn't like to compile in the form it is below. If I change the
template CountChange to use only 2 or 3 total denominations of coins
[pennies, nickels and dimes] it seem to compile OK with the default
settings on gcc-4.0. To do the whole 5 kinds of coins [including
quarters and half-dollars] I've had to use the -ftemplate-depth-NN
option where NN is currently at 100000 and it's been compilng for the
last 34 minutes  .
Obviously this isn't very practical, but it raises the question of
support for template recursion in C++ compilers and what developers can
expect in their compilers to be supported or what should be demanded
from vendors when it comes to support . This is surely an extreme
case that doesn't come up very often.
Here's the code:
---->8----
#include <iostream>
// Forward declare the "First denomination" class
template <int koc>
struct FirstDenomination;
// Helper macro so I don't have to write this over and over
#define FIRST_DENOM(x,y)
template <>
struct FirstDenomination <x>
{
enum {res = y};
}
// Use the macro to define the denominations
FIRST_DENOM(1,1); //1 cent
FIRST_DENOM(2,5); //5 cents
FIRST_DENOM(3,10); //10 cents
FIRST_DENOM(4,25); //25 cents
FIRST_DENOM(5,50); //50 cents
// Declare CC [count change] to be a template taking two integer
parameters
template <int amount, int koc>
struct CC;
// Specialize for amounts == 0
template <int koc>
struct CC <0, koc>
{
enum {res = 1};
};
// Specialize fo koc == 0 [kinds of coins]
template <int amount>
struct CC <amount, 0>
{
enum {res = 0};
};
// The regular specification of the functionality
template <int amount, int koc>
struct CC
{
enum {res = (CC <amount, koc-1>::res + CC<(amount -
FirstDenomination::res)};
};
// A "helper" to count any amount of change with all 5 types of coins
template <int amount>
struct CountChange
{
enum {res = CC<amount, 5>::res};
};
int main ()
{
std::cout << CountChange<100>::res << std::endl;
}
----8<----
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Hyman Rosen
Guest
|
| Posted: Fri Jul 29, 2005 2:55 pm Post subject: Re: template recursion "fun" |
|
|
[email]leimy2k (AT) gmail (DOT) com[/email] wrote:
| Quote: | I wonder if code like this is expected to be supported by the template
evaluation code of standards conformant C++ compilers.
|
When I try it on Comeau, it gives an error message about recursion
being too deep, at about 65 levels deep of instantiation. Appendix B
of the standard says that the recommended minimum level is only 17,
but that was written before metaprogramming became so popular. Still,
as you see, you can't go too deep.
You need to help the compiler out a little here. First of all, don't
allow negative amounts. Second, when there's only one coin kind, don't
recurse at all. Change your code like this:
// Specialize for koc == 1 [kinds of coins]
template <int amount>
struct CC <amount, 1>
{
enum {res = amount % FirstDenomination<1>::res == 0};
};
// The regular specification of the functionality
template <int amount, int koc>
struct CC
{
enum {res = (CC<amount, koc-1>::res +
CC<(amount - FirstDenomination
(amount >= FirstDenomination<koc>::res ? koc : 0)>::res)};
};
With these changes, gcc compiles the program in no time at all,
without having to specify any depth parameters.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
leimy2k@gmail.com
Guest
|
| Posted: Sat Jul 30, 2005 10:10 am Post subject: Re: template recursion "fun" |
|
|
Also, just like in any other functional programming language, I might
want to consider something such as simplifying the algorithm first.
Tree recursion tends to be bad for performance, even though
"performance" in this case is a "somewhat negligable" compile time
issue .
I forgot about the 17 level limit; seems a bit arbitrary in hindsight
.
Thanks for your simplification, I was merely using the code as an
example to aid discussion.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Sun Jul 31, 2005 11:45 am Post subject: Re: template recursion "fun" |
|
|
Hyman Rosen <hyrosen (AT) mail (DOT) com> wrote:
| Quote: | leimy2k (AT) gmail (DOT) com wrote:
I wonder if code like this is expected to be supported by the template
evaluation code of standards conformant C++ compilers.
When I try it on Comeau, it gives an error message about recursion
being too deep, at about 65 levels deep of instantiation. Appendix B
of the standard says that the recommended minimum level is only 17,
but that was written before metaprogramming became so popular. Still,
as you see, you can't go too deep.
You need to help the compiler out a little here. First of all, don't
allow negative amounts. Second, when there's only one coin kind, don't
recurse at all. Change your code like this:
// Specialize for koc == 1 [kinds of coins]
template <int amount
struct CC
{
enum {res = amount % FirstDenomination<1>::res == 0};
};
// The regular specification of the functionality
template <int amount, int koc
struct CC
{
enum {res = (CC
CC<(amount - FirstDenomination
(amount >= FirstDenomination<koc>::res ? koc : 0)
::res)};
};
With these changes, gcc compiles the program in no time at all,
without having to specify any depth parameters.
if you use Loki Typelist and Int2Type and NullType you can do it all |
without macros, or FirstDenomination metafuction. What you are doing
is combining the results obtained with a given Amt and a list of coin
values. This implimentation assumes the last such coin value is one and
is ommitted from the list. Typelist is a lisp like cons list ,Int2Type
is a class wrapper for integers and NullType is an end of list sentinel.
Loki provides a macro to accompilsh the typedef ... Money below but this
does everything without macros and should recurse only 5 levels deep
while walking the list.
code below purposely does not compile the error provides the result of
the meta programmed coin_counter. should indicate what<7> is an
incomplete class.
// code starts
// loki stuff
struct NullType{};
template <class H,class T> struct Typelist
{
typedef H Head;
typedef T Tail;
};
template <int N> struct Int2Type {static const int value = N;};
// end loki stuff
typedef Typelist
<
Int2Type<50>,
Typelist
<
Int2Type<25>,
Typelist
<
Int2Type<10>,
Typelist
<
Int2Type<5>,
NullType
template <int Amt,class TList=Money> class coin_counter;
template <int Amt,class H,class T> class coin_counter<Amt,Typelist
static const int coin_value = H::value;
static const int nc = Amt/coin_value;
static const int next_amt = Amt % coin_value;
public:
static const int value = nc + coin_counter<next_amt,T>::value;
};
template <int Amt> class coin_counter<Amt,NullType>
{
public:
static const int value = Amt;
};
template <int N> struct what;
what<coin_counter<74>::value> test;
[ 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
