Object-Oriented Concepts

An object is a unit that packages state (a set of fields, or instance variables) together with behavior (a set of methods) that is permitted to read and modify that state. A class is a template — a compile-time description of the fields and methods that every object created from it (every instance) will have. Creating an instance (`new Circle(5)`) allocates storage for the fields and associates the object with its class, so that later, when a method is invoked on the object, the language runtime knows which code to run.

Encapsulation is the discipline of hiding an object's representation behind a well-defined interface, exposing only the operations a client is permitted to use. Formally, encapsulation establishes a representation invariant — a property of the internal state (e.g., "the linked list's `size` field always equals the number of nodes reachable from `head`") that holds after every public operation completes, and that only the class's own methods are trusted to preserve. Access modifiers (`private`, `protected`, `public`) are the syntactic mechanism; the invariant is the semantic payoff. Encapsulation is what lets a class change its internal implementation (say, from an array to a hash table) without breaking client code, as long as the public interface's behavior is preserved — this is the same idea as an abstract data type, made concrete with bundled behavior.

Inheritance lets a class (the subclass or derived class) declare that it extends another class (the superclass or base class), automatically acquiring its fields and methods, and then adding new members or overriding (replacing) some of the inherited methods with more specific behavior. Inheritance serves two distinct purposes that are worth naming separately: implementation reuse (don't re-write code already written in the base class) and subtyping (a `Circle` is a `Shape`, so anywhere a `Shape` is expected, a `Circle` may be substituted). The Liskov Substitution Principle states this precisely: if `S` is a subtype of `T`, objects of type `T` in a program may be replaced by objects of type `S` without altering any desirable property of that program. Violating this principle — e.g., a `Square` subclass of `Rectangle` that breaks `setWidth`/`setHeight` independence — is a classic design trap, not a language bug, but the type system cannot catch it automatically.

Dynamic dispatch (also called late binding or virtual dispatch) is the mechanism that makes overriding meaningful: when code calls `shape.draw()`, the method body that executes is chosen based on the dynamic type (run-time type) of the object bound to `shape`, not the static type (compile-time declared type) of the variable. This is the crux of the whole paradigm. Contrast it with static dispatch (ordinary function calls, and overload resolution in most languages), which is fully resolved at compile time using only static type information — exactly the binding-time distinction studied for variable names in Names, Binding, and Scope, now applied to method names.

Dynamic dispatch must answer, at every call site, the question: "given this object, which method body runs?" The answer must be computed fast, because virtual calls are common in idiomatic OO code, and it must be computed correctly even when the object's exact class is unknown until run time (it might have been constructed behind a factory, deserialized, or passed in from a plugin). The standard solution, used by C++, Java, C#, and most statically-typed OO languages, is the virtual method table (vtable).

The layout. Each class (not each object) gets exactly one vtable: an array of function pointers, one slot per virtual method, ordered consistently across the whole hierarchy so that a method's slot index is the same in every subclass. Each object carries one extra hidden field — a pointer to its class's vtable — set once at construction time and never changed thereafter (assuming no dynamic reclassification, which most languages forbid). A method call `obj.method(args)` compiles not to a direct call but to: load the vtable pointer from `obj`, index into a fixed slot, and call the function pointer found there, passing `obj` itself as an implicit first argument (`this`/`self`).

Building the vtable. When a subclass `B` extends `A`:

• Every virtual method inherited unchanged from `A` keeps its slot, pointing at `A`'s implementation.
• Every method `B` overrides replaces the pointer in that same slot with `B`'s new implementation.
• Every new virtual method `B` introduces gets a new slot appended at the end.

This slot-stability is exactly what makes dispatch O(1): the compiler statically determines which slot a call site targets (by the method's name and the static type's layout), and defers only which pointer occupies that slot to run time. ``` ALGORITHM: build_vtable(class C) if C has no superclass: table := empty list of (name -> slot index) slots := empty array of function pointers else: (table, slots) := build_vtable(C.superclass) # copy inherited layout table := copy(table); slots := copy(slots) for each method m declared in C: if m.name in table: # overriding an inherited method idx := table[m.name] slots[idx] := address_of(m.body) else: # brand-new virtual method idx := length(slots) table[m.name] := idx append slots with address_of(m.body) C.vtable := slots C.slot_of := table # compile-time map, not stored per-object return (table, slots)

ALGORITHM: dispatch(obj, method_name, args) cls := obj.dynamic_type # read the hidden class tag / vtable pointer idx := STATIC lookup of method_name's slot, resolved at compile time using the STATIC type of the call site fn := cls.vtable[idx] # ONE indirection, resolved at run time return fn(obj, args) # obj passed as implicit 'this' ``` The key subtlety, and the one students most often get wrong: the slot index is a compile-time constant determined by the static type at the call site (or, more precisely, by the method's declared signature within the class hierarchy). Only the contents of that slot — which function pointer actually lives there — depends on the object's dynamic type, discovered at run time via the object's stored vtable pointer. This split is exactly why dispatch costs one extra memory load and one indirect call, not a search: no scanning, no hashing, no `if`-chain.

Construction and single dispatch. During object construction, the vtable pointer is set to the currently constructing class before that class's constructor body runs, which is why calling an overridable method from within a base-class constructor famously does not yet see the derived class's override in languages like C++ (the vtable pointer is still `A`'s at that point) — a well-known trap discussed below. ```

```

## Complexity & correctness

Time. A dynamically dispatched call costs O(1): one load to fetch the object's vtable pointer, one array index (constant offset, known at compile time) to fetch the function pointer, and one indirect call. This is asymptotically identical to a direct call except for the extra indirection, typically 1–3 additional cycles on modern hardware absent a branch-prediction miss (indirect calls are harder for the CPU's branch predictor than direct calls, which is the practical, not asymptotic, cost of virtual dispatch). Contrast this with a naive re-implementation using a type tag and an `if`/`switch` chain — also O(1) amortized if the switch compiles to a jump table, but O(n) in the number of cases if it compiles to a linear chain of comparisons, and in either case it requires editing that chain for every new subtype, which is precisely the maintenance cost OOP eliminates.

Space. Each class stores one vtable of size O(m), where m is the number of virtual methods reachable in that class's hierarchy — a fixed, shared cost independent of the number of objects. Each object pays exactly one extra pointer (typically one machine word, e.g., 8 bytes on a 64-bit system) for its vtable pointer, regardless of how many methods the class declares. This is the crucial efficiency argument: vtable space is amortized across all instances, so creating a million `Circle` objects costs a million extra words, not a million copies of the vtable.

Why building the vtable is correct. The construction algorithm above maintains an invariant by structural induction on the inheritance chain: slot assignment is stable under inheritance — if method `m` occupies slot `k` in class `A`, then `m` occupies slot `k` in every subclass of `A`, whether inherited unchanged or overridden. Base case: a root class assigns slots in declaration order, trivially stable (there is nothing to be stable with). Inductive step: `build_vtable(B)` for `B extends A` starts by copying `A`'s table and slot array verbatim, so every method already present in `A` keeps its slot number; overriding only replaces the pointer at that slot, never renumbering it. New methods are appended after all inherited slots, so they cannot collide with or shift existing indices. This invariant is exactly what allows the compiler to resolve a call site's slot index using only the static type — the slot number is guaranteed to be the same no matter which subclass the object turns out to be at run time.

Why dispatch resolves to the correct override. Given the slot-stability invariant, dispatch correctness reduces to a simple claim: at the moment a method call executes, the object's stored vtable pointer refers to the vtable of its most specific (leaf) dynamic class, and by construction that vtable's slot `k` contains the most-derived override of the method assigned to slot `k`, because later `build_vtable` calls always overwrite earlier pointers when overriding occurs, never the reverse. Hence dispatch always yields the same result as literally asking "does the leaf class override this method? if not, does its parent? ..." walking up the chain — but computed in O(1) instead of O(depth of hierarchy).

Honest tradeoffs. Dynamic dispatch trades a small, constant runtime cost and one pointer of space per object for the ability to add new subclasses without modifying existing code (the open/closed principle: open for extension, closed for modification). It also trades readability of control flow — a call to `shape.draw()` can silently invoke any of dozens of overrides scattered across a codebase, unlike a direct call whose target is textually visible — for extensibility. Static dispatch remains strictly cheaper and more predictable when the set of cases is fixed and known, which is why languages let you opt out (`final` methods in Java, non-`virtual` methods in C++) to recover direct-call performance and eliminate the indirection entirely.

## Worked example Consider this small hierarchy (syntax kept language-neutral): ``` class Shape: method area() -> Number: return 0 method draw() -> String: return "generic shape" method name() -> String: return "Shape" class Circle extends Shape: field radius: Number method area() -> Number: return 3.14159 radius radius method draw() -> String: return "circle r=" + radius

# 'name' not overridden — inherited from Shape class Ellipse extends Circle: field minor_radius: Number method area() -> Number: return 3.14159 radius minor_radius

# 'draw' and 'name' not overridden — inherited (from Circle, Shape respectively) ```

Step 1 — vtable construction (compile time / class-load time).

Note the slot numbers never change — `area` is slot 0 in all three classes, exactly as the induction argument guarantees.

Step 2 — objects and their vtable pointers (run time). ``` s : Shape = new Shape() # s.vptr → Shape::vtable c : Shape = new Circle(radius=5) # c.vptr → Circle::vtable (declared type Shape!) e : Shape = new Ellipse(radius=5, minor_radius=2) # e.vptr → Ellipse::vtable ``` Note carefully: `c` and `e` are declared with static type `Shape` (perhaps returned from a factory function `makeRandomShape()`), but their dynamic type is `Circle` and `Ellipse` respectively.

Step 3 — dispatching a loop over a list of shapes. ``` shapes : List = [s, c, e] for sh in shapes: print(sh.area()) ``` The compiler resolves `sh.area()` to slot 0, a fixed decision made once, using only the static type `Shape`. At run time, for each iteration:

Every call site is textually identical (`sh.area()`), every call resolves the same slot index (0), and yet three different function bodies execute — that is dynamic dispatch working exactly as designed. Now trace `sh.name()` for the same list: it resolves to slot 2 in all three cases, and because neither `Circle` nor `Ellipse` overrides `name`, every object's slot 2 still points at `Shape::name`, so all three calls print `"Shape"` — demonstrating that inheritance without overriding is simply "the pointer in that slot was never replaced," not a separate mechanism.

## Common pitfalls & traps

The object-oriented paradigm did not spring from a single insight; it accreted from a simulation language's practical needs, a research group's philosophical vision of "everything is a message," and later industrial languages that traded purity for performance and static type safety.

Virtual method tables and dynamic dispatch underpin nearly every mainstream object-oriented runtime: the JVM and CLR both implement `invokevirtual`/`callvirt` bytecode instructions using vtable-like structures (the JVM additionally uses inline caches to speed up repeated calls at the same call site). GUI frameworks (Java Swing, .NET WinForms, the browser DOM's event handlers) rely on overriding `paint`/`onEvent`-style methods so that a framework written once can render arbitrary custom widgets supplied later by application code — the direct descendant of the "add a new shape without touching drawing code" motivation from the overview. Plugin architectures (compiler backends targeting multiple instruction sets, database drivers implementing a common `Connection` interface, device drivers implementing a common `Driver` interface in an operating system) are essentially large-scale applications of dynamic dispatch: a fixed interface, an open set of implementations, resolved at run time by the loader. Understanding vtables also explains real compiler and JIT behavior: devirtualization (a compiler proving only one implementation is possible and replacing an indirect call with a direct one) is a major optimization in modern JITs precisely because it removes the indirection this article describes, and understanding Names, Binding, and Scope alongside dynamic dispatch clarifies why languages distinguish `virtual`/`override`/`final` keywords as binding-time annotations rather than mere style choices.

Ask the tutor: Can you trace what happens to the vtable and dispatch when a class overrides a method but also changes its parameter types — is that an override or a new overload?