Skip to content
Atoll Book

Generics

Write one declaration that works over a family of types — parameters, inference, explicit arguments, bounds, and opaque types.

Updated View as Markdown

A generic declaration is checked once and specialized per use. Type parameters go in square brackets after the name.

fn identity[T](value: T): T {
    return value
}

fn main(): void {
    n := identity(42)
    s := identity("atoll")
    println("${n} ${s}")
}

identity is checked as generic source before any call exists. Each call then gets its own substitution — identity(42) does not pin T to int for identity("atoll").

Generic types

Structs, enums, and type aliases take parameters with the same bracket syntax.

struct Pair[A, B] {
    first: A
    second: B
}

enum Tree[T] {
    Leaf(T)
    Branch([]Tree[T])
}

type Predicate[T] = fn(T) -> bool

fn count_leaves[T](node: Tree[T]): int {
    match node {
        Leaf(_) => 1
        Branch(children) => {
            mut total := 0
            for child in children {
                total = total + count_leaves(child)
            }
            total
        }
    }
}

fn main(): void {
    entry: Pair[string, int] = Pair { first: "port", second: 8080 }
    tree := Branch([Leaf(1), Branch([Leaf(2), Leaf(3)])])
    println("${entry.first}=${entry.second} leaves=${count_leaves(tree)}")
}

Every use supplies the declared number of arguments, and different arguments produce unrelated types. Pair[int, bool] and Pair[float, string] share a declaration but never a type:

struct Pair[A, B] {
    first: A
    second: B
}

fn f(): void {
    numeric := Pair { first: 1, second: 2 }
    textual: Pair[string, string] = numeric
}

That is rejected with ATOLL2002: expected Pair[string, string], found Pair[int, int].

Inference

A call infers its type arguments from the argument types and from the expected result type at the call site.

struct Wrapper[T] { inner: T }

fn wrap[T](value: T): Wrapper[T] {
    return Wrapper { inner: value }
}

fn main(): void {
    // T comes from the argument.
    a := wrap(1)
    // T comes from the annotation on the destination.
    b: Wrapper[string] = wrap("x")
    // An empty literal carries no information, so annotate it directly.
    rows: []int = []
    empty := wrap(rows)
    println("${a.inner} ${b.inner} ${empty.inner.len()}")
}

An annotation on a binding or a parameter drives inference when the value itself carries no information. Note that the annotation applies to the binding it is written on: empty: Wrapper[[]int] = Wrapper { inner: [] } still fails, because the empty literal inside the struct is checked before the outer annotation reaches it. Annotate the literal, as above.

Explicit type arguments

When inference has nothing to work from, or when you want the instantiation visible in the source, put the arguments in brackets before the call parentheses.

fn width_of[T](): int { return 8 }

fn main(): void {
    n := width_of[int]()
    empty := List.new[string]()
    println("${n} ${empty.len()}")
}

The brackets bind to a call. Without a following (...), value[index] stays an indexing expression, so the two forms never collide. The ::<T> and <T> spellings from other languages are not Atoll syntax.

Bounds

A bare type parameter has no behavior. The body may move values of type T around, but it cannot call methods on them:

trait Summary {
    fn summary(self): string
}

fn show[T](value: T): string {
    return value.summary()
}

That is ATOLL2003: no method summary on type ?1463 — the checker has no reason to believe every T has one. A bound supplies the reason. Write it inline for a single short requirement:

fn largest[T: Comparable[T]](values: []T, fallback: T): T {
    mut best := fallback
    for value in values {
        if value > best { best = value }
    }
    return best
}

fn main(): void {
    println("${largest([3, 9, 4], 0)}")
}

…or in a where clause when several parameters or several requirements interact. + combines requirements on one parameter.

trait Summary {
    fn summary(self): string
}

fn render[T, U](left: T, right: U): string
where T: Summary + Clone, U: Display {
    copy: T = left.clone()
    return "${copy.summary()} / ${right}"
}

struct Note { text: string }

impl Summary for Note {
    fn summary(self): string { return self.text }
}

impl Clone for Note {
    fn clone(self): Note { return Note { text: self.text } }
}

struct Tag { name: string }

impl Display for Tag {
    fn to_string(self): string { return "#${self.name}" }
}

fn main(): void {
    println(render(Note { text: "hi" }, "queued"))
    println(render(Note { text: "hi" }, Tag { name: "release" }))
}

The annotation copy: T is required: Clone::clone is declared to return Self, and the result of that call does not carry the Summary bound on its own. Annotating the binding puts it back on T, where the bound lives.

Bounds are capabilities resolved at check time, not runtime tests. T: Display lets the body call to_string; it does not insert a branch asking whether this particular value implements Display.

Which means a bound is only satisfied by an implementation that actually exists. The prelude implements Display for string and bool and for nothing else, so a T: Display bound does not accept an int — even though "${n}" interpolates one perfectly well through a separate path:

fn render[U](value: U): string
where U: Display {
    return "[${value}]"
}

fn main(): void {
    n: int = 42
    println(render(n))
}

That is ATOLL3100: type ?2 does not implement trait Display, reported when the instantiation is lowered. Give a numeric type its own impl Display, or drop the bound if the body never needs it.

Bounds also work on the operators those traits back. Comparable[T] is what makes value > best legal above, and Numeric is what makes + legal here:

fn total[T](values: []T, zero: T): T
where T: Numeric {
    mut sum := zero
    for value in values {
        sum = sum + value
    }
    return sum
}

fn main(): void {
    println("${total([1, 2, 3], 0)} ${total([1.5, 2.5], 0.0)}")
}

A bounded call inside a closure does not resolve

This is a current compiler limitation worth knowing before you hit it. A method that comes from a bound resolves in the function body, but not inside a closure passed to a combinator:

trait Summary {
    fn summary(self): string
}

fn labels[T](values: []T): []string
where T: Summary {
    return values.map(value => value.summary())
}

The closure parameter is a fresh inference variable that does not carry the outer bound, so the call fails with ATOLL2003. Write the loop instead:

trait Summary {
    fn summary(self): string
}

fn labels[T](values: []T): []string
where T: Summary {
    mut out: []string = []
    for value in values {
        out.add(value.summary())
    }
    return out
}

struct Note { text: string }

impl Summary for Note {
    fn summary(self): string { return self.text }
}

fn main(): void {
    println("${labels([Note { text: "a" }, Note { text: "b" }]).len()}")
}

Generic implementations

An impl block can carry its own parameters. Declare them after impl and use them in the target type.

struct Box[T] { value: T }

impl[T] Box[T] {
    fn get(self): T => self.value

    fn replace(self, next: T): Box[T] => Box { value: next }
}

fn main(): void {
    b := Box { value: 3 }
    println("${b.replace(9).get()}")
}

A trait implementation can be conditional: it applies only when its bounds hold for the arguments.

struct Box[T] { value: T }

impl[T] Equatable for Box[T]
where T: Equatable {
    fn equals(self, other: Box[T]): bool {
        return self.value == other.value
    }
}

fn main(): void {
    println("${Box { value: 3 } == Box { value: 3 }}")
}

Box[Token] satisfies Equatable only when Token does. A blanket implementation goes further and targets a type variable directly:

trait Printable: Display + Debug {}

impl[T] Printable for T
where T: Display + Debug {}

struct Tag { name: string }

impl Display for Tag {
    fn to_string(self): string { return self.name }
}

impl Debug for Tag {
    fn debug_string(self): string { return "Tag(${self.name})" }
}

fn emit[T](value: T): string
where T: Printable {
    return value.to_string()
}

fn main(): void {
    println(emit(Tag { name: "release" }))
}

Blanket implementations are project-wide policy — see Implementations for the coherence rules that keep two of them from overlapping.

Self

Inside a trait, Self names the implementing type, which lets a requirement relate its inputs and outputs without a second type parameter.

trait Merge {
    fn merge(self, other: Self): Self
}

struct Bag { count: int }

impl Merge for Bag {
    fn merge(self, other: Bag): Bag {
        return Bag { count: self.count + other.count }
    }
}

fn fold_all[T](values: []T, seed: T): T
where T: Merge {
    mut acc := seed
    for value in values {
        acc = acc.merge(value)
    }
    return acc
}

fn main(): void {
    total := fold_all([Bag { count: 1 }, Bag { count: 2 }], Bag { count: 0 })
    println("${total.count}")
}

In the implementation, write the concrete type name — Bag, not Self. Self as a return type in an inherent impl does not unify with the concrete target.

Opaque types

impl Trait names “some type satisfying this contract” without naming which.

trait Shape {
    fn area(self): float
}

struct Square { side: float }
struct Circle { radius: float }

impl Shape for Square {
    fn area(self): float { return self.side * self.side }
}

impl Shape for Circle {
    fn area(self): float { return 3.14159 * self.radius * self.radius }
}

fn describe(shape: impl Shape): string {
    return "area ${shape.area()}"
}

fn main(): void {
    println(describe(Square { side: 2.0 }))
    println(describe(Circle { radius: 1.0 }))
}

In parameter position, each call supplies one concrete argument satisfying the trait, and the body is specialized per argument type — impl Shape there is shorthand for an anonymous type parameter bounded by Shape.

In return position, the declaring function owns one hidden concrete type: callers may use the promised behavior but cannot name the representation, and two functions returning impl Shape do not share an opaque type even when their bodies currently return the same struct.

Return-position impl Trait type-checks today, but the opaque result does not survive lowering: calling a trait method on it, or passing it where the bound must be re-proved, fails at build time.

trait Shape {
    fn area(self): float
}

struct Square { side: float }

impl Shape for Square {
    fn area(self): float { return self.side * self.side }
}

fn unit_square(): impl Shape {
    return Square { side: 1.0 }
}

fn main(): void {
    shape := unit_square()
    println("${shape.area()}")
}

Until that is finished, return the concrete type — fn unit_square(): Square — and keep impl Trait for parameters.

Atoll uses static dispatch throughout. There is no dyn Trait, no vtable, and no downcast. When alternatives must stay open at runtime, use an enum or an anonymous union.

Compile-time type matching

match T selects on a type parameter at specialization time.

fn width_code[T](): int {
    return match T {
        u8 => 1
        u16 => 2
        u32 => 4
        else => 0
    }
}

fn main(): void {
    println("${width_code[u8]()} ${width_code[u32]()} ${width_code[int]()}")
}

Each arm is resolved once per instantiation, so the specialized body contains only the selected branch. This is not a runtime value is Type test — there is no value involved.

Errors and effects

A generic callable can carry fallibility through a function parameter. E is an ordinary type parameter that happens to sit on the error channel.

error CheckError { Rejected }

fn keep_all[T, E](values: []T, check: fn(T) -> Result[T, E]): []T ! E {
    mut out: []T = []
    for value in values {
        out.add(check(value)?)
    }
    return out
}

fn require_positive(n: int): int ! CheckError {
    if n <= 0 { error Rejected }
    return n
}

fn run(): []int ! CheckError {
    return keep_all([1, 2, 3], require_positive)?
}

fn main(): void {
    empty: []int = []
    println("${run().unwrap_or(empty).len()}")
}

A closure works in the same position: keep_all([1, 2, 3], n => require_positive(n)) infers T = int and E = CheckError identically.

Note the spelling of the parameter type. T ! E is sugar available on a declaration’s return type; inside a function type the fallible result must be written out as Result[T, E]. The sugared form does not unify with the function it is meant to accept:

error CheckError { Rejected }

fn keep_all[T, E](values: []T, check: fn(T) -> T ! E): []T ! E {
    mut out: []T = []
    for value in values {
        out.add(check(value)?)
    }
    return out
}

fn require_positive(n: int): int ! CheckError {
    if n <= 0 { error Rejected }
    return n
}

fn run(): []int ! CheckError {
    return keep_all([1, 2, 3], require_positive)?
}

That reports ATOLL2002: expected fn(int) -> int ! ?1470, found fn(int) -> Result[int, CheckError].

The error type stays concrete at each use, so keep_all does not erase which failures a caller must handle. The same holds for effects: passing a suspending closure keeps Suspend on the row. Genericity never makes a host operation pure — see Effects.

Recursive generics

A recursive generic type needs a representational break, exactly as a non-generic one does. A managed container supplies it.

enum Node[T] {
    Empty
    Children([]Node[T])
}

fn depth[T](node: Node[T]): int {
    match node {
        Empty => 0
        Children(kids) => {
            mut best := 0
            for kid in kids {
                d := depth(kid)
                if d > best { best = d }
            }
            best + 1
        }
    }
}

fn main(): void {
    tree: Node[int] = Children([Empty, Children([Empty])])
    println("${depth(tree)}")
}

A payload holding Node[T] inline with no indirection has no finite size and is rejected.

Monomorphization

The compiler specializes each reachable combination of type arguments: generic functions, methods, closures, and layouts all become concrete before codegen. That is what makes direct calls and flat field layouts possible.

Specialization is an implementation strategy, not permission to inspect a type parameter without a bound. The order is:

  1. check the generic body against its declared bounds only;
  2. infer or read concrete arguments at each reachable use;
  3. substitute types, associated types, methods, errors, and effects;
  4. reuse an existing specialization with the same canonical arguments, or make one;
  5. lower and validate the concrete body.

A failure at step 1 belongs at the declaration; a failure caused by a particular substitution should name both the declaration and the instantiating call. Many distinct instantiations cost code size, so prefer one generic algorithm over hand-written copies — but do not invent wrapper types just to force extra specializations.

A composed example

A paginated result type: one generic struct, an inherent generic impl, a static constructor, and a generic function over it.

struct Page[T] {
    items: []T
    next_cursor: string?
}

impl[T] Page[T] {
    fn empty(): Page[T] => Page { items: [], next_cursor: None }

    fn len(self): int => self.items.len()

    fn is_last(self): bool => self.next_cursor.is_none()
}

fn paginate[T](all: []T, size: int): Page[T] {
    if all.len() <= size {
        return Page { items: all, next_cursor: None }
    }
    return Page { items: all.take(size), next_cursor: Some("${size}") }
}

fn describe[T](page: Page[T]): string
where T: Display {
    mut joined := ""
    for item in page.items {
        if joined.len() > 0 { joined = joined + ", " }
        joined = joined + "${item}"
    }
    suffix := if page.is_last() { "end" } else { "more" }
    return "${joined} (${suffix})"
}

fn main(): void {
    names := paginate(["ada", "bob", "cy", "dee"], 2)
    numbers := paginate([1, 2, 3, 4, 5], 2)
    blank: Page[string] = Page.empty()
    println(describe(names))
    println("${numbers.len()} ${numbers.is_last()}")
    println("${blank.len()} ${blank.is_last()}")
}

Page is declared once; Page[int] and Page[string] are two independent static instantiations of that source. paginate is specialized for both; describe only for Page[string], because that is the one whose element type satisfies its Display bound.

Navigation

Type to search…

↑↓ navigate↵ selectEsc close