Shapes¶

A numeric array's shape — how many dimensions it has, and how large each one is — is exactly the kind of fact Type vocabulary already wants visible at the definition site, the same way mutability and variance are. typing.Shape and typing.Shape[...] give it a type, and this covers the operations built on top of it: taking one apart, combining two, and checking the constraints an operation like reshape or matrix multiplication actually needs.

`typing.Shape` and `typing.Shape[...]`¶

typing.Shape[2, 3, 4] borrows its syntax from Literal[1, 2, 3] — a builtin name, subscripted with however many type arguments the caller writes — but not its meaning. Literal[1, 2, 3] is a union: satisfied by any one of the three. typing.Shape[2, 3, 4] is a product: satisfied only by exactly that sequence, in that order — the same fixed-arity, exact-match structure an anonymous record like (x: int, y: int) already has, just with positions instead of names. typing.Shape is the trait every typing.Shape[...] instantiation satisfies.

A position ordinarily holds a Literal[int], but any position can hold a type variable instead, for a dimension whose size isn't fixed — an ordinary generic parameter sitting in one slot, the same way it would sit in any other type expression:

def batch_normalize[Batch: int](
    x: Array[Float32, typing.Shape[Batch, 3, 224, 224]],
) -> Array[Float32, typing.Shape[Batch, 3, 224, 224]]:
    ...

An array that doesn't track its shape at all uses none instead of a typing.Shape[...], so one class covers both:

class Array[D: DataType, S: typing.Shape | none]:
    ...

checked: Array[Float32, typing.Shape[2, 3, 4]]
unchecked: Array[Float32, none]

At runtime, a shape value is an ordinary !list[int] — hashable, immutable, exactly the sequence Hashable sequences already recommends for this job. typing.Shape[...] is the type such a value can be checked against, the same relationship any other type has to its values; a concrete ![2, 3, 4] satisfies typing.Shape[2, 3, 4] the same way (x=1, y=2) satisfies (x: int, y: int).

Everything from here on is a member of typing.Shape itself; the typing.Shape. qualifier is dropped from the definitions below, the same way a class's own methods never write the class's name in front of a call to another one of its own factories. Only a caller from outside needs the qualified name.

Shape is a sequence¶

Because Shape[...] fixes both its length and its order, indexing, slicing, concatenation, and equality already mean exactly what they mean for any other sequence, extended into type position the same way Arithmetic on literal types already extends +/-/* to a pair of Literal[int]:

type Get[S: Shape, I: int] = S[I]
type DropAt[S: Shape, I: int] = S[:I] + S[I + 1:]
type InsertAt[S: Shape, I: int, D: int] = S[:I] + Shape[D] + S[I:]
type Concat[A: Shape, B: Shape] = A + B
type Reverse[S: Shape] = S[::-1]

None of these need to walk the shape position by position: a fixed index or a fixed slice boundary already says exactly which positions are wanted, whether the other end is a concrete length or a generic parameter standing in for one.

Transpose — swapping the last two axes, the case that actually comes up, as opposed to swapping two arbitrary indices — is the same slicing, just naming both ends directly instead of walking to them:

type SwapLast2[S: Shape] = S[:-2] + Shape[S[-1], S[-2]]

Batch dimensions¶

The single most common shape pattern in real numeric code is "some number of leading batch dimensions, then a fixed trailing shape," and a fixed-length slice from the right already answers it:

type BatchDims[S: Shape] = S[:-3]
type TrailingShape[S: Shape] = S[-3:]

S[:-3] is every position except the fixed trailing three, however many leading positions there are; S[-3:] is exactly those three. A slice's other boundary is implicit in "everything else," so pulling out an unbounded batch prefix needs no name or index of its own — only the fixed end needs a number.

Broadcasting¶

Two dimensions are broadcast-compatible if they're equal, or either one is exactly 1. promote[A, B] already established the pattern for a type-level conditional — an ordinary if/else, reused in type position the same way +/-/* already are:

type BroadcastDim[A: int, B: int] =
    A if A == B else
    B if A == 1 else
    A if B == 1 else
    error   # A and B are not broadcast-compatible

Broadcasting aligns from the right: peel the last position off each shape, combine those two with BroadcastDim, and recurse on what's left. Once either shape runs out, the other's remaining prefix passes through unchanged — a shorter shape's missing leading dimensions behave as if they were 1, contributing no constraint:

type BroadcastAligned[A: Shape, B: Shape] =
    B if A == Shape[] else
    A if B == Shape[] else
    BroadcastAligned[A[:-1], B[:-1]] + Shape[BroadcastDim[A[-1], B[-1]]]

This resolves the same way Reverse and Concat do: a self-reference resolved lazily, the same as any other recursive type alias — just walking from the right instead of the left, since that's the end broadcasting actually aligns on.

Matrix multiplication's shape rule¶

Matmul needs the inner dimensions to match exactly and the batch dimensions — everything before the last two axes — to broadcast:

type MatmulShape[A: Shape, B: Shape] =
    Shape[*BroadcastAligned[A[:-2], B[:-2]], A[-2], B[-1]]
    if A[-1] == B[-2] else
    error   # inner dimensions don't match

A shape with fewer than two dimensions needs no separate case: A[-2] on a shape that short is already out of range, the same compile-time bounds error indexing anywhere else out of range already is — this gets rejected for free, not as a case this alias has to spell out.

Reshape validity¶

Reshaping is valid only when the total element count is unchanged — the one property in this whole library that's a genuine computation, not a structural comparison. Product folds literal multiplication over a shape the same recursive way BroadcastAligned folds BroadcastDim:

type Product[S: Shape] = 1 if S == Shape[] else S[0] * Product[S[1:]]

type Reshape[S: Shape, NewShape: Shape] =
    NewShape if Product[S] == Product[NewShape] else
    error   # element count doesn't match

Concatenation along an existing axis needs the same kind of computed value — the sizes of the concatenated axis add, and every other axis has to match exactly, which is now an ordinary slice comparison:

type ConcatAxis0[A: Shape, B: Shape] =
    Shape[A[0] + B[0], *A[1:]]
    if A[1:] == B[1:] else
    error   # every axis but the concatenated one must match

Dispatch by shape¶

Stacking N arrays along a new leading axis needs N itself as a literal type—the count of however many arrays were passed, not a dimension already written down anywhere. The type-level stack operation accepts operand shapes directly, infers that count from the argument list, and checks ranks and dimensions before constructing the result shape.

Lucid does not dispatch by shape. Multiple dispatch resolves on runtime class, and shape is a phantom type parameter of an array, not a separate runtime class. Two dispatch definitions whose parameters differ only by shape would therefore erase to the same runtime dispatch key, so the checker rejects them instead of picking one by declaration order.

Shape-specific behavior belongs in ordinary generic functions whose signatures state the required shape relationship. The checker can then prove the call valid from the type-level shape operations above, while the generated function body stays one ordinary implementation.