Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Generics

Generics let you write a struct or a function once and use it with many types. Add type parameters in angle brackets after the name, then use them like any other type name. The standard library’s Array<T>, HashMap<K, V>, and Result<TValue, TError> are all ordinary generic types written this way (Result is a generic enum).

Pepper generics work like C++ templates: each distinct set of type arguments, such as Stack<int> or Stack<String>, produces its own copy of the code, compiled for those exact types. There is no runtime cost for using them.

Generic structs

# `T` is a type parameter: each use such as `Stack<int>` or
# `Stack<String>` makes a separate, fully typed version of the struct.
struct Stack<T> {
    var items: Array<T>;

    construct() {
        items = Array<T>();
    }

    push(item: T) {
        items.append(item);
    }

    pop(): T {
        return items.pop();
    }

    peek(): T {
        # `top` is inferred as `T`: an `int` in `Stack<int>`, a `String`
        # in `Stack<String>`.
        var top = items.last();
        return top;
    }

    is_empty(): bool {
        return items.is_empty;
    }
}

# Several parameters are separated by commas.
struct Entry<K, V> {
    var key: K;
    var value: V;
    construct(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

main(): int {
    var numbers = Stack<int>();
    numbers.push(1);
    numbers.push(2);
    assert(numbers.peek() == 2, "peek looks at the top");
    assert(numbers.pop() == 2, "last in, first out");
    assert(numbers.pop() == 1, "then the first");
    assert(numbers.is_empty(), "empty again");

    var words = Stack<String>();
    words.push("hello");
    assert(words.pop() == "hello", "the same code works for Strings");

    var e = Entry<String, int>("answer", 42);
    assert(e.key == "answer" && e.value == 42, "two type parameters");
    return 0;
}
  • Name the type parameters after the struct’s name: struct Stack<T>, struct Entry<K, V>. Inside the struct, fields, parameters, return types, and locals can all use them.
  • Name the type arguments whenever you use the struct: Stack<int>(), var s: Stack<String>;.
  • Stack<int> and Stack<String> are different types.
  • A type argument is a type. The one exception is a number, which only the lane count of a SIMD vector accepts (Vector<int, 4>); a struct of your own cannot compute with a number parameter.
  • Each type argument makes a separate copy of the struct, so a struct whose copy needs a copy with a larger argument never ends: struct Foo<T> with a field var inner: Foo<Array<T>> makes Foo<int> need Foo<Array<int>>, which needs Foo<Array<Array<int>>>, and so on. The compiler stops 64 levels deep with an error at the type that asks for the next level ('Foo' is specialized 65 levels deep, past the limit of 64), with a note where the chain started.

Generic functions

A free function takes type parameters the same way:

larger<T>(a: T, b: T): T {
    if (a > b) {
        return a;
    }
    return b;
}

struct Circle {
    var radius: int = 1;
    area(): int { return 3 * radius * radius; }
}

struct Square {
    var side: int = 2;
    area(): int { return side * side; }
}

# The body can use anything the type argument provides: this works for
# any T that has an `area()` method returning a number.
total_area<T>(shapes: Array<T>): int {
    var sum = 0;
    for (var shape in shapes) {
        sum += shape.area();
    }
    return sum;
}

# `T()` calls the type argument's constructor.
fresh<T>(): Array<T> {
    var items = Array<T>();
    items.append(T());
    return items;
}

# A closure in generic code is compiled with each use too: for `T = int`
# it calls `larger<int>`.
larger_later<T>(a: T, b: T): () => T {
    return () => larger(a, b);
}

main(): int {
    # Type arguments come from the arguments, or can be written out.
    assert(larger(3, 9) == 9, "ints");
    assert(larger<float>(2.5, 1.5) == 2.5, "floats");

    var circles = Array<Circle>();
    circles.append(Circle());
    circles.append(Circle());
    assert(total_area(circles) == 6, "circles");

    var squares = Array<Square>();
    squares.append(Square());
    assert(total_area<Square>(squares) == 4, "squares");
    assert(total_area(fresh<Circle>()) == 3, "a constructed Circle");
    var pick = larger_later(4, 7);
    assert(pick() == 7, "a closure calling a generic function");
    return 0;
}

Pepper infers the type arguments from the arguments, so larger(3, 9) calls larger<int>. You can always write them out, larger<float>(2.5, 1.5), or write only the leading ones and let the arguments give the rest: pick<int>(1, "x") for pick<T, U>(a: T, b: U). You must write them when the arguments do not determine every type parameter, for example one that appears only in the return type:

main.pep:4:13: error: cannot infer the type arguments of 'make' from its arguments; write them: make<T>(...)
    4 |     var b = make();
      |             ^~~~
main.pep:1:1: note: declared here
    1 | make<T>(): Box<T> { return Box<T>(); }
      | ^~~~

A generic function used as a value, not called, takes its type arguments from the function type it is given: var f: (int, int) => int = larger; is larger<int> (see Function types).

A parameter whose type is a trait takes its type arguments from the trait the argument’s type declares: given total<T>(items: Iterator<T>), the call total(Countdown(4)) infers T = int from extend Countdown with Iterator<int>.

Inference works through closures in both directions. In transform(words, (w) => w.size), where transform<T, U>(items: Array<T>, f: (T) => U), words gives T, which types the closure’s parameter w, and the closure’s result gives U.

A closure inside a generic function or method is compiled with each use of it, so the generic calls in its body take their type arguments from that use: in larger_later<T>(a: T, b: T) above, () => larger(a, b) calls larger<int> when T is int.

Because each use is compiled for its concrete types, the body may use any operator, field, or method that the type arguments provide. total_area<T> calls shape.area(), so it works with any T that has an area() method returning a number, and using it with a type that lacks one is a compile error inside total_area. To state the requirement up front, and have the compiler report it where the function is used, give T a constraint.

That includes constructing one: T() (or T(args)) calls the type argument’s constructor, so fresh<Circle>() above makes a Circle. In a constrained generic, which offers only what its constraints declare, it is an error.

Generic methods

A method can have type parameters of its own, in a struct, a generic struct, an extension, or a trait’s default method. They are inferred at each call like a function’s, or written after the method name:

struct Box<T> {
    T value;
    construct(T v) { value = v; }

    # A method with a type parameter of its own: `U` is chosen per call.
    map<U>(f: (T) => U): Box<U> {
        return Box<U>(f(value));
    }
}

main(): int {
    var b = Box<int>(4);

    # `U` comes from what the closure returns...
    var tens = b.map((x) => x * 10);
    assert(tens.value == 40, "tens");

    var text = tens.map((x) => "forty");
    assert(text.value == "forty", "text");

    # ...or is written after the method name.
    var wide = b.map<long>((x: int): long => x + 1);
    assert(wide.value == 5, "wide");
    return 0;
}
  • Write the type arguments with no space before < or after >: b.map<long>(f). With a space, a.b < c is a comparison.
  • A generic method cannot be called through a trait value, since each of its uses is compiled separately. Call it on the concrete type.
  • The iterator adapters map, filter, enumerate and zip are generic default methods of Iterator<T>; see Iteration.

Default type arguments

A type parameter can have a default, written Name=Type. When a use leaves that argument out, the default fills it in:

struct Measurement<TValue, TUnit=String> {
    var value: TValue;
    var unit: TUnit;
}

main(): int {
    # `Measurement<float>` fills TUnit with its default, String.
    var length = Measurement<float>();
    length.value = 2.5;
    length.unit = "m";
    assert(length.unit == "m", "TUnit defaulted to String");

    # Any argument can still be given explicitly.
    var count = Measurement<int, int>();
    count.unit = 7;
    assert(count.unit == 7, "TUnit given as int");

    # The standard library's Result uses a default the same way:
    # Result<int> means Result<int, Error>.
    var ok = Result<int>.ok(42);
    assert(ok.value() == 42, "Result with the default error type");
    return 0;
}

Arguments are matched to parameters in order, so put the parameters that have defaults last. The standard library declares enum Result<TValue, TError=Error>, so Result<int> means Result<int, Error>. See Error handling with Result.

Constraints

A type parameter can require a trait: write the trait after a colon, T: Shape. Every type argument for T must then conform to Shape. Several constraints are joined with &, and a constrained parameter can still have a default, written after them:

trait Shape {
    area(): int;
}

trait Named {
    name(): String;
}

struct Circle {
    var radius: int = 1;
    area(): int { return 3 * radius * radius; }
}

extend Circle with Shape;

struct Square {
    var side: int = 2;
    area(): int { return side * side; }
    name(): String { return "square"; }
}

extend Square with Shape;
extend Square with Named;

# Every T must conform to Shape.
total_area<T: Shape>(shapes: Array<T>): int {
    var sum = 0;
    for (var shape in shapes) {
        sum += shape.area();
    }
    return sum;
}

# Several constraints are joined with `&`.
label<T: Shape & Named>(item: T): String { return item.name(); }

# A constrained parameter can have a default, which must conform too.
struct Gallery<TTag, TShape: Shape = Square> {
    var items = Array<TShape>();
    add(item: TShape) { items.append(item); }
    total(): int { return total_area(items); }
}

main(): int {
    var circles = Array<Circle>();
    circles.append(Circle());
    circles.append(Circle());
    assert(total_area(circles) == 6, "circles");
    assert(label(Square()) == "square", "label");

    # Gallery<String> is Gallery<String, Square>.
    var gallery = Gallery<String>();
    gallery.add(Square());
    assert(gallery.total() == 4, "default");

    # A trait type conforms to its own trait.
    var shapes = Array<Shape>();
    shapes.append(Circle());
    shapes.append(Square());
    assert(total_area(shapes) == 7, "trait values");
    return 0;
}

Constraints work on generic structs, enums whose cases carry values, functions, methods, traits and type aliases. A constraint may name the parameters before it in the same list: sum<T, I: Iterator<T>>(values: I).

A type argument conforms to a trait when:

  • it is a struct declared to have the trait with extend Circle with Shape. For a generic struct, extend Box<T> with Shape makes every Box<X> conform, and extend Box<int> with Shape only Box<int>. A generic trait must match exactly: extend Counter with Iterator<int> conforms to Iterator<int>, not to Iterator<long>. Having the right methods is not enough; the extension is what declares it.
  • it is the trait type itself (Array<Shape> passed as Array<T> with T: Shape), as long as every member of the trait can be called through a value of the trait type (see traits as types).
  • it is a type parameter constrained by that trait: inside wrap<T: Shape>, Gallery<String, T> is allowed.

A number type, char, bool or an enum whose cases carry no values conforms when it declares the trait the same way (extend int with Shape; see numbers, bool and enums), for constraints only: it never becomes a trait value. Pointers, tuples and function types conform to no trait.

The Shared constraint

T: Shared is built in: it requires a type that is safe to share between threads, by the same rule as a field of a [Shared] struct. The types that conform are listed in What threads can share; no extend can make another type conform. It gives T no methods, and it joins other constraints with & (T: Shared & Named):

import async;

[Shared]
struct Settings {
    const workers: int;
    construct(this.workers = 1) {}
}

# A cell that any thread may read: its value must be thread-safe.
[Shared]
struct Cell<T: Shared> {
    const value: T;
    construct(value: T) { this.value = value; }
}

share<T: Shared>(value: T): Cell<T> { return Cell<T>(value); }

main(): int {
    var count = share(3);
    var settings = share(Settings(4));
    assert(count.value == 3 and settings.value.workers == 4, "shared cells");

    # The runtime states the same rule: spawn<T: Shared>.
    async.run(() => {
        var task = async.spawn<Settings>(() => { return Settings(2); });
        assert(task.join().value().workers == 2, "spawned");
    });
    return 0;
}

The standard library states the rule this way where it applies: spawn<T: Shared>, run_blocking<T: Shared> and Lazy<T: Shared>, so async.spawn<String>(...) is reported at String, with a note saying why it is not thread-safe ('String' is not declared [Shared]). In a constraint, Shared always means this built-in, so a trait cannot be named Shared. A generic that passes its own T to one of these (say run_blocking<T>) needs T: Shared too.

A constraint can name another type parameter of the same declaration: count_all<T, I: Iterator<T>>(source: I). Inference reads it too: the argument gives I, and the Iterator<...> that I declares gives T. A trait’s default method may name the trait’s own parameters (put_all<I: Iterator<T>> in trait Sink<T>), which take the arguments of the conformance (extend Sum with Sink<int>).

# `I`'s constraint names `T`: the argument's type gives `I`, and the
# `Iterator<T>` it declares gives `T`.
count_all<T, I: Iterator<T>>(source: I): int {
    var count = 0;
    while (source.next()) {
        count += 1;
    }
    return count;
}

first<T, I: Iterator<T>>(source: I): T {
    source.next();
    return source.current();
}

main(): int {
    var words = Array<String>();
    words.append("pepper");
    words.append("salt");

    # Both inferred: I = ArrayIterator<String>, T = String.
    assert(count_all(words.iterate()) == 2, "count");
    assert(first(words.iterate()) == "pepper", "first");

    # Written type arguments may stop early; the rest are inferred.
    assert(count_all<String>(words.iterate()) == 2, "partial");
    return 0;
}

The compiler checks every use: a type argument you write, one it infers from a call, a default, and a concrete override. The error points at the type argument, or at the call argument the type came from:

main.pep:11:21: error: 'Circle' does not conform to trait 'Shape', required by 'T' in 'Gallery'
   11 |     var g = Gallery<Circle>();
      |                     ^~~~~~
main.pep:7:19: note: constraint declared here
    7 | struct Gallery<T: Shape> {
      |                   ^~~~~
main.pep:4:8: note: declare it with 'extend Circle with Shape'
    4 | struct Circle {
      |        ^~~~~~

A type parameter passed on to a constrained one must carry the constraint itself: wrap<T>(item: T): Gallery<String, T> is an error that suggests T: Shape. The language server offers both the extension and the constraint as quick fixes.

  • A constraint must name a trait: T: Point, with Point a struct, is an error.
  • An extension of a constrained struct keeps its constraints: extend Gallery<TTag, TShape> needs no TShape: Shape of its own. You may restate them as documentation, extend Gallery<TTag, TShape: Shape>. A constraint the struct does not have makes a constrained extension.
  • In an overload set, a generic member whose inferred type arguments do not meet its constraints is not viable, and the error lists why.
  • A constrained name is always a type parameter, never an override’s type argument: describe<Point: Shape> declares a generic function whose parameter happens to be named Point.

Inside a constrained generic

The compiler also checks the generic itself, once, whether or not anything uses it: inside largest<T: Shape & Ordered>, a value of type T offers exactly what Shape and Ordered declare. It may:

  • call their instance methods and operators (item.area(), best < item),
  • call their static members through the parameter (T.unit()),
  • convert to one of their trait types (var shape: Shape = item;),
  • be stored, passed, returned, and compared with ==, !=, === and !==.
trait Shape {
    area(): int;
    scaled(by: int): this;
    static unit(): this;
}

trait Ordered {
    <(other: this): bool;
}

struct Square {
    var side: int = 1;
    construct(this.side = 1) {}
    area(): int { return side * side; }
    scaled(by: int): Square { return Square(side * by); }
    static unit(): Square { return Square(1); }
    <(other: Square): bool { return side < other.side; }
}

extend Square with Shape;
extend Square with Ordered;

# Inside the body, a T offers what Shape and Ordered declare.
largest<T: Shape & Ordered>(items: Array<T>): T {
    var best = items[0];
    for (var item in items) {
        if (best < item) {
            best = item;
        }
    }
    return best;
}

# Static members are called through the parameter.
unit_area<T: Shape>(): int { return T.unit().area(); }

# A T converts to the trait types of its constraints.
as_shape<T: Shape>(item: T): Shape {
    var shape: Shape = item.scaled(2);
    return shape;
}

main(): int {
    var squares = Array<Square>();
    squares.append(Square(2));
    squares.append(Square(3));
    assert(largest(squares).side == 3, "largest");
    assert(unit_area<Square>() == 1, "static member");
    assert(as_shape(Square(3)).area() == 36, "conversion");
    return 0;
}

Anything else is an error at the member or operator, even before any use: a field, a method no constraint declares, a constructor T(), a call of a constraint’s method with the wrong number or types of arguments, or initializing, assigning or returning a T as another type. (Passing a T to a function that takes another type is still reported in each specialization.)

main.pep:5:45: error: no member named 'perimeter' in 'T'
    5 | total<T: Shape>(item: T): int { return item.perimeter(); }
      |                                             ^~~~~~~~~
main.pep:5:10: note: 'T' is constrained by 'Shape', which has no member 'perimeter'
    5 | total<T: Shape>(item: T): int { return item.perimeter(); }
      |          ^~~~~

A method that two constraints both declare is an error too ('name' is declared by both 'Named' and 'Titled'; call it through one of them).

Each use is still compiled for its type argument, so a call goes straight to that type’s own method, with no trait value in between. A parameter without a constraint keeps working as before: its uses are checked in each specialization. In a list that mixes the two, such as f<T: Shape, U>, only the uses of T are checked in the generic.

Constrained extensions

An extension of a generic struct can add a constraint the struct does not have: extend Box<T: Named> { ... }. Its members exist only on the specializations whose type argument meets it, so Box<Square> has label() and Box<String> does not. With with, the constraint makes a conditional conformance: after extend Box<T: Shape> with Shape, a Box<Square> is a Shape (it can be passed where T: Shape is required and converted to a Shape value), and a Box<String> is not.

trait Shape {
    area(): int;
}

trait Named {
    name(): String;
}

struct Square {
    area(): int { return 4; }
    name(): String { return "square"; }
}

extend Square with Shape;
extend Square with Named;

struct Box<T> {
    var item: T;
    construct(item: T) { this.item = item; }
}

# Only a Box of something Named has `label()`.
extend Box<T: Named> {
    label(): String { return "box of " + item.name(); }
}

# A Box of shapes is itself a shape.
extend Box<T: Shape> with Shape {
    area(): int { return item.area() * 2; }
}

main(): int {
    var box = Box<Square>(Square());
    assert(box.label() == "box of square", "constrained extension");

    Shape shape = box;
    assert(shape.area() == 8, "conditional conformance");

    # Box<String> is still a Box, without `label()` or `area()`.
    var text = Box<String>("plain");
    assert(text.item == "plain", "any Box");
    return 0;
}
  • Every Box<X> keeps the struct’s own members and constraints; an extension adds to them, it never removes any.
  • Inside the extension, T offers the struct’s constraints and the extension’s, as in any constrained generic.
  • A call of a member the specialization does not have names the constraint it misses:
main.pep:20:9: error: no member named 'label' in 'Box<Circle>'
   20 |     box.label();
      |         ^~~~~
main.pep:15:15: note: 'label' requires 'Circle' to conform to 'Named'
   15 | extend Box<T: Named> {
      |               ^~~~~

and a type argument that misses a conditional conformance says so too ('Box<String>' conforms to 'Shape' only when 'String' conforms to 'Shape').

  • Only the struct’s own parameters can carry an extension’s constraints: extend Box<int: Shape> is an error.
  • A conformance that holds for every Box needs its members on every Box: extend Box<T> with Named cannot rest on a name() that only extend Box<T: Named> provides. Make the conformance conditional instead (extend Box<T: Named> with Named).
  • Several extensions may declare the same trait with different constraints; a specialization conforms when it meets any of them.
  • Inside another generic, a call such as b.label() on a Box<T> is checked in each specialization, like any member of a generic struct.

Overriding a generic function for one type

You can give a generic function a separate definition for a specific type argument. Write the concrete type where the type parameter would go:

# The generic version handles every type...
describe<T>(value: T): String {
    return "something";
}

# ...and these definitions replace it for two specific types.
describe<int>(value: int): String {
    return "an int";
}

describe<String>(value: String): String {
    return "a String";
}

main(): int {
    assert(describe<float>(1.5) == "something", "the generic version");
    assert(describe<int>(7) == "an int", "the int override");
    assert(describe<String>("hi") == "a String", "the String override");

    # The standard library's hash<String> is such an override: it hashes
    # a String by its content instead of by identity.
    assert(hash<String>("pepper") == hash<String>("pepper"), "content hash");
    return 0;
}

A call whose type argument matches an override, such as describe<int>(7), uses the override; every other call uses the generic version. The standard library uses this to give hash<String> a content-based hash, while hash<T> hashes other structs by identity; a struct keyed by its content overrides hash<T> the same way (see Hashing and equality).

An override can name a built-in type (int, bool, String, and so on) or a struct, such as describe<Point>. It must be declared next to the generic function or next to one of its type arguments: in the file that declares either, or in another file of the same module. Here main.pep overrides shapes.pep’s describe<T> for its own Point, and the generic code in shapes.pep uses the override too:

# A generic function, and code that calls it for any type.
export describe<T>(v: T): int {
    return 0;
}

export describe_twice<T>(v: T): int {
    return describe<T>(v) * 2;
}

import "shapes";

struct Point {
    var x: int;
    var y: int;
}

# Overrides shapes.pep's describe<T> for Point, from another file.
describe<Point>(p: Point): int {
    return p.x + p.y;
}

main(): int {
    var p = Point();
    p.x = 3;
    p.y = 4;
    assert(describe<Point>(p) == 7, "the override");
    assert(describe_twice<Point>(p) == 14, "generic code in shapes.pep uses it too");
    assert(describe<int>(5) == 0, "other types keep the generic version");

    # The standard library's generics, such as hash<T>, can be overridden
    # for a struct the same way.
    return 0;
}

A function whose type parameters all name types the file can see (its own, the ones it imports, under any name such as P after import [Point as P] from geo, and the standard library’s) is an override when the file can also see a generic function of that name and number of type parameters (its own, an imported one, or the standard library’s); otherwise a struct’s name is just the name of a type parameter. The generic may be spelled by any name the file has for it (show<Point> after import [describe as show]). A type argument must name a struct, not a type alias or a trait. A generic and another function of the same name in one file are overloads, unless they have the same parameters, or the generic’s type parameters all name structs the file can see without a generic of that name to override: either is an error, since it usually means an override whose type argument the file cannot see, or of a generic the file’s own function of that name hides.

This placement rule (Rust calls it the orphan rule) means a file that can see both the generic and the type can also see every override that applies to them, so the compiler can check each file on its own. An override that neither of them is declared beside is an error:

main.pep:2:1: error: cannot override 'hash' for 'int' here: an override must be in the file or module that declares 'hash' or one of its type arguments
    2 | hash<int>(value: int): ulong {
      | ^~~~

The standard library’s generics, such as hash<T> and to_string<T>, can be overridden for your own structs, but not for built-in types: the standard library declares both. Wrap the built-in type in a struct of your own instead.

To add methods to a generic struct from outside its declaration, use an extension.