Rust, vectors and string

Vettori

Oggi parliamo di vettori in Rust, che definiamo come:
un vettore è un segmento di memoria contiguo in cui sono memorizzati un certo numero di dati dello stesso tipo

Poiché i dati sono contigui la loro posizione è indicizzabile tramite l’operatore [] da 0 a n-1, con n numero degli elementi del vettore stesso.
In linea con la filosofia di Rust, accedere a dati con indice fuori intervallo dovrebbe produrre un errore di compilazione — come accade in Go — invece attualmente (con la versione 0.9pre) produce un errore a runtime come dichiara il manuale, forse per motivi di performance.

In altri linguaggi, e mi viene in mente casualmente il Go, il vettore è chiamato con il termine array, e ciò può aiutare a rendere il concetto più famigliare.
Quello che non abbiamo ancora detto sui vettori è se la sua dimensione può cambiare oppure no. In Rust esistono tutte e due le possibilità. Cominciamo dalla seconda…

Vettori fixed-sized

I vettori a lunghezza fissa vengono istanziati nello stack come valori unboxed.
Significa che essi vengono eliminati dalla memoria in automatico quando termina il blocco in cui sono stati definiti, e che la copia è la costruzione di un nuovo vettore e non quella di un nuovo riferimento allo stesso vettore.
Gli elementi ereditano la mutabilità o l’immutabilità del vettore essendo il loro proprietario (leggere la puntata precedente per approfondimenti).

Se T è il tipo di dato degli elementi allora il tipo del vettore a lunghezza fissa si scriverà come [T, ..n], ed n dovrà essere un intero positivo letterale o quanto meno dal valore determinabile a tempo di compilazione (valore statico). La dimensione fa quindi parte del tipo.

Fino ad ora non ci sono differenze sostanziali con il Go, ma ecco finalmente il primo esempio di codice:

fn main() {
    // vettore a lunghezza fissa
    let v = [10, 20, 30];
    assert!(v[0] == 10);
    assert!(v[2] == 30);

    // altra espressione letterale di vettore
    // mutevole con 10 elementi di valore `true`
    let mut q = [true, ..10];
    assert!(q[0] == true);
    q[0] = false;
    assert!(q[0] == false);

    // ...con dichiarazione esplicita del tipo
    let s: [f64, ..3] = [1.0, 2.0, 3.0];
    println!("s = [{}, {}, {}]",
        s[0], s[1], s[2]); // stampa `s = [1, 2, 3]`

    // il primo termine determina il tipo dell'elemento:
    let t = [1.0_f64, 2.0, 3.0]
    let z = t[3] // runtime error: index out of bounds
}

Esempi minimi con gli unboxed vectors

Somma elementi

Scrivere una funzione che calcola la somma degli elementi di un vettore di interi di lunghezza 10.
La prima versione legge ogni valore tramite l’operatore di indicizzazione []:

fn sum_1(v: [int, ..10]) -> int {
    let mut s = 0i;
    for i in range(0, 10) {
        s += v[i];
    };
    return s;
}

Ma si può far ricorso alle funzioni della libreria standard implementate per l’oggetto vettore, per esempio iter() che fornisce un iteratore su tutti gli elementi tramite borrowed pointer e quindi di tipo &T (in questo caso &int):

fn sum_2(v: [int, ..10]) -> int {
    let mut s = 0i;
    for &value in v.iter() {
        s += value;
    };
    return s;
}

L’ultima versione parla in Rust più di tutte (riparleremo delle espressioni lambda e degli iteratori della libreria standard (forse)):

fn sum_3(v: [int, ..10]) -> int {
    let mut s = 0i;
    v.map(|val| s += *val);
    return s;
}

Determinante di una matrice 2×2

Una matrice a due dimensioni può essere implementata come un vettore di vettori:

fn main() {
    // matrice 2x2
    let m: [[int, ..2], ..2] = [[1, 2], [-3, 4]];
    // calcolo del determinante
    let detm = m[0][0] * m[1][1] - m[0][1] * m[1][0];
    println!("det M = {}", detm);
}

I vettori possono essere instanziati anche con il costruttore breve con cui si ottiene un vettore di elementi tutti uguali (come avevamo già visto in un esempio precendente in cui abbiamo istanziato un vettore di 10 booleani):

fn main() {// costruttore breve...
    let uv: [int, ..3] = [10, ..3];
    println!("{:?}", uv); // stampa `[10, 10, 10]`
}

Unique vectors

Ah ecco. Siamo giunti al cuore dell’argomento: gli ‘unique vectors’.
Si tratta di vettori a lunghezza variabile — a lunghezza indefinita nella terminologia di Rust — implementati come valori owned boxed. Questi dati occupano quindi la memoria dinamica e vengono eliminati quando il puntatore unico ad essi esce dal blocco in cui è definito.
La copia della variabile trasferisce alla nuova la ‘proprietà’ del vettore mentre quella originaria non può più essere usata (move semantics).

Se T è il tipo degli elementi, allora ~[T] è il tipo del puntatore proprietario. Abbiamo alla fine giustificato l’aggettivo ‘unique’ per questo tipo, notando che ad esso non è stato assegnato il nome di ‘owned vector’ forse perché farebbe pensare ad un vettore a lunghezza fissa nell’heap, mentre il nuovo nome ‘unique vector’ evidenzia la particolarità della lunghezza variabile.

Un esempio:

fn main() {// aggiungiamo due elementi...
    let mut uv: ~[int] = ~[1, 2, 3];
    uv.push(40);
    uv.push(50);

    println!("{:?}", uv); // stampa `~[1, 2, 3, 40, 50]`
}

Slice

Lo slice è una vista su un segmento continuo di un vettore, costituito da un puntatore al vettore e da una lunghezza che non fa parte del tipo. Il suo tipo è indicato con &[T] dove T è il tipo degli elementi.
Lo slice non è il proprietario degli elementi ma se mutabile può modificarli.

Uno slice si può ottenere direttamente con la forma letterale (vector expression), oppure lo si può derivare da un vettore, oppure ancora con la funzione slice() della libreria standard, sia in modo immutabile che mutabile:

fn main() {
    // slice da forma letterale
    let s1 = &[1, 2, 3];

    // slice da altro vettore
    let s2: &[int] = [4, 5, 6];

    // slice dalla funzione `slice()`
    let v = [7, 8, 9];
    let s3 = v.slice(1, 3); // v.slice(a, b) -> [a, b)

    println!("{:?}", s1); // stampa: `&[1, 2, 3]`
    println!("{:?}", s2); // stampa: `&[4, 5, 6]`
    println!("{:?}", s3); // stampa: `&[8, 9]`

    // slice mutevole da forma letterale
    let s4 = &mut [10, 11, 12];
    s4[0] += 1_000; // l'underscore è ignorato

    // slice mutevole da altro vettore
    let s5: &mut[int] = [13, 14, 15];
    s5[0] += 1_000;

    // slice mutevole da funzione
    let mut w = v;
    let s6 = w.mut_slice(0, 2);
    s6[0] += 1_000;

    println!("{:?}", s4); // stampa `&mut [1010, 11, 12]`
    println!("{:?}", s5); // stampa `&mut [1013, 14, 15]`
    println!("{:?}", s6); // stampa `&mut [1007, 8]`
}

Eliminare i doppioni dal vettore

Come esempio interessante vogliamo scrivere una funzione che dato un vettore restituisca un secondo vettore con gli elementi del primo ma senza duplicati.
La funzione può ricevere il vettore convenientemente come slice e restituire un unique vector:

fn clean_copies(v: &[int]) -> ~[int] {
    let mut z: ~[int] = ~[];
    for &elem in v.iter() {
        let mut is_uni = true;
        for &u in z.iter() {
            if elem == u {
                is_uni = false;
                break;
            }
        }
        if is_uni {
            z.push(elem);
        }
    }
    z
}

La funzione è già abbastanza efficiente perché il ciclo interno, non appena viene trovato che l’elemento è un duplicato, si interrompe, ma può essere ancora più veloce specie con vettori molto grandi, utilizzando una mappa.
Quindi, già questo semplice problema ci da due ulteriori argomenti da sviluppare: implementare la funzione con una mappa e generalizzarla a tutti i tipi, numerici o stringa, che possono essere confrontati…

Stringhe

E veniamo alle stringhe. In Rust le stringhe sono tipi primitivi di nome ‘str’ ma sorprendentemente non sono tipi istanziabili direttamente: sono permessi solo i tipi reference a ‘str’. Avremo cioé il tipo stringa dinamico ‘owned’ ~str gestito da un puntatore proprietario e il tipo ‘managed’ @str gestito dal garbage collector che libererà la memoria dalla stringa quando non esisteranno più puntatori ad essa, e infine il tipo slice &str.

Le stringhe sono rappresentate internamente come vettori di interi u8 (unsigned byte) nella codifica UTF-8. Dunque a differenza di quel che accade in molti altri linguaggi, in Rust le stringhe possono essere mutabili visto che possono esserlo i vettori.
Quando sono espresse in forma letterale ‘non decorata’, cioé senza i prefissi ~ o @, avremo solamente stringhe immutabili — del tipo &str — la cui vita si estende fino alla fine del programma (static lifetime).

A dimostrazione che le stringhe sono vettori, proviamo a stampare un elemento alla volta di una stringa sapendo che un carattere può essere rappresentato in UTF-8 in più byte:
fn main() {
// a is a ‘unique string’ (possiamo dire)
let a = ~”è sera”;
for i in range(0, a.len()) {
println!(“a[{}] = ‘{}'”, i, a[i]);
}
}

Mettiamo anche alla prova la mutabilità delle stringhe. Per questo non possiamo usare una stringa letterale perché immutabile per definizione.

fn main() {
    let mut s = ~"";
    s.push_char('P');
    s.push_char('i');
    s.push_char('p');
    s.push_char('p');
    s.push_char('o');
    s.push_str('...');
    // stampa risultato
    println(s);
}

Controlliamo anche la concatenazione si stringhe di diverso tipo:

fn main() {
    let s1 = "immutabile e borrowed"; // tipo &'static str
    let s2 = ~" più owned";           // tipo ~str
    let s3 = @" più managed";         // tipo @str

    println(s1+s2+s3);

    let a: ~str = s1+s2+s3;
    println(a);
    let b: &str = s1+s2+s3;
    println!("{}", b);
}

Tutto a posto. L’operatore di concatenazione ‘+’ è capace di gestire insieme stringhe di diversi riferimenti, mentre il compilatore è in grado di tradurre il risultato della concatenazione nel tipo specificato, come accade nelle ultime due righe di codice.

Nota finale

Secondo me, la prima cosa da studiare in Rust è il modello della memoria e quindi i tipi unboxed e boxed, che ho cercato di spiegare nel post precedente a questo, citato all’inizio. Possiamo poi seguire strade diverse ma penso che l’argomento logico successivo sia proprio questo: i vettori e di conseguenza anche le stringhe essendo un particolare tipo di vettore.

Quello che ho scritto dovrà essere ricontrollato con le prossime versioni di Rust che oggi è ancora in fase di sviluppo con una documentazione spesso ridotta all’osso (comunque il codice presentato compila correttamente con la versione 0.9pre di Rust).

Sia i vettori che le stringhe sono implementate secondo i concetti generali di gestione della memoria in Rust. Peccato che il compilatore non esegua il controllo sui valori degli indici quando questi assumono un valore statico, ma penso che ci sia una buona ragione perché non sia così.

Saluti.
R.