Chapter 11: Generics

What you'll learn. How to write functions, structs, classes, enums, and interfaces that take type parameters; how type arguments are inferred and when you must write them; how where clauses and bounds restrict a type parameter; and which parts of the generics design Loup 1.25.1 does not implement yet.

Why it matters. A web app is full of code that is the same for every element type: a cache of avatars and a cache of API responses, a "loading / ready / failed" state for a profile and for a feed. Generics let you write that code once and keep the element type checked at every use.

A generic declaration has one or more type parameters in square brackets after its name. At each use the type parameters are replaced by concrete type arguments, usually inferred from the values you pass. Loup uses square brackets where TypeScript, Rust, and Java use angle brackets: list[int], dict[string, User], Option[T].

Generic functions

Listing 11-1 declares three generic functions and calls them with different types.

@mode(web.compiled)

func identity[T](value: T): T {
    return value;
}

func swap[A, B](pair: (A, B)): (B, A) {
    return (pair.1, pair.0);
}

func firstOr[T](items: list[T], fallback: T): T {
    if (items.len() == 0) {
        return fallback;
    }
    return items[0];
}

func main(): void {
    println(identity(42));
    println(identity("hello"));
    println(swap(("port", 8080)));
    println(firstOr([3, 1, 2], 0));
    let empty: list[string] = [];
    println(firstOr(empty, "none"));
    println(identity[int](7));
}

Listing 11-1: Generic functions, called with inferred and explicit type arguments

42
hello
(8080, "port")
3
none
7

T, A, and B can appear anywhere a type can: in parameters, in the return type, in local annotations, and inside other types such as list[T] or (A, B). At each call the compiler matches the parameter types against the argument types to decide what T is: in firstOr([3, 1, 2], 0) both arguments say T = int. You can also write the type arguments yourself, in brackets right before the argument list: identity[int](7).

When inference cannot decide

Inference needs every argument to agree. Here the two arguments of pair say different things about T:

@mode(web.compiled)

func pair[T](first: T, second: T): list[T] {
    return [first, second];
}

func main(): void {
    let widths = pair(320, 480.5);
    println(widths);
}

main.lpweb:8:23: error[E0001]: argument 1 of 'pair': expected 'T0', found 'int'
main.lpweb:8:28: error[E0001]: argument 2 of 'pair': expected 'T0', found 'float'

T0 is the compiler's name for the type parameter it could not pin down. Because 320 is an int and 480.5 is a float, T is constrained by two different types, and the Language Reference (§1-4.8, ruling GEN-1) makes that an error instead of picking one. Loup never converts between int and float silently (Chapter 3), so the fix is to make the arguments agree:

let widths = pair(320.0, 480.5);
println(widths);

[320.0, 480.5]

The opposite problem is a type parameter that no argument mentions. emptyList below takes no arguments, so nothing tells the compiler what T is, and an annotation on the receiving variable does not count:

@mode(web.compiled)

func emptyList[T](): list[T] {
    return [];
}

func main(): void {
    let names: list[string] = emptyList();
    println(names.len());
}

main.lpweb:8:5: error[E0001]: cannot assign 'list[T0]' to binding 'names' of type 'list[string]'

The call stays generic (list[T0]), and a generic list is not a list[string]. Supply the type argument at the call:

var names = emptyList[string]();
names.push("ada");
println(names);

["ada"]

Supplying the wrong number of type arguments is also caught: emptyList[int, string]() reports function 'emptyList' expects 1 type argument(s), but 2 provided.

Generic structs, classes, and enums

Type declarations take type parameters the same way. Listing 11-2 shows one of each: a Range[T] value type, an undo Stack[T] class, and a Loadable[T] enum for data that is still being fetched.

@mode(web.compiled)

struct Range[T] {
    low: T;
    high: T;
}

class Stack[T] {
    var items: list[T] = [];

    pub modifier func push(item: T): void {
        this.items.push(item);
    }

    pub modifier func pop(): Option[T] {
        if (this.items.len() == 0) {
            return None;
        }
        return Some(this.items.pop());
    }

    pub func size(): int {
        return this.items.len();
    }
}

enum Loadable[T] {
    Loading,
    Ready(value: T),
    Failed(reason: string),
}

func main(): void {
    let ages = Range(low = 13, high = 120);
    let letters: Range[string] = Range(low = "a", high = "m");
    println(ages);
    println(letters.high);

    let undo: Stack[string] = Stack();
    safe {
        undo.push("type 'a'");
        undo.push("type 'b'");
        println(undo.pop().unwrap_or("nothing"));
    }
    println(undo.size());

    let unread: Loadable[int] = Loadable.Ready(value = 3);
    match unread {
        Loadable.Loading => println("loading"),
        Loadable.Ready(value) => println(i"{$ value $} unread messages"),
        Loadable.Failed(reason) => println(i"failed: {$ reason $}"),
    }
}

Listing 11-2: A generic struct, class, and enum

Range(low: 13, high: 120)
m
type 'b'
1
3 unread messages

Range(low = 13, high = 120) infers T = int from the field values. Stack() has no arguments to infer from, so the binding's annotation Stack[string] supplies T. Inside the class, T is used in field types, parameters, and return types, and every method is checked once against the unknown T.

⚠ Known gap. The Language Reference (§1-4.8) also lets you write the type argument on the constructor call: let undo = Stack[string]();. Loup 1.25.1 accepts that line but does not specialise the methods, so the first undo.push("…") is rejected with argument 1 of 'push': expected 'T0', found 'string'. Until this is fixed, put the type on the binding as Listing 11-2 does.

Bounds and where clauses

An unconstrained T supports almost nothing: you can store it, return it, and pass it to other generic code. To compare two T values, or use one as a dictionary key, you need a bound: a requirement that T implements an interface. The standard interfaces you will bound on most are Comparable[T] (ordering with <, >, <=, >=, through a compareTo(other: T): int method) and Hashable (a hashCode(): int method, required for dict keys and set elements). They are listed in Language Reference §1-11.2.

For a generic function, write the bound in a where clause after the return type. Listing 11-3 finds the newest release in a list; it works for int (which is Comparable built in) and for a Version class that implements Comparable[Version] itself.

@mode(web.compiled)

class Version implements Comparable[Version] {
    pub let major: int;
    pub let minor: int;

    new(major: int, minor: int) {
        this.major = major;
        this.minor = minor;
    }

    pub func compareTo(other: Version): int {
        if (this.major != other.major) {
            return this.major - other.major;
        }
        return this.minor - other.minor;
    }
}

func newest[T](items: list[T]): T where T: Comparable[T] {
    var best = items[0];
    for (item in items) {
        if (item > best) {
            best = item;
        }
    }
    return best;
}

func main(): void {
    println(Version(1, 2) < Version(1, 10));
    let v = newest([Version(1, 2), Version(2, 0), Version(1, 10)]);
    println(i"{$ v.major $}.{$ v.minor $}");
    println(newest([3, 9, 4]));
}

Listing 11-3: A where clause lets the body compare T values

true
2.0
9

item > best compiles because the bound promises compareTo: the comparison operators desugar to a.compareTo(b) > 0 and friends (Language Reference §1-5.1). Several bounds are joined with +, as in where T: Comparable[T] + Hashable, and several parameters are separated by commas.

Writing the bound inside the brackets

The Language Reference treats func newest[T: Comparable[T]](…) and func newest[T](…) where T: Comparable[T] as the same declaration. In Loup 1.25.1 they are not: a bound written inside the brackets of a function is not visible in its body.

@mode(web.compiled)

func newest[T: Comparable[T]](items: list[T]): T {
    var best = items[0];
    for (item in items) {
        if (item > best) {
            best = item;
        }
    }
    return best;
}

func main(): void {
    println(newest([3, 9, 4]));
}

main.lpweb:6:13: error[E0001]: type 'T0' has no method 'compareTo'

The message says that inside the body the checker knows nothing about T, so > (which needs compareTo) is unavailable. Move the bound to a where clause, as in Listing 11-3. The same limitation applies to the methods of a generic class: a class written class Leaderboard[T: Comparable[T]] cannot use > on T in its own methods today, and a where clause on a class is not parsed. Keep the comparison in a where-bounded free function and call it from the method:

@mode(web.compiled)

func newest[T](items: list[T]): T where T: Comparable[T] {
    var best = items[0];
    for (item in items) {
        if (item > best) {
            best = item;
        }
    }
    return best;
}

class Leaderboard[T: Comparable[T]] {
    var scores: list[T] = [];

    pub modifier func add(score: T): void {
        this.scores.push(score);
    }

    pub func best(): Option[T] {
        if (this.scores.len() == 0) {
            return None;
        }
        return Some(newest(this.scores));
    }
}

func main(): void {
    let board: Leaderboard[int] = Leaderboard();
    println(repr(board.best()));
    safe {
        board.add(120);
        board.add(340);
        board.add(95);
    }
    println(repr(board.best()));
}

Listing 11-4: A bounded generic class that delegates its comparison to a where-bounded function

None
Some(340)

Bounds on a generic type are checked where you use the type

A bound inside the brackets of a class, struct, or enum is enforced: every time you name the type with concrete arguments, the compiler checks them. Here a cache keyed by a Session object fails because Session is not Hashable:

@mode(web.compiled)

class Cache[K: Hashable, V] {
    var entries: dict[K, V] = {};
}

class Session {
    pub let token: string;
    new(token: string) { this.token = token; }
}

func main(): void {
    let bySession: Cache[Session, int] = Cache();
    println("created");
}

main.lpweb:13:20: error[E_GENERIC_BOUND_UNSATISFIED]: E_GENERIC_BOUND_UNSATISFIED: Session does not implement 'Hashable', required by type parameter 'K' of 'Cache'

The fix depends on what you meant. Usually the identity of a session is its token, so key the cache by the token string, which is Hashable built in:

@mode(web.compiled)

class Cache[K: Hashable, V] {
    var entries: dict[K, V] = {};
}

class Session {
    pub let token: string;
    new(token: string) { this.token = token; }
}

func main(): void {
    let session = Session("a1b2");
    let bySession: Cache[string, int] = Cache();
    println(i"cache ready for {$ session.token $}");
}

cache ready for a1b2

The other option is to make Session implement Hashable by giving it a pub func hashCode(): int method.

Function bounds are not checked at the call site yet

The Language Reference requires the compiler to reject a call whose type argument does not satisfy a function's bound (E_GENERIC_BOUND_UNSATISFIED, E_WHERE_BOUND_NOT_MET). Loup 1.25.1 does not check this for functions, in either form. The call compiles, and the program fails when the body uses the missing method:

@mode(web.compiled)

interface Named {
    func name(): string;
}

func names[T](items: list[T]): list[string] where T: Named {
    var out: list[string] = [];
    for (item in items) {
        out.push(item.name());
    }
    return out;
}

func main(): void {
    println(names([1, 2, 3]));
}

Uncaught RuntimeError: internal interpreter limitation: unsupported instruction: CallVirtual name on Int(1)

Until the check exists, treat a where clause as a promise you keep yourself, and test generic functions with the types you call them with.

Printing a value of a type parameter

A natural first generic helper describes a value. In Loup 1.25.1 an unconstrained T cannot be passed to println, str, repr, or an i"…" interpolation:

@mode(web.compiled)

enum Loadable[T] {
    Loading,
    Ready(value: T),
    Failed(reason: string),
}

func describe[T](state: Loadable[T]): string {
    return match state {
        Loadable.Loading => "loading…",
        Loadable.Ready(value) => i"ready: {$ value $}",
        Loadable.Failed(reason) => i"failed: {$ reason $}",
    };
}

func main(): void {
    let profile: Loadable[string] = Loadable.Ready(value = "ada");
    println(describe(profile));
}

main.lpweb:12:46: error[E0001]: argument 1 of '__render': expected 'Any', found 'T0'

__render is the function that interpolation calls; it takes Any, and the checker does not widen a type parameter to Any. The robust fix is the one you would use in TypeScript or Rust anyway: let the caller say how to show a T, by passing a function.

@mode(web.compiled)

enum Loadable[T] {
    Loading,
    Ready(value: T),
    Failed(reason: string),
}

func describe[T](state: Loadable[T], show: fn(T): string): string {
    return match state {
        Loadable.Loading => "loading…",
        Loadable.Ready(value) => i"ready: {$ show(value) $}",
        Loadable.Failed(reason) => i"failed: {$ reason $}",
    };
}

func main(): void {
    let profile: Loadable[string] = Loadable.Ready(value = "ada");
    let unread: Loadable[int] = Loadable.Ready(value = 3);
    let feed: Loadable[int] = Loadable.Failed(reason = "timeout");
    let pending: Loadable[int] = Loadable.Loading;
    println(describe(profile, func(name: string): string => name.to_uppercase()));
    println(describe(unread, func(n: int): string => i"{$ n $} unread"));
    println(describe(feed, func(n: int): string => str(n)));
    println(describe(pending, func(n: int): string => str(n)));
}

Listing 11-5: Passing a formatting function instead of rendering T directly

ready: ADA
ready: 3 unread
failed: timeout
loading…

The function type fn(T): string is itself generic: at each call T is fixed by the Loadable argument, and the lambda must match.

Generic interfaces and higher-order helpers

Interfaces take type parameters too. A class can implement a generic interface at a concrete type argument:

@mode(web.compiled)

interface Store[T] {
    func get(key: string): Option[T];
}

class ThemeStore implements Store[string] {
    var data: dict[string, string] = {"ada": "dark"};

    pub func get(key: string): Option[string] {
        if (this.data.contains_key(key)) {
            return Some(this.data[key]);
        }
        return None;
    }
}

func main(): void {
    let themes = ThemeStore();
    println(repr(themes.get("ada")));
    println(repr(themes.get("lin")));
}

Listing 11-6: Implementing a generic interface at a concrete type

Some("dark")
None

Functions with several type parameters are how you write higher-order helpers. mapAll turns a list[T] into a list[U], with U inferred from the lambda's return type:

@mode(web.compiled)

func mapAll[T, U](items: list[T], f: fn(T): U): list[U] {
    var out: list[U] = [];
    for (item in items) {
        out.push(f(item));
    }
    return out;
}

func main(): void {
    let cents = [1999, 450];
    let labels = mapAll(cents, func(c: int): string => "$" + str(c // 100) + "." + str(c % 100));
    println(labels);
}

Listing 11-7: A generic function with two type parameters

["$19.99", "$4.50"]

⚠ Planned. Two more forms from the Language Reference do not work in Loup 1.25.1. A generic class implementing a generic interface with its own parameter (class MemoryStore[T] implements Store[T]) is rejected with undefined type 'T'. A method that introduces its own type parameter (func map[U](f: fn(T): U): list[U] inside class Batch[T]) confuses U with T and rejects valid calls. Use a concrete type argument, as in Listing 11-6, or a free function like mapAll.

Variance

Variance answers the question "if Button is a Widget, is a list[Button] a list[Widget]?". The Language Reference (§1-4.8) makes generic types invariant by default, with optional out T (covariant) and in T (contravariant) annotations, and lets the compiler infer variance where it can. The annotations are not parsed by Loup 1.25.1 (class Feed[out T] is a syntax error).

For the built-in collections the question has a simple answer today: a list[Button] is accepted where a list[Widget] is expected.

@mode(web.compiled)

class Widget {
    pub func label(): string { return "widget"; }
}

class Button : Widget {
    pub override func label(): string { return "button"; }
}

func labels(widgets: list[Widget]): list[string] {
    var out: list[string] = [];
    for (w in widgets) {
        out.push(w.label());
    }
    return out;
}

func main(): void {
    let buttons: list[Button] = [Button(), Button()];
    println(labels(buttons));
}

Listing 11-8: Passing a list[Button] where a list[Widget] is expected

["button", "button"]

This is safe for built-in collections because assigning or passing one copies it (Chapter 6): code that receives widgets and pushes a plain Widget changes its own copy, not your buttons. Java's covariant arrays are unsafe precisely because they are shared.

A worked example: a small LRU cache

Listing 11-9 is a least-recently-inserted cache you might put in front of avatar URLs or API responses. It has two type parameters, a Hashable bound on the key, and evicts the oldest key when it is full.

@mode(web.compiled)

class Cache[K: Hashable, V] {
    let capacity: int;
    var entries: dict[K, V] = {};
    var order: list[K] = [];

    new(capacity: int) {
        this.capacity = capacity;
    }

    pub func get(key: K): Option[V] {
        if (this.entries.contains_key(key)) {
            return Some(this.entries[key]);
        }
        return None;
    }

    pub modifier func put(key: K, value: V): void {
        if (not this.entries.contains_key(key)) {
            if (this.order.len() == this.capacity) {
                let oldest = this.order[0];
                this.order = this.order.slice(1, this.order.len());
                this.entries.remove(oldest);
            }
            this.order.push(key);
        }
        this.entries[key] = value;
    }

    pub func size(): int {
        return this.entries.len();
    }
}

func main(): void {
    let avatars: Cache[string, string] = Cache(3);
    safe {
        avatars.put("ada", "/img/ada.png");
        avatars.put("lin", "/img/lin.png");
        avatars.put("sam", "/img/sam.png");
        avatars.put("kim", "/img/kim.png");
    }
    println(avatars.size());
    println(repr(avatars.get("ada")));
    println(avatars.get("kim").unwrap_or("/img/default.png"));

    let hits: Cache[int, int] = Cache(2);
    safe { hits.put(404, 12); }
    println(hits.get(404).unwrap_or(0));
}

Listing 11-9: A generic cache with a bounded key type

3
None
/img/kim.png
12

Inserting "kim" into the full cache evicted "ada", the oldest key. The same class serves Cache[string, string] and Cache[int, int]; Cache[Session, int] would be rejected at the annotation because Session is not Hashable.

Try it yourself

1. Add a func clampTo[T](value: T, low: T, high: T): T where T: Comparable[T] and call it with ints and with floats. Then call it as clampTo(2.5, 0, 10) and read the errors.
2. Give Cache a func keys(): list[K] method that returns the keys from oldest to newest.
3. Write func countWhere[T](items: list[T], keep: fn(T): bool): int and use it to count the failed requests in a list[int] of HTTP status codes.

Summary

• Type parameters go in square brackets after the name: func f[T], struct Range[T], class Stack[T], enum Loadable[T], interface Store[T].
• Type arguments are inferred from the arguments; write them explicitly (emptyList[string]()) when nothing constrains a parameter, and make arguments agree (320.0, not 320) when two disagree.
• Bound a function's type parameter with a where clause (where T: Comparable[T] + Hashable). In Loup 1.25.1 an in-bracket bound on a function is not visible in its body, and function bounds are not checked at call sites.
• Bounds in the brackets of a generic type are checked wherever the type is named (E_GENERIC_BOUND_UNSATISFIED).
• An unconstrained T cannot be printed or interpolated today; pass a fn(T): string instead.
• Generic interfaces work at concrete type arguments; generic implements Store[T], method-level type parameters, explicit constructor type arguments, and out/in variance annotations are not implemented yet.