Data abstraction, objects and modules

Large programs survive only if their parts can be understood, changed and replaced independently. Programming languages support this through abstraction mechanisms: abstract data types that hide a representation behind operations, objects that bundle state with behaviour and choose code at run time, and modules that control which names a unit of code exposes. This lesson studies these mechanisms as language features with precise semantics: what an object is in terms of closures and records, how dynamic dispatch and inheritance are resolved, why multiple inheritance needs a linearization rule, how structural and nominal typing differ, and what modules and metaprogramming add. CMPUT-274 taught you to write classes; here the question is how languages define them.

Abstract data types

Barbara Liskov and Stephen Zilles introduced abstract data types in 1974, and Liskov's language CLU (1975) built them in. An abstract data type is a type defined by its operations and their behaviour, not by its representation. Clients can only use the operations, so the implementer can change the representation without breaking clients. The idea goes back to David Parnas's 1972 paper on information hiding, which argued that modules should be divided around design decisions likely to change, each hidden behind an interface.

# Two implementations of one abstract data type: a FIFO queue.
# Clients see only the operations empty, push, pop and is_empty, never the representation.
class ListQueue:                       # representation 1: a single Python list
    def __init__(self): self._xs = []
    def push(self, x): self._xs.append(x)
    def pop(self): return self._xs.pop(0)          # O(n): shifts every element
    def is_empty(self): return not self._xs

class TwoStackQueue:                   # representation 2: two stacks, amortized O(1)
    def __init__(self): self._front, self._back = [], []
    def push(self, x): self._back.append(x)
    def pop(self):
        if not self._front:
            while self._back: self._front.append(self._back.pop())
        return self._front.pop()
    def is_empty(self): return not (self._front or self._back)

def client(q):                         # written once, against the interface only
    for word in ["alpha", "beta", "gamma"]: q.push(word)
    out = [q.pop()]
    q.push("delta")
    while not q.is_empty(): out.append(q.pop())
    return out

for impl in (ListQueue, TwoStackQueue):
    print(f"{impl.__name__:14} {client(impl())}")

ListQueue      ['alpha', 'beta', 'gamma', 'delta']
TwoStackQueue  ['alpha', 'beta', 'gamma', 'delta']

The client function produces the same results with both representations, even though one stores a single list and the other two stacks. This property, representation independence, is what makes abstraction valuable: the slow ListQueue can be replaced by TwoStackQueue without touching a line of client code. Python enforces the boundary only by convention (a leading underscore); CLU, Ada, ML and Java enforce it with the type system or access modifiers. John Reynolds showed in 1983 that parametric polymorphism guarantees representation independence, a result known as parametricity.

Objects as closures and records

Under the surface, an object is a record of functions that share hidden state. A closure already gives us that: the local variables of an enclosing function are private, and the inner functions that capture them are the methods. The slogan 'objects are a poor man's closures, and closures are a poor man's objects' captures the equivalence. Smalltalk (Alan Kay and others at Xerox PARC, 1972 to 1980) described method calls as messages sent to objects, and the dispatch function below makes that view literal.

# Objects from closures: state is hidden in the enclosing scope, methods are a dispatch table.
def make_account(balance):
    def deposit(amount):
        nonlocal balance
        balance += amount
        return balance
    def withdraw(amount):
        nonlocal balance
        if amount > balance: return "insufficient funds"
        balance -= amount
        return balance
    def send(message, *args):                  # message passing: dispatch on a name
        return {"deposit": deposit, "withdraw": withdraw,
                "balance": lambda: balance}[message](*args)
    return send

acct = make_account(100)
print(acct("deposit", 50))
print(acct("withdraw", 500))
print(acct("withdraw", 30))
print(acct("balance"))
other = make_account(10)
print("independent state:", other("balance"), acct("balance"))

150
insufficient funds
120
120
independent state: 10 120

William Cook's essay 'On understanding data abstraction, revisited' (2009) argues that objects and abstract data types are two different forms of abstraction. An abstract data type hides a representation behind a type, so operations on two values of the type can look inside both (two sets of one implementation can be merged efficiently). An object hides its representation behind an interface of methods, so an object can only ask other objects to do things through their methods, which lets different implementations interoperate (a set backed by a list can be combined with one backed by a hash table). Each choice makes some extensions easy and others hard.

The last two rows describe the expression problem, named by Philip Wadler in 1998: how to add both new variants and new operations to a data type without modifying or recompiling existing code, while keeping static type safety. Functional languages with algebraic data types make new operations easy and new variants hard; object-oriented languages do the reverse. Visitors, type classes, multimethods and Scala's traits are all partial answers.

Dynamic dispatch and inheritance

The defining feature of object-oriented languages is dynamic dispatch: the method run by obj.m() is chosen by the run-time class of obj, not by the static type of the expression. Inheritance lets a class reuse its parent's methods and override some of them. Crucially, self (or this) is late bound: when an inherited method calls self.area(), it calls the override in the subclass. That late binding is what lets a superclass define a template whose steps subclasses fill in, and it is also what makes inheritance fragile.

# Dynamic dispatch by hand: each class is a record with a parent link and a method table.
def lookup(cls, name):
    while cls is not None:
        if name in cls["methods"]: return cls["methods"][name]
        cls = cls["parent"]
    raise AttributeError(name)

def send(obj, name, *args):
    method = lookup(obj["class"], name)          # chosen by the object's run-time class
    return method(obj, *args)

Shape = {"name": "Shape", "parent": None, "methods": {
    "describe": lambda self: f"a {self['class']['name']} with area {send(self, 'area'):.2f}",
}}
Circle = {"name": "Circle", "parent": Shape, "methods": {
    "area": lambda self: 3.14159 * self["r"] ** 2,
}}
Square = {"name": "Square", "parent": Shape, "methods": {
    "area": lambda self: self["side"] ** 2,
}}
Unit = {"name": "UnitSquare", "parent": Square, "methods": {
    "describe": lambda self: "the unit square",   # override
}}

for obj in [{"class": Circle, "r": 1.0}, {"class": Square, "side": 3}, {"class": Unit, "side": 1}]:
    print(send(obj, "describe"))

a Circle with area 3.14
a Square with area 9.00
the unit square

The describe method is defined once in Shape, yet it calls the right area for each object, because send looks up area starting from the object's own class. Compiled languages make this fast with virtual method tables: each class has an array of method pointers, every object carries a pointer to its class's table, and a call becomes one indirect jump at a fixed index. C++ and Java implement virtual calls this way; just-in-time compilers go further by inlining the method they observe at a call site and guarding with a cheap class check.

The fragile base class problem is the price of late-bound self. If a library's base class changes how its own methods call each other, subclasses that override one of those methods can break without any change on their side. The classic example, from Joshua Bloch's Effective Java, is a subclass of HashSet that counts insertions by overriding both add and addAll: because HashSet.addAll calls add internally, every element is counted twice. This is why modern advice favours composition over inheritance, and why Go and Rust have no implementation inheritance at all.

Multiple inheritance and linearization

If a class may have several parents, a method name may be found along several paths. The diamond problem arises when two parents share a common ancestor: which version of an inherited method should the child see, and should the ancestor's state be duplicated? C++ answers with explicit qualification and virtual base classes. Python, like Dylan, Perl 6 (now Raku) and Solidity, computes a single method resolution order with the C3 linearization algorithm, which preserves each class's local order of parents and puts every class before its ancestors. super() then means 'the next class in the linearization', not 'my parent'.

# Multiple inheritance needs a linearization: Python uses C3 (from Dylan, 1996).
class Base:
    def hello(self): return "Base"
class Left(Base):
    def hello(self): return "Left -> " + super().hello()
class Right(Base):
    def hello(self): return "Right -> " + super().hello()
class Child(Left, Right):
    def hello(self): return "Child -> " + super().hello()

print([c.__name__ for c in Child.__mro__])
print(Child().hello())

try:
    class X(Left, Base): pass
    class Y(Base, Left): pass       # Base before its own subclass: no consistent order
except TypeError as e:
    print("TypeError:", e)

['Child', 'Left', 'Right', 'Base', 'object']
Child -> Left -> Right -> Base
TypeError: Cannot create a consistent method resolution order (MRO) for bases Base, Left

Observe that super() in Left calls Right, not Base, because Right comes next in Child's resolution order. That cooperative behaviour is useful but surprising. When no ordering consistent with every class's declared parent order exists, Python refuses to create the class. Traits, introduced by Nathanael Schärli and colleagues in 2003 and adopted by Scala, PHP, Rust and Pharo Smalltalk, offer composable units of behaviour without state, with explicit resolution of conflicting method names. Mixins, a related idea from Flavors and CLOS, are classes designed to be combined with others.

# Mixins: small classes that add methods to any class providing a few hooks.
import functools

class ComparableMixin:              # needs: key()
    def __lt__(self, other): return self.key() < other.key()
    def __eq__(self, other): return self.key() == other.key()

class ReprMixin:                    # needs: nothing but attributes
    def __repr__(self):
        fields = ", ".join(f"{k}={v!r}" for k, v in vars(self).items())
        return f"{type(self).__name__}({fields})"

@functools.total_ordering          # derives <=, >, >= from < and ==
class Version(ComparableMixin, ReprMixin):
    def __init__(self, text): self.text = text
    def key(self): return tuple(int(p) for p in self.text.split("."))

vs = [Version("1.10.0"), Version("1.2.9"), Version("1.2.10")]
print(sorted(vs))
print(Version("2.0") > Version("1.99"), max(vs))

[Version(text='1.2.9'), Version(text='1.2.10'), Version(text='1.10.0')]
True Version(text='1.10.0')

Nominal and structural typing

Two object types can be compatible for two different reasons. In nominal typing, used by Java, C# and C++, a class is a subtype of an interface only if it declares so by name. In structural typing, used by Go interfaces, TypeScript, OCaml objects and Python's typing.Protocol, a type is compatible with an interface simply by having the required methods with compatible types. Duck typing is the dynamic counterpart: Python and Ruby check only at the moment a method is called. Structural typing lets independently written code fit together without a shared declaration, while nominal typing prevents accidental matches between types that happen to share method names.

package main

import (
	"fmt"
	"math"
)

// Structural typing: a type satisfies an interface just by having the methods.
type Shape interface {
	Area() float64
}

type Circle struct{ R float64 }
type Rect struct{ W, H float64 }

func (c Circle) Area() float64 { return math.Pi * c.R * c.R }
func (r Rect) Area() float64   { return r.W * r.H }

// Embedding instead of inheritance: Tagged reuses Rect's methods by composition.
type Tagged struct {
	Rect
	Label string
}

func main() {
	shapes := []Shape{Circle{1}, Rect{2, 3}, Tagged{Rect{4, 5}, "door"}}
	total := 0.0
	for _, s := range shapes {
		fmt.Printf("%-24T %.3f\n", s, s.Area())
		total += s.Area()
	}
	fmt.Printf("total %.3f\n", total)
}

main.Circle              3.142
main.Rect                6.000
main.Tagged              20.000
total 29.142

Neither Circle nor Rect mentions Shape, yet both satisfy it. Tagged has no Area method of its own; it embeds a Rect, and Go promotes the embedded field's methods. That is composition with convenient syntax, not inheritance: inside Rect's Area there is no late-bound self pointing back to the Tagged value.

Prototypes instead of classes

Classes are not the only way to organize objects. In prototype-based languages, pioneered by Self (David Ungar and Randall Smith, 1987), objects are created by cloning other objects and inherit by delegation: if an object lacks a property, the lookup continues in its prototype. JavaScript adopted this model, and its class syntax, added in ECMAScript 2015, is a layer over prototype chains. The Self project also developed the adaptive compilation techniques, such as inline caches and type feedback, that later made the HotSpot Java virtual machine and the V8 JavaScript engine fast.

// Prototype-based objects (Self, 1987; JavaScript): no classes, only delegation.
const animal = { speak() { return `${this.name} makes ${this.sound()}`; },
                 sound() { return "a noise"; } };
const dog = Object.create(animal);           // dog delegates to animal
dog.sound = function () { return "woof"; };
const rex = Object.create(dog);              // rex delegates to dog
rex.name = "Rex";

console.log(rex.speak());
console.log(Object.getPrototypeOf(rex) === dog, Object.getPrototypeOf(dog) === animal);
animal.sound = () => "a changed noise";      // only affects objects that do not override it
const generic = Object.create(animal); generic.name = "Thing";
console.log(generic.speak(), "|", rex.speak());

// ES2015 class syntax is a layer over the same prototype chain.
class Point { constructor(x, y) { this.x = x; this.y = y; } norm() { return Math.hypot(this.x, this.y); } }
console.log(typeof Point, Object.getPrototypeOf(new Point(3, 4)) === Point.prototype, new Point(3, 4).norm());

Rex makes woof
true true
Thing makes a changed noise | Rex makes woof
function true 5

Modules and interfaces

A module groups related definitions and controls which are visible outside. Modula-2 (Niklaus Wirth, 1978) and Ada (1983) separated a module's interface from its implementation; Standard ML went further with signatures (module types) and functors, which are functions from modules to modules, so that, for example, a balanced-tree set can be built for any ordered key module. OCaml, Rust and modern JavaScript and Python have module systems with explicit exports; Java added modules in version 9 (2017). Separate compilation, namespaces and abstract types are the three jobs a module system does.

// Modules give information hiding at the file level; TypeScript adds type-level hiding.
// A "branded" type: callers cannot forge a UserId from an arbitrary number.
type UserId = number & { readonly __brand: "UserId" };

const Users = (() => {
  let next = 1;                               // private to the module closure
  const names = new Map<UserId, string>();
  return {
    create(name: string): UserId { const id = next++ as UserId; names.set(id, name); return id; },
    name(id: UserId): string { return names.get(id) ?? "unknown"; },
  };
})();

const a = Users.create("Ada");
const b = Users.create("Alan");
console.log(Users.name(a), Users.name(b));
console.log(Users.name(42));                  // type error: number is not UserId

$ tsc --strict --target es2020 users.ts
users.ts(17,24): error TS2345: Argument of type 'number' is not assignable to parameter of type 'UserId'.
  Type 'number' is not assignable to type '{ readonly __brand: "UserId"; }'.
$ node users.js
Ada Alan
unknown

Metaprogramming

Some languages let programs manipulate programs. Lisp's macros, from the 1960s, transform code represented as lists before it is evaluated, and Scheme's hygienic macros (1986 onward) prevent accidental variable capture, the same problem met with substitution in lesson 5. Rust has macro_rules! and procedural macros, C++ has templates and constexpr evaluation, and Python exposes its abstract syntax tree through the ast module. Reflection is the run-time counterpart: Java's java.lang.reflect and Python's getattr let a program inspect and call methods by name.

# Metaprogramming on the abstract syntax tree: rewrite x ** 2 into x * x before running.
import ast

source = "def area(r):\n    return 3.14159 * r ** 2\n\nprint(area(2.0), area(10))\n"

class SquareToMultiply(ast.NodeTransformer):
    def visit_BinOp(self, node):
        self.generic_visit(node)
        if isinstance(node.op, ast.Pow) and isinstance(node.right, ast.Constant) and node.right.value == 2:
            return ast.BinOp(left=node.left, op=ast.Mult(), right=node.left)
        return node

tree = ast.parse(source)
new_tree = ast.fix_missing_locations(SquareToMultiply().visit(tree))
print(ast.unparse(new_tree).splitlines()[1].strip())
exec(compile(new_tree, "<rewritten>", "exec"))

return 3.14159 * (r * r)
12.56636 314.159

Worked examples