/
Search
EN
ENRU

Generics

A generic function is one function written once that works for many types. In C you get this with macros or with void* and casts; in Python every function is generic because nothing is checked until run time. kola checks generic code at compile time, the way Rust and C++ do, and writes its parameters in square brackets.

What kola leaves out is the machinery other languages build around generics. Rust has traits (named sets of methods a type promises to provide, similar to interfaces in Java or Go), dyn values that pick the right method at run time through a table of function pointers called a vtable, and specialization. kola has none of these. Every generic function and struct is monomorphized: for each concrete set of arguments it is used with, the compiler produces a separate, ordinary function, as if you had written first_u64 next to first_bool by hand. The Basics chapter showed first[T: data]. This chapter covers the rest: how regions, types and constants share one bracket list, which bounds exist, how the standard library's hash map works without a trait, and what monomorphization costs.

Monomorphization is how C++ templates work too. The alternative, used by Java and by Rust's dyn, is dynamic dispatch: one shared body that decides at run time which concrete code to call. That design suits a reviewer less, because it hides a decision. Which implementation runs is resolved behind an indirection you cannot see at the call site. In kola, once you know the instantiation, the code you are reading is the code that runs.

One bracket list for regions, types and constants

A region is an arena: a block of memory that everything in a region r { ... } block is allocated from, freed all at once at the closing brace (see Memory: regions and references). A function that takes a reference into a region names that region as a parameter, just as it names a type. Generics and regions use the same square brackets, and <...> never appears in kola. The case of the name tells the kinds apart. A lowercase name binds a region, an Uppercase name binds a type, and a const parameter is Uppercase too. fn f[r, T](x: &r T) reads as "for any region r the caller has and any type T, given a reference into r". Here is the card's own contract example with a test:

fn split_at[r, T](xs: &r [T], mid: usize) -> (&r [T], &r [T])
    req mid <= xs.len
    ens ret.0.len == mid
{
    (xs[0..mid], xs[mid..xs.len])
}

test split_works {
    region r {
        let xs = alloc in r [10u64, 20u64, 30u64, 40u64];
        let (left, right) = split_at(xs, 2);
        assert left.len == 2 && right.len == 2;
        assert left[0] == 10 && right[0] == 30;
    }
}

Both halves point into the same region as the input. The call does not mention r or T: both are inferred from the argument. You may write type and const arguments explicitly (split_at[u64](xs, 2)), and a partial list is allowed, with the rest inferred. You may never write a region in a call. If you try, the compiler refuses the call and tells you to delete the region from the list, because a region parameter is always inferred from the call. This is deliberate: adding a region parameter to an existing generic function does not break any of its callers.

A region-generic type is different. In a type position you always write its region arguments (Header[r], never a bare Header), because that is a type, not a call.

Putting regions first and types after them is a convention the standard library follows; the checker does not enforce the order.

Bounds: none, data and move

A bound is a requirement a generic parameter places on the types it accepts. In Rust a bound names a trait, such as "T must support Clone". kola has no traits, so a bound cannot ask for an operation. It can only say how a value of the parameter may be treated: may it be copied, may it be thrown away? That matters because kola has three kinds of values. Plain data (numbers, structs of numbers) can be copied freely. A resource (an open file, a socket) must be used exactly once, never copied and never silently dropped. An owning value (a growable Vec that owns a heap buffer, a Map) moves from one owner to the next and is never copied, so two names never share one buffer. There are three choices of bound.

An unbounded parameter accepts any type, including a resource. Inside the body, T is treated as linear: a value of T must be used exactly once, never copied and never dropped. Option[T] and Result[T, E] are unbounded, which is why Result[File, FsErr] works as well as Result[u32, ParseErr], and linearity follows a resource through the generic wrapper as if the wrapper were not there:

resource struct Ticket { id: u64 }

struct Box[T] { v: T }

fn box_new[T](v: T) -> Box[T] !{} {
    Box { v }
}

fn box_open[T](b: Box[T]) -> T !{} {
    let Box { v } = b;
    v
}

fn close_ticket(t: Ticket) -> u64 !{} {
    let Ticket { id } = t;
    id
}

test unbounded_generic_holds_a_resource {
    let b = box_new(Ticket { id: 7 });
    let t = box_open(b);
    let id = close_ticket(t);
    assert id == 7;
}

Because the body must assume the worst, an unbounded T cannot be duplicated. A function such as fn dup[T](x: T) -> (T, T) { (x, x) } is refused with "use of consumed resource x", and the help line suggests the bound [T: data].

[T: data] promises that T is plain copyable data: no resource inside it, and nothing owning either (no owned Vec, no Map, no value holding a &mut). The body may then copy T freely, return it from an index or compare it with ==. Passing an owned Vec[u8] to a : data parameter is refused at the call, with the advice to pass a reference or drop the bound.

[T: move] sits between the two. It accepts data and owning values but no resource. A value of T moves, may be dropped and may be stored in a Vec, but is never copied. It is the bound for containers and helpers that shuffle owned buffers around:

// Keep one of two values and drop the other.
fn pick[T: move](old: T, new: T, take_new: bool) -> T !{} {
    if take_new { new } else { old }
}

fn stack_push[T: move](s: &mut Vec[T], x: T) !{alloc(heap)} {
    s.push(x);
}

test move_bound_takes_owned_vecs {
    let a: Vec[u8] = Vec::new();
    let mut b: Vec[u8] = Vec::new();
    b.push(7u8);
    let kept = pick(a, b, true);
    assert kept.len == 1;
    let mut all: Vec[Vec[u8]] = Vec::new();
    stack_push(&mut all, kept);
    assert all.len == 1;
}

Instantiating pick with Ticket is refused: a : move parameter may be dropped, and a resource must be consumed. Any other bound name is refused by name:

fn first[T: copyable](xs: &[T]) -> T !{} {
    xs[0]
}
error[card §2]: unknown bound `copyable` (kola has no traits)
  --> a.kl:1:13
   |
 1 | fn first[T: copyable](xs: &[T]) -> T !{} {
   |             ^^^^^^^^
   = help: the bounds are `data` (copyable, no resources inside) and `move` (moves, may be dropped, never copied; no resources inside)

A generic type from the standard library: Map[a, K, V]

The hash map in std::collections::map has one region parameter and two type parameters, and it works without any trait. Map::new(hint, hash, eq) takes a capacity hint and two fn references, one that hashes a key and one that compares two keys. A fn reference is a function used as a value, like a function pointer in C; it captures nothing from its surroundings. The map stores them and calls them directly. id_u64 and eq_u64 ship with the module for u64 keys; for any other data key type you write the pair yourself.

A Map is an owning value: it moves rather than copies. Pass &m to a function that reads it and &mut m to one that changes it. The methods are get, insert, has, remove, key_at, val_at and cursor, and m.len is a read like every other .len (the call m.len() is refused):

use std::collections::map;
use std::collections::map::Map;

fn total_values[r](m: &Map[r, u64, u64]) -> u64 !{} {
    let mut s: u64 = 0;
    let mut c = m.cursor();
    while c.next() {
        s = s +% c.val();
    }
    s
}

test map_insert_get_replace {
    region r {
        let mut m: Map[r, u64, u64] = Map::new(16, map::id_u64, map::eq_u64);
        let a = m.insert(100, 1);
        let b = m.insert(200, 2);
        assert a && b;
        assert m.get(100) == Some(1u64);
        assert m.get(300) == None;
        let fresh = m.insert(100, 9);
        assert !fresh;
        assert m.get(100) == Some(9u64);
        assert m.has(200) && m.len == 2;
        assert total_values(&m) == 11;
    }
}

insert answers true for a new key and false when it replaced a value. The inserts are bound to names before the assert because an assert may not change state: a proven assert is removed from the build, so its expression must mean the same thing whether or not it runs.

Two limits matter in practice. The capacity is a hard bound with no rehashing, so inserting many more distinct keys than the hint (roughly four times as many) traps rather than degrading. And a cursor is a view of the map: while it is still in use, you may not insert into the map or remove from it.

total_values declares its own region parameter [r] so that it can name Map[r, u64, u64] in its signature. A region that appears in a type must be bound somewhere: by an enclosing region r { ... } block, or by the function's generic list. Types are module items, so outside its module the map is either imported by name (use std::collections::map::Map;, as here) or written with its path, map::Map[r, K, V].

Writing your own generic type

An impl block attaches methods to a generic type. Its parameters are in scope for every method, and a method call takes them from the receiver. This small association list shows the same design as Map, with equality supplied as a fn reference:

struct Assoc[a, K, V] {
    eq: fn(K, K) -> bool !{},
    keys: &a mut Vec[K],
    vals: &a mut Vec[V],
}

impl Assoc[a, K: data, V: data] {
    pub fn new(eq: fn(K, K) -> bool !{}) -> Assoc[a, K, V] !{alloc(a)} {
        Assoc { eq, keys: alloc in a mut Vec::new(), vals: alloc in a mut Vec::new() }
    }

    pub fn put(self: &mut Assoc[a, K, V], k: K, v: V) -> bool !{alloc(a)} {
        let eqf = self.eq;
        for i in 0..self.keys.len {
            if eqf(self.keys[i], k) {
                self.vals[i] = v;
                return false;
            }
        }
        self.keys.push(k);
        self.vals.push(v);
        true
    }

    pub fn get(self: &Assoc[a, K, V], k: K) -> Option[V] !{} {
        let eqf = self.eq;
        for i in 0..self.keys.len {
            if eqf(self.keys[i], k) {
                return Some(self.vals[i]);
            }
        }
        None
    }
}

fn same_u64(a: u64, b: u64) -> bool !{} {
    a == b
}

test assoc_put_and_get {
    region r {
        let mut m: Assoc[r, u64, u64] = Assoc::new(same_u64);
        let fresh = m.put(7, 700);
        assert fresh;
        assert m.get(7) == Some(700u64);
        assert m.get(8) == None;
    }
}

Note let eqf = self.eq; before the call. A fn-typed field is called through a binding or through parentheses ((self.eq)(a, b)), because self.eq(a, b) would be a method call.

The same three functions can serve two different types side by side. In the playground example below, a one-slot cell lives in a region, and a transform arrives as a plain fn reference. Press "Check", then "Tests": cell_new, cell_get and cell_apply are instantiated once for u64 and once for a two-field struct.

use std::log;

struct Cell[a, T] { v: &a mut Vec[T] }

fn cell_new[a, T: data](x: T) -> Cell[a, T] !{alloc(a)} {
    let c = Cell { v: alloc in a mut Vec::new() };
    c.v.push(x);
    c
}

fn cell_get[a, T: data](c: Cell[a, T]) -> T !{} {
    c.v[0]
}

// The transform arrives as a plain fn reference.
fn cell_apply[a, T: data](c: Cell[a, T], f: fn(T) -> T !{}) !{} {
    c.v[0] = f(c.v[0]);
}

fn double_u64(x: u64) -> u64 !{} {
    x *% 2
}

struct Point { x: i64, y: i64 }

fn negate(p: Point) -> Point !{} {
    Point { x: -p.x, y: -p.y }
}

fn main(sys: Sys) -> u8 !{io, block, alloc(heap), log} {
    region r {
        let c = cell_new(21u64);
        cell_apply(c, double_u64);
        log::info(f"cell holds {cell_get(c)}");
    }
    0
}

test cell_over_u64 {
    region r {
        let c = cell_new(21u64);
        cell_apply(c, double_u64);
        assert cell_get(c) == 42u64;
    }
}

test cell_over_a_struct {
    region r {
        let c = cell_new(Point { x: 3, y: -5 });
        cell_apply(c, negate);
        let p = cell_get(c);
        assert p.x == -3 && p.y == 5;
    }
}

Const generics

Sometimes the thing a function should be generic over is a number rather than a type: the length of a fixed-size array, for example. A [const N: usize] parameter binds such a compile-time usize. You can use N as an array length ([T; N]), in constant arithmetic inside a type ([T; 2*N], with +, - and *), and as an ordinary usize value in the body. Each distinct N produces its own type, so [u64; 3] and [u64; 8] instances of the same function never unify. N is inferred from an argument when it can be, or written explicitly: sum[3](&a).

fn sum[const N: usize](a: &[u64; N]) -> u64 !{} {
    let mut s = 0u64;
    for i in 0..N { s = s + a[i]; }
    s
}

fn twice[const N: usize](a: &[u8; N]) -> [u8; 2*N] !{} {
    let mut out = [0u8; 2*N];
    for i in 0..N {
        out[i] = a[i];
        out[N + i] = a[i];
    }
    out
}

test const_generic_fns {
    let a = [1u64, 2u64, 3u64];
    assert sum(&a) == 6;
    assert sum[3](&a) == 6;
    let p = twice(&[7u8, 9u8]);
    assert p.len == 4 && p[3] == 9u8;
}

A generic type can take a const parameter as well. When nothing in a call carries N (a constructor with no arguments, for example), name it on the callee in brackets:

struct Recent[const N: usize] { slots: [u64; N], next: usize }

impl Recent[const N: usize] {
    pub fn new() -> Recent[N] !{} {
        Recent { slots: [0u64; N], next: 0 }
    }

    pub fn push(self: &mut Recent[N], x: u64) !{} {
        self.slots[self.next % N] = x;
        self.next = self.next + 1;
    }

    pub fn sum(self: &Recent[N]) -> u64 !{} {
        let mut s = 0u64;
        for i in 0..N { s = s +% self.slots[i]; }
        s
    }
}

test recent_keeps_the_last_n {
    let mut w = Recent::new[3]();
    w.push(1);
    w.push(2);
    w.push(3);
    w.push(10);
    assert w.sum() == 15;
}

Three rules come with const parameters. The name must be Uppercase: [const n: usize] is refused, and the help line tells you to rename it to N because lowercase names bind regions. The type must be usize; a const B: bool or const K: u32 parameter is refused with the advice to write usize. And an array length is resolved in constant scope, so a run-time local cannot stand in for N: [0u64; n] where n is a local is refused. For a count computed at run time, use a Vec.

What generics are not

Several familiar parts of generics in Rust, C++ or Java have nowhere to attach in kola:

  • Trait objects and vtables. There is no dynamically dispatched "some type implementing X" value. Every parameter resolves to one concrete type at compile time.

  • Specialization and overlapping impls. A generic function has exactly one body, and it cannot be overridden for a more specific type.

  • Variance. Instantiations have no subtyping relationship, so there is nothing for covariance or contravariance to describe.

  • Higher-kinded types. A parameter is a type, a region or a usize constant, never a type constructor.

  • Default type parameters and blanket impls. struct Pair[A, B = A] does not parse, and there is no way to say "implement this for every T: data".

  • Operator overloading. == is always the language's structural equality. To compare differently, pass a comparator as a fn reference, as Map::new does with eq.

What monomorphization costs

Every instantiation compiles to its own copy, a separately named function, not a shared body behind a run-time tag. If the main of the cell example also used a Cell of Point, kola build would emit these functions (trimmed from the generated C; the k_cell__ prefix comes from the file name cell.kl):

struct k_cell__Cell__uint64_t k_cell__cell_new__uint64_t(KRegion* k_rgn_a, uint64_t x);
uint64_t k_cell__cell_get__uint64_t(struct k_cell__Cell__uint64_t c);
struct k_cell__Cell__struct_k_cell__Point k_cell__cell_new__struct_k_cell__Point(KRegion* k_rgn_a, struct k_cell__Point x);
struct k_cell__Point k_cell__cell_get__struct_k_cell__Point(struct k_cell__Cell__struct_k_cell__Point c);

cell_new and cell_get are written once in the source and appear twice in the binary, each with its own struct type. Code size grows with the number of instantiations a program actually uses (an instantiation nobody calls is never generated). In exchange there is no vtable pointer, no indirect call and nothing for the optimizer to fail to inline. The region parameter becomes an ordinary KRegion* argument. The backends that produce this code are described in Under the hood.