Channels ▼

Walter Bright

Dr. Dobb's Bloggers

Function Overloading With Partial Ordering

December 03, 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 <stdio.h>

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++.

D:

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 <stdio.h>

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.

D:

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, D and C++ use partial ordering to resolve template overloading. C# and Java do not have specialization for templates.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video