9. Generics

What this is for

You write a function returning the larger of two Ints. A week later you need it for Decimal<2>. Every language answers this, and the answer says what the language actually values:

Burxt takes the last one, and for this page there is only one reason worth knowing: erasure would put a pointer where the value was, and a boxed Decimal<2> is not the thing the money guarantees are about. Everything Burxt promises is about what a value is — an exact decimal is an integer and a scale, a class is its fields laid out in order, a region is a bump pointer. Hand that to a generic and get a pointer back and you have handed away the whole design.

Think of a cookie cutter

A cookie cutter is not a container. You do not put dough in it and get a generic cookie out. You press it into whatever dough you have, and what comes out is a real cookie made of that dough — gingerbread if the dough was gingerbread, shortbread if it was shortbread.

One cutter, three doughs, three real cookies. Not three references to a cookie-shaped idea.

A step closer

In code

Writing one

function identity<T>(x: T) -> T {
    return x;
}

print(identity(3));         // T = Int
print(identity("text"));    // T = String

The type parameter is named where the function is declared, in angle brackets after the name.

There is no turbofish. You never write identity::<Int>(3) or identity<Int>(3), because the argument already says what T is and asking twice is asking you to repeat yourself. Type arguments are inferred by matching each declared parameter type against the actual one, and inference descends through nesting — [T], [T; 4]:

function first<T>(xs: [T]) -> T {
    return xs[0];
}

let mutable names: [String] = [];
let n: Int = push(names, "ada");
print(first(names));        // T = String, from one level down

Classes and enums

class Point { x: Int, y: Int }
class Pair<T> { first: T, second: T }
enum Holder<T> { Empty, Full(T) }

let small: Pair<Int> = Pair { first: 3, second: 4 };
let wide: Pair<Point> = Pair { first: Point { x: 1, y: 2 },
                               second: Point { x: 9, y: 8 } };
print(small.first);
print(wide.second.y);

Those two are genuinely different shapes in memory. Pair<Int> is two cells; Pair<Point> is four. Nothing is boxed to make them the same size — which is exactly what one-copy-per-type buys.

Building one out of nothing

Type arguments can also come from where the value lands rather than from an argument:

class Bag<T> { items: [T], count: Int }

function empty_bag<T>() -> Bag<T> {
    return Bag { items: [], count: 0 };
}

let mutable names: Bag<String> = empty_bag();   // T = String, from the annotation
let numbers: Bag<Int> = empty_bag();            // T = Int, same source, second stamp
print(names.count);
print(numbers.count);

empty_bag() takes no arguments, so there is nothing to infer T from — except the type already written on the left. Reading it from there is the same principle as the missing turbofish: writing empty_bag::<String>() would be the language demanding an answer it is already holding.

This works when every field can be built without a T in hand — an empty [T] needs no element. A Bag<T> with a first: T field cannot be built out of nothing, and asking says so by name.

A generic name always needs its arguments. let x: Pair = ... is refused, and so is this:

enum Holder<T> { Empty, Full(T) }
let nothing = Holder.Empty;

error: `Holder.Empty` does not say what `T` is, and nothing here does. Write the type
       where the value lands — `let x: Holder<...> = Holder.Empty;` — or pass it
       somewhere that names it.

Methods

A method on a generic type names the parameter in the receiver:

class Pair<T> { first: T, second: T }

function (self: Pair<T>) left() -> T {
    return self.first;
}

function (mutable self: Pair<T>) swap() -> Int {
    let keep: T = self.first;
    self.first = self.second;
    self.second = keep;
    return 0;
}

Pair<Int>.swap and Pair<Point>.swap are separately compiled, because for Point each of those three assignments moves two cells instead of one. Same source, different instructions.

Bounds

A bare T can be moved, stored and returned. It cannot be compared, added or printed, because nothing said it could be. To ask for more, name a bound:

function largest<T: Ordered>(a: T, b: T) -> T {
    if a > b {
        return a;
    }
    return b;
}

print(largest(3, 9));
print(largest($19.99, $4.50));
print(largest("apple", "pear"));

Two bounds ship, and each is exactly a set the language already has:

A bound cannot promise more than the language delivers. There is no Addable, because + on two Decimals has a scale rule that a bound would have to lie about.

A String is ordered by its bytes — so "Zebra" comes before "apple", because Z is 90 and a is 97. That is not alphabetical order in any language, and it is deliberate: locale collation means choosing a language and one of that language’s several orders, which is a decision nobody wrote down. Byte order is the one ordering that needs no decision and is identical on every machine, which is what a sort has to be to stay reproducible.

When a bound is missing, the error names the operator rather than the bound, because the operator is the thing you were actually trying to use:

error: `largest` needs `T: Ordered`, and Bool has no order. Ordered is Int,
       Decimal and String — the types `<` works on.

Bounds are checked where the type argument is chosen — at the call site — so the error points at the call that made the choice, not at the body that needed it.

What is refused

• print(x) on a bare T. Printing has to know how wide the value is and how to format it. Add a bound, or take a String.
• A generic external function. C has no type parameters, so there would be no symbol to link against.
• An enum as a generic enum’s payload. Holder<Inner> where Inner is itself an enum is refused: the inner one’s payload area would have to be big enough for the outer one, so there is no finite size without indirection. A class payload — Holder<Point> — works, and it is checked per instantiation, because Holder<T>’s payload is neither one thing nor the other until an argument says which.
• Type arguments on a plain type, and the wrong number of them. Both say so by name.

Under the hood, if you are reading the compiler

Monomorphisation usually means substitution: copy the declaration and rewrite the types inside it. Burxt mostly does not.

A layout here is a count of eight-byte cells — everything a value can be is eight bytes wide, or an aggregate of things that are. So Pair<Int> and Pair<Point> are read from one declaration under different bindings, and no copy of the type exists anywhere. Only bodies need copies, because identity<T> compiles to a load for Int and a memory copy for Point.

The rule the compiler follows: a type parameter is a question, not a placeholder. Answer it at every point that asks, and almost nothing has to be substituted. (The design record.)

Why it is built this way

Because erasure would put a pointer where a value belongs. A Stack<Decimal<2>> holds scaled integers laid out end to end. If generics were erased it would hold pointers to boxed integers, and every read would be a chase — which would make the exact-money story slower than the float story it replaces.

Because it is the test of whether the generics are real. Option<T> is four lines of Burxt with no compiler support beyond generics. Map<K, V> is one file. If either had needed a keyword, the generics were decoration — that was the bar set in spec/1.0/M7-GENERICS.md, and it is why the standard library looks the way it does.

Because a bound is a promise a reviewer can read. T: Ordered in a signature says exactly which types may arrive, in the place people already look.

What it costs

One machine function per type that uses it. Three instantiations are three copies in the binary. For the sizes real programs reach this is the right trade; for a generic used at forty types it is forty copies.

Bounds are a short list. Ordered is Int and Decimal — the types < works on. Equatable is those plus Bool and String. You cannot define a bound of your own.

No specialisation, no variance, no associated types, no higher-kinded anything. A type parameter is a type, and that is all it is.

Type arguments come from the annotation when the arguments cannot settle them — let m: Map<String, Int> = map_new();. That reads well and it means a call whose result you do not bind sometimes has nothing to infer from.

When you reach for it

Examples

One definition, two types, two real functions.

function largest<T: Ordered>(a: T, b: T) -> T {
    if a > b { return a; }
    return b;
}

print(largest(3, 9));
print(largest($19.99, $4.50));
print(largest("apple", "pear"));

9
19.99
pear

Those are three separate machine functions — one over Int, one over Decimal<2>, one over String — and the Decimal one compares scaled integers directly rather than unboxing anything.

And the bound doing its job. Bool has no order — is false smaller than true, or is the question meaningless? Nobody wrote it down, so it cannot arrive:

function largest<T: Ordered>(a: T, b: T) -> T {
    if a > b { return a; }
    return b;
}

print(largest(true, false));

error: `largest` needs `T: Ordered`, and Bool has no order. Ordered is Int, Decimal and String — the types `<` works on.
 --> largest.bx:6:7
  |
6 | print(largest(true, false));
  |       ^^^^^^^^^^^^^^^^^^^^

The message names the bound, names the type that failed it, and lists what the bound contains — so you do not have to go and look it up.

Next

Absence and failure — Option, Result, and why there is no null. Both are ordinary Burxt written with exactly what this page describes, which was the test for whether these generics are real.