template metaprogramming syntax

[nooneinparticular314159]

Hello. If I declare the following:

template<int a, int b, int SomeArray[]>
class DoSomething{

public:
..
..
..

I have no problems, and the compiler is quite happy, and my template
function works as expected. But I want to add in an array for my
template to act on. I change the first line to:

template<int MIDPOINT, int Key, int ArrayToSearch[]>

but I get the following error:
error: provided for 'template<int a, int b, int * SomeArray> class
DoSomething'

Why do I get this error when I attempt to pass in an array? What can
I do to get rid of this error? Is there a correct way to pass arrays
around inside a template?

Thanks!

 

[Stephen Horne]

Why do I get this error when I attempt to pass in an array? What can
I do to get rid of this error? Is there a correct way to pass arrays
around inside a template?

You haven't really posted enough information here, and what you have
posted is confusing. For example...

template<int a, int b, int SomeArray[]>

template<int MIDPOINT, int Key, int ArrayToSearch[]>

These two template lines are identical, other than the parameter
names. The compiler shouldn't care which you use.

I will take a guess, though.

Basically, an array is a run-time data type. Trying to use arrays for
metaprogramming seems unlikely to work.

Using an array as a template parameter is intended for cases where a
generic algorithm is to be applied to a single application-specific
array, which must be global or static. It's normally a bad idea -
trying to avoid run-time parameter passing can be a recipe for
code-bloat.

The "right" way to do metaprogramming (if there is such a thing) is
using recursive structures such as linked lists. The items in your
lists will be C++ template classes, recursively defined so that each
template class contains a variation of itself as a member (probably a
typedef). Specialisation will be used to terminate the list (ie define
a class that doesn't have a recursive child). The values will often be
member types, member enumerates, or const static member fields.

With that kind of structure, you're far more likely to be using linear
searches than binary searches, though binary trees are certainly
possible. Binary searches may be needed, but over value search-spaces,
not over "data" structures. An example where a binary search makes
sense for metaprogramming is the classic integer square root.

My advice - play with Scheme, Haskell or Objective Caml for a bit,
then (if you must) come back to template metaprogramming when you're
used to handling lists in a recursive functional way. Using a
functional language is much easier as there's far less code overhead
for the relevant concepts, and if you're used to an imperitive
approach, you may need to do a paradigm shift.

BTW - I'm not against metaprogramming. I'm just against
metaprogramming in C++. The current template facilities aren't
designed for it, and aren't really up to doing the job. Template
metaprogramming also imposes a completely different approach for
compile-time code than for run-time code, as you appear to be
discovering. If you can't use run-time code or relatively simple
template methods (policies and mixin layers are OK, to a point), my
view is that you should write a code generator or domain-specific
language. That or work in Objective Caml, which supposedly allows
metaprogramming in the same style as the run-time programming, though
I personally never got past the basic of the language.

 

[James Kanze]

Hello. If I declare the following:

template<int a, int b, int SomeArray[]>
class DoSomething{

public:
.
.
.

I have no problems, and the compiler is quite happy, and my
template function works as expected. But I want to add in an
array for my template to act on. I change the first line to:

template<int MIDPOINT, int Key, int ArrayToSearch[]>

but I get the following error:
error: provided for 'template<int a, int b, int * SomeArray> class
DoSomething'

Why do I get this error when I attempt to pass in an array?
What can I do to get rid of this error? Is there a correct
way to pass arrays around inside a template?

The only allowable types for a template non-type parameter are
integral or enumeration types, pointers to objects or to
functions, references to objects or to functions or pointers to
members. An array is none of these.

An array is an object, however, and you can use either a pointer
to an array or a reference to an array, e.g.:

template<int MIDPOINT, int Key, int (&ArrayToSearch)[]>

Note that you're likely to get into trouble here with the
dimensions, however.

Alternatively, you can use the old C hack, declare the argument
int*, and pass it the address of the first element.

 

[James Kanze]

@yahoo.com"

You haven't really posted enough information here, and what
you have posted is confusing. For example...

template<int a, int b, int SomeArray[]>
template<int MIDPOINT, int Key, int ArrayToSearch[]>

These two template lines are identical, other than the
parameter names. The compiler shouldn't care which you use.

I will take a guess, though.

Basically, an array is a run-time data type. Trying to use
arrays for metaprogramming seems unlikely to work.

The first statement is false (or you meant something different
than what you said). An array is a type known to the compiler,
and it's possible to instantiate templates with references to
arrays, etc. Accessing an array is never a constant expression,
however, even if the array is const, it's initializer is
visible, and the index is a constant integral expression. Which
means that you can't use array elements (even const) as template
arguments. (Since his array type wasn't const, I doubt that he
was trying to do metaprogramming. Even if his choice of names
is very suggestive of a compile time binary search.)

Using an array as a template parameter is intended for cases
where a generic algorithm is to be applied to a single
application-specific array, which must be global or static.
It's normally a bad idea - trying to avoid run-time parameter
passing can be a recipe for code-bloat.

It depends on what you're doing. Things like:

template< typename T, std::size_t N >
T*
end( T (&array)[ N ] )
{
return array + N ;
}

are a standard part of everyone's tool kit. The compiler can
deduce the number of elements in the array as part of template
argument deduction, and where counting is involved, I trust the
compiler more than I do myself.

 

[Stephen Horne]

Stephen Horne wrote:
..

C++ TMP is the greatest thing since sliced bread. In-language
metaprogramming is at least very convenient, and can drastically
increase productivity.

True, but as I said, it still takes a different approach than run-time
code, implying a different skill-set. There are C++ programmers and
C++ TMP programmers, and those sets are very far from being
equivalent.

Also, the error handling is problematic. Get one tiny detail wrong and
you're deciphering bizarre error messages for days.

I have yet to see a stand-alone C++ code
generator that produces anything human-readable, much less maintainable.

I agree, in general. However...

First, when I write my own code generators, I make a point of ensuring
that the generated code is readable. I do this for my own benefit -
otherwise, how can I have any confidence that the generated code is
correct. I don't even see why other code generator writers find this
so hard.

If you'd like to put me to the test on this, I'm quite happy to let
you try (but not disclose) one code generator and its documentation.
It started out as basically a treecc replacement. Only supports C++,
and only runs on Win32 I'm afraid - at least until I get the rest of
my unexpected porting issues covered. Not much in the way of examples
because I'm the only user and I use it for non-trivial apps, but the
docs are OK-ish because I'm pretty forgetful at times.

Some of the generated code is aweful, but in terms of design rather
than readability. For example, I there's and iterator class generator
that generates each class separately - I should be using a data driven
system with thin wrappers around a shared implementation (though
that's naughty because I'll need offsetof with potentially non-POD
classes - sigh - oh well, maybe member pointers might work in this
case), but the current version is really just testing a principle.

A lot of the generated code would also upset idealists, but e.g. the
use of gotos was the most readable way to implement the stepping
through a decision digraph whatever peoples opinions of goto may be.

As for maintainability, that's besides the point - it's like
criticizing a compiler because the object files aren't maintainable.
You're *supposed* to maintain the DSL source files, and the whole
point is to avoid equally unmaintainable manually-written source code.

Are you really going to manually code an LALR state model just because
yaccs output isn't maintainable, even though yaccs input files clearly
are?

The popular compilers may not have been "up to doing the job" ten years
ago, they are now.

I didn't say the compilers - I said the language, as in the *current*
standard. Coping with correct code is one thing - being robust WRT
applications usage of libraries and giving good error messages is
something else.

The extreme differences between compile-time and
run-time syntax you mentioned can be annoying, but (1) the new standard
greatly improves the situation with the decltype, constexpr, and auto
keywords, and (2) syntax that makes it obvious which code runs at
compile-time isn't necessarily evil.

It's not so much the syntax difference as the paradigm difference that
bothers me.

Even so, that's good - and if I understand the 'auto' keyword right,
I'd say that type inference in particular is very welcome.

But have these features been seriously tested by a wide audience as
compiler extensions in the real world? Or are they *genuinely* known
to be the right approach in C++ even without such testing? Or are they
untested creative ideas that people are prematurely committing to,
that may end up being the next standards disaster plot?

 

[Stephen Horne]

The first statement is false (or you meant something different
than what you said). An array is a type known to the compiler,
and it's possible to instantiate templates with references to
arrays, etc.

Very pendantically, I meant something different to what I said...

Accessing an array is never a constant expression,
however, even if the array is const, it's initializer is
visible, and the index is a constant integral expression.

And that is what I didn't know for certain but suspected.

In practice, this means that arrays are not compile-time data types.
They can be referred to at compile time and their types can be
manipulated, but they can't be accessed or updated which is what
arrays are basically for.

Using an array as a template parameter is intended for cases
where a generic algorithm is to be applied to a single
application-specific array, which must be global or static.
It's normally a bad idea - trying to avoid run-time parameter
passing can be a recipe for code-bloat.

It depends on what you're doing. Things like:

template< typename T, std::size_t N >
T*
end( T (&array)[ N ] )
{
return array + N ;
}

are a standard part of everyone's tool kit.

The array isn't a template parameter in this case - it's a method
parameter which is used to infer the template parameters (non-array)
types. Not the same thing, and not what I'd call template
metaprogramming with arrays. It's doing pattern-matching, yes, but
it's doing what templates were designed to do from the start.

The compiler can
deduce the number of elements in the array as part of template
argument deduction, and where counting is involved, I trust the
compiler more than I do myself.

Agreed.

That said, with trivial library tools, I tend to think they obscure
more than they reveal. The names tend not to express *precisely* what
the code does, and you can end up in the perverse situation where the
manually written code is more readable and maintainable, and far less
error prone, than the library call.

Not in the above case, since "end" is so heavily used and it's meaning
relative to containers generally is familiar to any competent C++
programmer.

 

[Stephen Horne]

You're probably mostly on your own when you don't consider
this being TMP.

The point is that templates were designed to do a job which they do
well. Then they were pushed to do more. The term "template
metaprogramming" wasn't even coined until some time after templates
were being routinely used.

Therefore, I'm taking the term "metaprogramming" in a subjective way,
not referring to objective language features, but to the way in which
they are used. Which I think is how most people understand the term.

And I stick by the opinion - until the language is made more robust
WRT metaprogramming, I don't want to see every Tom, Dick and Harry
shoving metaprogramming code everywhere. What's valid as an experiment
or for people who really know what they're doing (and really need to
do it) may still need to be treated with caution.

Would you consider this TMP?

Probably not, but there's no hard line. If "template metaprogramming"
means something other than "template", that meaning must be somewhat
subjective.

*Real* TMP, to me, at the very least uses multiple templates with
interacting specialisation trickery, and I'm only sure it really
qualifies when you start seeing recursive definitions - things like
those compile-time square-root and trig functions are about the
simplest definitely-qualifies stuff I'll accept as metaprogramming.
It's like I don't consider people to have done real imperative
programming just because they can type an expression into Python.

This not only depends on the tool, but also on the alternatives.
Too often for my taste, in code like 'sizeof(arr)', 'arr' turned
out to be a pointer instead of an array. Horrendous compile-time
error messages suddenly seem not all that bad compared to what
happens at run-time.

Agreed. TMP or not, trivial or not, any tool may or may not be a good
thing. It requires a pragmatic - rather than dogmatic - attitude to
figure out which is which.

"The libraries are there therefore use them" doesn't work for me. I
use what I think will work best in the circumstances.

OTOH, it's clear than in some respects my knowledge of what the
library guarantees is dated (or maybe was always wrong), so some of my
decisions based on that will have been wrong. Oh well.

 

[Stephen Horne]

I know TMP was an accidental discovery and I know that that's
the main reason for meta programming being so hard to do. Still,
every bug showing up during compilation won't hit a customers.
And that's a very important argument pro TMP.

Catching bugs at compile-time is a big argument pro static checking,
certainly. It is, however, perfectly possible for TMP code to have
bugs that cause it to generate incorrect run-time code without any
errors or warnings. I've had that happen with (what I thought was)
reasonably simple policy-based code, which I don't even consider to be
metaprogramming.

Any code can have untested cases with stupid typos, out-by-one errors,
or whatever, and if that compile-time error results in a run-time
error in some relatively unusual run-time special case, are you
certain your unit tests caught it? Unit tests that were designed for a
different white box, because one of your template parameters changed,
restructuring that white box in some subtle way?

The real issue is whether you can read, understand, maintain, test,
and generally have confidence in the code. Templates are just
templates. I only add the "metaprogramming" when I'm scared of it, I
guess.

I don't know. I always thought people understand it the way
Scott Meyers described it in "Effective C++". Essentially:
TMP is writing programs that execute inside the compiler
during compilation and result in ordinary C++ programs which
are then regularly compiled.

I read some papers by Todd whatshisname, never read Effective C++. At
least I don't think I did. It's possible I read some in a library once
- could be where I got the word 'policy' from.

If Tom, Dick, and Harry manage to write more reliable software
through using TMP, I'm fine with them doing so.

But if they don't know what they're doing, it's not reliable. And even
if you catch the error at compile time, a month past deadline because
a template parameter changed and caused a thousand cryptic error
messages and no-one could understand or maintain the TMP stuff because
the guy who wrote it left a year ago...

TMP is just compile-time programming. People have been doing it in
Lisp for decades, with a language designed for the job - and they've
certainly managed to release some buggy code in that time.

TMP may be more of a Haskell/Prolog mix rather than Lisp, but the
point stands. It's not magic bug spray.

 

[Stephen Horne]

Stephen Horne wrote:

Veldhuizen? The one who came up with expression templates
and invented blitz++?

Yes - I only read the papers, though, never used the library.

Only the last (3rd) edition of "Effective C++" has a chapter
on TMP. You possibly picked up policy-based programming from
Andrei Alexandrescu's "Modern C++ Design".

Very likely - sounds familiar and after doing a web search I spotted
some familiar ideas - the type list, for instance. Also a quote
stating that when it was released, only two compilers (CodeWarrior
being one) could handle everything described.

Probably something I borrowed for a while, but dismissed as mostly
impractical at the time.

Interesting to note that my IMO-not-a-metaprogramming technique was
described in a book about TMP, though.