Multiple dispatch¶

The problem with left-operand dispatch¶

Ordinary method resolution dispatches on one type: the type of self. That is not enough for a binary operator, which has two operand types to consider. Python's workaround is a protocol built from three separate pieces: __add__ tries to handle the right operand by type-checking it, NotImplemented signals "not my type" so the interpreter can retry with the right operand's own __radd__, and library authors are expected to implement both methods, symmetrically, on every type that wants to participate:

class X:
    def __add__(self, other):
        if isinstance(other, X):
            return ...
        return NotImplemented

    def __radd__(self, other):
        if isinstance(other, X):
            return ...
        return NotImplemented

x = X()
3 + x             # accepted by type checkers, then TypeError at runtime
reveal_type(x + x) # Any, even though the real return type is known

Multiple-dispatch operators¶

Binary operators are relations between two operand types.

def dispatch __add__(lhs: X, rhs: Y) -> Z:
    ...

x + y

Dispatch requirements¶

A trait can require one element of a multiple-dispatch operation by writing a dispatch member without a body, the same as any other trait obligation:

trait Addable:
    def dispatch __add__(lhs: Self, rhs: Self) -> Self

Ambiguous dispatch is an error¶

Two dispatch definitions can each be applicable to the same call without either being more specific than the other:

def dispatch __add__(lhs: Cat, rhs: Animal) -> str:
    ...

def dispatch __add__(lhs: Animal, rhs: Dog) -> str:
    ...

Cat() + Dog()  # error: ambiguous between both definitions above

Dispatch across projects and hierarchies¶

Because a dispatch definition is not owned by either operand's type, two projects can each contribute an overload for their own pair of types without either project importing the other:

# in project p_x
def dispatch __add__(lhs: X, rhs: Y) -> X:
    ...

# in project p_y
def dispatch __add__(lhs: Y, rhs: X) -> X:
    ...

No reflected binary methods¶

The matching dispatch can be supplied wherever dispatch definitions for that generic operation are allowed. It is not owned by the left operand. Lucid does not need reflected binary methods such as __radd__.

No NotImplemented operator negotiation¶

Lucid does not use NotImplemented as an operator negotiation protocol. Dispatch applicability decides whether an operation is available.

Dispatch beyond operators¶

Every example so far has been a binary operator, but dispatch is not specific to operators — it is a general way to give an ordinary function a growing, independently-checked set of cases, one per argument type. Walking a nested structure built from unrelated container types is a natural fit: each container gets its own case, and recursion resolves the next case by whatever type shows up at that level:

def dispatch tree_map[A, B](tree: list[A], f: (A) -> B) -> list[B]:
    return [tree_map(item, f) for item in tree]

def dispatch tree_map[X, A, B](tree: dict[X, A], f: (A) -> B) -> dict[X, B]:
    return {k: tree_map(v, f) for k, v in tree.items()}

def dispatch tree_map[A, B](tree: A, f: (A) -> B) -> B:
    return f(tree)

A third party can add a tree_map(tree: SomeClass[A], ...) case for their own container type without touching list, dict, or this code at all — the same extensibility Dispatch across projects and hierarchies already described, applied to a plain function instead of an operator:

def dispatch tree_map[A, B](tree: SomeTree[A], f: (A) -> B) -> SomeTree[B]:
    return SomeTree(tree_map(tree.left, f), tree_map(tree.right, f))

def dispatch tree_reduce[A, B](tree: list[A], f: (B, A) -> B, init: B) -> B:
    acc = init
    for item in tree:
        acc = tree_reduce(item, f, acc)
    return acc

def dispatch tree_reduce[X, A, B](tree: dict[X, A], f: (B, A) -> B, init: B) -> B:
    acc = init
    for v in tree.values():
        acc = tree_reduce(v, f, acc)
    return acc

def dispatch tree_reduce[A, B](tree: A, f: (B, A) -> B, init: B) -> B:
    return f(init, tree)

No @overload¶

Python's @overload fakes multiple signatures for one function: each @overload-decorated stub has a body of ..., existing only for the type checker, while a single, separately-written implementation underneath does the real work for every case:

@overload
def parse(s: str) -> int: ...
@overload
def parse(s: bytes) -> int: ...
def parse(s):
    return int(s)

Lucid needs no separate mechanism for this: it is exactly Dispatch beyond operators, applied to a function with no shared body across its cases:

def dispatch parse(s: str) -> int:
    return int(s)

def dispatch parse(s: bytes) -> int:
    return int(s.decode())

Applicability includes how many arguments a call passes, not just their types — every example above happens to keep that fixed, but nothing requires it. A call with two arguments is simply not applicable to a dispatch definition with one parameter, the same way a call with a str argument is not applicable to a definition typed for bytes; different-arity definitions can never be ambiguous with each other, since a given call is applicable to at most one arity to begin with.

def dispatch pop(self) -> T:
    ...

def dispatch pop(self, i: int) -> T:
    ...

def dispatch pop(self, i: int, j: int) -> list[T]:
    ...

Promotion¶

A binary operator between two different numeric types — int32 + float32 — still looks like a job for one dispatch case per type pair. For a family with even a handful of members, that is quadratic: every pair of numeric types needs its own case, most of them following the exact same rule ("convert both to the wider type, then add"), duplicated once per pair instead of stated once.

The fix is to stop enumerating pairs and instead give each type exactly one fact about itself: every other type it promotes to. Promotes demands nothing but that fact, declared as a classvar rather than a method — a type relationship belongs at the definition site, the same principle already behind definition-site variance and mutability views, not something computed by running code:

trait Promotes:
    classvar promotes_to: !set[type]

class int32(Promotes):
    classvar promotes_to = {int64, float32, float64, complex64, complex128}

class float32(Promotes):
    classvar promotes_to = {float64, complex64, complex128}

class float64(Promotes):
    classvar promotes_to = {complex128}

class complex128(Promotes):
    classvar promotes_to = {}

promote[A, B] finds the two types' common target directly from these sets — no walk required, since each set already contains everything reachable, not just one step of it. A generic arithmetic operator can then be written once, for the whole family, instead of once per pair:

def dispatch __add__[A: Promotes, B: Promotes](lhs: A, rhs: B) -> promote[A, B]:
    common = type promote[A, B]
    return common(lhs) + common(rhs)