Limits of programming by interface

Article misses the obvious solution name the interface for its contract. e.g. SortedMap can have the exact same methods as Map but has an additional bahavoural contract. TreeMap may be a concrete implementation but using the interface is preferable.