Type substitution (or Liskov Substitution Principle in object-oriented contexts) allows an object of a certain type (supertype, superclass) to be replaced with an object of another type (subtype, subclass).

Let’s clarify the difference between subclass and subtype (and their super- counterparts) first. They are closely related, but stem from different concepts: inheritance and type compatibility.

Subtype vs. Subclass

Subclass is a class that inherits from another class, known as its superclass. A subclass inherits methods and properties (behavior and state) from the superclass and can add new methods and properties or override existing ones.

Subtype is a broader concept that refers to a type that satisfies the contract or interface of another type, known as its supertype. A subtype guarantees that it can be used in any context where its supertype is expected, adhering to the Liskov Substitution Principle (LSP). This relationship is not limited to classes and inheritance but also applies to interfaces, traits, and other type constructs.

Supertype vs. Superclass

Superclass is the class from which a subclass inherits. It’s a specific entity in class-based OOP that provides a blueprint for creating subclasses.

Supertype is a type that is generalized or abstracted from its subtypes. A supertype defines a contract (set of operations, methods, properties) that all its subtypes must satisfy. The subtype-supertype relationship can be determined by inheritance in OOP, but it can also arise from other type relationships, such as implementing an interface (Java) or conforming to a protocol (Clojure).

Type substitution

The key aspect of this concept is that the substituting object (the subtype instance) must be able to perform all the duties that the original object (the supertype instance) could perform, without requiring any changes to the external code that uses the object.

In order to achieve this level of compatibility, the following rules must apply:

  • The subtype must implement all the methods and properties that the supertype defines.

  • The subtype must not alter the expected behavior of the supertype in a way that could break the client code: preconditions, postconditions, and invariants must remain the same. For example, a subtype must not throw exceptions not expected from the supertype methods.

Java example

Java supports classical inheritance, making it straightforward to demonstrate subtyping.

abstract class Animal {
    abstract void makeSound() throws AnimalSoundException;
}

class AnimalSoundException extends Exception {
    public AnimalSoundException(String message) {
        super(message);
    }
}

class Dog extends Animal {
    @Override
    void makeSound() throws AnimalSoundException {
        System.out.println("Woof!");
    }
}

class Cat extends Animal {
    @Override
    void makeSound() throws AnimalSoundException {
        System.out.println("Meow!");
    }
}

class Rhino extends Animal {
    @Override
    void makeSound() throws AnimalSoundException {
        throw RuntimeException("Rhinos are silent and deadly!");
    }
}

public class Main {
    public static void main(String[] args) {
        Animal[] animals = new Animal[]{new Dog(), new Cat()};
        for (Animal animal : animals) {
            try {
                animal.makeSound();
            } catch (AnimalSoundException e) {
                System.err.println("Error occurred: " + e.getMessage());
            }
        }
    }
}

Here, Dog, Cat, and Rhino have the same method makeSound as their supertype. However, only Dog and Cat adhere to LSP. Rhino violates the behavior of its supertype by throwing a RuntimeException and breaks the logic used by the client code which process instances of Animal-compatible types.

Python example

We could have used inheritance for Python as well but let’s demonstrate subtyping via different means: duck typing.

class AnimalSoundException(Exception):
    pass

class Dog:
    def make_sound(self):
        print("Woof!")

class Cat:
    def make_sound(self):
        print("Meow!")

class Rhino:
    def make_sound(self):
        raise RuntimeError("Rhinos are silent!")

def let_it_speak(animal):
    try:
        animal.make_sound()
    except AnimalSoundException as e:
        print(f"Error occurred: {str(e)}")

animals = [Dog(), Cat(), Rhino()]
for animal in animals:
    let_it_speak(animal)

Rhino violates the supertype’s behavior even though it commits to the same interface.

Variance

Variance is a type system concept that describes how the subtyping relationship between more complex types relates to the subtyping relationship between their component types. It’s mostly relevant in the context of generic types. Variance determines whether a generic type with a certain component type (like List<String>) can be considered a subtype or supertype of the same generic type with a different component type (like List<Object>). There are three main kinds of variance: covariance, contravariance, and invariance.

Covariance

Covariance allows for type substitution in a same direction. This means that if type A is a subtype of type B, then Container<A> is considered a subtype of Container<B>.

Covariance is applied in contexts where it is safe to read items from a container, but not to write items into it, because every item read out of a Container<A> is guaranteed to be at least an instance of B.

Consider a system where we need to read or extract information from a collection of objects. With covariance, we can use a collection of a more specific type where a collection of a more general type is expected. This is particularly useful when dealing with read-only operations where the type safety of write operations is not a concern.

Let’s use Java for this example, focusing on a scenario involving a collection of messages and the task of reading these messages.

First, we define message classes:

abstract class Message {
    abstract String getInfo();
}

class TextMessage extends Message {
    private String content;

    TextMessage(String content) {
        this.content = content;
    }

    @Override
    String getInfo() {
        return "TextMessage: " + content;
    }
}

class ImageMessage extends Message {
    private String imageUrl;

    ImageMessage(String imageUrl) {
        this.imageUrl = imageUrl;
    }

    @Override
    String getInfo() {
        return "ImageMessage with URL: " + imageUrl;
    }
}

Next, we define a MessageReader interface with a covariant generic type:

interface MessageReader<T extends Message> {
    T readMessage();
}

Suppose we want a reader that specifically reads TextMessage objects from a source. We’ll create a TextMessageReader:

class TextMessageReader implements MessageReader<TextMessage> {
    @Override
    public TextMessage readMessage() {
        return new TextMessage("Hello from TextMessageReader");
    }
}

Finally, to demonstrate covariance, we’ll use a method that expects a MessageReader<Message>, but we’ll pass it a MessageReader<TextMessage> thanks to covariance:

public class MessageReaderDemo {
    // A method that expects a reader capable of reading messages.
    public static void displayMessageInfo(MessageReader<? extends Message> reader) {
        Message message = reader.readMessage();
        System.out.println(message.getInfo());
    }

    public static void main(String[] args) {
        // Despite expecting a MessageReader<Message>, we can pass a
        // MessageReader<TextMessage> thanks to covariance.
        TextMessageReader textReader = new TextMessageReader();
        displayMessageInfo(textReader);
    }
}

In this example, displayMessageInfo method is designed to work with a MessageReader that can read any Message. Thanks to covariance (MessageReader<? extends Message>), we can pass it a TextMessageReader, which is a MessageReader specialized for TextMessage objects. This is safe because the method only reads messages from the reader and doesn’t attempt to write or modify them, ensuring type safety.

Covariance allows us to substitute a generic type with a subtype in situations where it’s safe to do so, typically in read-only contexts. In our case, a MessageReader specialized for a subtype (TextMessage) can be used wherever a MessageReader for the supertype (Message) is expected.

Contravariance

Contravariance allows for type substitution in an opposite direction. This means that if type A is a subtype of type B, then Container<B> is considered a subtype of Container<A>.

Contravariance is useful when dealing with types of functions (or more generally, producers and consumers of data). In a contravariant scenario, we can substitute a type with one of its supertypes. This is the opposite of covariance, where we can substitute a type with one of its subtypes.

Consider a function as a box that does something with input. If you have a function that expects a specific type of input (say, an Animal), you can safely replace it with a function that works with a more general input (say, a LivingCreature, of which Animal is a subtype).

Why is this safe? Because anywhere the original function was used, it was expected to handle an Animal. The new function can handle not just Animal but any LivingCreature, making it more flexible without breaking the original contract.

Imagine we have a system that processes messages, and we have a function type that handles these messages:

interface MessageHandler<T> {
    void handle(T message);
}

Let’s reuse Message and TextMessage types from the previous example. Then TextMessageHandler can be defined as follows:

class TextMessageHandler implements MessageHandler<TextMessage> {
    @Override
    public void handle(TextMessage message) {
        System.out.println("Handling text message: " + message.getContent());
    }
}

If MessageHandler were contravariant, you could use a MessageHandler<Message> wherever a MessageHandler<TextMessage> is expected. This means you could substitute a handler that is capable of dealing with all kinds of messages, not just text messages, which could look like this:

class GenericMessageHandler implements MessageHandler<Message> {
    @Override
    public void handle(Message message) {
        System.out.println("Handling a message: " + message.getInfo());
    }
}

This substitution is safe because the GenericMessageHandler can handle everything that TextMessageHandler can (since TextMessage is a subtype of Message), plus possibly more:

class MessageProcessor {
    // Process a list of messages with a handler
    // that can handle a supertype of those messages
    public static void processMessages(List<? extends Message> messages, MessageHandler<? super Message> handler) {
        for (Message message : messages) {
            handler.handle(message);
        }
    }

    public static void main(String[] args) {
        List<Message> messages = List.of(new TextMessage("Hello, World!"), new ImageMessage("http://example.com/omnomnom.jpg"));

        // Using the generic handler to process a mixed list of messages
        GenericMessageHandler genericHandler = new GenericMessageHandler();
        processMessages(messages, genericHandler);
    }
}

The principle here is that it’s safe to write (or in this case, handle) something more general in a place that expects something more specific. Contravariance is applicable in situations where data flows into a component (like function arguments).

Invariance

Invariance means there is no subtype relationship between different instantiations of the same generic type, regardless of their component types' relationship. Neither Container<A> nor Container<B> is considered a subtype of the other, even if A is a subtype of B. Both reading from and writing to an invariant container are type-safe, but this comes at the cost of flexibility.

Conclusion

Type substitution deals with how objects of different types can be used interchangeably without breaking the functionality of a program. It can be implemented through various mechanisms, such as inheritance, interfaces, generic, or duck typing, depending on the programming language.

When using generics, type substition becomes somewhat more complicated and determines its rules via a concept called variance:

  • Covariance allows substituting a type with its subtype, ideal for read-only scenarios.

  • Contravariance permits a type to be replaced with its supertype, suitable for write operations.

  • Invariance disallows substituting a generic type with its subtypes or supertypes.