Chapter 11: Generics

Generics let one definition work for many types: a Stack[T] of anything, a binarySearch over any ordered list. Type parameters are written in square brackets, and bounds in a where clause say what a type parameter must be able to do. This chapter covers generic functions, classes, structs, enums and methods, bounds, and the two mistakes Loup 1.25.1 makes easy to hit.

Generic functions

Type parameters follow the function name. The compiler infers them from the arguments, or you can give them explicitly:

@mode(host.native)

func swap[A, B](pair: (A, B)): (B, A) {
    let (a, b) = pair;
    return (b, a);
}

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

func main(): void {
    println(swap((42, "hello")));
    println(firstOr([7, 8], 0));
    println(firstOr[string]([], "none"));
}

Listing 11-1: Generic functions

("hello", 42)
7
none

Inside firstOr, T is an unknown type: the body may store, pass and return T values, but it cannot call methods or operators on them until a bound says they exist.

Bounds with where

A where clause after the return type states what each type parameter must implement. The body may then use that interface's methods, and operators derived from them:

func binarySearch[T](sorted: list[T], target: T): Option[int] where T: Comparable[T] {
    var lo = 0;
    var hi = sorted.length();
    while (lo < hi) {
        let mid = (lo + hi) // 2;
        let order = sorted[mid].compareTo(target);
        if (order < 0) {
            lo = mid + 1;
        } else if (order > 0) {
            hi = mid;
        } else {
            return Some(mid);
        }
    }
    return None;
}

func dedupe[T](items: list[T]): list[T] where T: Hashable {
    var seen: set[T] = {};
    var result: list[T] = [];
    for (x in items) {
        if (not seen.contains(x)) {
            seen.add(x);
            result.push(x);
        }
    }
    return result;
}

func main(): void {
    let primes = [2, 3, 5, 7, 11, 13];
    println(binarySearch(primes, 7) ?? -1);
    println(binarySearch(primes, 8) ?? -1);
    println(binarySearch(["ant", "bee", "cat"], "cat") ?? -1);
    println(dedupe(["eu", "us", "eu", "ap"]));
}

Listing 11-2: A generic binary search and de-duplication

3
-1
2
["eu", "us", "ap"]

Comparable[T] (chapter 10) provides compareTo and the ordering operators; Hashable is what a set element or dictionary key needs. int, float and string implement both. Several bounds on different parameters are separated by commas: where K: Hashable, V: Comparable[V].

Mistake: the inline bound

The Language Reference also allows the bound inside the brackets, func largest[T: Comparable[T]](…), and many readers will reach for it first, as in Rust. Stage0 1.25.1 parses it but does not apply it to the body:

@mode(host.native)

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

func main(): void {
    println(largest([3, 9, 2]));
}

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

T0 is the compiler's internal name for T, and > is defined through compareTo. Move the bound into a where clause and the same body compiles:

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

func main(): void {
    println(largest([3, 9, 2]));
    println(largest(["pear", "apple", "zucchini"]));
}

Listing 11-3: The bound in a where clause

9
zucchini

Two more forms from the specification do not work yet: combining bounds with + after a generic interface (where T: Equatable[T] + Hashable does not parse; write where T: Hashable, T: Equatable[T]), and using an arithmetic operator through an operator interface (where T: Add[T, T] does not make a + b type-check on T). For generic arithmetic, pass the operation as a function value.

Generic classes, structs and enums

A type's parameters follow its name. Methods use them like any other type:

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

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

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

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

enum Lookup[T] {
    Found(value: T),
    Missing(key: string),
}

func main(): void {
    let undo: Stack[string] = Stack();
    safe {
        undo.push("insert line 3");
        undo.push("delete line 7");
        println(undo.pop() ?? "nothing to undo");
    }
    println(undo.size());

    let result: Lookup[int] = Lookup.Missing(key = "timeout");
    match result {
        Lookup.Found(v) => println(v),
        Lookup.Missing(k) => println(i"{$ k $} is not configured"),
    }
}

Listing 11-4: A generic class and a generic enum

delete line 7
1
timeout is not configured

Generic structs work the same way (Listing 7-6). When a constructor's arguments mention T, the compiler infers it (Box(1) is a Box[int]).

Mistake: explicit type arguments without an annotation

Stack has no constructor arguments, so nothing tells the compiler what T is. Writing the type arguments on the constructor call looks like it should be enough:

@mode(host.native)

class Stack[T] {
    var items: list[T] = [];
    pub modifier func push(x: T): void { this.items.push(x); }
}

func main(): void {
    let undo = Stack[string]();
    safe { undo.push("insert line 3"); }
}

main.lphc:10:22: error[E0001]: argument 1 of 'push': expected 'T0', found 'string'

In 1.25.1 the binding's type still contains the unresolved T0. Annotate the binding, as in Listing 11-4: let undo: Stack[string] = Stack();.

Generic methods

A method can have type parameters of its own, independent of its class:

class Pipeline {
    pub let name: string;
    new(name: string) { this.name = name; }

    pub func run[In, Out](input: In, step: fn(In): Out): Out {
        println(i"[{$ this.name $}] running step");
        return step(input);
    }
}

func main(): void {
    let p = Pipeline("ingest");
    let size = p.run("hello world", func(s: string): int { return s.length(); });
    println(size);
}

Listing 11-5: A generic method

[ingest] running step
11

How generic code is compiled

Type checking happens once, on the generic definition, with the bounds as the only knowledge of T. That is why a missing bound is reported at the definition rather than at a call. The specification allows a native compiler to specialise (monomorphize) generic code for each type it is used with. The native code generator in 1.25.1 compiles a generic function once and passes T values in a uniform boxed form across the generic boundary (ruling GBOX-1), so do not assume that a generic function costs nothing compared with a hand-written one.

Chapter 18 covers lifetime parameters, which share the bracket syntax (func longest[lifetime ~a](…)) but are a compile-time region label rather than a type.

Summary

• Type parameters go in square brackets: func f[T](x: T), class Stack[T], enum Lookup[T], and per-method func run[In, Out](…). They are inferred from arguments where possible.
• Bounds go in a where clause: where T: Comparable[T], where K: Hashable, V: Comparable[V]. The body can then call the bound's methods and derived operators.
• The inline form [T: Comparable[T]] is accepted but ignored by the 1.25.1 checker (type 'T0' has no method 'compareTo'); use where.
• + between bounds after a generic interface, and arithmetic through Add[T, T] bounds, do not work yet.
• A generic class constructed without arguments needs an annotated binding: let s: Stack[string] = Stack();.
• Native code compiles generics once with boxed type-parameter values today; lifetime parameters are chapter 18.
• Chapter 12 covers error handling.