One of the problems with this comes if you're able to dynamically promote something that was passed to you as an "immutable" type to its actual implementation type, you can break this "contract".

I'm currently being annoyed by python's type hinting system, which has exactly this sort of hierarchy for containers, but there's nothing stopping a caller/callee from using type-narrowing to "discover" that the underlying type is actually e.g. a (mutable) list, and then modifying it without any complaints from the type checker. The only way to enforce this would be to actually convert to an immutable implementation type, involving unnecessary copying.