Lesson 17 of 25 · Data and types

Generics and interfaces

Generics let you write a function or a container once and use it with any type. Interfaces describe what a type can do, so that different types can be handled by the same code.

In this lesson

Generic functions and structs
A generic container
Several type parameters
Interfaces
impl: an interface for an existing type
Bounds: generics that call methods
Mixed collections with dyn
Generic or dyn?
Rules of thumb

Generic functions and structs

Write <T> after the name and the function or struct works for any type T. For every type you actually use, the compiler builds a separate, fully specialised copy, so generic code runs as fast as code written by hand for that type.

generics.salam

struct Box<T>:
    pub inside: T
end

func larger<T>(a: T, b: T): T:
    if a > b:
        ret a
    end
    ret b
end

func main:
    println larger(3, 9), larger("a", "b"), larger(2.5, 1.5)
    b := Box { inside = "a gift" } as Box<str>
    println b.inside
end

Output9 b 2.5 a gift

The type of a generic function comes from its arguments: larger(3, 9) uses int and larger("a", "b") uses str. You cannot name the type at the call (larger<int>(3, 9) does not parse), so if a literal should have another type, cast it with as. A generic struct takes its type from the cast, as in Box { ... } as Box<str>.

The body has to make sense for every type you call it with. larger compares with >, which works for numbers and strings. Call it with two structs and the compiler stops with E021: cannot compare 'P' and 'P'.

A generic container

Most generic code you write will be a container: a struct that holds values of some type and offers a small, clear set of operations on them. This stack keeps its items in a Vector<T> and exposes only what a stack should do. The same code serves as an undo history of strings and as a list of page numbers.

generics-stack.salam

struct Stack<T>:
    items: Vector<T> = Vector {}

    pub func push(x: T):
        this.items.push(x)
    end

    pub func pop(): T:
        ret this.items.pop()
    end

    pub func peek(): T:
        ret this.items.get(this.items.len() - 1)
    end

    pub func size(): int:
        ret this.items.len()
    end

    pub func is_empty(): bool:
        ret this.items.len() == 0
    end

    pub func free():
        this.items.free()
    end
end

func main:
    undo := Stack {} as Stack<str>
    defer undo.free()
    undo.push("type 'hello'")
    undo.push("make it bold")
    undo.push("delete a line")
    println undo.size(), "steps, last:", undo.peek()
    until not undo.is_empty():
        println "undo", undo.pop()
    end

    pages := Stack {} as Stack<int>
    defer pages.free()
    pages.push(1)
    pages.push(14)
    println "back to page", pages.pop()
end

Output3 steps, last: delete a line undo delete a line undo make it bold undo type 'hello' back to page 14

The struct owns a Vector, so it also gets a free method, and each stack is released with defer right after it is created. That is the same habit as for a plain Vector; the memory lesson explains why.

Several type parameters

A generic can take more than one type, separated by commas. Pair<A, B> holds two values of different types, and swap turns a Pair<A, B> into a Pair<B, A>. Printing a generic struct shows the types it was built with.

generics-pair.salam

struct Pair<A, B>:
    pub first: A
    pub second: B
end

func swap<A, B>(p: Pair<A, B>): Pair<B, A>:
    ret Pair { first = p.second, second = p.first }
end

func main:
    stock := Pair { first = "pencils", second = 120 } as Pair<str, int>
    println stock
    println swap(stock)
    point := Pair { first = 2.5, second = -1.0 } as Pair<f64, f64>
    println point.first + point.second
end

OutputPair<str, i32> {first = "pencils", second = 120} Pair<i32, str> {first = 120, second = "pencils"} 1.5

Interfaces

An interface is a list of method signatures. A struct that has all of those methods implements the interface automatically; there is no "implements" line to write. A parameter of type dyn Shape accepts any value whose type implements Shape.

interface.salam

interface Shape:
    func area(): int
    func name(): str
end

struct Square:
    side: int = 0
    pub func area(): int: ret this.side * this.side end
    pub func name(): str: ret "square" end
end

struct Rectangle:
    width: int = 0
    height: int = 0
    pub func area(): int: ret this.width * this.height end
    pub func name(): str: ret "rectangle" end
end

func describe(s: dyn Shape):
    println s.name(), s.area()
end

func main:
    describe(Square { side = 5 })
    describe(Rectangle { width = 4, height = 6 })
end

Outputsquare 25 rectangle 24

An interface method may carry a default body. A struct that does not write that method gets the default, and a struct that does write it keeps its own. The default can call the other methods of the interface through this.

interface-default.salam

interface Shape:
    func area(): f64
    func describe(): str:
        ret "area " + this.area()
    end
end

struct Circle:
    pub radius: f64 = 1.0
    pub func area(): f64:
        ret 3.14 * this.radius * this.radius
    end
end

struct Square:
    pub side: f64 = 1.0
    pub func area(): f64:
        ret this.side * this.side
    end
    pub func describe(): str:
        ret "a square with side " + this.side
    end
end

func main:
    println Circle { radius = 2.0 }.describe()
    println Square { side = 3.0 }.describe()
end

Outputarea 12.56 a square with side 3

If a type is missing a method, the compiler says so where the value is used as the interface: E002: 'Box' does not implement interface 'Scored': missing method 'score'.

impl: an interface for an existing type

impl Interface on Type gives the methods of an interface to a type you did not write, even a built-in one like int or str. Inside those methods, this is the value itself. The <T: Ranked> in this example is a bound: the function accepts only types that implement Ranked.

impl.salam

interface Ranked:
    func rank(): int
end

impl Ranked on int:
    func rank(): int: ret this end
end

impl Ranked on str:
    func rank(): int: ret len(this) end
end

func higher<T: Ranked>(a: T, b: T): int:
    if a.rank() > b.rank():
        ret a.rank()
    end
    ret b.rank()
end

func main:
    println higher(3, 9)
    println higher("hi", "salam")
end

Output9 5

Bounds: generics that call methods

A plain <T> knows nothing about T, so the body cannot call methods on it. A bound such as <T: Scored> promises that every T has the methods of Scored, and the body is free to use them. Bounds work on structs too: Board<T: Scored> is a leaderboard for players, bids or anything else that has a score.

generics-bound.salam

interface Scored:
    func score(): int
    func label(): str
end

struct Player:
    pub name: str = ""
    pub points: int = 0
    pub func score(): int: ret this.points end
    pub func label(): str: ret this.name end
end

struct Bid:
    pub bidder: str = ""
    pub amount: int = 0
    pub func score(): int: ret this.amount end
    pub func label(): str: ret this.bidder + " with " + this.amount end
end

struct Board<T: Scored>:
    entries: Vector<T> = Vector {}

    pub func add(x: T):
        this.entries.push(x)
    end

    pub func best(): T:
        mut top := this.entries.get(0)
        each e in this.entries:
            if e.score() > top.score():
                top = e
            end
        end
        ret top
    end

    pub func total(): int:
        mut sum := 0
        each e in this.entries:
            sum += e.score()
        end
        ret sum
    end

    pub func free():
        this.entries.free()
    end
end

func higher<T: Scored>(a: T, b: T): T:
    if b.score() > a.score():
        ret b
    end
    ret a
end

func main:
    team := Board {} as Board<Player>
    defer team.free()
    team.add(Player { name = "Sara", points = 42 })
    team.add(Player { name = "Reza", points = 57 })
    team.add(Player { name = "Mina", points = 49 })
    println "best player:", team.best().label()
    println "team total:", team.total()

    first := Bid { bidder = "Ali", amount = 120 }
    second := Bid { bidder = "Nima", amount = 150 }
    println "winning bid:", higher(first, second).label()
end

Outputbest player: Reza team total: 148 winning bid: Nima with 150

Each Board holds a single type: a Board<Player> cannot also hold a Bid. That is the other side of the speed of generics, and it is exactly the problem dyn solves.

Mixed collections with dyn

dyn Notifier is a value of any type that implements Notifier, decided at run time. With it, one list can hold different types: the Vector<dyn Notifier> below holds an email sender and two SMS senders, and one loop sends through all of them. A struct field can be dyn as well, so an alert can be wired to whichever channel you choose.

interface-dyn.salam

interface Notifier:
    func send(who: str, text: str): bool
    func channel(): str
end

struct Email:
    pub server: str = "mail.example.com"
    pub func send(who: str, text: str): bool:
        println "  email to", who, "via", this.server, "|", text
        ret true
    end
    pub func channel(): str: ret "email" end
end

struct Sms:
    pub credit: int = 0
    pub func send(who: str, text: str): bool:
        if this.credit == 0:
            ret false
        end
        println "  sms to", who, "|", text
        ret true
    end
    pub func channel(): str: ret "sms" end
end

struct Alert:
    pub via: dyn Notifier = Email {}
    pub func fire(who: str):
        ok := this.via.send(who, "disk almost full")
        println "alert by", this.via.channel(), ok ? "sent" : "failed"
    end
end

func main:
    channels := Vector {} as Vector<dyn Notifier>
    channels.push(Email {})
    channels.push(Sms { credit = 0 })
    channels.push(Sms { credit = 5 })
    mut delivered := 0
    each c in channels:
        if c.send("sara", "your order has shipped"):
            delivered += 1
        end
    end
    println delivered, "of", channels.len(), "delivered"
    each c in channels:
        c.free()
    end
    channels.free()

    alert := Alert { via = Sms { credit = 1 } }
    alert.fire("ops")
    alert.via.free()
end

Output email to sara via mail.example.com | your order has shipped sms to sara | your order has shipped 2 of 3 delivered sms to ops | disk almost full alert by sms sent

A dyn value lives in a small box on the heap. Storing a value copies it into the box, so changing the original later does not reach the stored copy. Freeing a Vector<dyn ...> frees the list but not the boxes in it, which is why the example frees each element before the Vector itself. A dyn field is released the same way, with field.free().

Generic or dyn?

	`<T: Shape>`	`dyn Shape`
The type is chosen	While compiling, with one copy of the code per type	At run time, with one copy of the code for all types
Calls	Direct, as fast as hand-written code	Through a small dispatch step
Different types in one collection	No, one type per instance	Yes, `Vector<dyn Shape>`
Memory	Values are stored directly	Each value is boxed, and the box has to be freed
Good for	Containers and algorithms	Handlers, plugins, lists of different things

Rules of thumb

Use a generic when the same code works for many types, and add a bound as soon as the body needs a method.
Use dyn only when one collection or field must hold different types.
Keep interfaces small. Two or three methods are easy to implement and easy to give defaults.
Use impl ... on to teach an existing type, even int or str, a new interface without touching its code.
A generic container that owns a Vector or a HashMap needs a free method, and boxed dyn values are freed one by one.

Generic enums such as Maybe<T> and Result<T, E> are covered in the enums lesson, and the built-in generic containers Vector and HashMap in the collections lesson.