Chapter 4

Functions

fn add(a, b) = a + b                    # inferred as Int, Int -> Int
fn scale(v: Float, k: Float) = v * k    # annotated
fn apply(f, x) = f(x)                   # higher-order

Functions are values: pass them by name (map(xs, double)) or as lambdas. Closures capture the variables they use by value. A lambda's body is an expression, or an indented block on the lines after the ->:

nearer = \a, b ->
  da = dist(a, origin)
  db = dist(b, origin)
  da < db

Inside parentheses layout is off, so a lambda written as an argument stays on one line; bind the long one first.

Generics

A function used at more than one type is generic automatically:

fn id(x) = x                # forall a. a -> a
fn len(l) = match l         # forall a. List(a) -> Int
  Nil -> 0
  Cons(_, rest) -> 1 + len(rest)

Generic functions are monomorphized: the compiler emits one specialized copy per concrete type, so there is no boxing and no dispatch overhead.

Requirements a body imposes travel with the type. fn biggest(a, b) = if a > b then a else b works for any ordered type, and using it at a type that isn't ordered is a compile error naming the function and the type. A requirement may also be said, in a where clause after the signature:

fn shout(x: a) -> Str where Describe(a) = describe(x) + "!"
fn sorted(xs: List(a)) -> List(a) where Ord(a) = ...

It names a trait of one of the signature's type variables — a user trait, or Ord or Show — and is checked at every use of the function like a requirement the body implied, naming the function, the type and the trait. What it adds is that the signature says it: rill types and a reader see the contract without the body, and a use at the wrong type is refused for the reason the author gave. The body is still inferred; a where says what is required, not what the body may do.

A lowercase name in an annotation is a type variable, and the same name is the same type throughout the signature: fn same(x: a, y: a) = x takes two of one type, whatever it is.

A function is generic at every use, wherever in the file it is defined. The one thing inference will not do is give a function two types inside its own dependency group — g used at Int and at Str by an f that g calls back — or let it call itself at another type. Writing the whole signature down lifts that: fn g(x: a, n: Int) -> a declares the scheme, every use takes it at its own type, and the body is held to the declaration — one that only works for Int is refused as not keeping its promise. What stays out of reach is recursion whose types never stop growing: a call to itself at a bigger type each time is stopped when the types have grown past anything a program writes, since a copy is made per type; and a type that holds itself at a bigger type, Nest(a) holding a Nest((a, a)), is refused where it is written, for the same reason.

Loops

Counting over a range has a form of its own:

for i in 0..n                  # the half-open range: 0 up to but not n
  v[i] = i * i

A loop that carries something says so, and is worth what it carried:

total = for i in 0..#v with acc = 0
  acc + v[i]                   # the body's value is the next `acc`

Writing the accumulation in the body instead — acc = acc + v[i], with the with left off — is refused, and named as what it is. A binding is not a value, so a block ending in one has nothing to answer with and the name it bound can never be read: the loop would have run and thrown every iteration away. The error says so wherever it happens, and says with when the binding's value reads the name it is binding.

Both forms are spelled out as the tail-recursive function below before anything else looks at them — the end of the range is evaluated once, and what the loop carries is a parameter, which is to say a register. Carrying it in a one-element buffer instead, which is what a program without this had to do, puts it in memory and reaches through a pointer for every touch. +=, -=, *= and /= write a buffer element in terms of what it held: v[i] += 1. The index is evaluated once, so off[eu[i]] += 1 reads eu[i] one time.

Everything else is tail recursion: a call in tail position compiles to a jump, so it runs in constant stack, exactly like a loop. That holds for a loop written as several functions calling each other as much as for one calling itself, and it holds whatever the loop's value is — Rill's functions use LLVM's guaranteed-tail-call convention and mark the call musttail, so it is a promise the optimizer cannot take back rather than a hint it usually honours.

One limit on the promise: it is made through the machine's registers, and a signature with more than six integer or pointer parameters, or more than eight floats, takes the C convention instead (a flat record counts by its fields, a closure's environment as one more). A function calling itself still runs in constant stack; several such functions calling each other in tail position do not, and the compiler warns, naming the two and the count. Pack the extras into one tuple — a tuple is one pointer — and the promise is back.

fn sum_to(n) = go(n, 0)
fn go(i, acc) = if i == 0 then acc else go(i - 1, acc + i)   # a loop

A loop written this way is usually about the values around it, so it can be written there: a fn inside a body sees the names in scope, and may call itself and the functions beside it.

fn sum_to(n) =
  fn go(i, acc) = if i > n then acc else go(i + 1, acc + i)
  go(1, 0)                     # `n` comes from the enclosing function

Only the loop's own variables are parameters; everything else is simply in scope. The compiler lifts each such function out to the top level and hands it the names it uses, so nothing is allocated and the tail call is still a tail call — a local function is a loop, not a closure. That is also why it can only be called: there is no single value to pass around for one, since each call site supplies the captured names. A lambda is the thing to pass around.

A local function that captures something is typed together with the one it is written inside, which is what lets a captured buffer keep its width. The price is that it has one type rather than a scheme: a capturing helper used at two different types has to be a top-level function, where it generalizes as usual. One that captures nothing is tied to nothing, and generalizes where it stands:

fn main() =
  fn id(x) = x

  println(id(1))
  println(id("a"))

Each parameter is a loop variable and the if is the exit condition. This holds for loops that print, and for server loops that run forever:

fn worker(jobs, results) =
  n = recv(jobs)
  send(results, n * 2)
  worker(jobs, results)        # runs forever, stack never grows

Most everyday loops are written with the prelude instead — range, map, filter, fold — which are themselves tail recursive:

range(1, 10) |> filter(\x -> x % 2 == 0) |> map(\x -> x * x) |> sum

See examples/loops.rill.