Re: Multivariate Partial Specialization Broken?

[John McCorquodale <mcq at eroica dot cs dot utah dot edu>]

NOTE: This is long-winded.  There's a better description of the bug down
      below.  Search for "EGCS BUG" if you want to skip my discussion of
      template specialization.

Wolfgang> In my eyes, your example should be perfectly valid, though it
Wolfgang> indeed is suspicious that Stroustrup doesn't cover it but does
Wolfgang> so for much more elaborate examples.

Yeah; I find that Stroustrup tends to underemphasize template value
parameters as a rule.  His primary concern seems to be (understandably)
typing and type-based implementation specialization.  I *really* care about
value-based specialization at the moment, however.

Wolfgang> I'd call what you do an explicit specialization, since Stroustrup
Wolfgang> defines (declares?) that to be (in others words): a specialization
Wolfgang> ...

Here's how I understand the words.  Syntactically, a specialization is
recognizable by the presence of second set of <>'s in a template declaration:

  template<...> declaration<...> ...
                           ^^^^^ if this is here, it's a specialization

Conceptually, think of specialization as a definition that applies to a subset
of the template's parameter-space.  Here's a template class:

  template<class C> class A { ... };

Here, the parameter-space of the template is "all types".  One can provide a
specialized version of A for a particular type:

  template<> class A<int> { ... };

This specialized A will get used any time an A<int> is called for, in lieu of
the other, more genreal declaration.  One can think of this specialized
version of A as being declared "appropiate" to a subset of the parameter-space,
in this case a single point in the parameter-space, the "int" type.  When the
specialization applies to a point in the parameter-space, it's "explicit
specialization" or just "specialization".

One can declare a specialization that applies to a non-singular subset of
parameter-space in the following way:

  template<class P> class A<P*> { P p; ... };
      "X"=^^^^^^^^^        ^^^^="Y"

Here, in "X", we introduce a template variable, P.  In "Y", we define a
pattern (in the Standard ML sense of the word) containing this variable.
This pattern matches the (infinite) subset of parameter-space containing all
pointer types (eg: int*, int**, char***, etc.)  When this template is
instantiated on a pointer class, the pattern in "Y" is unified with the
particular instantiation argument and the variables in "X" become known.  For
example, if we instantiate A thus:

  A<char**> a;

The unificiation algorithm will try to match "P*" against "char**", which
is accomplished when P (a type parameter) is "char*".  Thus, since the
unification was successful, this specialization applies to this use, and is
instantiated.  When it is, the "p" variable in the body is of whatever type
"P" was found to be, in this case "char*" (not! char**).

Specializations that involve unification in this manner (ie: any specialization
for which "X" is not "<>") are what Stroustrup calls "partial specializations".
They're "partial" in the sense that they define a specialization on a subset
of parameter-space, rather than an "explicit" point in parameter-space.

If the pieces of parameter space two specializations apply to are disjoint,
there is no ambiguity; each is used when it is appropriate.

If the piece of parameter space one specialization applies to is a subset
of the piece that another specialization applies to, the first is said to
be "more specialized" than the second, and is used in lieu of the second
whenever it applies.

However, if the intersection set of the pieces of parameter-space appropriate
to two partial specializations is nonempty and not equal to one of the
pieces, no "more specialized" relationship exists, and the are specializations
are "ambiguous" in the overlap region.  A compiler should produce an error
when ambiguous partial specializations exist.

I find it much easier to think about the "more specialized" relationship in
terms of subsets of parameter space and set operations, than in terms of
the kind of "fuzzy English quantification" Stroustrup uses in 13.5.1.

MULTIVARIATE SPECIALIZATION

All those "parameter-space" arguments apply to templates with more than one
parameter; you're just living in a higher-dimensional parameter-space.

Explicit specialization still picks out a point in parameter-space, in this
case the point (int,double) in the space (any type * any type):

  template<class A,class B> class C { ... };    // Base def'n
  template<> class C<int,double> { ... };       // Explicit specialization

One should certainly be able to do partial specialization on both arguments:

  template<class A,class B> class C<A*,B**> { ... };

or:

  template<class A,class B> class C<A*,B> { ... };

This second example is *still* partial specialization in both A and B, it's
just that the unification of "B" is trivial.

You can do partial specialization in one parameter and explicit in another:

  template<class B> class C<int,B*> { ... };

or:

  template<class B> class C<int,B> { ... };

In this second example, I've essentially specialized for C<int,_anything_>,
and made the _anything_ avaiable as "B" in the body.

VALUE-PARAMETER SPECIALIZATION

You can apply all that subset-of-parameter-space stuff to value parameters
as well, it's just that now instead of parameter-space being types, it's
values of a particular primitive type.  For example:

  template<int N> class C { ... };       // Base def'n
  template<> class C<0> { ... };         // Explicit specialization
  template<int N> class C<N+1> { ... };  // "Algebraic unification" -- not
                                         // implemented in egcs yet.  No
                                         // surprise here.

Things get more interesting in the multivariate case:

  template<int A,int B> class C { ... }; // Base def'n
  template<> class C<0,0> { ... };       // Explicit specialization
  template<int A> class C<A,1> { ... };  // Partial specialization in A;
                                         //   explicit specialization in "B"

Non-linear unification is also supported in egcs.  This is amazingly cool,
and makes my life good:

  template<int A> class C<A,A> { ... };  // Partial specialization -- matches
                                         //   all C<1,1>, C<2,2>, etc.

So far, all this works fine in egcs-1.0.2.  It's beautiful.  Whoever wrote 
all this code in egcs deserves a free beer.  Come to Salt Lake City, and I'll
buy ya one or six.  ;-)

*** EGCS BUG ***

When egcs starts to have problems is when you're trying to do the above sorts 
of things with template functions, not template classes.  In particular, I
care about value parameters, so I'll do my examples with those:

This stuff works:

  template<int N> void f(void) { }       // Base def'n
  template<> void f<0>(void) { }         // Explicit specialization

  template<int A,int B> void g(void) { } // Base def'n
  template<> void g<0,0>(void) { }       // Explicit specialization

THIS STUFF DOESN'T WORK:

  template<int A> void g<A,0>(void) { }  // Partial specialization in A,
                                         //   explicit specialization in B
  ERROR: "Internal compiler error."

  template<int A> void g<A,A>(void) { }  // Partial specialization; subset of
                                         //   param space <n,n>
  ERROR: "Internal compiler error."

Further, I noticed while playing that if you give a type for a value
parameter:

  template<> void g<int,0>(void) { }    // Bogus, "int" is a type, value
                                        //   param expected
  ERROR: "Internal compiler error 243."

*** END OF EGCS BUG ***

Hope that sheds more light on things.  Is there an official "bug tracking"
system in place?  I don't really want to fix this myself (I doubt I can), but
will try if it's going to be the old-fashioned gcc "3 years" before it starts
working in the snapshot.

Thanks, guys,

-mcq