Mal was anderes: Kleine Fingerübung in Rust

krümelkacker

Test: Implementiere eine einfach verkettete Liste in Rust sowie den Merge-Sort-Algorithmus auf so einer Liste. Idealerweise werden beim Sortieren keine neuen Knoten im Speicher angelegt sondern nur "Zeiger verbogen".

Als ich es das erste Mal versucht habe, bin ich gescheitert. Aber jetzt, mit ein bisschen mehr Ahnung von Rust, ging das ganz einfach. Falls Euch das interessiert, könnt ihr da ja mal einen Blick drauf werfen:

#![feature(macro_rules)]

use std::fmt::Show;
use std::mem::replace;
use std::mem::swap;

type List<T> = Option<Box<Node<T>>>;

struct Node<T> {
    head: T,
    tail: List<T>,
}

impl<T> Node<T> {
    fn new(value: T, tail: List<T>) -> List<T> {
        Some(box Node::<T>{head: value, tail: tail})
    }
}

fn split<T>(list: List<T>) -> (List<T>, List<T>) {
    match list {
        None => (None, None),
        Some(mut bn1) => {
            let list = replace(&mut bn1.tail, None);
            match list {
                None => (Some(bn1), None),
                Some(mut bn2) => {
                    let list = replace(&mut bn2.tail, None);
                    let (tail1, tail2) = split(list);
                    bn1.tail = tail1;
                    bn2.tail = tail2;
                    (Some(bn1), Some(bn2))
                }
            }
        }
    }
}

fn merge<T: Ord>(l1: List<T>, l2: List<T>) -> List<T> {
    match (l1, l2) {
        (None, None) => None,
        (Some(bn1), None) => Some(bn1),
        (None, Some(bn2)) => Some(bn2),
        (Some(mut bn1), Some(mut bn2)) => {
            if bn1.head.cmp(&bn2.head) == Greater {
                swap(&mut bn1, &mut bn2);
            }
            bn1.tail = merge(replace(&mut bn1.tail, None), Some(bn2));
            Some(bn1)
        }
    }
}

fn merge_sort<T: Ord>(list: List<T>) -> List<T> {
    match split(list) {
        (None, None) => None,
        (Some(x), None) => Some(x),
        (None, Some(y)) => Some(y),
        (Some(x), Some(y)) => merge(merge_sort(Some(x)), merge_sort(Some(y)))
    }
}

fn print_list<T: Show>(list: &List<T>) {
    print!("[");
    let mut remain = list;
    loop  {
        match remain {
            &Some(box ref node) => {
                print!(" {}", node.head);
                remain = &node.tail;
            },
            &None => break
        }
    }
    println!(" ]");
}

macro_rules! list(
    ( ) => ( None );
    ( $x:expr $( , $more:expr )* ) => (
        Node::new( $x , list!( $( $more ),* ) )
    )
)

fn main() {
    let list = list!(1i, 6, 3, 2, 4, 5, 9, 7, 8);
    let list = merge_sort(list);
    print_list(&list);
}

Ein paar Anmerkungen dazu:

Per Default sind in Rust die Variablen "const". Wenn man das bei einer bestimmten Variablen nicht will, muss man ein mut davor schreiben.
Per Default werden non-PODs gemoved. Move Semantik ist in Rust "richtig destruktiv" in dem Sinne, dass in einem moved-from Zustand auch kein Destruktor mehr laufen würde. Der Compiler verbietet einem auch die Verwendung (abgesehen von einer neuen Zuweisung, die die Variable wieder gültig machen würde). Gemoved wird immer ber shallow copy. Datentypen sind also immer effizient move-bar. In diesem Beispiel werden also die Listen in die Funktionen split, merge und merge_sort rein und rausgemoved. Wenn das Kopieren bei einem komplizierteren non-POD benötigt wird, muss dieser das Trait Clone implementieren. Das liefert eine Kopie by-value (keinen Zeiger).
Option<T> ist ein algebraischer Typ. Some(3i) ist sowie None ein Wert des Typs Option<int> .
Wie in C++ bekommt man in Rust nur eine Indirektion, wenn man danach explizit fragt. &T ist der Typ eines "borrowed pointers" auf ein T . Box<T> kann man sich als einen boost::ptr_vector<T> mit fixer Größe 1 denken.
Es gibt zwar in Rust keine Nullzeiger ("borrowed pointers" und "boxes" sind immer gültig) aber hier ist Option<Box<T>> so etwas wie ein boost::ptr_vector<T> , der auch leer sein kann. "Box" wird in diesem Beispiel für die Indirektion gebraucht, da sonst Node<T> unendlich groß sein würde.
new ist in Rust kein Schlüsselwort. Die Funktion heißt hier einfach so. Im allgemeinen arbeitet man in Rust auch viel mit return-by-value bei solchen Funktionen. Das ist flexibler so; denn der Aufrufer kann so entscheiden, wo das Objekt landet. Will er es direkt im Stack parken oder im Heap anlegen? Beides geht und letzteres wird auch schön optimiert (move elision).
Pattern Matching ist sehr mächtig. Man ist Rust gezwungen, alle Fälle bei so einem Match zu behandeln. Das heißt, man kann in diesem Beispiel "None" quasi nicht aus Versehen "dereferenzieren".
Die Funktion split gibt ein Paar zurück. Tuple werden direkt in Rust unterstützt und lassen sich auch per let und match "destrukturieren" (destructuring bind).
Da ich hier keinen unsafe -Block verwendet habe, wo man auch schmutzigere Dinge mit machen kann, weiß ich, dass das Programm speichersicher ist (keine Leaks, keine buffer overflows, keine baumelnde Zeiger, kein Zugriff auf nichtinitialisierte Variablen, keine Datenrennen).
Rust-Macros arbeiten nicht auf dem Text-Level sondern etwas höher in Richtung Syntaxbaum. Sie sind außerdem "hygienisch". Ich habe es hier verwendet, um das Bauen einer Liste mit list!(1i,2,3,4) abkürzen zu können. Dass irgendwo ein Makro verwendet wird, erkennt man an dem Ausrufungszeichen.
Literale wie 3, 6 und 4 sind generische/typlose Ganzzahlkonstanten. Damit der Compiler weiß, dass ich eine List<int> haben will, muss ich irgendwo mal konkreter werden: Deswegen steht oben bei dem ersten Listenelement ein int-Suffix dran. Ähnliches gilt für Fließkommazahlen: 6.0 ist ein generischer Float, 6.0f32 ist dann vom Typ f32, 6.0f64 vom Typ f64 (32Bit- und 64Bit-Floats).
Type Deduktion ist hier mächtiger als das, was man von einem C++ Compiler gewohnt ist.
Die Implementierung von split und merge ist wahrscheinlich nicht die beste. Ich würde mir bei größeren Listen Sorgen um den Stackspeicherverbrauch machen. Ob der Compiler das zu einer Schleife optimieren kann, habe ich mir nicht angeguckt. Aber offensichtlich sind die Funktionen so, wie ich sie hier stehen habe, nicht endrekursiv.
Die Concepts, die wir in C++ vermissen, gibt es in Rust und nennen sich Traits. Man achte darauf, dass ich das Ord -Trait als Typbeschränkung bei merge und merge_sort verwendet habe. Nur deswegen lässt mich der Compiler die cmp -Funktion benutzen.
Traits schlagen in Rust gleich zwei Fliegen mit einer Klappe. Sie erfüllen auch die Funktion einer abstrakten Basisklasse für Laufzeitpolymorphie.
Es gibt keine Überladung von Funktionen in Rust. Dafür können Funktionen aber generisch sein. Wenn man aus dem C++-Land kommt, fehlt einem das mit der Überladung ein bisschen. Aber meist kommt man mit einfachen Sachen aus und muss selten mal zu Mechanismen wie Double-Dispatch greifen (was aber über Generics auch komplett zur Compilezeit aufgelöst werden kann, wie bei C++ Templates).
Option<> und Box<> sind generische Typen aus der Standardbibliothek. Sie gehören zu den häufig benutzten Dingen, so dass sie implizit zur Verfügung stehen, ohne dass man dafür ein "use" braucht. libstd wird auch automatisch dazugelinkt. Ein Option<Box<T>> ist übrigens genauso groß wie ein Box<T> . Sofern T ein Datentyp und kein Trait ist, ist das nur ein einziger Zeiger. Wenn T ein Trait ist, besteht eine Box<T> oder ein borrowed pointer &T aus zwei rohen Zeigern. Einer zeigt auf die Daten, der andere auf einen "vtable".

Auweia ... das ist ja viel Text geworden ... War gar nicht so gedacht.

Wer Bock hat, Rust auszuprobieren, ohne sich vorher erst den Compiler installieren zu müssen, kann hier direkt im Browser spielen.

Viel Spaß!

krümelkacker

Irgendwelche Fragen, Kommentare? Macht das Appetit auf Rust? Ja, ist 'ne ziemliche Textwand geworden, aber die Informationsdichte dürfte sehr hoch sein.

Helium

Ich habe noch nie was mit Rust gemacht, sondern nur ein wenig drüber gelesen. Nach meinem ersten Einblick hätte ich gesagt eine Liste würde am einfachsten in etwa so implementiert?

enum List<T>
{
	Node(T, ~List<T>),
	Nil
}

(Hoffe das ist syntaktisch korrekt.)

Wieso hast du dich für deine Variante entschieden?

Marthog

Danke fuer den Online-Compiler. Dann kann ich es dochmal ausprobieren, ohne meinen ganzen gcc umstrukturieren zu muessen.

Ich freue mich sehr ueber diese "modernen Programmiersprachen", also Rust, Go, Swift, denn durch die funktionalen Elemente, kann man manche Algorithmen sehr strukturiert und einfach ausdruecken. Ausserdem sind es endlich mal wieder statisch typisierte Programmiersprachen und dadurch fuer groessere Projekte bei hoher Sicherheit geeignet. Dann sind sie auf nativen Code ausgelegt statt auf irgendwelchem Bytecode.
Zudem muss man viel weniger Boilerplate-Code schreiben als bei C++, Java und C# und sie haben neben maechtigen Optimierungsmoeglichkeiten bei gleichzeitig kompakter Schreibweise auch endlich vernuenftiges Multithreading.

Rust gefaellt mir von den 3 genannten Sprachen am Besten und ich warte im Grunde nur noch bis irgendwann eine langzeitunterstuetzte Version, also wahrscheinlich 1.0 rauskommt, und werde dann vielleicht C++ in privaten Projekten verlassen.

krümelkacker

Helium schrieb:

Ich habe noch nie was mit Rust gemacht, sondern nur ein wenig drüber gelesen. Nach meinem ersten Einblick hätte ich gesagt eine Liste würde am einfachsten in etwa so implementiert?
enum List<T>
{
	Node(T, ~List<T>),
	Nil
}

So stand das jedenfalls mal in einem Tutorial. Und so hatte ich es auch vor einigen Wochen ausprobiert. Bin damit aber nicht weit gekommen. Die split-Funktion, die ich damals schrieb, erzeugte neue Listen im Heap statt die "Knoten" zu recyceln. Und damals wusste ich nicht, wie man es anders lösen kann.

In der aktuellen Rust Version gibt es kein ~ mehr. Das heißt jetzt Box. Man müsste jetzt folgendes schreiben:

enum List<T>
{
    Node(T, Box<List<T>>),
    Nil
}

Das Blöde daran ist aber, dass der erste Wert direkt gehalten wird und dass es am Ende dann noch einen extra Nil-Knoten gibt. Das mit dem Nil-Knoten ist nicht so schlimm. Aber dass der erste Wert direkt in List<T> gehalten wird, macht das Recyceln der Boxen schwierig und man "muhft" (move) auch die T-Werte ständig hin und her so.

Man könnte es vielleicht noch mit

enum List<T>
{
    Node(Box<(T,List<T>)>),
    Nil
}

versuchen.

Solche Datenstruktoren würde man aber sowieso nicht so bauen, sondern eher mit rohen Zeigern und ein bisschen "unsafe" Code, so ähnlich wie man in C++ auch std::list und std::vector baut. Hauptsache, diese Bausteine haben eine gute und sichere Schnittstelle, über die man sich nicht in den Fuß schießen kann.

krümelkacker

Marthog schrieb:

Danke fuer den Online-Compiler.

Die gibt's wirklich überall. Sogar auf der Homepage und auch auf der Rust By Example-Seite.

Marthog schrieb:

[...]
Rust gefaellt mir von den 3 genannten Sprachen am Besten und ich warte im Grunde nur noch bis irgendwann eine langzeitunterstuetzte Version, also wahrscheinlich 1.0 rauskommt, und werde dann vielleicht C++ in privaten Projekten verlassen.

Ja, bis 1.0 passiert sicher noch so einiges. Es gibt schon noch ein paar Ecken und Kanten. Ich bin schon an die eine oder andere Grenze gestoßen. Aber so, wie es aussieht, sollen die teilweise bis zur Version 1.0 noch fallen bzw sich verschieben. In Sachen generischer Programmierung und Operatorüberladung gibt es noch Verbesserungspotential. Production-ready sind die noch nicht.

Ich persönlich finde die funktionalen Aspekte mit dem Matching nur nett. Der Knaller sind IMHO die Garantien bzgl Speicher- und Threadsicherheit. Iterator invalidation? Gibt's nicht. Eine Referenz auf ein Element eines Vec<T>s behalten und danach reserve aufrufen und die Referenz damit üngültig werden lassen? Kompiliert gar nicht erst ...

krümelkacker schrieb:

Irgendwelche Fragen, Kommentare? Macht das Appetit auf Rust? Ja, ist 'ne ziemliche Textwand geworden, aber die Informationsdichte dürfte sehr hoch sein.

danke jedenfalls dass du mich darauf aufmerksam gemacht hast, dass es diese sprache überhaupt gibt. werd ich mir bei zeiten einmal näher ansehen!

krümelkacker

dsdadasda schrieb:

danke jedenfalls dass du mich darauf aufmerksam gemacht hast, dass es diese sprache überhaupt gibt. werd ich mir bei zeiten einmal näher ansehen!

Gerne!

Was ich noch nicht erwähnt hatte: Es gibt auch Funktionszeiger und Closures. Allerdings sind Closures noch immer "boxed". Das entspricht in C++ einer Kombination aus std::function und [&] ... bzw [dings=move(dings)] ... je nachdem, welche Closure ihr benutzt.

Es gibt Referenzclosures (wie z.B. |x|{2*x+b} ), die sich mit einer Referenz auf die lokale Umgebung (im Beispiel für das b ) beziehen aber dementsprechend keine besonders große Lebenszeit haben können. Es reicht, um Funktionen damit zu füttern, die so etwas nicht wo anders speichern wollen:

fn main() {
    let b = 1;
    for x in range(0i,10).map(|z|{2*z+b}) {
        print!(" {}",x);
    }
    println!("");
}

Und es gibt noch "One-Shot Closures", die einige Variablen aus ihrer Umgebung implizit per move "klauen". Die schreibt man mit proc . Diese können dann auch irgendwo gespeichert oder an einen anderen Task übergeben und dort einmal ausgeführt werden:

fn main() {
    let (tx,rx) = channel(); // Unidirektionaler Kanal mit Sende- (tx)
                             // und Empfangseinheit (rx)

    spawn( proc(){               // <-- so eine "one-shot closure"
        tx.send("Hello World!"); // tx hat sie sich aus main geklaut
    });

    let msg = rx.recv(); // blockiert bis die Nachricht da ist
    println!("{}",msg);
}

Man sieht hier auch, dass ich nirgens einen Typ hingeschrieben habe. Das ist die Typinferenz à la Hindley-Milner in Aktion. Der Kanal ist schon typisiert. Ich kann da jetzt nicht einmal einen int und dann einen string rüberschicken. Das coole dabei ist, dass relativ viel (wie u.a. auch Kanäle) selbst in Rust in der Standardbibliothek implementiert sind, also nicht alles Compiler-Magie ist. Man kann übrigens die "Sendeeinheit" (tx) auch klonen, so dass mehrere Tasks etwas in den Kanal stecken können.

Bzgl "boxed closure": Das soll noch wegfallen. Die Rust-Macher wollen auch "unboxed closures" zulassen, die sich dann schön inlinen lassen, so, wie man das von C++11 Lambdas auch kennt. Das dürfte dann nochmal ein Performancegewinn sein.

Der ganze Iterator-Kram aus der Standardbibliothek arbeitet aber ohne runtime Dispatch (wie in C++ auch). Die Typen sind zur Compilezeit ja alle klar. So ein for x in iterator -Loop kann deswegen gut optimiert werden.