Generics and Type Variables

The previous lesson measured that an annotation gets stored and does not get checked; four of five calls were violations and the number that errored at run time was zero. The measured function’s annotation carried two concrete type names: name: str, age: int. Such a signature declares a contract that only works with those two types, and what it declares is explicit.

A great many functions, though, are indifferent to type. A function giving a list’s first item does not care what the list is filled with — but even not caring, it knows one thing: what it returns is the same type as what is inside the list. This bond cannot be written with a concrete type name. This lesson’s question is whether that bond can be written at all, and what it earns you when it is. The measure is again the course’s axis: which notation can declare which violation?

The Two Ends of a Concrete Type Name

There are two easy ways to write the first function, and both cost you something.

The first way is to loosen the annotation: def first(seq: list) -> object. This signature accepts every list, it is correct, and it rejects no call needlessly. What it loses is the bond — saying “an object” for the return says nothing about the value in the caller’s hand.

The second way is to concretize the annotation: def first(seq: list[int]) -> int. This signature declares the return exactly. What it loses is the function itself — even though the body works with every list, the signature only accepts lists of integers, and a valid call made with a list of strings is also counted a violation.

There seems to be no middle ground between the two: either you give up the bond, or you narrow the function. Generics are exactly the notation that removes this dilemma.

The Type Variable

A type variable is a name that stands in for a type name. The line T = TypeVar("T") produces such a name; T is not itself a type, it marks where a type will stand in the signature.

from typing import TypeVar

T = TypeVar("T")


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

This signature says two things. First: the argument is a list filled with any type — the accepted set did not narrow. Second: the return is of the same type as what is inside that list. The same name appearing in two places is what creates the bond; whatever T is in one spot, it is that in the other too.

A structure whose signature carries the same name is called generic. A generic can be on a function just as it can be on a class: a class deriving from Generic[T] can spread the type of the value it carries into its own signatures.

A type variable does not have to be left completely free. A bound type variable declares an upper limit — TypeVar("Text", bound=str) only accepts strings and their subclasses. A constrained type variable, by contrast, declares a finite list of options: TypeVar("Numeric", int, float). Both kinds of limit can be read at run time; the measurement shows the difference between these limits being readable and being checked, too.

The Measurement’s Setup

The measurement compares four notations at four call sites. Every call site consists of two things: a call to first, and an operation applied to its result. The operation expects a type from the result — + 1 expects an integer, .upper() expects a string. A call site being a violation means the list’s item type does not match the type the operation expects.

The measurement’s assumptions:

• TL9 — The oracle is the setup itself: which of the four call sites is a violation is decided by the list’s item type and the type the operation requires; both were written by the lesson’s author.
• TL10 — Two of the four call sites are violations. The set is kept small, because what is measured is not the violation rate, it is the set of violations each notation can declare.
• TL11 — The inference step is modeled within the lesson: it produces a call site’s return type from a return annotation and substitutes the type variable with the argument’s item type. A full checker is not built in this lesson.
• TL12 — “Declared” means the notation reports a problem at that call site; it happens for one of two reasons: the argument does not match the annotation, or the inferred return type is other than what the operation expects.
• TL13 — “Correct” means the declaration really lands on a violating call site. “Missed” means the violation was not declared. “False alarm” means a declaration was made at a valid call site.
• TL14 — An object return is never counted equal to any operation’s expected type; the loose notation declaring at all four call sites is a consequence of this rule.
• TL15 — The runtime column is measured by actually running the four call sites, and only type-originated exceptions are counted.
• TL16 — In the generic class measurement, identity is shown with is; no identity number is printed.
• TL17 — The measure for bound and constrained type variables is whether the bound is readable and whether a call breaking the bound runs. In the two-argument measurement, the unification step is also modeled within the lesson: the type variable binds on its first match, and consistency of the bond is tested at subsequent matches.

Measurement

"""Generics: which notation can declare which violation."""
from typing import Generic, TypeVar

T = TypeVar("T")


def first(items):
    return items[0]


NOTATIONS = (("no annotation", None, None),
            ("list -> object", list, object),
            ("list[int] -> int", list[int], int),
            ("list[T] -> T", list[T], T))

# call site: the source list's item type, the type the following operation requires
SITES = (("first([1, 2]) + 1", int, int),
          ("first(['a', 'b']) + 1", str, int),
          ("first(['a', 'b']).upper()", str, str),
          ("first([1, 2]).upper()", int, str))


def accepts(param, item):
    """Does the annotation accept this call site's argument."""
    inner = getattr(param, "__args__", (None,))[0]
    return param is None or param is list or inner is T or inner is item


def infer(ret, item):
    """Can the call site's return type be inferred from the return annotation."""
    if ret is None:
        return None
    return item if ret is T else ret


print(f"{'notation':<18s} {'inferred':>10s} {'declared':>11s} {'correct':>6s}"
      f" {'missed':>10s} {'false alarm':>13s}")
for name, param, ret in NOTATIONS:
    inferred = declared = correct = missed = false_alarm = 0
    for site, item, expected in SITES:
        real_violation = item is not expected
        c = infer(ret, item)
        inferred += c is not None
        flag = (not accepts(param, item)) or (c is not None and c is not expected)
        declared += flag
        correct += flag and real_violation
        missed += real_violation and not flag
        false_alarm += flag and not real_violation
    print(f"  {name:<16s} {f'{inferred}/4':>10s} {declared:11d} {correct:6d}"
          f" {missed:10d} {false_alarm:13d}")

REAL = (lambda: first([1, 2]) + 1,
          lambda: first(["a", "b"]) + 1,
          lambda: first(["a", "b"]).upper(),
          lambda: first([1, 2]).upper())
failing = 0
for fn in REAL:
    try:
        fn()
    except (TypeError, AttributeError):
        failing += 1
print(f"call sites {len(SITES)}, real violations "
      f"{sum(o is not g for _, o, g in SITES)}, "
      f"erroring at runtime {failing}")


def combine(a, b):
    return a if a == b else b


PAIRS = ((int, int), (int, str), (str, str))
SIGNATURES = (("a: object, b: object", (object, object)),
           ("a: T, b: object", (T, object)),
           ("a: T, b: T", (T, T)))


def unify(signature, types):
    """Binds the type variable on first match, then tests consistency."""
    binding = {}
    for annotation, type_ in zip(signature, types):
        if annotation is T:
            if T in binding and binding[T] is not type_:
                return False
            binding[T] = type_
        elif annotation is not object and annotation is not type_:
            return False
    return True


print()
print(f"{'two-argument signature':<24s} {'declared':>11s}")
for name, signature in SIGNATURES:
    print(f"  {name:<22s} "
          f"{sum(not unify(signature, c) for c in PAIRS):11d}")
print(f"pairs {len(PAIRS)}, with differing types "
      f"{sum(x is not y for x, y in PAIRS)}, "
      f"combine(1, 'a') -> {combine(1, 'a')!r} (runtime raised no error)")


class Box(Generic[T]):
    def __init__(self, value: T):
        self.value = value

    def get(self) -> T:
        return self.value


b = Box[int]("string")
print()
print(f"Box[int]('string').get() -> {b.get()!r}")
print(f"type(b) is Box -> {type(b) is Box}; "
      f"Box[int] is Box[str] -> {Box[int] is Box[str]}")
print(f"isinstance(b, Box) -> {isinstance(b, Box)}")
try:
    isinstance(b, Box[int])
    print("isinstance(b, Box[int]) -> tested")
except TypeError:
    print("isinstance(b, Box[int]) -> cannot be tested")
print(f"get's annotation: {Box.get.__annotations__}")

Text = TypeVar("Text", bound=str)
Numeric = TypeVar("Numeric", int, float)
print()
print(f"bound type variable's bound: {Text.__bound__}")
print(f"constrained type variable's options: {Numeric.__constraints__}")


def widen(d: Text) -> Text:
    return d


print(f"widen(7) -> {widen(7)!r} (the bound was not checked at runtime)")

notation             inferred    declared correct     missed   false alarm
  no annotation           0/4           0      0          2             0
  list -> object          4/4           4      2          0             2
  list[int] -> int        4/4           3      2          0             1
  list[T] -> T            4/4           2      2          0             0
call sites 4, real violations 2, erroring at runtime 2

two-argument signature      declared
  a: object, b: object             0
  a: T, b: object                  0
  a: T, b: T                       1
pairs 3, with differing types 1, combine(1, 'a') -> 'a' (runtime raised no error)

Box[int]('string').get() -> 'string'
type(b) is Box -> True; Box[int] is Box[str] -> False
isinstance(b, Box) -> True
isinstance(b, Box[int]) -> cannot be tested
get's annotation: {'return': ~T}

bound type variable's bound: <class 'str'>
constrained type variable's options: (<class 'int'>, <class 'float'>)
widen(7) -> 7 (the bound was not checked at runtime)

Four Notations, Four Results

The upper table’s last three columns count three independent defects: a missed violation, a false alarm, and an uninferrable return type. Only one of the four notations zeroes out all three at once.

The unannotated notation infers no return type at all: 0/4. The declaration count is 0, missed is 2. False alarm is also 0 — a signature that says nothing cannot be mistaken either. This row is a baseline: what the three notations below earn is measured by how far they move from this row.

The loose notation infers a return type at all four of the four call sites: 4/4. But the type it infers is object every time, and no operation expects object. Declared 4, correct 2, false alarm 2. A notation declaring at every call site is a notation telling no call site apart from another. Missed dropped to 0, and in exchange, false alarm rose from 0 to 2.

The overly concrete notation makes three declarations: 2 correct, 1 false alarm. The false alarm comes from the valid call made with a list of strings — the signature rejects that call at the argument level, even though the body works with it without a problem. One of the correct declarations comes from the same place too, meaning it gives the right result for the wrong reason: the violation sits on the return side, while the signature blames the argument.

The generic notation infers the return type at all four of the four call sites, makes 2 declarations, both correct, missed 0, false alarm 0. It zeroes missed the way the loose notation does, and zeroes false alarm the way the unannotated notation does. Both at once, in a single row.

The gain’s source sits in one place: the bond. The other three notations build no relationship between the argument and the return — each gets a separate type written on it, or none at all. The generic notation declares the relationship by using a single name in two places, and inference can produce a call-site-specific answer from that relationship.

Using the Same Name in Two Arguments

The bond’s power is not limited to the return. The second table measures a two-argument function: combine, which compares two values and returns one of them. If the contract is to say “the two arguments must be of the same type,” the only way to write that is using the same type variable in two parameters.

The measurement models this with a unification step: the type variable binds to a type on its first match, and if the same variable is seen at the next parameter, whether the bond holds is checked.

Three signatures, three pairs. The signature written with object makes 0 declarations — there is a pair with differing types, but the signature says nothing that could tell them apart. a: T, b: object also gives 0: when the type variable appears in only one spot, no bond forms, because a bond needs two ends. a: T, b: T, by contrast, makes 1 declaration, and that is the one real mismatch in the set.

The last line answers the “who caught it” question again: the call combine(1, "a") raises no error, it returns a value. Run time does not see this mismatch; the only thing that sees it is the repeated name in the signature.

Who Caught It in This Measurement

The layer making the declarations is the side reading the annotation, and in this lesson only its inference step was modeled; a full checker is the subject of the next lesson.

The runtime row gives a separate result: 2 errors come out at the four call sites, meaning both real violations do get caught. This does not contradict the previous lesson’s 0 result — there, the body was a formatting that accepted every type; here, the operation outside the body really uses the type. The difference sits at three points. Run time gives the error after the call, once first has already returned. It only gives it on lines that actually run; had one of the four call sites sat inside a condition that was never satisfied, that violation would have stayed invisible. And what produces the error is not the annotation, it is the operation itself — had the annotation been deleted, the same two errors would have come out at the same places.

The generic notation’s 2 declarations, by contrast, are produced without running anything, purely by looking at the call site. The two layers catch the same violations here; when they catch them is what differs.

What Happens to a Generic Class at Run Time

The lower blocks measure generics’ run-time counterpart, and the result confirms the previous lesson’s claim.

Box[int]("string") is a type violation: the box is declared to carry an integer, and a string is put inside it. The call runs, get() gives the string back, no error. type(b) is Box is true — the produced object’s class is Box; the type in the square brackets does not get baked into the object’s class. Box[int] is Box[str] is false: the two are separate objects, but both produce instances of the same class.

isinstance(b, Box) gives true; isinstance(b, Box[int]), by contrast, cannot be tested. The same result as list[int] in the previous lesson: a parameterized annotation cannot be given directly to a run-time test. The get method’s annotation also carries the type variable itself — not a resolved type, but the name of the spot to be resolved.

The last two lines measure bound and constrained type variables. The bounds can be read: the bound variable’s upper limit is str, the constrained variable’s options are int and float. But the call widen(7), which breaks the bound, runs and returns 7. A bound is an annotation too: it gets recorded, it gets read, it does not get checked.

Summary

• A type variable is a name standing in for a type name; the same name appearing twice in a signature builds a bond between argument and return, and a generic is the notation carrying that bond.
• Four notations diverge at four call sites: the unannotated notation gives 0 declarations and 2 missed, the loose notation gives 4 declarations and 2 false alarms, the overly concrete notation gives 3 declarations and 1 false alarm.
• The generic notation makes 2 declarations, both correct; missed and false alarm are 0. The gain’s source is the bond, not the concreteness of the type names.
• A bond needs two ends: when the same type variable appears in two parameters, a mismatch is declared (1); when it appears in a single parameter, or when object is written, it is not declared (0).
• A bound type variable declares an upper limit, a constrained type variable a finite set of options; both kinds of limit can be read at run time but are not checked.
• A generic class’s type in square brackets does not get baked into the instance’s class: type(b) is Box is true, while an instance test made with Box[int] cannot be performed.

Next Step

In this lesson, only one step of the side reading the annotation was modeled: inferring a call site’s return type. A real static checker does more than this — it scans every call, compares each one’s arguments against the signature, and declares the mismatches without running anything. The next lesson models that checker within the lesson and applies it to the previous lesson’s five calls. The number asked is this: of the four violations, how many does it find, how many does it miss — and why can it not find the ones it misses?