Heroes / Guide / chapter 11

Values all the way down

Building and traversing trees while keeping copies of values independent.

In Heroes, changing a copy of a value does not change the original. You can still build a tree whose branches have the same type as the tree by using a container such as an array.

Why a field cannot directly contain its own type

If a case directly contains another value of its own type, the compiler reports the problem and suggests a solution:

$ heroes check trees.hero
error[no_size]: `variant Expr` contains itself, so it has no size
  at trees.hero:16:16
     |
  16 |         inner: Expr
     |                ^^^^
  note: every value is an independent copy, so `Expr` holding one more `Expr` would need one at every depth
  note: `[T]` holds its contents elsewhere, so it is how a type contains itself
  fix (guess): hold them in an array: `[Expr]`

A record or variant includes the storage for its fields. If a field directly contained another Expr, which contained another, one value would require infinite memory. Heroes rejects this definition.

Using an array for branches

variant Expr
    number
        v: i64
    add
        parts: [Expr]
    multiply
        parts: [Expr]
    negate
        inner: [Expr]

The representation of [Expr] has a fixed size: its array elements are stored separately. The Expr type can therefore contain other Expr values through the array without having infinite size. Here negate uses a list with one element. Maps can also represent recursive structures.

With Heroes values, you cannot build reference cycles. The runtime, the code that supports execution, frees memory when its reference count reaches zero. No garbage collector is needed to find cycles, and no weak annotations are needed to mark weak references.

Walking it is one match and one for

# Recursion over a variant is one `match` and one `for` — and the `match` is
# exhaustive or it does not compile.
function value_of(e: Expr) -> i64
    return match e
        .number n   => n.v
        .add a      => sum_of(a.parts)
        .multiply m => product_of(m.parts)
        .negate g   => 0 - first_value(g.inner)

function sum_of(parts: [Expr]) -> i64
    total: i64 @= 0

    for part in parts
        total @ total + value_of(part)

    return total

function product_of(parts: [Expr]) -> i64
    total: i64 @= 1

    for part in parts
        total @ total * value_of(part)

    return total

value_of and sum_of call each other. You can declare them in either order without forward declarations.

The initial value is 0 for a sum and 1 for a product. So value_of(.add(parts: [])) returns 0 and value_of(.multiply(parts: [])) returns 1. The tests below check these results.

Building one

# The annotation on the binding is not decoration: a leading-dot case takes its
# variant from the context, and a bare `=` gives it none (§4.5). Written without
# it, the compiler says so and names the three places the type could come from.
function two_plus_three_times_four() -> Expr
    three_times_four: Expr = .multiply(parts: [.number(v: 3), .number(v: 4)])
    return .add(parts: [.number(v: 2), three_times_four])

The return line needs no annotation, because the function signature already says Expr. The binding above it does, and leaving it out gets an error that names where the type could have come from:

$ heroes check trees.hero
error[cannot_infer]: `.multiply` does not say which variant it belongs to — the type has to come from the context (a signature, an annotation, or the value being returned)
  at trees.hero:81:24
     |
  81 |     three_times_four = .multiply(parts: [.number(v: 3), .number(v: 4)])
     |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Checking empty cases

test "the tree evaluates and measures itself"
    e = two_plus_three_times_four()
    assert value_of(e) == 14
    assert depth_of(e) == 3
    assert is_combination(e)
    assert is_combination(.number(v: 1)) == false

test "negation nests, and an empty child list is neutral"
    assert value_of(.negate(inner: [.number(v: 7)])) == 0 - 7
    assert value_of(.add(parts: [])) == 0
    assert value_of(.multiply(parts: [])) == 1
    assert value_of(.negate(inner: [])) == 0

The tests check the result of the empty cases. The four assertions detect accidental changes to the behaviour of value_of.

# Two cases share one answer, so their patterns share one arm (`|`).
function is_combination(e: Expr) -> bool
    return match e
        .add _ | .multiply _ => true
        .number _            => false
        .negate _            => false

function main()
    print(value_of(two_plus_three_times_four()))

$ heroes run examples/gallery/11-trees.hero
14

This example represents and calculates two plus three times four using a tree of values. The Heroes compiler uses larger structures of the same kind to represent the programs it reads.

Next: Modules and files, which is where a program bigger than one file puts them. Back to the chapter list. ← Previous: Maps

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.