Heroes / Guide / chapter 8

Generics and function values

One function can work with different types and take other functions as arguments.

A generic function can perform the same operation on different types. For example, you can write one function to transform list elements, whether they are numbers or strings. The arguments at each call determine the concrete types.

Declaring type parameters

# The parentheses around a function type are mandatory: without them
# `f: function(A) -> B -> [B]` would be a guessing game.
function each<A, B>(xs: [A], f: (function(A) -> B)) -> [B]
    out: [B] @= []

    for x in xs
        out @ out.push(f(x))

    return out

<A, B> declares two type parameters. The compiler determines the concrete types from the call arguments. In the body, [A] means a list of A values, and out: [B] @= [] declares an empty list of B values. An empty list needs an explicit type because it has no elements to infer it from.

Three rules for generic functions

• Only functions can be generic. A field of a record or a variant has one concrete type, and there is no record Box[T]. A list and a map each take an element type, and each one holds a single type at a time: ys = [1, "a"] is an error[type_mismatch]. To keep values of different kinds in one list, declare a variant and make a list of that.
• No conditions on the types. There is no way to say “any A, as long as it can be compared”. If a function needs an operation on A, you pass that operation in as an argument, like f above.
• Do not write type arguments in a call. The compiler infers them from the arguments. If it cannot, it reports an error. The syntax each<i64, str>(…) is not allowed.

Call each with its ordinary arguments; their types give the compiler the information it needs.

Functions are values, and they have names

# The functions passed above are ordinary declarations. No lambdas exist.
function double(n: i64) -> i64
    return n * 2

function is_positive(n: i64) -> bool
    return n > 0

function add(a: i64, b: i64) -> i64
    return a + b

function label(n: i64) -> str
    return n.to_str()

The name of a function declared at the file’s top level, written without parentheses, is a value you can pass to another function. Heroes has no lambdas, or anonymous functions, and no functions that capture surrounding variables. Every function therefore has a name and a declaration you can read, test and reuse.

This is not a postponement, it is a decision that was taken. Anonymous functions were examined and refused, and what settled it is not an argument but a measurement: underneath, a function you pass around is a single memory address, a number saying where the code sits, and that is exactly what a C library expects to receive. A function carrying values with it would take up several times as much room. Tried against a real C library, with every one of the compiler’s checks turned on, the compilation reported nothing and the program crashed as soon as it ran.

The gain, measured, was small. In the Heroes compiler, which is written in Heroes and runs to more than fifty thousand lines, a function is passed to another one in fewer than five places. The one-line named functions a lambda would have deleted come to fewer than twenty-five, all of them in the example programs, and more than half the files holding them are the very examples whose subject this is: they are the demonstration, not the nuisance. Nor is the choice an isolated one: other languages built under the same constraints refuse the same thing, and say so in their own documentation. It is one of the no’s on the record, with who said it and what would prove it wrong: the refusals →

Write a function type as (function(A) -> B). The outer parentheses are required: without them, f: function(A) -> B -> [B] would be ambiguous. The compiler reports the error:

$ heroes check generics.hero
error[expected_type]: expected a type, found `function` — a type is `i64`, `f64`, `bool`, `str`, `[T]`, `{K: V}`, `T?`, `()`, or the name of a `record` or `variant`
  at generics.hero:18:38
     |
  18 | function keep_if<A>(xs: [A], ok_for: function(A) -> bool) -> [A]
     |                                      ^^^^^^^^

Filtering and combining elements

function keep_if<A>(xs: [A], ok_for: (function(A) -> bool)) -> [A]
    out: [A] @= []

    for x in xs
        if ok_for(x)
            out @ out.push(x)

    return out

This function has one type parameter because filtering preserves the element type. If you pass a function with incompatible types, the error identifies the argument and shows both types:

$ heroes check generics.hero
error[type_mismatch]: expected `bool`, found `i64`
  at generics.hero:52:36
     |
  52 |     assert keep_if([-1, 2, -3, 4], double) == [2, 4]
     |                                    ^^^^^^

# Two type parameters, and the accumulator is the one that names the result.
function combine<A, B>(xs: [A], start: B, step: (function(B, A) -> B)) -> B
    total: B @= start

    for x in xs
        total @ step(total, x)

    return total

combine iterates over a list of A values and calculates a result of type B. By changing the step function, you can sum numbers, join strings or count elements that meet a condition.

One generic, three element types

test "one generic, three element types"
    assert each([1, 2, 3], double) == [2, 4, 6]
    assert each([1, 2], label) == ["1", "2"]
    assert keep_if([-1, 2, -3, 4], is_positive) == [2, 4]
    assert combine([1, 2, 3, 4], 0, add) == 10

If you pass each a function that returns str, the result is a [str] list. The compiler infers and checks the types in both calls.

The compiler generates a version of each for each combination of concrete types used by the program. The C output therefore contains separate versions for integers and strings. The program does not need to select types at run time or wrap values in a generic container. Additional versions do increase the executable’s size.

function main()
    print(combine([1, 2, 3, 4], 0, add))

$ heroes run examples/gallery/06-generics.hero
10

The functions map, filter, fold, find, any and all are already available and are written in Heroes. This chapter’s three functions illustrate how they work under different names, because you cannot redefine a built-in name.

Next: Strings, learn to distinguish bytes from characters and choose the right operations. Back to the chapter list. ← Previous: Bindings and mutation

Run a program of your own: it takes four commands. Or take the whole language in one file, and every program already written in it.