In the paper, we provide several thoughts, including one example, when type _in_stability actually makes sense. In particular, the example concerns a typical `parse` function, that converts a string into an AST node. Assuming you have one struct per AST type, the parse function is unstable.
Generally, several well-known OOP design patterns would naturally lead to instability. In turn, those patterns can be handy to solve certain typical problems. If you have such a problem at hand, you have a choice: either do a well-known thing and embrace instability (which is actually not always all that harmful for performance), or get out of your way and torture your code to make it stable…
i think you can successfully type the return type using a Union. This might have the performance penalty of instability, but i care more about the soundness issue of potentially returning garbage types than about e.g. vtables
btw rust-miniscript is a nice example of a type stable parser :)
You can use Unions, and in fact that's what Julia do. The issue is performance -- that's what the paper advocates: stable (grounded, more precisely) functions are a clear cut in terms of optimization. Unstable ones is a lottery (sometimes Julia does a decent Job at optimizing them sometimes not).
Rust is an interesting example, maybe I should look into the library. But the compilation model is very different from probably any JIT, including Julia. Optimizations too. For one, unions (enums) in Rust would have much less profound impact on possible optimizations and therefore performance.
I think that Julia lacks a native tagged enum, which is what rust has. Unions are more akin to a local trait T that you box and implement for all the return types, which is strictly worse. If instead explicit unions were optimized to be tagged enums you could get the big performance gains of rust.
Calling code would, of course, have to destructure the return. But destructures of a return value can be very efficient using match (jump tables internally where possible).
There isn't a massive difference between type instability vs programming against interfaces in OOP languages or using a Box<dyn T> in Rust, both add an extra indirection which has a performance impact, but depending on the situation it could be a positive or negative impact.
it has a huge impact on static analysis to know that the type is a Box<dyn T> in rust, and you can't (without something else) downcast Box<dyn T> to a specific U.
i don't care about the performance as much the correctness :)
Generally, several well-known OOP design patterns would naturally lead to instability. In turn, those patterns can be handy to solve certain typical problems. If you have such a problem at hand, you have a choice: either do a well-known thing and embrace instability (which is actually not always all that harmful for performance), or get out of your way and torture your code to make it stable…