# 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: ```loup @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* ```text ("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: ```loup #~ @mode(host.native) 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* ```text 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: ```loup,does_not_compile @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])); } ``` ```text 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: ```loup #~ @mode(host.native) 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* ```text 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: ```loup #~ @mode(host.native) 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* ```text 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: ```loup,does_not_compile @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"); } } ``` ```text 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: ```loup #~ @mode(host.native) 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* ```text [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.