Ich spiele mit Rust-Closures, versuche, ein Gefühl dafür zu bekommen, und eine Aufgabe, die ich mir gestellt habe, war, eine In-Order-Traversal im Continuation-Passing-Stil zu implementieren. Normalerweise kann ich das in etwa einer Stunde in anderen Sprachen erledigen, aber hier habe ich es geschafft, festzustecken, wie ich die Lebensdauer einer Schließung verwalten kann, die ich im Rückruf verwende.
Ich habe einen binären Baum wie folgt definiert, was ziemlich einfach ist:
// A node is a tuple of (left, value, right)
struct Node<T>(pub Tree<T>, pub T, pub Tree<T>);
// A tree is an optional pointer to a node
type Tree<T> = Option<Box<Node<T>>>;
und ich kann eine direkte rekursive Traversierung so durchführen, wie ich es erwarten würde:
// Direct recursion.
// The <T: Copy> is needed because we copy values into
// the result vector. For other usages we might not need it
fn inorder<T: Copy>(t: &Tree<T>, res: &mut Vec<T>) {
// If t is not empty it is Some(node)
if let Some(node) = t {
// Pull out the values of the node.
// In the development branch of Rust there is
// a nicer syntax, but this is how it is now
let Node(left, val, right) = node.as_ref();
inorder(left, res);
res.push(*val);
inorder(right, res);
}
}
Um dies jedoch mit Fortsetzungen zu tun, muss ich Closures definieren, um den Rest der Traversierung zu verwalten und diese zusammen mit einer Tail-Rekursion weiterzugeben, und meine unmittelbare Lösung sah nicht viel anders aus als meine aktuelle:
// Ideally, we wouldn't need to pass the vector along with the closures
// but Rust won't let us hold on to a mutable reference in a closure if
// another closure also has a mutable reference, so we pass the vector
// from continuation to continuation instead.
fn cps_rec<T: Copy>(t: &Tree<T>, res: &mut Vec<T>,
k: Box<dyn FnOnce(&mut Vec<T>)>)
{
match t {
None => { k(res) },
Some(node) => {
let Node(left, val, right) = node.as_ref();
let after_left = |v: &mut Vec<T>| {
// After we have gone left, add v and go right,
// calling k when we are done
v.push(*val);
cps_rec(right, v, k);
};
cps_rec(left, res, Box::new(after_left));
}
}
}
fn cps<T: Copy>(t: &Tree<T>) -> Vec<T> {
let mut res = vec![];
cps_rec(t, &mut res, Box::new(|_| ()));
res
}
Spielplatz
Das Problem liegt in der Rekursion, cps_rec(left, res, after_left)bei der die Lebensdauer des Abschlusses nicht mit der Einschränkung übereinstimmt. (Ich denke, ich kann nicht sagen, dass ich genau verstehe, worüber Rust sich beschwert, aber das Problem verschwindet, sobald ich den Körper des Verschlusses leer mache, also ist es etwas in der abgeleiteten Lebensdauer, das die Dinge durcheinander bringt). Ich vermutete zuerst, dass es das Leben von war valoder rightdas mich bekämpfte, aber es hilft nicht, movedie Schließung nach der Dereferenzierung voranzustellen
fn cps_rec<T: Copy>(t: &Tree<T>, res: &mut Vec<T>,
k: Box<dyn FnOnce(&mut Vec<T>)>)
{
match t {
None => { k(res) },
Some(node) => {
let Node(left, val, right) = node.as_ref();
let val = *val;
let right = *right;
let after_left = move |v: &mut Vec<T>| {
// After we have gone left, add v and go right,
// calling k when we are done
v.push(val);
cps_rec(&right, v, k);
};
cps_rec(left, res, Box::new(after_left));
}
}
}
Spielplatz
Ich kann also nicht herausfinden, was das Problem ist oder wie ich Rust sagen kann, dass diese Schließung lange genug überleben wird, um die Rekursion abzuschließen...
Ich habe dann versucht, einen generischen Typ für die Fortsetzung zu verwenden, um zu sehen, ob Rust das Problem dadurch für mich lösen würde:
fn cps_rec<'a, T: Copy, Cont>(t: &'a Tree<T>, res: &'a mut Vec<T>, k: Cont)
where Cont: FnOnce(&'a mut Vec<T>)
{
match t {
None => { k(res) },
Some(node) => {
let Node(left, val, right) = node.as_ref();
let after_left = |v: &'a mut Vec<T>| {
// After we have gone left, add v and go right,
// calling k when we are done
v.push(*val);
cps_rec(right, v, k);
};
cps_rec(left, res, Box::new(after_left));
}
}
}
Spielplatz
aber das unterbricht die Kompilierung, wenn der Typprüfer auf den Typrückschluss zurückgreifen muss. Vielleicht nicht überraschend, da die Art der Schließung wahrscheinlich von der abgeleiteten Art der Rekursion abhängt.
Kann ich etwas tun, um das zu beheben, oder ist die Idee bei der Ankunft tot und ich muss einen völlig anderen Ansatz ausprobieren, wenn ich etwas in dieser Richtung machen möchte?
Lösung des Problems
Das Lebensdauerproblem besteht darin, dass Box<dyn FnOnce(&mut Vec<T>)>tatsächlich, mit explizit angegebenen Lebensdauern, Box<dyn FnOnce(&mut Vec<T>) + 'static>. Das heißt, es erfordert, dass die Schließungen 'static. Eine Closure ist statisch, wenn alles, was sie erfasst, 'static. Natürlich erfüllt ein leerer Verschluss diese Bedingung – er fängt nichts ein, also hat es funktioniert, wenn Sie seinen Körper geleert haben.
Ihre Schließung erfasst jedoch Nicht- 'staticReferenzen - valund right. Ich werde bald erklären, warum das Kopieren nicht funktioniert.
Die Lösung ist einfach: Wir brauchen nicht wirklich, dass die Schließung 'static; uns kann es gut gehen, auch wenn es nicht so sein wird - wir speichern es nicht oder so. Um das dem Compiler gegenüber auszudrücken, müssen wir Box<dyn FnOnce(&mut Vec<T>)>zu Box<dyn FnOnce(&mut Vec<T>) + '_>( Spielplatz ) wechseln. Das ist es. '_ist die explizit eliminierte Lebensdauer: Sie sagt dem Compiler, "selbst die richtige Lebensdauer herauszufinden". Normalerweise macht das der Compiler automatisch, aber bei dyn Traitgibt er manchmal auf und benutzt einfach 'static. Die Lebensdauer wird gemäß den Lebensdauerausschlussregeln abgeleitet; in diesem Fall führt es ein neues Leben ein, als ob wir schreiben würden:
fn cps_rec<'elided_lifetime, T: Copy>(
t: &Tree<T>,
res: &mut Vec<T>,
k: Box<dyn FnOnce(&mut Vec<T>) + 'elided_lifetime>,
) {... }
Was hier verwirrt, ist die Fehlermeldung des Compilers. Es wäre klarer, wenn Sie dem Vorschlag des Compilers gefolgt wären und T: 'static( Spielplatz ) gesetzt hätten:
error: lifetime may not live long enough
--> src/lib.rs:17:32
|
6 | fn cps_rec<T: Copy + 'static>(t: &Tree<T>, res: &mut Vec<T>, k: Box<dyn FnOnce(&mut Vec<T>)>) {
| - let's call the lifetime of this reference `'1`
...
17 | cps_rec(left, res, Box::new(after_left));
| ^^^^^^^^^^^^^^^^^^^^ cast requires that `'1` must outlive `'static`
Das habe ich gesagt. 'staticist wegen der impliziten 'staticGrenze des Abschlusses erforderlich.
Aber der Compiler hat Ihnen etwas Wichtigeres zu sagen (oder eher anzuschreien). Es denkt: "Da die Schließung erforderlich 'staticist, sind diese Referenzen offensichtlich 'static. Dieser Benutzer lügt mich nicht an, er ist ein guter Bürger!" Erst später wird es erkennen, dass es falsch war, aber es wird nie zu diesem "später" kommen, weil es die Kompilierung aufgrund von Fehlern früher stoppen wird. Aber jetzt denkt es: "Angesichts der Tatsache, dass diese Referenzen offensichtlich 'static sind, sind sie &'static T(für val, oder &'static Option<Box<T>>für right). Aber &'static Tum gültig zu sein, T: 'staticmüssen gelten (stellen Sie sich eine Referenz vor wie &'long &'short i32: Sie können darauf zugreifen für 'long, aber solange 'shortes vorbei ist, ist es ungültig, und Sie werden eine baumelnde Referenz verwenden!) Kann ich das beweisenT: 'staticimmer halten? Nö! Nun, sollte einen Fehler ausgeben." (Sie können einen Fehlerbericht unter https://github.com/rust-lang/rust/issues ausfüllen, die Rust-Entwickler werden es zu schätzen wissen, auch wenn ich nicht sicher bin, wie viel sie tun können um die Situation zu verbessern).
Warum hat das Kopieren nicht geholfen? Erstens hat sich die Art und Weise, wie der Compiler darüber nachgedacht hat, nicht geändert, und daher wird immer noch derselbe Fehler ausgegeben. Zweitens, selbst wenn wir es lösen könnten (z. B. durch Angabe von T: 'static), gibt es einen weiteren Fehler ( Spielplatz ):
error[E0507]: cannot move out of `*right` which is behind a shared reference
--> src/lib.rs:12:34
|
12 | let right: Tree<T> = *right;
| ^^^^^^ move occurs because `*right` has type `Option<Box<Node<T>>>`, which does not implement the `Copy` trait
|
help: consider borrowing the `Option`'s content
|
12 | let right: Tree<T> = *right.as_ref();
| +++++++++
help: consider borrowing here
|
12 | let right: Tree<T> = &*right;
| ~~~~~~~
Hoffentlich ist dieser hier selbsterklärend.
In Bezug auf die generische Version ist Ihre Annahme in der Tat richtig: Keine Sprache kann rekursives CPS mit Monomorphisierung ausführen, sie alle verwenden den dynamischen Versand (der äquivalent zu Box<dyn FnOnce()>(oder einer GCed-Version) oder zu &mut dyn FnMut()oder etwas Ähnlichem ist). Wir müssen es ad infinitum instanziieren.
Keine Kommentare:
Kommentar veröffentlichen