Function Overloading With Partial Ordering

written by Walter Bright

December 3, 2008

Modern statically typed programming languages like Java, C#, C++ and the D programming language can overload functions based on the number and types of the function’s parameters. The function selected is the one with the best match of the supplied arguments to the function’s parameters. How is the best match determined?

(Note: a function argument is the expression used to set the value of the corresponding function parameter.)

C# and C++ use a method I’ll dub “best conversion”. The idea is to select the function which has the simplest conversions for the arguments to the parameters. It starts by first producing a list of candidate functions that can be called by the arguments. For example,

void foo(int);
void foo(int, long);
void foo(int, double);

If the call is foo(1,2) then the candidate functions are foo(int, long) and foo(int, double). foo(int) is not a candidate because it only accepts one argument.

Next, the arguments are compared, one by one, with the corresponding parameters and a note is made about how close a match it is. A simple integral conversion, for example, is considered a closer match than than a user defined conversion. C# and especially C++ have a complex and detailed specification of what conversions would constitute a closer match than another. C++’s is defined in the C++ 98 standard paragraph 13.3.3.

The quality of the match as a whole is done by combining the results of each of the argument to parameter matches. If there’s one function that matches better than any of the others, it is selected. An ambiguity error results if there’s more than one best match.

In our foo(1,2) example, 1 is an exact match for int, and 2 (an int) can be implicitly converted to a long, which is better than converting 2 to double. Thus, foo(int, long) is selected as the best match.

While these rules, especially for C++, tend to be complex they usually produce what one would intuitively expect to be the best match, and so rarely cause any problems.

Java and D use a method called “partial ordering” to find the best match. The idea of partial ordering is to select the most specialized function, not the function with the simplest argument conversions. The most specialized function is presumably the one that can handle the task the most efficiently. It is analogous to the idea that a derived class is more specialized than its base class, and so the derived class’ methods override the equivalent base class ones.

Partial ordering works as follows. Just like for best conversion, first a list of candidate functions is produced. The “most specialized” function in that list is selected based on the following process. Suppose there are two functions in the candidate list, f1() and f2(). If the parameters to f1() can successfully be used as arguments to f2(), but not vice-versa, then f1() is considered to be “more specialized” than f2(). This process is repeated for each possible pairing of functions in the candidate list. If one emerges as more specialized than any of the others, it is selected, otherwise there is an ambiguity error.

In our example, foo(int, long) is compared with foo(int, double). foo(int, double) can be called with arguments (int, long). But foo(int, long) cannot be called with arguments (int, double), because a double does not implicitly convert to long (using the D programming language implicit conversion rules). Thus, foo(int, long) is more specialized and is preferred.

For this case, the same result is produced with best conversion as is produced with partial ordering.

Here’s an example where different results are produced:

C++:

#include 

class A { };
class B : A { };
class C : B { };

void f(long,A&)  { printf("f(A)\n"); }
void f(int, B&)  { printf("f(B)\n"); }

void main()
{   C c;
    f(1L, c);
}

Both functions f are candidates. The first parameter, 1L, is a better match to long than to int. But the second parameter, is a better match to B& than to A&. Hence, this is an ambiguity error in C++.

import std.c.stdio;

class A { }
class B : A { }
class C : B { }

void f(long,A)  { printf("f(A)\n"); }
void f(int, B)  { printf("f(B)\n"); }

void main()
{   C c;
    f(1L, c);
}

Both functions f are candidates. While f(long, A) can be called with arguments (int, B), the function f(int, B) cannot be called with arguments (long, A) as an A cannot be implicitly converted to a B. Hence, f(int, B) is the most specialized, and is selected. (Note that class types are reference types in D.)

And here’s the other case where C++ picks one and D gives an ambiguity error:

C++:

#include 

void f(double)       { printf("f(double)\n"); }
void f(long double)  { printf("f(long double)\n"); }

void main()
{
    f(1.0f);
}

The conversion of float to double is considered to be better than a conversion of float to long double, so f(double) is selected.

import std.c.stdio;

void f(double)  { printf("f(double)\n"); }
void f(real)    { printf("f(real)\n"); }

void main()
{
    f(1.0f);
}

Since doubles can be implicitly converted to reals and vice versa, neither is more specialized than the other and an ambiguity error results.

(Note that D reals are the same as C++ long doubles.)

So which scheme, best conversion, or partial ordering, is better? They both work and tend to produce what the programmer would intuitively expect, although I contrived a couple cases where they produced different results. Under either method it’s fairly easy to adjust parameter types to eliminate ambiguity problems.

The best conversion method can get pretty hairy to implement, and requires many rather arbitrary and arcane decisions about what constitutes a “better” conversion than another. It further has the disadvantage of leaving user defined types as second class, as their conversions are always considered worse by the language.

It’s easy to remember how partial ordering works, and the implementation is straightforward. Adding new types and implicit converisions fits right in. User defined types have equal rank with builtin types.

Interestingly, C++ uses partial ordering to resolve template overloading.

Articles

Function Overloading With Partial Ordering