Heroes / Guida / capitolo 11

Valori fino in fondo

Costruire e percorrere alberi mantenendo indipendenti le copie dei valori.

In Heroes, modificare una copia di un valore non cambia l’originale. Puoi comunque costruire un albero i cui rami hanno lo stesso tipo dell’albero: basta usare un contenitore come un array.

Perché un campo non può contenere direttamente se stesso

Se un caso contiene direttamente un altro valore dello stesso tipo, il compilatore segnala il problema e suggerisce una soluzione:

$ 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]`

Un record o un variant include lo spazio dei propri campi. Se un campo contenesse direttamente un altro Expr, e questo un altro ancora, servirebbe una quantità infinita di memoria per un solo valore. Heroes rifiuta questa definizione.

Usare un array per i rami

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

La rappresentazione di [Expr] ha dimensione fissa: gli elementi dell’array sono memorizzati separatamente. Il tipo Expr può quindi contenere altri Expr attraverso l’array senza avere dimensione infinita. Qui negate usa una lista con un solo elemento. Anche le mappe possono rappresentare strutture ricorsive.

Con i valori Heroes non puoi costruire cicli di riferimenti. Il runtime, il codice di supporto all’esecuzione, libera la memoria quando il conteggio dei suoi riferimenti arriva a zero. Non serve un garbage collector che cerchi cicli, né annotazioni weak per indicare riferimenti deboli.

Percorrerlo è un match e un 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 e sum_of si chiamano a vicenda. Puoi dichiararle in qualsiasi ordine, senza dichiarazioni anticipate.

Il valore iniziale è 0 per la somma e 1 per il prodotto. Perciò value_of(.add(parts: [])) restituisce 0 e value_of(.multiply(parts: [])) restituisce 1. I test qui sotto verificano questi risultati.

Come se ne costruisce uno

# 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])

La riga del return non ha bisogno di annotazione, perché la firma della funzione dice già Expr. Quella sopra invece sì, e a toglierla il compilatore protesta, e ti dice da dove quel tipo sarebbe potuto arrivare:

$ 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)])
     |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Verificare i casi vuoti

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

I test verificano il risultato dei casi vuoti. I quattro assert permettono di rilevare una modifica involontaria al comportamento di 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

L’esempio rappresenta e calcola due più tre per quattro usando un albero di valori. Il compilatore Heroes usa strutture dello stesso genere, più articolate, per rappresentare i programmi che legge.

Poi: I moduli e i file, che è il posto in cui un programma più grande di un file li mette. Torna all’elenco dei capitoli. ← Prima: Le mappe

Esegui un programma tuo: bastano quattro comandi. Oppure prendi tutto il linguaggio in un file solo, e tutti i programmi già scritti.