You're right that in general an AOT compiler cannot solve this problem. Swift does specialize generic functions within a module. Across module boundaries, you can declare a function with the `@inlinable` attribute, which makes its body available as part of the module's binary interface. Of course this hinders future evolution of the function -- you can swap in a more efficient implementation of an algorithm for instance, but you have to contend with existing binaries that compiled an older version of the function.
The standard library makes extensive use of `@inlinable` for algorithms on generic collection protocols and so on.
Basically, because Swift has to support separate compilation of shared libraries.
The @inlinable attribute is in fact implemented by serializing the high-level IR of a function as part of the module's interface; but doing this for all functions would be a non-starter, because it would place unacceptable restrictions on binary framework evolution.
You can think of @inlinable as being somewhat similar to defining a function in a C header file. Unlike C++ templates, Swift generics don't require all definitions to be available at compile time, because dictionary passing is used to compile generic code when monomorphization cannot be performed.
The standard library makes extensive use of `@inlinable` for algorithms on generic collection protocols and so on.