Sn Tin

Chapter 5 of 8

Generics

Generic code is specialised at compile time. Stack<int> and Stack<string> become separate WebAssembly functions.

examples/06-generics.tintin run examples/06-generics.tin
// Generics are monomorphised: Stack<int> and Stack<string> each compile to
// their own specialised WebAssembly, with no boxing and no runtime type checks.

type Stack<T> = { items: T[] }

fn newStack<T>(): Stack<T> {
  Stack { items: [] }
}

fn Stack.push<T>(s: inout Stack<T>, item: T) {
  s.items.push(item)
}

fn Stack.pop<T>(s: inout Stack<T>): Option<T> {
  if s.items.len == 0 { None } else { Some(s.items.pop()) }
}

type Pair<A, B> = { first: A, second: B }

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

fn largest<T>(xs: T[]): Option<T> {
  if xs.len == 0 { return None }
  var best = xs[0]
  for x in xs {
    if x > best { best = x }
  }
  Some(best)
}

fn main() {
  var numbers: Stack<int> = newStack()
  numbers.push(1)
  numbers.push(2)
  numbers.push(3)
  print(numbers.pop())
  print(numbers.pop())

  var words: Stack<string> = newStack()
  words.push("tin")
  print(words.pop())
  print(words.pop())

  let p = Pair { first: "answer", second: 42 }
  print(p)
  print(swap(p))

  print(largest([3, 9, 4]))
  print(largest([2.5, 1.5]))
  print(largest(["pear", "apple", "zebra"]))
}
Some(3)
Some(2)
Some("tin")
None
Pair { first: "answer", second: 42 }
Pair { first: 42, second: "answer" }
Some(9)
Some(2.5)
Some("zebra")

There's no boxing and no runtime type check: the checker monomorphises each use. Recursive sum types work the same way, which is how the next example builds an immutable tree.

examples/07-tree.tintin run examples/07-tree.tin
// A recursive sum type: an immutable binary search tree.

type Tree =
  | Leaf
  | Node { left: Tree, value: int, right: Tree }

fn insert(t: Tree, v: int): Tree => match t {
  Leaf => Node { left: Leaf, value: v, right: Leaf }
  Node { left, value, right } =>
    if v < value { Node { left: insert(left, v), value, right } }
    else if v > value { Node { left, value, right: insert(right, v) } }
    else { t }
}

fn contains(t: Tree, v: int): bool => match t {
  Leaf => false
  Node { left, value, right } =>
    if v == value { true } else if v < value { contains(left, v) } else { contains(right, v) }
}

fn depth(t: Tree): int => match t {
  Leaf => 0
  Node { left, right } => 1 + max(depth(left), depth(right))
}

fn inOrder(t: Tree, out: inout int[]) {
  match t {
    Leaf => {}
    Node { left, value, right } => {
      inOrder(left, &out)
      out.push(value)
      inOrder(right, &out)
    }
  }
}

fn main() {
  var tree: Tree = Leaf
  for v in [50, 30, 70, 20, 40, 60, 80, 30] {
    tree = insert(tree, v)
  }
  var sorted: int[] = []
  inOrder(tree, &sorted)
  print(sorted)
  print("depth: {depth(tree)}")
  print("contains 60? {contains(tree, 60)}")
  print("contains 65? {contains(tree, 65)}")
}
[20, 30, 40, 50, 60, 70, 80]
depth: 3
contains 60? true
contains 65? false