Tags

, , , ,

How is an overloaded function compiled? It’s not something I truly considered prior to writing Leaf. My first implementation mimicked C++, at least how they appear to behave in C++. It worked, but only partially, and didn’t fully expose the features I wanted. The problem must be considered differently. Surprisingly, I found the solution by answering a rather simple question: what is the type of an overloaded symbol? For Leaf this is the “selectable tuple”.

The Standard Approach

My first approach was handling overloads the way we think about them. What happens when we encounter an overloaded symbol?

void process( int a );
void process( float b );
...
int a = 5;
process( a );

Encountering ‘process(a)’, the compiler must choose which function to call. It iterates over all ‘process’ functions and tests which ones have matching parameters. Thinking this way avoids referring to ‘process’ in isolation. The code is calling a specific ‘process’ function. Each potential function has a definite type, but the name ‘process’ on its own has no meaning.

Now consider the parsing and syntax tree. This interpretation of an overloaded function requires that ‘process’ remains as a name label rather than a generic symbol. The call operator needs the actual name to do the resolution. Compare to the next example using a function pointer. Here the call operator works on the value of the variable, not caring what name it has.

void single( int a );

auto fptr = single;
fptr(5);

This contrast between using the value and using the name is quite important. Consider that ‘fptr’ could have been any name we wanted. We can even assign this value to another name and call the function through that instead. With ‘process’ however, such an assignment is not possible because the name must be retained. This is very restrictive for the programmer and complicated for the compiler.

Something interesting

C++ allows taking the address of an overloaded function so long as which definition can be determined.

void (*fptr)(int) = process;
fptr(5);

By default you cannot use ‘process’ without parameters in C++; the standard instead lists a series of exceptions. The list is however complete enough to create the illusion of normal syntax. The previous may look like a normal assignment, but it actually follows a special rule about assigning overloaded functions. The illusion can be broken quite easily using the ‘auto’ keyword.

auto fptr = process;
fptr(5);

This fails because C++ doesn’t define what ‘process’ means on its own. It isn’t a normal symbol, nor does it have a proper type. This results in the complex specification and the limitation of how it is used. It’s unfortunate, but in fairness it is unlikely a generic alternative would have been accepted at the time it was written.

Overloaded as a type

It would be somewhat silly for a compiler to actually implement the rules exactly as specified. And after examining the error messages of GCC and Clang I suspect it isn’t implemented that way. In various scenarios one can get GCC to emit a type error including “”. The way the message is formatted indicates GCC actually resolved the ‘process’ symbol into an internal type. It doesn’t retain the name for overloading purposes.

Despite the standard disallowing it, ‘process’ has been given semantic meaning without parameters. Only at the point the value is used, or assigned, is the matching done. The rules of the standard are ultimately attained, but in a more natural, less exception-ridden, manner. (My apologies if it is not actually implemented as I believe.)

A selectable type

To be orthogonal we need to give ‘process’ a type on its own. Prior to resolving to a single function, the symbol must have meaning — it must have a value and a type. We know two things about this value, it must be usable as a function, and it must be able to locate all the potential matches. Leaf accomplished this by using a special tuple type called a ‘selectable’.

Explaining the ‘selectable’ is perhaps easier with non-overloaded functions. Below, a ‘selectable’ tuple, comprising two functions, is constructed.

var proc_integer = (a:integer)->() { ... }
var proc_float = (b:float)->() { ... }

var sel : selectable = [ proc_integer, proc_float ]
sel(8) //calls proc_integer
sel(1.5) //calls proc_float

This essentially creates an overloaded function called ‘sel’. The value assigned to ‘sel’ is just a normal tuple which contains two functions. An added specifier ‘selectable’ gives it the overload behaviour. Later, when Leaf encounters the ‘selectable’ type it compares each item in the tuple looking for the best match. The selectable value then resolves to a single function.

Note that Leaf does implied, or inferred typing. Though ‘sel’ is marked solely with ‘selectable’ it has a complete and concrete type inferred from the assignment. The full type of ‘sel’ is ‘selectable [ (:integer)->(), (:float)->() ]’. The tuple is merely a collection of a signatures of the functions.

Viewed from this angle it is hopefully clearer how the ‘process’ symbol would resolve. It becomes a selectable tuple which contains both of our ‘process’ functions. The type of ‘process’ is the exact same type as ‘sel’. After this point there are no special rules dictating how the overload works: the ‘selectable’ rules are generic. This results in a lot of flexibility and simplifies the language rules.

Non-functions

The generic selectable ends up allowing types other than functions. The same basic rules apply and the best item is chosen for conversion. I unfortunately can’t think of a strong use-case for this yet; I’m thinking it may be useful once sub-typing and templates are introduced. Certainly the below is an example of bad code. if you have a good idea on how to use this feature then please let me know.

var a : integer = 10
var b : float = 5.5

var alt : selectable = [ a, b ]

var c : integer = alt //gets assigned 10
var d : float = alt //gets assigned 5.5