I think it's only really doable in purely functional language (like Haskell), though. It sort of means versioning of individual functions, and also types. It's very similar to rebinding values only as opposed to modification of variables.
But naming is a problem. Maybe.. There are two kinds of names of types and functions - intrinsic and extrinsic. Intrinsic name only describes what the thing is (e.g. array.search()). Extrinsic name relates to the problem being solved (e.g. product.findByPrice()). Maybe the functions (and types) that have only extrinsic names should be versioned and short name should be assigned to the latest version.
All in all, I think it's a concept worth researching.