Vor einigen Tagen hat 0xd34df00d die Übersetzung des Artikels veröffentlicht , in der die möglichen Informationen zu bestimmten Funktionen beschrieben werden, wenn wir sie als "Black Box" verwenden und nicht versuchen, ihre Implementierung zu lesen. Natürlich sind diese Informationen von Sprache zu Sprache sehr unterschiedlich. Im ursprünglichen Artikel wurden vier Fälle berücksichtigt:
- Python - dynamische Typisierung, fast keine Informationen aus der Signatur, einige Hinweise werden durch die Tests gewonnen;
- C - schwache statische Typisierung, etwas mehr Information;
- Haskell - starke statische Typisierung, standardmäßig mit reinen Funktionen, viel mehr Informationen;
- Idris-abhängige Eingabe, Compiler kann die Funktionskorrektheit beweisen.
"Hier ist C und da ist Haskell, und was ist mit Rust?" - Dies war die erste Frage in der folgenden Diskussion. Die Antwort ist hier.
Erinnern wir uns zunächst an die Aufgabe:
Geben Sie bei einer Liste von Werten und einem Wert den Index des Werts in der Liste zurück oder geben Sie an, dass er nicht in der Liste vorhanden ist.
Wenn jemand nicht alles lesen möchte, werden die Codebeispiele auf dem Rust-Spielplatz bereitgestellt.
Ansonsten fangen wir an!
Einfache Suche
Der erste Ansatz wird die fast naive Signatur sein, die sich vom C-Code nur in einigen idiomatischen Elementen unterscheidet:
fn foo(x: &[i32], y: i32) -> Option<usize> {
Was wissen wir über diese Funktion? Nun, in der Tat - nicht sehr viel. Natürlich ist Option<usize> als Rückgabewert eine große Verbesserung gegenüber dem, was von C bereitgestellt wird, aber es gibt keine Informationen über die Funktionssemantik. Insbesondere haben wir keine Garantie dafür, dass die Nebenwirkungen fehlen, und keine Möglichkeit, das gewünschte Verhalten irgendwie zu überprüfen.
Kann ein Test dies verbessern? Schau hier:
#[test] fn test() { assert_eq!(foo(&[1, 2, 3], 2), Some(1)); assert_eq!(foo(&[1, 2, 3], 4), None); }
Nichts weiter, wie es scheint - all diese Überprüfungen können in Python genau gleich sein (und in Erwartung werden Tests für den gesamten Artikel wenig hilfreich sein).
Benutze die Generika, Luke!
Aber ist es gut, dass wir nur vorzeichenbehaftete 32-Bit-Zahlen verwenden müssen? Behebung:
fn foo<El>(x: &[El], y: El) -> Option<usize> where El: PartialEq, {
Nun, das ist etwas! Jetzt können wir jede Scheibe nehmen, die aus Elementen eines vergleichbaren Typs besteht. Expliziter Polymorphismus ist fast immer besser als implizit (Hallo, Python) und fast immer besser als gar kein Polymorphismus (Hallo, C), oder?
Diese Funktion kann diesen Test jedoch unerwartet bestehen:
fn refl<El: PartialEq + Copy>(el: El) -> Option<usize> { foo(&[el], el)
Dies deutet auf den einen fehlenden Punkt hin, da die Spezifikation möchte, dass die refl Funktion tatsächlich immer Some(0) refl . Dies ist natürlich alles auf das spezifische Verhalten der teilweise äquivalenten Typen im Allgemeinen und der Floats im Besonderen zurückzuführen.
Vielleicht wollen wir dieses Problem loswerden? Also werden wir einfach die Grenze für den El-Typ verschärfen:
fn foo<El>(x: &[El], y: El) -> Option<usize> where El: Eq, {
Jetzt müssen nicht nur die Typen vergleichbar sein, sondern auch die Äquivalenzen . Dies schränkt natürlich die möglichen Typen ein, die mit dieser Funktion verwendet werden können, aber jetzt deuten sowohl die Signatur als auch die Tests darauf hin, dass das Verhalten in die Spezifikation passen sollte.
Randnotiz: Wir wollen generischer gehen!Dieser Fall hat nichts mit der ursprünglichen Aufgabe zu tun, aber dies scheint ein gutes Beispiel für das bekannte Prinzip zu sein: "Sei liberal in dem, was du akzeptierst, sei konservativ in dem, was du tust". Mit anderen Worten: Wenn Sie den Eingabetyp verallgemeinern können, ohne die Ergonomie und Leistung zu beeinträchtigen, sollten Sie dies wahrscheinlich tun.
Jetzt werden wir dies überprüfen:
fn foo<'a, El: 'a>(x: impl IntoIterator<Item = &'a El>, y: El) -> Option<usize> where El: Eq, {
Was wissen wir jetzt über diese Funktion? Im Allgemeinen trotzdem, aber jetzt akzeptiert es nicht nur das Slice oder die Liste, sondern auch ein beliebiges Objekt, das die Verweise auf den Typ El liefern kann, so dass wir es mit dem fraglichen Objekt vergleichen. Wenn ich mich beispielsweise nicht irre, wäre dieser Typ in Java Iterable<Comparable> .
Wie zuvor, aber etwas strenger
Aber jetzt brauchen wir vielleicht noch mehr Garantien. Oder wir möchten am Stack arbeiten (und können daher Vec nicht verwenden), müssen aber unseren Code für jede mögliche Arraygröße verallgemeinern. Oder wir möchten die für jede konkrete Arraygröße optimierte Funktion kompilieren.
Wie auch immer, wir brauchen ein generisches Array - und es gibt eine Kiste in Rust, die genau das bietet.
Hier ist unser Code:
use generic_array::{GenericArray, ArrayLength}; fn foo<El, Size>(x: GenericArray<El, Size>, y: El) -> Option<usize> where El: Eq, Size: ArrayLength<El>, {
Was wissen wir daraus? Wir wissen, dass die Funktion das Array einer bestimmten Größe annimmt, die sich in seinem Typ widerspiegelt (und für jede dieser Größen unabhängig kompiliert wird). Im Moment ist dies fast nichts - die gleichen Garantien wurden zur Laufzeit von der vorherigen Implementierung bereitgestellt.
Aber wir können weiter kommen.
Arithmetik auf Typebene
Der erste Artikel erwähnte mehrere Garantien von Idris, die aus anderen Sprachen nicht zu bekommen waren. Einer von ihnen - und wahrscheinlich der einfachste, da er keine Beweise oder Tests enthält, sondern nur eine kleine Änderung der Typen - gibt an, dass der Rückgabewert, wenn er nicht Nothing , immer kleiner als die Listenlänge ist.
Sieht so aus, als wären die abhängigen Typen - oder so ähnlich - für eine solche Garantie notwendig, und wir können nicht dasselbe von Rust bekommen, oder?
Treffen Sie den Typenum . Mit ihm können wir unsere Funktion folgendermaßen schreiben:
use generic_array::{ArrayLength, GenericArray}; use typenum::{IsLess, Unsigned, B1}; trait UnsignedLessThan<T> { fn as_usize(&self) -> usize; } impl<Less, More> UnsignedLessThan<More> for Less where Less: IsLess<More, Output = B1>, Less: Unsigned, { fn as_usize(&self) -> usize { <Self as Unsigned>::USIZE } } fn foo<El, Size>(x: GenericArray<El, Size>, y: El) -> Option<Box<dyn UnsignedLessThan<Size>>> where El: Eq, Size: ArrayLength<El>, {
"Was ist das für schwarze Magie ?!" - Du könntest fragen. Und Sie haben Recht: Typenum ist eine schwarze Magie, und alle Versuche, es zu verwenden, sind noch magischer.
Diese Funktionssignatur ist jedoch ziemlich konkret.
- Es braucht ein Array von El's mit der Länge Size und ein weiteres El.
- Es gibt eine Option zurück, die, wenn es sich um Some handelt,
- enthält ein Merkmalsobjekt , das auf dem Merkmal
UnsignedLessThan<Size> basiert; - und
UnsignedLessThan<T> wird überall dort implementiert, wo Unsigned und IsLess<T> implementiert sind und IsLess<T> B1 zurückgibt, d. IsLess<T> . true.
Mit anderen Worten, diese Funktion gibt garantiert eine vorzeichenlose Ganzzahl zurück, die kleiner als die Arraygröße ist (genau genommen gibt sie das as_usize zurück, aber wir können die Methode as_usize aufrufen und die Ganzzahl as_usize ).
Ich kann jetzt von zwei wichtigen Vorbehalten sprechen:
- Wir können einen Leistungsverlust bekommen. Wenn sich diese Funktion irgendwie auf dem "heißen" Pfad des Programms befindet, können die konstanten dynamischen Versendungen den gesamten Prozess verlangsamen. Dies ist zwar kein großes Problem, aber es gibt noch ein anderes:
- Damit diese Funktion kompiliert werden kann, müssen wir entweder den Beweis ihrer Richtigkeit direkt in sie schreiben oder das Typsystem mit etwas
unsafe . Ersteres ist ziemlich komplex und letzteres betrügt nur.
Fazit
In der Praxis verwenden wir natürlich im Allgemeinen entweder den zweiten Ansatz (mit generischem Slice) oder den Ansatz im Spoiler (mit Iterator). Alle nachfolgenden Diskussionen sind wahrscheinlich nicht von praktischem Interesse und dienen hier nur als Übung mit Typen.
Wie auch immer, die Tatsache, dass das Rust-Typ-System die Funktion des stärkeren Idris-Typ-Systems emulieren kann, ist für mich selbst ziemlich beeindruckend.