The Zeno Book Zeno 0.1 zeno-lang.org

19 Generics

A stack of numbers and a stack of names are the same code. A function that gives the first item of a list does the same whatever the items are. Generics let such code be written once, with the type left open, and still be checked for every type it is used with.

19.1 A generic function

A function names the type it leaves open in square brackets after its name, and uses that name where a type would go:

function first[T](items: list[T]) -> T {
    return items[0]
}

print(first([3, 1, 2]), first(["ada", "alan"]))
let n = first([10, 20])
print(n + 1)
3 ada
11

T is a type parameter. Read the heading as "first, for any type T, takes a list of T and gives a T". At each call Zeno works out what T is, so first([10, 20]) is known to be an int, and n + 1 is checked as an int sum.

Without generics, first would be written once for each type, or once with no types at all, and then nothing that used its answer could be checked.

Zeno already writes "a type applied to a type" as list[int]. first[T] is the same sentence, so there is one rule and no new punctuation. The angle brackets of C++, Java and Rust would make a < b > c a puzzle for the parser and the reader; Go chose square brackets for that reason. (Decision 3.16.)

A type parameter starts with a capital letter, so a reader can tell it is a type without looking back at the heading:

function first[t](items: list[t]) -> t {
    return items[0]
}
error: a type parameter starts with a capital letter, as in `T` or `Item`, and this is `t`
 --> main.zeno:1:1
  |
1 | function first[t](items: list[t]) -> t {
  | ^

1 error found. Nothing was run.

19.2 Several type parameters

A function can leave several types open. Here convert takes a list of one type and a function that turns it into another:

function convert[T, U](items: list[T], change: function(T) -> U) -> list[U] {
    var out: list[U] = []
    for item in items {
        out.append(change(item))
    }
    return out
}

let labels = convert([1, 2, 3], function(n) { return f"#{n}" })
print(labels, labels[0].upper())
["#1", "#2", "#3"] #1

Zeno works out T from the list, then calls the function in its head with an int to find what it gives back, and that is U.

19.3 A generic class

A class can leave types open the same way. Stack[T] is a stack of anything, and Stack[str] is a stack of text:

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

    function push(self, item: T) {
        self.items.append(item)
    }

    function pop(self) -> T {
        return self.items.pop()
    }

    function is_empty(self) -> bool {
        return len(self.items) == 0
    }
}

let names: Stack[str] = Stack()
names.push("ada")
names.push("grace")
print(names.pop().upper(), names.is_empty(), names)
GRACE false Stack(items=["ada"])
class Pair[A, B] {
    left: A
    right: B
}

let p = Pair(36, "Ada")
print(p, p.left + 1, p.right.upper())
Pair(left=36, right="Ada") 37 ADA

Inside Pair[A, B], A is the type parameter, even though A is also the unit of current: the name declared right there in the heading is the nearest, and the nearest name wins. A quantity inside it is still written 3 A.

19.4 Where the types come from

A type argument is never written at the call. There is no first[int](xs). Zeno finds each type parameter in this order:

  1. from the arguments;

  2. from an argument that is a function, by calling it in its head with what the others gave;

  3. from the place the result goes, such as a variable with a written type.

The third is what a stack that starts empty needs: nothing in Stack() says what it will hold, so the variable says it, as let names: list[str] = [] does for a list. If nothing says, strict mode asks for it, and shows how:

class Box[T] {
    items: list[T]
}
let box = Box([])
$ zeno check --strict main.zeno
error: `Box` cannot tell what `T` is from this call: no argument says. Put the result where its type is written, as in `let x: Box[int] = Box(...)`
 --> main.zeno:4:11
  |
4 | let box = Box([])
  |           ^

1 error found. Nothing was run.

A written number waits for the other arguments to decide. With level a u8, same(level, 9) is a u8, and same(level, 300) is an error, so a generic used for bytes never needs u8(0) where 0 is meant. (Decision 3.16c.)

19.5 The body is checked for each type

largest below uses >, and nothing in its heading says that T must have one:

function largest[T](items: list[T]) -> T {
    var best = items[0]
    for item in items {
        if item > best {
            best = item
        }
    }
    return best
}
print(largest([3, 9, 2]), largest(["pear", "fig", "apple"]))
9 pear

Zeno checks the body once for each type the program uses it with. For ints and for text it passes. For a class, which has no >, the mistake is reported inside largest, with a note that names the type and the line that asked for it:

class Point {
    x: int
}

function largest[T](items: list[T]) -> T {
    var best = items[0]
    for item in items {
        if item > best {
            best = item
        }
    }
    return best
}
print(largest([Point(1), Point(2)]))
error: `>` does not work between Point and Point
 --> main.zeno:8:12
  |
8 |         if item > best {
  |            ^
  = note: this is inside `largest[Point]`: `largest` with T = Point, which line 14 asks for

1 error found. Nothing was run.

A bound, such as "T must be something with >", needs a name for "something with >". Checking each use instead is what C++ did for thirty years, and it still finds every mistake before the program runs, which is the promise that matters. The note under the error is there so that the message points back to the call. (Decision 3.16d.)

19.6 What a compiled program does

In a compiled program each use becomes its own copy: largest for ints and largest for text are two functions in the C, each as fast as if it had been written by hand. Nothing is looked up while the program runs. The cost is size: each type a generic is used with adds a copy to the program, which on a microcontroller is flash. That is why an untyped function is not made generic by itself: a program asks for copies by writing [T].

19.7 What generics leave out

In version 0.1, these are refused, each with a message that says so: an enum with type parameters, a method with type parameters of its own, a generic function kept as a value or passed along, and raising an object of a generic class.

function first[T](items: list[T]) -> T {
    return items[0]
}
let pick = first
error: `first` is generic. It can be called, as in `first(...)`, but it cannot be kept as a value or passed along yet
 --> main.zeno:4:12
  |
4 | let pick = first
  |            ^

1 error found. Nothing was run.

The commonest generic enum, "a T or nothing", is already there: T or none. (Decision 3.16e.)

function name[T](...) and class Name[T] leave a type open. Type parameters start with a capital, and are worked out at each call from the arguments, from a function argument, or from where the result goes, never written at the call. The body is checked for every type it is used with, and a compiled program has a copy for each.

  1. Write function last[T](items: list[T]) -> T or none, which gives none for an empty list.

  2. Write a generic class Ring[T] that holds at most size items and drops the oldest when a new one comes. Use it for a ring of u8 and a ring of V.

  3. Write a generic count_if[T] that takes items: list[T] and test: function(T) -> bool, and gives how many items pass the test.

  4. Give largest a list of bool and read the message.