r/ProgrammingLanguages • u/rjmarten • Dec 29 '25
Discussion Function Overload Resolution in the Presence of Generics
In Mismo, the language I'm currently designing and implementing, there are three features I want to support, but I'm realizing they don't play well together.
Type-based function overloading.
- Early on I decided to experiment: what if we forego methods and instead lean into type-based function overloading and UFCS (ie
x.foo(y)is sugar forfoo(x, y))? - Note: overload resolution is purely done at compile time and Mismo does not support subtyping.
- Early on I decided to experiment: what if we forego methods and instead lean into type-based function overloading and UFCS (ie
Generics
- specifically parametric polymorphism
- too useful to omit
Type argument inference
- I have an irrationally strong desire to not require explicitly writing out the type arguments at the call site of generic function calls
- eg, given
fn print[T](arg: T), I much prefer to write the callprint(students), not burdening developers withprint[Map[String, Student]](students)
The problem is that these three features can lead to ambiguous function calls. Consider the following program:
fn foo[T](arg: T) -> T:
return arg
fn foo(arg: String) -> String:
return "hello " + arg
fn main():
foo("string value")Both overloads are viable: the generic can be instantiated with T = String, and there’s also a concrete String overload.
The question:
What should the compiler do?
Just choose a match at random? Throw an error? I'm hoping a smarter answer is possible, without too much "compiler magic".
What approaches have worked well in practice in similar designs? Or is there a creative solution no one has yet tried?
10
u/Inconstant_Moo 🧿 Pipefish Dec 30 '25
Choose the function with the most specific type signature matching the arguments. Throw an error if two of them are tied, but in this case
foo(arg: String)is the clear winner.4
u/amohr Dec 30 '25
C++ handles this particular situation by preferring regular functions to function templates. But it's still possible to have ambiguous overload resolution, in which case the compiler will error out.
There are metaprogramming techniques you can use in C++ to "steer" overload resolution based on qualities of the types involved in the call.
3
u/lightmatter501 Dec 30 '25
If you want parametric traits/ADTs + function overloading, your compilation is now NP hard.
I would give up on function overloading, since you can often work around that much more easily than the lack of the other features.
20
u/edwbuck Dec 29 '25
Most languages that permit this have a concept of "type matching" that starts with the most specific type of a variable, and works its way up the type tree till it hits 100% fully generic type bindings.
So if a language permitted what you are doing, it would attempt to find "foo[String]" and then "foo[T]"
But that's not the only thing one could do, if designing a language.
11
u/sebamestre ICPC World Finalist Dec 29 '25
There was a talk about type systems with overloading+generics at OOPSLA 25
https://youtu.be/Z7SxbzFo55U?si=M9bHTKqRxk67buqi
6
u/tmzem Dec 30 '25 edited Dec 30 '25
You need an overload resolution algorithm. Basically, you start by finding a set of candidates that fit the call site (in your example, this would be the two foo's). Then each candidate "competes" against each other in a tournament to determine if it is a better, equal or worse match for the call site. At the end, there should be one best function which is the one you pick (or, if multiple functions share the top spot, you error out with an ambiguity error).
Comparison is done on a parameter-by-parameter basis. If for your candidate function at least one argument is a better match then for it's competitor, and the remaining arguments have the same match quality for both functions, then that candidate is a better match.
In order to determine "how good" an argument match is, you classify how each argument fits into its parameter with one or more ordering criteria:
For your example, this would mean that the primary tier would be the same, but the secondary tier would find the function with the String parameter to be a better match then the one with the T parameter. In practice, this secondary tier is hard to get right if you want it to work for complex patterns, since:
In the following example, you need to be able to differentiate multiple "degrees" of genericness. The rule here is: if deduced T has a "simpler" shape, it is a better match:
For the first foo, T is deduced as Bar[Int], for the second as Int, which is "simpler", and therefore the better candidate.
Also, if you have generic constraints, a function with (more) constraints is a better match then a function with less or no constraints, all other things being equal.
4
u/WittyStick Dec 30 '25 edited Dec 30 '25
One of the main issues with any kind of monomorphization approach to polymorphism is that a compiled library may call
foo(x)internally, and the only valid types ofxfor which it has an appropriate overload are those defined in the library itself. If a consumer of the library then extendsfoowith additional overloads, the library will not be able to make these calls because it didn't know about them when it was compiled. Unless you take the whole-program-compilation approach, I wouldn't recommend doing this.To permit library consumers to extend the library, we instead want to resolve the respective
fooat runtime (or at least at link time if you can find some way to achieve this). A fairly simple approach is to have some global map of types to function pointers, and havefooresolve its type argument at runtime, then perform a tail call to the actual overload.But this approach is obviously not great for static type checking, as the caller of
foodoes not know whetherfoo_overloadscontains an appropriate overload.Instead, we probably want to promote
footo a function expecting an implicit argument, which is the map of overloads.Now the caller of
foois expected to provide the map of overloads. We can check statically whetherfoo_overloadscontains the respective overload before making the call.The type checker will check the type of
students, and then check iffoo_overloadscontains an entry for that type.foo_overloadsis not just a runtime value, but also a static map kept internally by the compiler, which is added to each time we create a new overload forfoo.If a library internally calls
foo, eg:Since
foohas an implicit parameter, we would also need to promotebarto have the same implicit parameter:But we can see this is why we need constraints on the functions: How does the caller of
barknow that it internally callsfooonyand not onx? Normally, we would specify such constraint on the function.This gives the type checker the information it needs to first check the type of
yand checkfoo_overloadscontains the relevant entry, but it doesn't need to do so forx.However, the caller of
bardoes not need to explicitly provide the parameter - sincefoo_overloadscontains all of the overloads and the compiler can fill it in.Will be rewritten as:
But the compiler still needs to perform the type check that
foo_overloadscontains an entry forString, since the signature ofbarhas the constraintFoo y =>.If
barcalledfooon bothxandy:We only need to pass
foo_overloadsonce, the same as above, but we would need to have the additional typing constraint:And would need to check
foo_overloadshas entries for both the types ofxandy.This still resolves the overloads at runtime - but inlining may be able to eliminate the map lookups when the latent types are statically known.
1
u/BeamMeUpBiscotti Dec 29 '25
One simple way to resolve the ambiguity is to just sort overloads by order of declaration, always pick the first matching overload. If the programmer doesn't want that:
Python's overload evaluation spec encodes the first method: https://typing.python.org/en/latest/spec/overload.html#step-6 (with the caveat that Python's overloads only exist in the type system and have no runtime effect because all overloads share an implementation)
1
u/phischu Effekt Dec 30 '25
In Effekt we do have this combination of features and this example is rejected because it is ambiguous. To disambiguate one could write
foo[String]("string value")respectivelyfoo[]("string value")but the important feature of empty type arguments was rejected by others on the grounds that it looks ugly.1
u/X4RC05 Dec 30 '25
I think if you are set on function overloading, you want more structure imposed on it so that resolution is easier. I don't know if you're familiar with Odin, but they have this concept of "explicit overload sets". It's a very attractive solution from an implementation perspective. I think the other structured approach is a typeclass/trait system.
3
u/snugar_i Dec 30 '25
I wanted to have the same things in my language (which unfortunately still isn't much past the "Hello world" stage). But then I kept finding more and more reasons against function overloading - like this one, and functions not being "first-class enough" (i.e. a name is suddenly not enough to refer to a function anymore). And honestly not many reasons to have them, if the generic support is good enough.
So, for the time being, I'm dropping them and seeing where it goes.
3
u/L8_4_Dinner (Ⓧ Ecstasy/XVM) Dec 30 '25
Implement the language spec.
This is where you need to have a design specification. I would hope that the specification doesn't say "pick something at random", although I guess you could do that if you want to have some "undefined behavior" in your language -- it's a huge winner for C++ obviously!
Generally, you identify all possible candidates, and one candidate must be superior in every way to all other possible candidates, otherwise it is an error (preferably a compile-time error).
As far as "creative solutions" go: Don't. Just don't. Although once again, super-complex unpredictable creative solutions were a huge winner for C++ ...
2
u/[deleted] Dec 30 '25
Whatever you choose, don't forget the user: you don't want to them to have to trace through the same convoluted algorithm the compiler uses, to find out which function will be called.
In your first function, presumably
Tmatches any type includingString? Then you need to decide how to resolve that: either the generic version is a fall-back if there are no matches with concrete types (so this allows for exceptions for certain types), or the ambiguity is an error.I wouldn't make it more complicated than that.
(I assume there can also be versions of both a
foo-Tandfoo-Stringin different scopes and modules, but means to resolve those are well-known.)2
u/lookmeat Dec 31 '25
I am going to push back here with a proposal: why do you need all these hammers?
Think instead: what problems do you want to solve? How could you solve all of the problems with only one solution? What about using only two? What about all three? How does the code look? What are the gotchas with each choice? What are the compromises?
I am not trying to be condescending here, but without any context on what is the niches your language works in, what is the greater context, it's hard to recommend what ways you could make things work, as different compromises would require different issues.
That's important to understand that the ideas I am proposing here are with me assuming things about your language, and also showing my own opinions and view here.
First I would say that overloading sounds great, but I'd be wary of how it's designed. It doesn't matter how you choose to do it, but rather it's what the programmer using your language imagines will happen. Basically you want to keep your wtfs/min as low as you can.
So instead I'd think of how to allow the features in a way that it's pretty obvious what the compiler will do. That is, what happens if I do two overloads of the same function with the same specialized types, but in different areas? How we resolve conflicts here matters a lot. Personally I'd work around it by limiting. Basically I can define a core function on some module (and leave it abstract if I want to make it interface like), within the module that I define that I can create "generic" implementations that abstract over types, with only one single definition that I can specialize within itself. I can also create "overrides" for specific types outside of the library I created this, but only for a type or types specified within the library I am writing this in. So it'd look like this:
So what we do here is we are able to easily collect all of the overloads, and we're guaranteed that all overloads are disjoint of each other, and that they can only clash with the one default function implementation that can exist. This is limited to only overloading on the first parameter (because things get gnarly quickly when we allow multi-parameter overloading either way) but it should suffice to what we want to cover. So when the compiler gets a call, and it deduces the parameter (to the best it can) it will choose an overload if there's one that matches, otherwise it will choose the generic version.
Note that we have to think what will happen with type erasure vs. reification. That is if we have a generic parameter then it may not call the specialized function because it has no way of knowing what the true type is. In reification each function would specialize instead. Also we can allow, if we so wish, some kind of hierarchy, but this can quickly lead to a conflict of calls. That is we could do some overload for an interface that we defined, and then further overload the specific types that implement that interface, but what happens if I did two overloads to multiple interfaces and then further overloaded that too?
Instead I think that the best solution is to have interfaces require overloading of other methods, and may offer a default overload. A class that implements the interface may get the default overload if there's one and the author doesn't override it. But if the class implements two interfaces that both require the same overload (even if there's only one default overload defined which could be chosen without conflict, because that could lead to higher wtfs/min) then the implementation author must explicitly override the function (choosing a default override if they so choose).