Terminology in english :)

[James Kanze]

My statement may have made more sense if I used the correct function
name - toupper! Somehow I made this mistake.

A yes. So there's both a function template and overloading for
the compiler to contend with.

And by arranging it to be a non-template class type, we delay
overload resolution until the function is called?

Overload resolution always occurs at the call site. The problem
here isn't overload resolution---it's template type deduction.
If the fourth argument is an overload set which contains a
function template, the compiler cannot do type deduction---it
needs to know the target type to do type deduction on the
function template, and it needs the exact type of the function
in order to do type deduction for std::transform. There's a
cyclic dependency. If the fourth argument is an overloaded
function, even without a template, the compiler still needs to
know the target type to do overload resolution, and it needs the
results of the overload resolution to do argument deduction for
std::transform (and thus determine the target type).

When we pass a functional object, we specify an exact type---the
type of the object. This breaks the cycle in the dependencies:
the type of the argument is fixed; the compiler does not have to
deduce or resolve it. This is true regardless of whether the
functional argument is a template or not---it is an object, it
has a fixed type, and there is no possible overloading or
automatic type deduction. There is no automatic type deduction
for class templates or objects. Only for functions. Thus, for
example, if I create a ToUpper template class:

template< typename charT >
class ToUpper
{
public:
explicit ToUpper( std::locale const& l = std::locale() )
: myLocale( l )

( l ) )

{
}

charT operator()( charT ch ) const
{
return myCtype->toupper( ch ) ;
}
private:
std::locale myLocale ;
std::ctype< charT > const*
myCtype ;
} ;

I would have to explicitly specify the type in order to use it:

std::transform( s.begin(), s.end(), s.begin(),
ToUpper< char >() ) ;

And having explicitly specified the type, the compiler no longer
has any argument deduction or overload resolution to do, and the
cycle is broken.

 

[Taras_96]

I think I understand what you're saying now, but I still don't
understand how the dependance is cyclical. I've tried to recreate a
similar situatino in some artificial code below.

callThisFunction is loosely equivalent to transform
X parameter is supposed to be equivalent to toupper (a function
pointer)
I assume that toupper receives the characters to transfrom from the
iterators. This is the purpose of the Y parameter - it is going to be
input into the X function

TEST CODE:

#include <iostream>
using namespace std;

template <class X, class Y> void callThisFunc(X x, Y y)
{
x(y);
}

template <class X> void templatedUselessFunction(X x)
{
cout << "templated useless function: " << x << endl;
}

void overloadedFunction(char c)
{
cout << "in char function: " << c << endl;
}

void overloadedFunction(int x)
{
cout << "in int function: " << x << endl;
}

----------END CODE----------

Let's consider the overloaded functions first

As you mentioned,

If the fourth argument is an overloaded
function, even without a template, the compiler still needs to
know the target type to do overload resolution, and it needs the
results of the overload resolution to do argument deduction for
std::transform (and thus determine the target type).

callThisFunc(overloadedFunction,51234);

The type X can not be deduced for callThisFunc because the function is
overloaded. Even though obviously at the point where the fucntion is
called, the version of the function to call is unambiguous, at the
point callThisFunc is called the type X is unknown, and thus automatic
template type deduction can't be done (even though the version of the
function to call is not indeterminate - we intend to call the int
version). We can disambiguate the type of the argument by using a
cast-like syntax (even though, as explained earlier, it isn't a case).

callThisFunc((void(*)(int))overloadedFunction,51234);

This however forces us to explicitly specify the function, and thus we
lose the advantage of having overloaded functions in the first place.
Alternatively we could wrap overloadedFunction into a functor, and use
this instead.

Now, onto the templated function

callThisFunc(templatedUselessFunction,3);

This won't work because at the point the function is called, the type
of X can not be determined (similar to the overloaded function case),
even though again the call is ultimately unambiguous (if the compiler
could look ahead into how the templated function is used.....). Again,
similar to the overloaded function case, we can explicitly specify the
type of the argument:

callThisFunc(templatedUselessFunction<int>,3);

I don't understand, however, how this is a cylical dependancy -
callThisFunc requires to know the type of X, the type of X is not
known because it is a templated function - the type of the templated
function does not depend on callThisFunc (well, to me anyway).

In the case of 'toupper', to upper is both a templated function and an
overloaded function, so it's a bit of both situations.

 

[James Kanze]

I think I understand what you're saying now, but I still don't
understand how the dependance is cyclical.

The compiler needs to know the type of the function argument of
std::transform in order to do type deduction on std::tolower
(and thus determine its type), and it need to know the type of
std::tolower in order to do type deduction for the function
argument of std::transform. You can break the cycle by
specifying one or the other:

std::transform< std::string::iterator,
std::string::iterator,
int (*)( int ) >
( s.begin(), s.end(), s.end(), std::tolower ) ;
or
std::transform(
( s.begin(), s.end(), s.end(),
static_cast< int(*)( int ) >( std::tolower ) ) ;

(The first would be a lot easier to use if the type of the
function were the first template argument of std::transform, and
not the last.)

(And obviously, these are just examples to clarify the
situation. The actual call of std::toupper in the above would
result in undefined behavior unless you've previously ensured
that all elements in the string have non-negative values.)

I've tried to recreate a similar situatino in some artificial
code below.

callThisFunction is loosely equivalent to transform X
parameter is supposed to be equivalent to toupper (a function
pointer)

I assume that toupper receives the characters to transfrom
from the iterators. This is the purpose of the Y parameter -
it is going to be input into the X function

TEST CODE:

#include <iostream>
using namespace std;

template <class X, class Y> void callThisFunc(X x, Y y)
{
x(y);
}

template <class X> void templatedUselessFunction(X x)
{
cout << "templated useless function: " << x << endl;
}

void overloadedFunction(char c)
{
cout << "in char function: " << c << endl;
}

void overloadedFunction(int x)
{
cout << "in int function: " << x << endl;
}

----------END CODE----------

Let's consider the overloaded functions first

As you mentioned,


The type X can not be deduced for callThisFunc because the
function is overloaded. Even though obviously at the point
where the fucntion is called, the version of the function to
call is unambiguous, at the point callThisFunc is called the
type X is unknown, and thus automatic template type deduction
can't be done (even though the version of the function to call
is not indeterminate - we intend to call the int version). We
can disambiguate the type of the argument by using a cast-like
syntax (even though, as explained earlier, it isn't a case).

This however forces us to explicitly specify the function, and
thus we lose the advantage of having overloaded functions in
the first place. Alternatively we could wrap
overloadedFunction into a functor, and use this instead.

Now, onto the templated function

This won't work because at the point the function is called,
the type of X can not be determined (similar to the overloaded
function case), even though again the call is ultimately
unambiguous (if the compiler could look ahead into how the
templated function is used.....). Again, similar to the
overloaded function case, we can explicitly specify the type
of the argument:

Correct. Strictly speaking, the error doesn't occur during
overload resolution per se, but because type deduction fails.
Type deduction can fail in two ways: if no function can be
deduced, then no instantiation of the template function is added
to the overload set, and the compiler continues, considering the
other possible overloads. If the deduction is ambiguous,
however, as it is here, and can give more than one result, it is
an error.

For the user, of course, it comes out to pretty much the same
thing. You can sort of think of a function template as an
infinite set of overloads. (It's not quite the same thing,
because the compiler considers a much smaller set of possible
implicit conversions when doing template argument deduction than
it does when doing function overload resolution.)

callThisFunc(templatedUselessFunction<int>,3);

I don't understand, however, how this is a cylical dependancy

This isn't. In fact, this should work, since there is only one
possible 'templatedUselessFunction<int>. Drop the <int>,
however, and the compiler needs to know the results of argument
deduction on callThisFunc, in order to deduce the type of
templatedUselessFunction, and it needs to know the type of
templatedUselessFunction, in order to do argument deduction on
callThisFunc. Specify the template argument of
templatedUselessFunction (or which function to choose from an
overload set), and you break the dependency. Specifying the
type of the first parameter of callThisFunc also words, e.g.:

- callThisFunc requires to know the type of X, the type of X
is not known because it is a templated function - the type of
the templated function does not depend on callThisFunc (well,
to me anyway).

In the case of 'toupper', to upper is both a templated
function and an overloaded function, so it's a bit of both
situations.

Yes, but it fails because the template argument deduction is
ambiguous. (If somehow the template argument deduction could be
made to work, without forcing the use of the template function,
it would fail because of the overloaded function.)

 

[Taras_96]

So is the following correct?

template <class X>
void foo(X x);

foo needs to know the type of x so that it can deduce the type of X.
eg, if we call foo('a'), then the compiler knows that X refers to
'char'.

void aFunc(int (*) (int))
template <class X> bFunc(X x);
aFunc(bFunc);

this is fine because type type of X can be deduced from the aFunc
declaration

However, if we combine the two (generic function with a generic
function as a templated parameter)

foo(bFunc) //<- problems

we get problems

Is this correct?

 

[James Kanze]

So is the following correct?

template <class X>
void foo(X x);

foo needs to know the type of x so that it can deduce the type of X.
eg, if we call foo('a'), then the compiler knows that X refers to
'char'.

void aFunc(int (*) (int))
template <class X> bFunc(X x);
aFunc(bFunc);

this is fine because type type of X can be deduced from the aFunc
declaration

However, if we combine the two (generic function with a generic
function as a templated parameter)

foo(bFunc) //<- problems

we get problems

Is this correct?

Exactly. The compiler needs a known point to start from.

 

[Taras_96]

Exactly. The compiler needs a known point to start from.

Thanks a lot James, you should be on experts exchange or something!