Interview

The Three Major Characteristics of Object-Oriented Programming

Interviews often ask about the three major characteristics of object-oriented programming, but no single book explains all three thoroughly. Here I try to synt…

Published

Tags

Interviews often ask about the three major characteristics of object-oriented programming, but no single book explains all three thoroughly. Here I try to synthesize material from several books and understand these three characteristics from different perspectives.

Today, the three major characteristics of object-oriented programming are generally considered to be encapsulation, inheritance, and polymorphism.

To be honest, I do not know where this answer came from. I deliberately spent quite a while searching on Google and various academic search engines, but I could not find the source. Instead, Wikipedia lists several major features, along with sources.

Benjamin C. Pierce and some other researchers view any attempt to distill OOP to a minimal set of features as futile. He nonetheless identifies fundamental features that support the OOP programming style in most object-oriented languages:

- Dynamic dispatch – when a method is invoked on an object, the object itself determines what code gets executed by looking up the method at run time in a table associated with the object. This feature distinguishes an object from an abstract data type (or module), which has a fixed (static) implementation of the operations for all instances. It is a programming methodology that gives modular component development while at the same time being very efficient.
- Encapsulation (or multi-methods, in which case the state is kept separate)
- Subtype polymorphism
- Object inheritance (or delegation)
- Open recursion – a special variable (syntactically it may be a keyword), usually called this or self, that allows a method body to invoke another method body of the same object. This variable is late-bound; it allows a method defined in one class to invoke another method that is defined later, in some subclass thereof.

Similarly, in his 2003 book, Concepts in programming languages, John C. Mitchell identifies four main features: dynamic dispatch, abstraction, subtype polymorphism, and inheritance. Michael Lee Scott in Programming Language Pragmatics considers only encapsulation, inheritance and dynamic dispatch.

Given that, I will not discuss the source or original explanation. I will directly explain the three concepts of encapsulation, inheritance, and polymorphism, so that interviewers will not think I do not understand object-oriented programming.

Encapsulation #

The main significance of encapsulation is that it can restrict access to an object’s contents. In C++, there are three access levels (not counting friends): public, protected, and private. In Java, C#, or other languages, there may be even more fine-grained access control mechanisms.

This control over access to an object’s internals has two benefits:

  1. It can protect internal data from accidental modification.
  2. It can hide internal implementation details from the outside, so that when the implementation needs to be changed later, existing code will not be broken.

The following examples illustrate these two points.

First, look at how the C language, without object-oriented programming, implements a stack:

cpp
#define STACK_SIZE_MAX 10000
int stack[STACK_SIZE_MAX];
int stackTop = 0
#define PUSH_STACK(x) (stack[stackTop++]=(x))
#define TOP_STACK() (stack[stackTop-1])
#define POP_STACK() (stack[--stackTop])

This is concise and efficient, but this code has several problems:

  1. It can only store the int type.
  2. There is only one stack.
  3. It is not thread-safe.
  4. The stack has a limited size.
  5. The stack variable and the stackTop variable may be modified accidentally or intentionally.

The first problem cannot be solved even by using object-oriented programming; it is solved through generics. Of course, if type safety is not a concern, the void * type can also be used for storage. For the second problem, the usual solution is to imitate object-oriented programming. The code is as follows:

cpp
typedef int stack_item_type;
struct stack_struct
{
    int capacity;
    int top;
    stack_item_type * stack;
};
typedef struct stack_struct * stack_type;

inline stack_type new_stack_ex(int capacity)
{
    stack_type stack = (stack_type)malloc(sizeof(struct stack_struct));
    stack->capacity = capacity;
    stack->top = 0;
    stack->stack = (stack_item_type *)malloc(sizeof(stack_item_type) * capacity);
    return stack;
}

inline void delete_stack_ex(stack_type stack)
{
    free(stack->stack);
    free(stack);
}

inline void push_stack_ex(stack_type stack, stack_item_type item)
{
    stack->stack[stack->top++] = item;
}

inline stack_item_type top_stack_ex(stack_type stack)
{
    return stack->stack[stack->top - 1];
}

inline void pop_stack_ex(stack_type stack)
{
    stack->top--;
}

With this solution, problems two, three, and four are all solved. But the last problem can only be solved if the language provides mechanism support for information hiding. This is exactly the problem solved by the information-hiding mechanism introduced by C++, namely encapsulation of information. Let us see how to implement a stack in C++:

cpp
template<typename T, int STACK_CAPACITY = 10000>
class Stack
{
public:
    inline void Push(T item) { stack[top++] = item; }
    inline T Top(void) { return stack[top - 1]; }
    inline void Pop(void) { top--; }
private:
    int stack[STACK_CAPACITY];
    int top;
public:
    Stack(void) : top(0) { }
};

By setting the access level of the stack variable and the top variable to private, no method other than member functions in the Stack class can access these two variables. This effectively prevents unexpected results caused by accidental modification.

On the other hand, by restricting access to the contents of Stack, callers can only access it through the public methods exposed by the Stack class, which also abstracts the implementation of the Stack class. This is equivalent to establishing an interface (contract) between the caller and the implementer, so that both sides reach a shared understanding. This brings an additional benefit: as long as the interface does not change, the internal implementation of a class can change freely. For example, the implementer may think that a stack object implemented with an array wastes too much memory and that a singly linked list would be better, so the implementation is changed as follows:

cpp
template<typename T>
struct ListNode
{
    T data;
    std::shared_ptr<ListNode> next;
    ListNode(T data, std::shared_ptr<ListNode> next)
        : data(data), next(next)
    { }
};

template<typename T>
class Stack
{
public:
    inline void Push(T item) { list = std::make_shared<ListNode<T>>(item, list); }
    inline T Top(void) { return list->data; }
    inline void Pop(void) { list = list->next; }
private:
    std::shared_ptr<ListNode<T>> list;
public:
    Stack(void) : list(nullptr) { }
};

Because the externally exposed interface has not changed at all, all callers of the Stack class do not need to modify their code. This is something that languages such as C, which do not provide such strong encapsulation mechanisms, cannot achieve.

Inheritance #

The original purpose of inheritance was to directly reuse code written in a parent class. However, people quickly discovered that simply using inheritance to reuse code can easily create even greater confusion, so it must be constrained. This constraint is the Liskov Substitution Principle. The content of the Liskov Substitution Principle can be described as: “Objects of a derived class (subclass) should be able to replace objects of its base class (superclass) where they are used.” The preceding statement is not Liskov’s original wording, but a translation of Robert Martin’s interpretation of the original text. This is an intuitive constraint: if a subtype cannot be used in places where the parent type is used, then the two classes should not have an inheritance relationship. That is, the subclass should be an (is-a) special case of the parent class.

Next, consider a counterintuitive example. This is a bad example, constructed only to illustrate the problem; please do not imitate it.

Intuitively, a square is a special case of a rectangle, so a square should inherit from a rectangle.

cpp
class Rectangle
{
public:
    inline int getWidth(void) const { return width; }
    inline int getHeight(void) const { return height; }
    inline int getArea(void) const { return width * height; }
private:
    int width;
    int height;
public:
    Rectangle(int width, int height)
        : width(width), height(height)
    { }
};

class Square : public Rectangle
{
public:
    Square(int sideLength) : base(sideLength, sideLength) { }
};

In this case, anywhere Rectangle is used, Square can also be used. But suppose the Rectangle class also has two member functions:

cpp
class Rectangle
{
    ...
public:
    virtual void setWidth(int width) { this->width = width; }
    virtual void setHeight(int height) { this->height = height; }
};

class Square : public Rectangle
{
    ...
public:
    virtual int setWidth(int width) override { setSideLength(width); }
    virtual int setHeight(int height) override { setSideLength(height); }
private:
    void setSideLength(int length)
    {
        width = length;
        height = length;
    }
};

Then the Square class should not inherit from the Rectangle class, because the logic that the Square class uses to handle changes to width and height is completely different from that of Rectangle; it is not an extension of the original functionality. As a result, code originally written for Rectangle may produce unexpected results if it is given a Square. For example, the following test case fails when the object passed in is an instance of Square:

cpp
void TestArea(Rectangle &rectangle)
{
    const int deltaWidth = 10;
    int originArea = rectangle.getArea();
    const int exceptedArea = originArea + deltaWidth * rectangle.getHeight();

    rectangle.setWidth(rectangle.getWidth() + deltaWidth);
    int actualArea = rectangle.getArea();
    TEST_ASSERT_EQUAL(exceptedArea, actualArea);
}

This is because the length and width of the original rectangle can be changed independently, while the requirements for a square are stricter, which leads to a violation of the Liskov Substitution Principle.

For languages that support contravariance, covariance, and exceptions, the requirements are:

  • In a subclass, method parameters must be contravariant.
  • In a subclass, method return values must be covariant.
  • If a method in the parent class does not throw exceptions, then the corresponding method in the subclass should not throw exceptions either.
  • If a method in the parent class throws an exception, then the corresponding method in the subclass may throw a subclass exception of that exception.

In addition, subclass design should follow these general principles:

  • In a subclass, preconditions must not be strengthened.
  • In a subclass, postconditions must not be weakened.
  • In a subclass, the invariants of the parent class must be preserved.
  • If a subclass introduces methods that do not exist in the parent class, those methods must not change state inherited from the parent class.

The rectangle-and-square example above violates the principle that postconditions must not be weakened.

Polymorphism #

Polymorphism (specifically, the term “polymorphism” in object-oriented programming) is a technique in which the code that should be executed by the invoked method is not determined until runtime.

Usually, in languages such as C/C++, Java, and C#, the code to execute is determined at compile time. This is called “early binding.” The compiler knows where the invoked function is located, so when it calls the function, it simply pushes the parameters onto the stack according to the calling convention and then jumps to the function’s location to continue execution. Polymorphism, however, can delay this process until runtime, when the program knows the true location of the code for the function being called. Because the code to execute is not determined until runtime, this is also called “late binding.” Many dynamic languages use “late binding” by default.

Polymorphism is closely related to inheritance. In C++, only functions declared as virtual functions in a parent class can be overridden in a subclass, thereby implementing polymorphism.

The benefit of polymorphism is that we can extend functionality without modifying existing code. Using the stack code above as an example again:

cpp
template<typename T>
class Stack
{
public:
    virtual void Push(T) = 0;
    virtual T Top(void) const = 0;
    virtual void Pop(void) = 0;
};

template<typename T, int CAPACITY>
class ArrayStack : public Stack
{
public:
    virtual void Push(T item) override { stack[top++] = item; }
    virtual T Top(void) const override { return stack[top - 1]; }
    virtual void Pop(void) override { top--; }
private:
    T stack[CAPACITY];
    int top;
public:
    ArrayStack(void) : top(0) { }
};

...

template<typename T>
class LinkedListStack : public Stack
{
public:
    virtual void Push(T item) override
    {
        list = std::make_shared<ListNode<T>>(item, list);
    }
    virtual T Top(void) const override { return list->data; }
    virtual void Pop(void) override { list = list->next; }
private:
    std::shared_ptr<ListNode<T>> list;
public:
    LinkedListStack(void) : list(nullptr) { }
};

When using it, suppose there is a function like this:

cpp
void PushZero(Stack<int> &stack)
{
    stack.Push(0);
}

Then which function is the Push function called here? First, it is certainly not the Push function in the Stack class, because Stack is a pure virtual class, and its Push method has no implementation at all. Second, it depends on the argument passed to this function and what its actual type is at runtime. If the stack variable passed in is of type ArrayStack, then the Push method in the ArrayStack class is called. If it is of type LinkedListStack, then the Push method in LinkedListStack is called. If we implement another class, for example like this:

cpp
template<typename T>
class VectorStack : public Stack
{
public:
    virtual void Push(T item) override { stack.push_back(item); }
    virtual T Top(void) const override { return stack.back(); }
    virtual void Pop(void) override { stack.pop_back(); }
private:
    std::vector<T> stack;
};

Then if the argument stack passed to PushZero is of type VectorStack, the Push method in VectorStack is called. Notice that we did not know in advance that there would be a class such as VectorStack, but later, in order to extend the functionality of the Stack class, we wrote this new class, and without modifying any code in the PushZero function, we can make use of the VectorStack class.

C++ implements this functionality by using virtual function tables. For details, see section 3.5, Virtual Functions, in The Design and Evolution of C++.