Generics: one algorithm, many types

Every language with generics answers the same three questions: how does a type parameter get its value, what may the body do with it, and what exists at run time? The industry’s answers range from one erased body with casts underneath, through boxed interfaces, to a real body per type whose constraints arrived decades late — so a bad call exploded inside the template. Mica answers the third question with monomorphization — one real specialization per concrete type — and makes the second question strict from the start: the body may only do to T what its capabilities grant.

The example is Generics.

The gen clause

function Twice(item : U) : U;
gen
    U is numeric;
begin
    Twice := item + item;
end;

gen declares the type parameters, and each one names its capabilities — what a concrete type must be able to do to stand in. numeric admits every integer and floating type and nothing else. The vocabulary is closed and the compiler will list it for you if you guess wrong:

analyzer error 5212: unknown capability 'comparable' in the constraint of
type parameter 'T'; a constraint is one of: numeric, ordered, equality,
logical, integral, fractional, dereferenceable, addressable, plain,
convertible, negatable, ordinal, bits

Inference: each call teaches the compiler a type

small := 5;              { int32   }
large := 3000000000;     { int64   }
fraction := 1.25;        { float64 }
WriteLn("  Twice of int32 5: %d", Twice(small));
WriteLn("  Twice of int64 3000000000: %lld", Twice(large));
WriteLn("  Twice of float64 1.25: %lf", Twice(fraction));

Inference: each call teaches the compiler a type
  Twice of int32 5: 10
  Twice of int64 3000000000: 6000000000
  Twice of float64 1.25: 2.500000

Three calls, three inferred type arguments, three real specializations in the binary — and the middle line is the proof they are real: 6,000,000,000 does not fit an int32, so the int64 doubling demonstrably ran in int64. A second call with a type already seen reuses its specialization; instantiation is deduplicated by the concrete type-argument set.

Inference unifies, it never converts: both arguments of a Smallest(a : U, b : U) must agree on one U:

analyzer error 5208: type parameter 'U' is inferred as both 'int64' and
'float64' in this generic call; one type parameter cannot bind two
different types

When the arguments say nothing

Inference reads the type arguments off the value arguments, which works until a type parameter appears nowhere in them. A factory is the clean case: it takes nothing that mentions T and answers a T.

function Zero() : T;
gen
    T is numeric;
begin
    Zero := 0;
end;

Nothing in Zero() says what T is. What the call is assigned to does, and that is where the compiler reads it from:

whole := Zero();      { T is int32, because whole is }
fraction := Zero();   { T is float64, because fraction is }

The call looks like any other call, because it is one. The target imposes its type on the call before the call is analyzed — the same top-down imposition a bitset assignment already makes on a bare constructor — and the deduction that follows is the ordinary one aimed at the return position instead of a parameter position. A structural return type carries its parameters out of the target the same way a structural parameter carries them out of an argument, so a function Wrap(x : T) : Box of T binds T from a Box of int32 target through the same field walk.

Three contexts impose a type, and they cover nearly everything a factory is used for: an assignment, a local initializer, and a return.

var seed : int32 := Zero();    { the declared type imposes }

function Forwarded() : float64;
begin
    Forwarded := Zero();       { the return type imposes }
end;

Where no context imposes one — a call standing as an argument to another call — the type arguments are written out, spelled exactly as a type reference spells them:

WriteLn("%d", Zero of int32 ());

The argument list still follows, always: a routine is called with its argument list and never read by name, which is the same rule that lets Mica do without function pointers. Write too many arguments, or name a type that does not exist, and the call is refused before anything is bound.

A generic body may declare its own types

A specialization is a clone of its template’s body, and the clone carries what the body declares — including a type:

function Accumulate(x : T) : T;
gen
    T is numeric;
type
    Pair = record a : T; b : T; end;
var
    p : Pair;
begin
    p.a := x;
    p.b := x + x;
    Accumulate := p.a + p.b;
end;

Each specialization gets its own Pair, laid out at the type that specialization was instantiated for. A nested subprogram is still refused (5424), and the reason is the difference between the two: a type is a type expression, while a subprogram is a scope of its own with parameters and a static link, so monomorphizing one would mean authoring a second specialization inside the first.

Constraints cut both ways

This is the part template systems famously shipped without for decades, and here it is checked in both directions.

The call’s duty: a type argument must satisfy the constraint —

analyzer error 5210: type argument 'string' for type parameter 'U' does
not satisfy its constraint (requires numeric)

The body’s rights: the generic may only do to U what the constraint grants. Smallest compares with <, so numeric is not enough — write it with U is numeric and the body is refused, before any call exists:

analyzer error 5116: data type 'U' cannot be used in comparison operation
'less' (requires ordered)

function Smallest(a : U, b : U) : U;
gen
    U is ordered;
begin
    if a < b then
        Smallest := a
    else
        Smallest := b;
end;

Because the body was checked against the constraint alone, no legal instantiation can ever break it — the instantiation error novel, three screens deep inside someone else’s header, is structurally impossible.

Generic types

Type parameters for the type section are declared at the unit level, and a generic type is one declaration standing for a family:

gen
    T is numeric;

type
    Triple of T = array[0..2] of T;

var
    vi : Triple of int32;
    vf : Triple of float64;

A generic function then rides the family — the vector arrives by value like every fixed array, and the element type follows as the result type:

function Total(v : Triple of U) : U;
gen
    U is numeric;

Generic types: one declaration, a family
  Total of a Triple of int32: 42
  Total of a Triple of float64: 0.875000

Four declarations on the screen; four real types and two real functions in the binary; nothing shared, boxed, or dispatched at run time.

Shapes are type arguments too

A gen entry has a second face. Beside the type parameter and its capabilities, a value parameter declares a compile-time integer — N : int64 — and a template can then be generic over a shape:

gen
    T is numeric;
    N : int64;

type
    Series of (T, N) = vector[N] of T;

var
    x : Series of (float64, 4);
    a : Series of (int64, 3);

One declaration, a family of shapes. The two faces read as what they are: a type parameter constrains by capability (is), a value parameter by type (:), and the of-list binds them in declaration order. N may stand in any dimension or bound position — vector[N], matrix[R, C], array[1..N] — and inside the body it is an ordinary constant of its declared type:

function Inner(u : Series of (T, N), v : Series of (T, N)) : T;
gen
    T is numeric;
    N : int64;
var
    i : int64;
begin
    Inner := 0;

    for i := 0 to N - 1 do
        Inner := Inner + u[i] * v[i];
end;

Inner(x, y) over two Series of (float64, 4) infers T = float64, N = 4 from the argument’s element and its dimension — the same deduction that binds an element type, extended to the shape — and monomorphizes one specialization per shape. A factory return binds the other way, from the target, exactly as Zero() did:

f := Fill(2.5);       { f : Series of (float64, 4) — N = 4 read off the target }

A named constant denotes the same instantiation its number denotes. Arr of (int64, Cols) at Cols = 3 is Arr of (int64, 3) — one type, assignable both ways, served by one specialization — and a constant declared as an expression over another constant (Rows = Cols + 1) folds the same way. A value parameter is identified by the number it folds to, never by the spelling that produced it, and the rule is observable in the debugger: step into a specialization and the frame names the shape it was built for, SumV__int64__3, in the file the template was written in.

A shape-generic template crosses a unit boundary like any other export: mark it exp, and the emitted contract carries the value face beside the capability constraints, so an importing build instantiates the same family at its own shapes — units and libraries shows the road.

And when the shape needs no domain name at all, the language’s own form stands directly in the signature — function Inner(u : vector[N] of T, …) works without declaring Series first, and it is how the standard library’s math unit spells its entire shaped surface. A template earns its keep as a domain name — Series, Map of (K, V) — never as a re-spelling of a shape the language already owns.

What the compiler refused

What this does not do

• No implicit conversions across a type parameter. The 5208 refusal is the policy: unify or say what you mean at the call.
• Monomorphization costs binary size, visibly. Each concrete type-argument set is real code. That is the trade for zero runtime dispatch — the same trade C++ and Rust chose, made with open eyes.
• The capability vocabulary is closed. Thirteen words, compiler-owned. There is no user-defined capability (no traits, no concepts) in this release — a constraint states machine-level abilities, not protocols.
• Generic generators exist — a stream of U composes with the generator machinery — and this tutorial leaves them as its reader’s experiment. A stream element may be any scalar, integer or floating alike; an aggregate element — a record, an array, a string — still waits for the slice that carries a copy across the suspension.
• A value parameter is integral, and it stands alone only beside a type parameter. No strings, no records in a value position — the integer families size shapes and bounds, and that is the whole job. A template whose parameters are all values is refused (5430) in this release.
• A dimension built from an expression over a value parameter — array[0..N - 1] — instantiates at concrete shapes only. Crossing it into a generic function is refused by name (5433): only the bare parameter — vector[N], array[1..N] — re-derives inside another template in this release.

Try it

git clone https://gitlab.com/mica-lang/mica-container.git
make -C mica-container/examples/Generics run

Change Smallest’s constraint to is numeric and meet 5116 pointing at the < inside the body — the two-sided check in one edit. Then call Twice("ab") and watch 5210 refuse the call instead of the body.

Then try the factory two ways. Assign Zero() to an int32 and to a float64 and watch one template answer both. Now move that same call into a WriteLn argument, where nothing imposes a type, and meet 5209 naming the written-out form — then write it, Zero of int32 (), and watch it compile.

Then give a shape a name. Declare const Cols = 3;, a Series of (int64, Cols) and a Series of (int64, 3), and assign one to the other — one type, by the canonical-name rule. Then index element 9 of a three-element shape inside the generic body and watch 5128 refuse it in the specialization, where the shape has its number.

Next

Units and libraries — how a program grows past one file: exp deciding what escapes a unit, the import doctrine that makes nothing ambient, and a library whose emitted contract another build imports.