Types and type systems

A type describes a set of values and the operations allowed on them: integers can be added, strings can be concatenated, and adding an integer to a string makes no sense. A type system is the set of rules a language uses to assign types to expressions and to reject programs that misuse them. Type systems differ in when they check, how strictly they check, and how much they can express. This lesson compares static and dynamic typing, strong and weak typing, nominal and structural typing, and then looks at the features that make modern type systems expressive: generics, variance, union and optional types, and inference. Python is dynamically typed, but its optional type hints, checked by tools such as mypy, let you experience static typing in a familiar language. The algorithms a compiler uses to infer types belong to CMPUT-325; here we study what type systems can do for the programmer.

Static and dynamic typing

In a statically typed language, types are checked before the program runs, usually by the compiler. Java, Rust, C and Haskell are statically typed: if you call a method that the declared type does not have, the program does not compile. In a dynamically typed language, values carry their types at run time and operations check them when they execute. Python, JavaScript and Ruby are dynamically typed: a misuse is detected only when the faulty line actually runs, and only on the paths you happen to exercise.

def describe(x):
    if x > 100:
        return "big " + x          # bug: str + number, only on this branch
    return f"small {x}"

print(describe(5))                  # this path works
try:
    print(describe(500))            # the bug appears only now, at run time
except TypeError as err:
    print("TypeError:", err)

small 5
TypeError: can only concatenate str (not "int") to str

A static checker would have rejected `describe` immediately, because `'big ' + x` adds a string to a number for any numeric `x`. Static typing catches whole classes of errors without running the program, documents what functions expect, and lets editors offer accurate completion and refactoring. Dynamic typing makes small programs quicker to write, supports flexible idioms such as duck typing without declarations, and avoids fighting a type checker over code that is correct but hard to express. Large Python codebases at many companies now use type hints and a checker to get some of both.

Strong and weak typing

Strength is a separate axis from when checking happens. A strongly typed language refuses to apply operations to values of the wrong type, or converts only in well-defined, limited ways. A weakly typed language converts values implicitly and liberally. Python is dynamic but strong: `'3' + 4` raises an error. JavaScript is dynamic and weak: `'3' + 4` is the string `'34'` and `'3' * 4` is the number 12. C is static but weak in places: it lets you reinterpret memory through pointer casts, as you saw in CMPUT-201. The terms are informal and best used in comparisons, but the distinction explains a lot of surprising behaviour.

console.log("3" + 4);       // string concatenation
console.log("3" * 4);       // numeric multiplication
console.log([] + {});       // both converted to strings
console.log(0 == "0", 0 == "", "0" == "");   // == converts; not transitive
console.log(0 === "0");     // === compares without conversion

34
12
[object Object]
true true false
false

The last two lines show why weak conversion is dangerous: `0 == '0'` and `0 == ''` are both true, yet `'0' == ''` is false, so equality is not even transitive. JavaScript programmers use the strict operator `===` to avoid conversions, and TypeScript adds a static type system on top of JavaScript to catch these mistakes before run time.

Type hints and static checking in Python

Since Python 3.5, functions and variables can carry type hints: `def area(w: float, h: float) -> float`. The interpreter ignores them at run time; they are read by checkers such as mypy and by editors. A checker analyses the program without running it and reports calls that do not fit. The example below has two bugs that a test suite might miss. mypy, run in strict mode, finds both.

from dataclasses import dataclass

@dataclass
class Item:
    name: str
    price_cents: int

def total(items: list[Item]) -> int:
    return sum(i.price_cents for i in items)

def label(item: Item) -> str:
    return item.name + ": " + item.price_cents      # bug 1: str + int

def find(items: list[Item], name: str) -> Item | None:
    for i in items:
        if i.name == name:
            return i
    return None

cart = [Item("tea", 350), Item("scone", 275)]
print(total(cart))
print(find(cart, "tea").price_cents)                # bug 2: result may be None

$ mypy --strict cart.py
cart.py:12: error: Returning Any from function declared to return "str"  [no-any-return]
cart.py:12: error: Unsupported operand types for + ("str" and "int")  [operator]
cart.py:22: error: Item "None" of "Item | None" has no attribute "price_cents"  [union-attr]

The first two messages both point at bug 1 on line 12: the addition is invalid, and because of it the result type is unknown. The third message is bug 2, and it is the more valuable catch. `find` can return `None`, and the call site uses the result as if it were always an `Item`. In a dynamically typed run, this fails only when a name is missing, perhaps months later in production. Tony Hoare, who introduced null references in 1965, later called them his billion-dollar mistake. Types that make absence explicit, `Item | None` in Python, `Optional<Item>` in Java and `Option<Item>` in Rust, force the caller to handle the missing case. After the fixes below, the checker reports no issues.

from dataclasses import dataclass

@dataclass
class Item:
    name: str
    price_cents: int

def label(item: Item) -> str:
    return f"{item.name}: {item.price_cents}"

def find(items: list[Item], name: str) -> Item | None:
    for i in items:
        if i.name == name:
            return i
    return None

cart = [Item("tea", 350), Item("scone", 275)]
found = find(cart, "tea")
if found is not None:                 # narrowing: inside, found is an Item
    print(label(found))

$ mypy --strict cart_fixed.py
Success: no issues found in 1 source file

Nominal and structural typing

When is one type compatible with another? Under nominal typing, compatibility follows declared names: in Java a class is a `Shape` only if it says `implements Shape`. Under structural typing, compatibility follows structure: any value with the required members fits. Duck typing is structural typing checked at run time. Python's `typing.Protocol` brings structural typing to the static checker: a protocol lists required methods, and any class with matching methods satisfies it, with no inheritance required. TypeScript and Go also use structural typing for interfaces.

from typing import Protocol

class HasArea(Protocol):
    def area(self) -> float: ...

class Square:
    def __init__(self, s: float) -> None:
        self.s = s
    def area(self) -> float:
        return self.s * self.s

class Label:
    def __init__(self, text: str) -> None:
        self.text = text

def total_area(shapes: list[HasArea]) -> float:
    return sum(s.area() for s in shapes)

print(total_area([Square(2), Square(3)]))     # fine: Square has area()
print(total_area([Square(2), Label("x")]))    # rejected: Label has no area()

$ mypy --strict protocols.py
protocols.py:20: error: List item 1 has incompatible type "Label"; expected "HasArea"  [list-item]

Generics and parametric polymorphism

Generic code works for many types while keeping track of which one is in use. A function that returns the first element of a list should return an `int` for a list of integers and a `str` for a list of strings. Without generics you would either write one function per type or give up and return an unspecified type, losing checking. A type variable expresses the relationship: if the argument is a list of `T`, the result is a `T`. This is parametric polymorphism, the third kind of polymorphism mentioned in lesson 4.

from typing import TypeVar, Callable

T = TypeVar("T")
U = TypeVar("U")

def first(xs: list[T]) -> T:
    return xs[0]

def apply_all(f: Callable[[T], U], xs: list[T]) -> list[U]:
    return [f(x) for x in xs]

n: int = first([3, 1, 2])
s: str = first(["b", "a"])
lengths: list[int] = apply_all(len, ["tea", "scone"])
oops: str = first([3, 1, 2])          # rejected: first returns int here

$ mypy --strict generics.py
generics.py:15: error: Incompatible types in assignment (expression has type "int", variable has type "str")  [assignment]

Python 3.12 added a shorter syntax, `def first[T](xs: list[T]) -> T`, which means the same thing. Java writes `static <T> T first(List<T> xs)`, and Rust writes `fn first<T: Clone>(xs: &[T]) -> T`. In Rust and C++, generic functions are compiled separately for each type they are used with, so generics cost nothing at run time. Java erases type parameters after checking and uses a single compiled version, which is why `List<String>` and `List<Integer>` are the same class at run time.

Variance

If `Cat` is a subtype of `Animal`, is a list of cats a subtype of a list of animals? It seems natural, but for mutable lists the answer must be no. A function that accepts a list of animals could append a dog to it, and if you had passed a list of cats, your list of cats would now contain a dog. Variance is the rule that says how subtyping of the element type affects subtyping of the container. Read-only containers can be covariant: a sequence of cats is a sequence of animals. Mutable containers must be invariant. Function parameter types are contravariant: a function that handles any animal can be used where a function that handles cats is expected.

from typing import Sequence

class Animal:
    def speak(self) -> str: return "..."
class Cat(Animal):
    def speak(self) -> str: return "meow"
class Dog(Animal):
    def speak(self) -> str: return "woof"

def chorus(animals: Sequence[Animal]) -> str:     # read-only: covariant
    return " ".join(a.speak() for a in animals)

def adopt(animals: list[Animal]) -> None:         # mutable: invariant
    animals.append(Dog())

cats: list[Cat] = [Cat(), Cat()]
print(chorus(cats))     # accepted: Sequence[Cat] is a Sequence[Animal]
adopt(cats)             # rejected: list[Cat] is not a list[Animal]

$ mypy --strict variance.py
variance.py:18: error: Argument 1 to "adopt" has incompatible type "list[Cat]"; expected "list[Animal]"  [arg-type]
variance.py:18: note: "list" is invariant -- see https://mypy.readthedocs.io/en/stable/common_issues.html#variance
variance.py:18: note: Consider using "Sequence" instead, which is covariant

Type inference and stronger guarantees

Static typing does not have to mean writing types everywhere. Type inference lets the compiler work out types from how values are used. Haskell and ML can infer the types of whole programs; Rust, Java's `var`, C++'s `auto`, TypeScript and Kotlin infer the types of local variables and closures. Programmers usually annotate function signatures, which serve as documentation and keep error messages local, and let the compiler infer the rest.

Type systems can also express more than the shapes of values. Rust's ownership types track who owns each piece of memory and reject programs with dangling references or data races at compile time, the class of bugs that CMPUT-201's sanitizers found only at run time. The program below tries to use a vector after moving it into another variable; the compiler rejects it and explains why.

fn total(v: Vec<i32>) -> i32 {      // takes ownership of v
    v.iter().sum()
}

fn main() {
    let scores = vec![70, 85, 92];
    let t = total(scores);             // ownership moves into total
    println!("total = {}", t);
    println!("first = {}", scores[0]); // error: scores was moved
}

error[E0382]: borrow of moved value: `scores`
 --> main.rs:9:28
  |
6 |     let scores = vec![70, 85, 92];
  |         ------ move occurs because `scores` has type `Vec<i32>`, which does not implement the `Copy` trait
7 |     let t = total(scores);             // ownership moves into total
  |                   ------ value moved here
8 |     println!("total = {}", t);
9 |     println!("first = {}", scores[0]); // error: scores was moved
  |                            ^^^^^^ value borrowed here after move
  |
note: consider changing this parameter type in function `total` to borrow instead if owning the value isn't necessary
 --> main.rs:1:13
  |
1 | fn total(v: Vec<i32>) -> i32 {      // takes ownership of v
  |    -----    ^^^^^^^^ this parameter takes ownership of the value
  |    |
  |    in this function
help: consider cloning the value if the performance cost is acceptable
  |
7 |     let t = total(scores.clone());             // ownership moves into total
  |                         ++++++++
error: aborting due to 1 previous error
For more information about this error, try `rustc --explain E0382`.

The fix is to lend the vector instead of giving it away: `fn total(v: &[i32])` and `total(&scores)`. The compiler then knows `scores` is still owned by `main` and can be used afterwards. Ownership and borrowing are a type-system answer to memory safety without garbage collection, and lesson 9 shows that the same rules prevent data races between threads.