Tests oder Typen? - Rostversion

Vor ein paar Tagen hat 0xd34df00d hier eine Übersetzung eines Artikels veröffentlicht, der beschreibt, was Sie über eine Funktion in verschiedenen Sprachen lernen können, wenn Sie sie als "Black Box" betrachten, ohne Informationen über ihre Implementierung zu verwenden (aber natürlich ohne die Verwendung des Compilers zu verhindern). Natürlich sind die erhaltenen Informationen sehr abhängig von der Sprache - vier Beispiele wurden im Originalartikel berücksichtigt:

• Python - dynamisch typisierte, minimale Informationen, nur Tests geben einige Hinweise;
• C - schwach statisch typisiert, nicht viel mehr Informationen;
• Haskell - stark statisch typisiert, mit reinen Funktionen, viel mehr Informationen;
• Idris ist eine Sprache mit abhängigen Typen. Es gibt genügend Informationen, um die Richtigkeit der Funktion während der Kompilierung zu beweisen.

"Da ist C, da ist Haskell, aber wo ist Rust ?!" - Sofort wurde die Frage aufgeworfen. Die Antwort ist unter dem Schnitt.

Erinnern Sie sich an den Zustand des Problems:

Lassen Sie eine Liste und eine Bedeutung gegeben werden. Es ist erforderlich, den Index dieses Werts in der Liste zurückzugeben oder anzugeben, dass dieser Wert nicht in der Liste enthalten ist.

Für Ungeduldige - alle unten diskutierten Optionen sind auf dem Rust-Spielplatz zu sehen .
Lass uns gehen!

Einfache Suche

Wir beginnen mit einer fast naiven Signatur, die sich tatsächlich nur in einigen idiomatischen Elementen vom C-Code unterscheidet:

fn foo(x: &[i32], y: i32) -> Option<usize> { // 10000    } 

Was wissen wir über diese Funktion? Naja ... eigentlich nicht so sehr. Natürlich ist es viel besser, Option<usize> in den Rückgabewerten zu haben, als C uns zur Verfügung gestellt hat, aber wir haben immer noch keine Informationen über die Semantik der Funktion. Insbesondere gibt es keine Garantie dafür, dass keine Nebenwirkungen auftreten, und es gibt auch keine Möglichkeit, das erwartete Verhalten zu überprüfen.

Kann ein korrekt geschriebener Test die Situation beheben? Wir schauen:

 #[test] fn test() { assert_eq!(foo(&[1, 2, 3], 2), Some(1)); assert_eq!(foo(&[1, 2, 3], 4), None); } 

Im Allgemeinen haben wir nichts Neues bekommen - all die gleichen Überprüfungen, die wir mit Python problemlos durchführen konnten (und die Tests werden in Zukunft praktisch nichts mehr bringen).

Benutze die Generika, Luke!

Aber ist es wirklich gut, dass wir nur signierte 32-Bit-Zahlen verwenden müssen? Das Durcheinander. Wir beheben:

 fn foo<El>(x: &[El], y: El) -> Option<usize> where El: PartialEq, { // 10000    } 

Ja! Das ist schon was. Jetzt können wir Scheiben nehmen, die aus beliebigen Elementen bestehen, die wir auf Gleichheit vergleichen können. Expliziter Polymorphismus ist fast immer besser als implizit und fast immer besser als keiner, oder?

Eine solche Funktion kann jedoch unerwartet den folgenden Test für uns bestehen:

 fn refl<El: PartialEq + Copy>(el: El) -> Option<usize> { foo(&[el], el) // should always return Some(0), right? } #[test] fn dont_find_nan() { assert_eq!(refl(std::f64::NAN), None); } 

Dies weist sofort auf einen Fehler unsererseits hin, da ein solcher Aufruf gemäß der ursprünglichen Spezifikation Some(0) müsste. Natürlich liegt das Problem hier an der Spezifität von Typen mit einem teilweise definierten Vergleich im Allgemeinen und Floats im Besonderen.
Nehmen wir jetzt an, wir wollen ein solches Problem beseitigen - dafür verschärfen wir nur die Anforderungen für den Typ El:

 fn foo<El>(x: &[El], y: El) -> Option<usize> where El: Eq, { // 10000    } 

Jetzt fordern wir nicht nur die Möglichkeit eines Vergleichs für Gleichheit - wir fordern, dass dieser Vergleich eine Äquivalenzbeziehung ist . Dies schränkt den Bereich möglicher Parameter etwas ein, aber jetzt legen sowohl Typen als auch Tests nahe (wenn auch nicht explizit), dass das erwartete Verhalten wirklich in die Spezifikation fallen sollte.

 fn foo<'a, El: 'a>(x: impl IntoIterator<Item = &'a El>, y: El) -> Option<usize> where El: Eq, { // 10000    } 

Nach wie vor nur strenger

Zum Beispiel reichen uns jedoch die vom Compiler in bereits bekannten Phasen angebotenen Garantien nicht aus. Oder sagen wir, wir möchten nicht (aus dem einen oder anderen Grund) in einen Heap gelangen, sondern am Stapel arbeiten - was bedeutet, dass wir ein Array anstelle eines Vektors benötigen -, aber gleichzeitig möchten wir, dass unser Code auf verschiedene Größen des Arrays verallgemeinert wird . Oder wir möchten, dass die Funktion für jede bestimmte Größe der Eingabeliste so weit wie möglich optimiert wird.

Kurz gesagt, wir brauchen ein generisches Array - und Rust hat bereits ein Paket, das es wörtlich bereitstellt.

Jetzt steht uns folgender Code zur Verfügung:

 use generic_array::{GenericArray, ArrayLength}; fn foo<El, Size>(x: GenericArray<El, Size>, y: El) -> Option<usize> where El: Eq, Size: ArrayLength<El>, { // 10000    } 

Was wissen wir aus diesem Code? Dass die Funktion ein Array mit einer festen Größe verwendet, das sich in seinem Typ widerspiegelt (und für jede dieser Größen unabhängig kompiliert wird). Bisher ändert sich daran nicht viel - am Ende haben genau die gleichen Garantien, nicht nur in der Monomorphisierungsphase, sondern auch zur Laufzeit, die vorherige Version mit einem Schnitt versehen.

Aber wir können noch weiter gehen.

Typ Level Arithmetik

Der ursprüngliche Artikel erwähnte mehrere Garantien, die wir von Idris erhalten hatten und von niemand anderem bekommen konnten. Einer von ihnen - und vielleicht der einfachste, weil Sie dafür nicht einmal einen vollständigen Beweis oder einen vollständigen Test schreiben müssen, sondern nur den Typ ein wenig angeben müssen -, dass der Rückgabewert, falls vorhanden (d. H. Wenn er Nothing ) wird die Länge der Eingabeliste garantiert nicht überschreiten.

Es scheint, dass die notwendige Bedingung für eine solche Garantie das Vorhandensein abhängiger Typen oder zumindest eine Art Ähnlichkeit ist, und es wäre seltsam, so etwas von Rust zu erwarten, oder?

Meet - Typenum . Damit kann unsere Funktion folgendermaßen dargestellt werden:

 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>, { // 10000    } 

"Was zum Teufel ist diese schwarze Magie ?!" - Du fragst. Und Sie werden sicherlich Recht haben: Typenum ist diese schwarze Magie, und Versuche, sie zumindest irgendwie vernünftig einzusetzen, sind doppelt.

Trotzdem ist die Signatur dieser Funktion ziemlich eindeutig.

• Die Funktion akzeptiert ein Array von El-Elementen der Länge Size und ein Element vom Typ El.
• Die Funktion gibt einen Optionswert zurück, der, wenn es sich um Some handelt,
  
  • Es ist ein Merkmalobjekt, das auf dem UnsignedLessThan<T> basiert und den UnsignedLessThan<T> Size als Parameter akzeptiert.
  • Das IsLess<T> UnsignedLessThan<T> IsLess<T> für alle Typen implementiert, die Unsigned und IsLess<T> implementieren, für die IsLess<T> B1 zurückgibt, d. IsLess<T> wahr

Mit anderen Worten, auf diese Weise haben wir eine Funktion geschrieben, die garantiert eine nicht negative (vorzeichenlose) Zahl zurückgibt, die kleiner als die ursprüngliche Größe des Arrays ist (oder vielmehr natürlich dasselbe Merkmalsobjekt zurückgibt, von dem wir später die as_usize Methode aufrufen as_usize , die garantiert eine solche Zahl as_usize ). .

Bei diesem Ansatz gibt es genau zwei Tricks:

1. Wir können spürbar an Leistung verlieren. Wenn sich unsere Funktion aus irgendeinem Grund plötzlich im "heißen" Teil des Programms befindet, kann der ständige Bedarf an dynamischen Aufrufen eine der langsamsten Operationen sein. Dieser Nachteil mag zwar nicht so bedeutend sein, wie es scheint, aber es gibt einen zweiten:
2. Damit diese Funktion korrekt kompiliert werden kann, müssen wir entweder den Beweis für die Richtigkeit ihrer Arbeit in sie schreiben oder das Typensystem durch unsafe „austricksen“. Der erste ist zu kompliziert für den Artikel vom Freitag, aber der zweite ist einfach ein Betrug.

Fazit

In der Praxis wird in solchen Fällen natürlich entweder die zweite Implementierung (Empfang eines Slice eines beliebigen Typs) oder die Implementierung unter einem Spoiler (Empfang eines iterierbaren Objekts) verwendet. Alle nachfolgenden Argumente sind mit ziemlicher Sicherheit nicht von praktischem Interesse und dienen lediglich als Übung bei der Arbeit mit einem Typensystem.

Dennoch ist die Tatsache, dass das Rust-Typ-System eines der Merkmale des offensichtlich stärkeren Idris-Typ-Systems emulieren kann, meiner Meinung nach ziemlich bezeichnend.