Compiling an overloaded function: the selectable type

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;

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;

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;

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.


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

7 replies »

    • That’s good to know, thank you.

      It does appear that the paper is primarily considering runtime overloading, so a form of virtual functions. The selectable type in Leaf is for static typing now, as the static types decides which branch to take. In the future however I do see it extending to the runtime branch selection as well.

    • In fact, I had a bit of trouble finding a precise enough reference (I distinctly remember seeing a discussion of static overloading as intersection types, probably in the context of formalizing the Algol 68 language, but I couldn’t find it back), so this one is a bit inaccurate.

      Note that type classes (more generally qualified types) can be seen as a generalization of this kind of overloading mechanism, that allows to “abstract” over an overloaded call whose meaning cannot be resolved statically (“fun x => x + x” will have type (Num a => a -> a), abstracting over which type provides the “+” operation). When used in this abstracted way they have a runtime cost, but I think that they are a good choice in this design space — with potential issues with specific implementations, eg. there are probably problems of Haskell type classes that can be solved better by starting afresh with a slightly different design.

    • I’d be concerned about doing a runtime type check. I’m not sure if actually needs to be implemented that way, but that seems to be what the implication is. In a typical virtual function setup, like C++, you don’t do any real type checking at runtime. The virtual table is directly included in the class and indicates which actual function to call.

      With Leaf I’m trying to provide a nice orthogonal design for the logical language. I do however intend that things like overloading will be compiled in a variety of different ways: each optimized to a typical pattern of use. There’s no way the most generic approach will be efficient.

    • The intersection type is the term more commonly used here, I think. They are a static concept. Now Ceylon supports them, and Typed Racket as well I believe. They capture the concept that a single value has multiple types, which is what you are doing here. The implementation of such, behind the scenes, is also similar to what you show – some kind of structure with a value of each type and the appropriate value is selected based on the “desired” type of the expression.

  1. Thanks for the post. I just wanted to add some background information about C++ and its future direction.

    There is an attractive proposal by Philipp Juschka for defining function (and function objects) overload sets as polymorphic function objects: N3617. In short, it would be used like this:

    void process( int a );
    void process( float b );
    vector<int> v;
    for_each(v.begin(), v.end(), []process);

    Here, []process denotes a function object with variadic, perfect-forwarded function call operator. Which forwards to the appropriate “real” function. In fact, this can be implemented in C++14 (which provides polymorphic and variadic lambdas), as shown by Tomasz Kaminski in this post. It defines macro LIFT as:

    #define LIFT(id) [](auto&&... args) -> delctype(auto) \
      { return id(std::forward<decltype(args)>(args)...); }

    With this macro you can write:

    vector<int> v;
    for_each(v.begin(), v.end(), LIFT(process));
    • This will definitely be a welcome additon to C++. It also makes me feel more comfortable with my decision to allow this in Leaf: it isn’t a crazy idea but indeed quite desired.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s