Lottando con chiusure e vite in Rust

Question

Sto provando a portare un piccolo benchmark da F # a Rust. Il codice F # è simile al seguente:

let inline iterNeighbors f (i, j) = 
    f (i-1, j) 
    f (i+1, j) 
    f (i, j-1) 
    f (i, j+1) 

let rec nthLoop n (s1: HashSet<_>) (s2: HashSet<_>) = 
    match n with 
    | 0 -> s1 
    | n -> 
     let s0 = HashSet(HashIdentity.Structural) 
     let add p = 
     if not(s1.Contains p || s2.Contains p) then 
      ignore(s0.Add p) 
     Seq.iter (fun p -> iterNeighbors add p) s1 
     nthLoop (n-1) s0 s1 

let nth n p = 
    nthLoop n (HashSet([p], HashIdentity.Structural)) (HashSet(HashIdentity.Structural)) 

(nth 2000 (0, 0)).Count 

calcola gli ennesimi-più vicine conchiglie vicino di un vertice iniziale in un grafico potenzialmente infinita. Ho usato qualcosa di simile durante il mio dottorato di ricerca per studiare materiali amorfi.

Ho passato molte ore a provare e non riuscire a portare questo a Rust. Sono riuscito a far funzionare una versione, ma solo inserendo manualmente la chiusura e convertendo la ricorsione in un loop con mutabili locali (yuk!).

use std::collections::HashSet; 

Ho provato a scrivere la funzione iterNeighbors simili:

fn iterNeighbors<F>(f: &F, (i, j): (i32, i32)) ->() 
    where F : Fn((i32, i32)) ->() { 
    f((i-1, j)); 
    f((i+1, j)); 
    f((i, j-1)); 
    f((i, j+1)); 
} 

Credo che è una funzione che accetta una chiusura (che si accetta una coppia e ritorna unità) ed una coppia e ritorna unità. Mi sembra di dover raddoppiare le cose: è corretto?

ho provato a scrivere una versione ricorsiva come questo:

fn nthLoop(n: i32, s1: HashSet<(i32, i32)>, s2: HashSet<(i32, i32)>) -> HashSet<(i32, i32)> { 
    if n==0 { 
     return &s1; 
    } else { 
     let mut s0 = HashSet::new(); 
     for &p in s1 { 
      if !(s1.contains(&p) || s2.contains(&p)) { 
       s0.insert(p); 
      } 
     } 
     return &nthLoop(n-1, s0, s1); 
    } 
} 

Si noti che non ho nemmeno preso la briga con la chiamata a iterNeighbors ancora.

Penso di dover fare in modo che le durate degli argomenti siano corrette perché vengono ruotate nella chiamata ricorsiva. Come dovrei annotare le durate se desidero che los sia deallocato immediatamente prima dello return e voglio che sopravviva quando viene restituito o nella chiamata ricorsiva?

Il chiamante sarebbe simile a questa:

fn nth<'a>(n: i32, p: (i32, i32)) -> &'a HashSet<(i32, i32)> { 
    let s0 = HashSet::new(); 
    let mut s1 = HashSet::new(); 
    s1.insert(p); 
    return &nthLoop(n, &s1, s0); 
} 

ho rinunciato a questo e ha scritto come un ciclo while con i locali mutevoli invece:

fn nth<'a>(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> { 
    let mut n = n; 
    let mut s0 = HashSet::new(); 
    let mut s1 = HashSet::new(); 
    let mut s2 = HashSet::new(); 
    s1.insert(p); 
    while n > 0 { 
     for &p in &s1 { 
      let add = &|p| { 
       if !(s1.contains(&p) || s2.contains(&p)) { 
        s0.insert(p); 
       } 
      }; 
      iterNeighbors(&add, p); 
     } 
     std::mem::swap(&mut s0, &mut s1); 
     std::mem::swap(&mut s0, &mut s2); 
     s0.clear(); 
     n -= 1; 
    } 
    return s1; 
} 

Questo funziona se INLINE la chiusura a mano ma non riesco a capire come invocare la chiusura. Idealmente, mi piacerebbe la spedizione statica qui.

La funzione main è quindi:

fn main() { 
    let s = nth(2000, (0, 0)); 
    println!("{}", s.len()); 
} 

Allora ... cosa sto sbagliando? :-)

Inoltre, ho utilizzato solo HashSet in F # perché presumo che Rust non fornisca un Set puramente funzionale con operazioni di teorizzazione dell'insieme efficienti (unione, intersezione e differenza). Sono corretto nel presupposto che?

Answer 1

credo che è una funzione che accetta una chiusura (che si accetta una coppia e ritorna unità) e una coppia e restituisce unità. Mi sembra di dover raddoppiare le cose: è corretto?

Sono necessarie le doppie parentesi perché si passa una tupla da 2 a quella che corrisponde al codice F # originale.

Penso che sto lottando per ottenere la durata degli argomenti corretta perché sono ruotati nella chiamata ricorsiva. Come dovrei annotare le durate se voglio che S2 sia deallocato appena prima dei ritorni e voglio che s1 sopravviva quando viene restituito o nella chiamata ricorsiva?

Il problema è che si sta utilizzando riferimenti a HashSet s quando si dovrebbe semplicemente usare direttamente HashSet s. La tua firma per nthLoop è già corretta; hai solo bisogno di rimuovere alcune occorrenze di &.

Per deallocare s2, è possibile scrivere drop(s2). Nota che Rust non ha chiamate tail garantite, quindi ogni chiamata ricorsiva occuperà ancora un po 'di spazio nello stack (puoi vedere quanto con la funzione mem::size_of), ma la chiamata drop eliminerà i dati sull'heap.

Il chiamante sarebbe simile a questa:

Anche in questo caso, è sufficiente rimuovere le & 's qui.

Nota che non mi sono nemmeno preoccupato della chiamata a iterNeighbors ancora.

---

Questo funziona se inline la chiusura a mano ma non riesco a capire come richiamare la chiusura. Idealmente, mi piacerebbe la spedizione statica qui.

Ci sono tre tipi di chiusure a Rust: Fn, FnMut e FnOnce. Differiscono dal tipo del loro argomento self. La distinzione è importante perché pone delle restrizioni su ciò che la chiusura è autorizzata a fare e su come il chiamante può utilizzare la chiusura. Il libro Rust ha a chapter on closures che già lo spiega bene.

vostro chiusura deve mutare s0. Tuttavia, iterNeighbors è definito come previsto per una chiusura Fn. Il tuo chiusura non può attuare Fn perché Fn riceve &self, ma di mutare s0, è necessario &mut self. iterNeighbors non può utilizzare FnOnce, poiché è necessario chiamare la chiusura più di una volta. Pertanto, è necessario utilizzare FnMut.

Inoltre, non è necessario per passare la chiusura con riferimento a iterNeighbors. Puoi semplicemente passarlo per valore; ogni chiamata alla chiusura prenderà in prestito solo la chiusura, non la consumerà.

Inoltre, ho usato solo HashSet in F # perché presumo che Rust non fornisca un Set puramente funzionale con operazioni teoriche di set efficienti (unione, intersezione e differenza). Sono corretto nel presupposto che?

Non esiste un'implementazione di set puramente funzionale nella libreria standard (forse ce n'è uno su crates.io?). Mentre Rust abbraccia la programmazione funzionale, sfrutta anche la sua proprietà e il suo sistema di prestiti per rendere la programmazione imperativa più sicura. Un set funzionale probabilmente imporrà utilizzando una qualche forma di conteggio dei riferimenti o raccolta dei dati inutili per condividere elementi tra i set.

Tuttavia, HashSet implementi operazioni insiemistiche. Ci sono due modi di usarli: iteratori (difference, symmetric_difference, intersection, union), che generano la sequenza pigramente, o operatori (|, &, ^, -, come elencato nella trait implementations for HashSet), che producono nuovi set contenenti cloni di i valori dai set sorgente.

---

Ecco il codice di lavoro:

use std::collections::HashSet; 

fn iterNeighbors<F>(mut f: F, (i, j): (i32, i32)) ->() 
    where F: FnMut((i32, i32)) ->() 
{ 
    f((i-1, j)); 
    f((i+1, j)); 
    f((i, j-1)); 
    f((i, j+1)); 
} 

fn nthLoop(n: i32, s1: HashSet<(i32, i32)>, s2: HashSet<(i32, i32)>) -> HashSet<(i32, i32)> { 
    if n == 0 { 
     return s1; 
    } else { 
     let mut s0 = HashSet::new(); 
     for &p in &s1 { 
      let add = |p| { 
       if !(s1.contains(&p) || s2.contains(&p)) { 
        s0.insert(p); 
       } 
      }; 
      iterNeighbors(add, p); 
     } 
     drop(s2); 
     return nthLoop(n-1, s0, s1); 
    } 
} 

fn nth(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> { 
    let mut s1 = HashSet::new(); 
    s1.insert(p); 
    let s2 = HashSet::new(); 
    return nthLoop(n, s1, s2); 
} 

fn main() { 
    let s = nth(2000, (0, 0)); 
    println!("{}", s.len()); 
} 

Answer 2

Mi sembra di dover raddoppiare le cose: è corretto?

No: la doppia bracketes sono perché hai scelto di utilizzare tuple e chiamare una funzione che prende una tupla richiede la creazione di una tupla prima, ma si può avere chiusure che prendono più argomenti, come F: Fn(i32, i32).Cioè, si potrebbe scrivere quella funzione come:

fn iterNeighbors<F>(i: i32, j: i32, f: F) 
    where F: Fn(i32, i32) 
{ 
    f(i-1, j); 
    f(i+1, j); 
    f(i, j-1); 
    f(i, j+1); 
} 

Tuttavia, sembra che il mantenimento delle tuple abbia senso per questo caso.

Penso che sto lottando per ottenere la durata degli argomenti corretta perché sono ruotati nella chiamata ricorsiva. Come dovrei annotare le durate se voglio che S2 sia deallocato appena prima dei ritorni e voglio che s1 sopravviva quando viene restituito o nella chiamata ricorsiva?

Non c'è bisogno di riferimenti (e quindi senza bisogno di vite), basta passare i dati attraverso direttamente:

fn nthLoop(n: i32, s1: HashSet<(i32, i32)>, s2: HashSet<(i32, i32)>) -> HashSet<(i32, i32)> { 
    if n==0 { 
     return s1; 
    } else { 
     let mut s0 = HashSet::new(); 
     for &p in s1 { 
      iterNeighbors(p, |p| { 
       if !(s1.contains(&p) || s2.contains(&p)) { s0.insert(p); } 
      }) 
     } 
     drop(s2); // guarantees timely deallocation 
     return nthLoop(n-1, s0, s1); 
    } 
} 

La chiave qui è che si può fare tutto per valore, e le cose passato in giro per valore ovviamente manterrà i loro valori in giro.

Tuttavia, questo non riesce a compilare:

error: cannot borrow data mutably in a captured outer variable in an `Fn` closure [E0387] 
      if !(s1.contains(&p) || s2.contains(&p)) { s0.insert(p); } 
                 ^~ 
help: see the detailed explanation for E0387 
help: consider changing this closure to take self by mutable reference 
     iterNeighbors(p, |p| { 
      if !(s1.contains(&p) || s2.contains(&p)) { s0.insert(p); } 
     }) 

Vale a dire, la chiusura sta cercando di mutare i valori che cattura (s0), ma il tratto Fn chiusura non consente questo. Quel tratto può essere chiamato in un modo più flessibile (quando condiviso), ma questo impone più restrizioni su ciò che la chiusura può fare internamente. (Se siete interessati, ho scritto più su questo: http://huonw.github.io/blog/2015/05/finding-closure-in-rust/)

Fortunatamente c'è una soluzione semplice: utilizzando il FnMut tratto, che richiede che la chiusura può essere chiamato solo quando si ha accesso unico ad esso, ma consente agli interni di mutare le cose.

fn iterNeighbors<F>((i, j): (i32, i32), mut f: F) 
    where F: FnMut((i32, i32)) 
{ 
    f((i-1, j)); 
    f((i+1, j)); 
    f((i, j-1)); 
    f((i, j+1)); 
} 

Il chiamante sarebbe simile a questa:

valori del lavoro anche qui: che restituisce un riferimento in tal caso sarebbe di restituire un puntatore a s0, che vive lo stack frame che si sta distrutto quando la funzione ritorna. Cioè, il riferimento punta a dati morti.

La correzione non è solo utilizzando i riferimenti:

fn nth(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> { 
    let s0 = HashSet::new(); 
    let mut s1 = HashSet::new(); 
    s1.insert(p); 
    return nthLoop(n, s1, s0); 
} 

Questo funziona se INLINE la chiusura a mano, ma non riesco a capire come invocare la chiusura. Idealmente, mi piacerebbe la spedizione statica qui.

(non capisco che cosa questo significa, tra cui i messaggi di errore del compilatore hai problemi con ci aiuta aiutarti.)

Inoltre, ho usato solo HashSet in F #, perché Supponiamo che Rust non fornisca un Set puramente funzionale con efficienti operazioni teorico-settoriali (unione, intersezione e differenza). Sono corretto nel presupposto che?

A seconda esattamente ciò che si desidera, no, ad es. sia HashSet sia BTreeSet forniscono varie operazioni teoriche di serie come methods which return iterators.

---

Alcuni punti di piccole dimensioni:

• esplicito/vite nome permettono al compilatore di ragionare sulla validità statica dei dati, che non controllano (cioè permettono al compilatore di sottolineare quando si fare qualcosa di sbagliato, ma il linguaggio ha ancora lo stesso tipo di utilizzo di risorse statiche/garanzie del ciclo di vita come C++)
• la versione con un ciclo rischia di essere più efficiente come scritto, poiché riutilizza direttamente la memoria (scambiando i set, più lo s0.clear(), tuttavia, lo stesso beneficio può essere realizzato con una versione ricorsiva passando s2 in basso per riutilizzarlo invece di lasciarlo cadere.
• loop while potrebbe essere for _ in 0..n
• non c'è bisogno di passare chiusure per riferimento, ma con o senza il riferimento, c'è ancora la consegna statica (la chiusura è un parametro di tipo, non un oggetto tratto).
• convenzionalmente, argomenti di chiusura sono ultimo, e non presi per riferimento, perché rende definire & passandoli linea più facile da leggere (es foo(x, |y| bar(y + 1)) anziché foo(&|y| bar(y + 1), x))

• della parola return non è necessaria per i ritorni finali (se la ; è omesso):

  fn nth(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> { 
      let s0 = HashSet::new(); 
      let mut s1 = HashSet::new(); 
      s1.insert(p); 
      nthLoop(n, s1, s0) 
  }