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:
from the arguments;
from an argument that is a function, by calling it in its head with what the others gave;
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 = firsterror: `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.
Write
function last[T](items: list[T]) -> T or none, which givesnonefor an empty list.Write a generic
class Ring[T]that holds at mostsizeitems and drops the oldest when a new one comes. Use it for a ring ofu8and a ring ofV.Write a generic
count_if[T]that takesitems: list[T]andtest: function(T) -> bool, and gives how many items pass the test.Give
largesta list ofbooland read the message.