On Sat, Jan 16, 2010 at 1:08 AM, Victor Lazzarini
<[email protected]> wrote:
> Torben's new project brought back to my mind this mind-bending C++
> template example (see attached), which I could not yet get to compile, I
> have been told it has been compiled, but g++ will have none of it. So I
> still have doubts on whether it includes legal C++ code or not. But it is an
> interesting example (even if it does not build) of what (possibly) can be
> done with templates.
>
> My question to the list is: has anyone managed to compile this code?
Wow, that's insane. But as far as I can tell, it is (almost) valid
C++. What gcc rightly complains about are a couple of missing typename
keywords. That's actually a pretty common mistake, because it's hard
to understand why these are even necessary, and some compilers simply
don't care.
The attached version of the file compiles fine with gcc, and the
program gives the correct answer.
Dominic
//
// A C++ program to test for the primality of the number 13
//
// It has the curious property that it does no arithmetic
// but uses only the template mechanism and class derivation
// to achieve its result. It starts at the most basic axioms
// of arithmetic starting with the definition of zero and
// its successors...
//
// You'll need a good C++ compiler.
//
// (c) D Piponi (But copy it as much as you like if you credit me)
//
//
// First a little trick to find the base class of our
// classes because the template mechanism requires
// exact matches.
//
// Two values are considered equivalent if they have
// the same baseclass. For example 1+1 isn't
// identical to 2 but 1+1 *is* derived from 2.
//
template<typename V> struct Value { typedef V value; };
//
// Define zero
//
struct zero
: public Value<zero> { };
//
// Define the successor of an integer
//
template<typename C> struct S
: public Value<S<C> > { typedef C predecessor; };
//
// Now we have the integers. So introduce some convenience
// types.
//
typedef S<zero> one;
typedef S<one> two;
typedef S<two> three;
typedef S<three> four;
typedef S<four> five;
typedef S<five> six;
typedef S<six> seven;
typedef S<seven> eight;
typedef S<eight> nine;
typedef S<nine> ten;
//
// Define plus,...
//
template<typename C,typename D> struct plus
: public S<plus<C,typename D::predecessor> > { };
template<typename C> struct plus<C,zero>
: public C { };
//
// ...minus...
//
template<typename C,typename D> struct minus
: public minus<C,typename D::predecessor>::predecessor { };
template<typename C> struct minus<C,zero>
: public C { };
//
// ...and times.
//
template<typename C,typename D> struct times
: public plus<C,typename times<C,typename D::predecessor>::value> { };
template<typename C> struct times<C,zero>
: public zero { };
//
// Define the usual ordering on the integers.
//
template<typename C,typename D> struct ge
: public ge<typename C::predecessor,typename D::predecessor> { };
template<typename C> struct ge<C,zero>
: public one { };
template<typename C> struct ge<zero,C>
: public zero { };
template<> struct ge<zero,zero>
: public one { };
//
// Divisibility testing
//
template<typename C,typename D,typename E = S<S<zero> > > struct Divisible { };
template<typename C,typename D> struct Divisible<C,D,S<S<zero> > >
: public Divisible<C,D,typename ge<C,D>::value> { };
//
// The case C<D:
// In this case D divides C iff C is zero.
//
template<typename C,typename D> struct Divisible<C,D,zero>
: public zero { };
template<typename C> struct Divisible<zero,C,zero>
: public one { };
//
// The case C>=D:
// D divides C iff D divides C-D.
//
template<typename C,typename D> struct Divisible<C,D,S<zero> >
: public Divisible<typename minus<C,D>::value,D> { };
//
// Primality testing
//
template<typename C,typename D = two,typename S = zero,typename E = zero,typename F =
zero> struct Prime { };
//
// We use recursion to set up a loop from 2 to one less
// than the integer we are testing. Essentially this is a state machine
// using template parameters to record the current state.
//
// Are we at the end of the recursion?
//
template<typename C,typename D> struct Prime<C,D,zero,zero,zero>
: public Prime<C,D,one,zero,typename ge<D,C>::value> { };
//
// Test potential factor D, trying successor on failure.
//
template<typename C,typename D> struct Prime<C,D,one,zero,zero>
: public Prime<C,S<D>,zero,typename Divisible<C,D>::value,zero> { };
//
// Found a factor.
//
template<typename C,typename D> struct Prime<C,D,zero,one,zero>
: public zero { };
//
// Reached the end of the loop without finding divisor.
//
template<typename C,typename D> struct Prime<C,D,one,zero,one>
: public one { };
//
// Convenience method for humans allowing input of
// numbers in decimal format.
//
template<typename C,typename D> struct Decimal
: public plus<typename times<ten,C>::value,D> { };
//
// Unfortunately the I/O interface spoils the purity of it all.
//
#include <stdio.h>
template<typename C> char const *output(C);
template<> char const *output(zero) { return "No"; }
template<> char const *output(one) { return "Yes"; }
main() {
//
// Is 13 prime?
//
puts(output(Prime<Decimal<one,three>::value>::value()));
}
_______________________________________________
Linux-audio-dev mailing list
[email protected]
http://lists.linuxaudio.org/listinfo/linux-audio-dev
