Wie erreicht man in der funktionalen Programmierung Modularität durch mathematische Gesetze?

11

Ich habe in dieser Frage gelesen , dass funktionale Programmierer dazu neigen, mathematische Beweise zu verwenden, um sicherzustellen, dass ihr Programm korrekt funktioniert. Das klingt viel einfacher und schneller als Unit-Tests, aber ich komme aus einem OOP / Unit-Test-Hintergrund, den ich noch nie gesehen habe.

Können Sie es mir erklären und mir ein Beispiel geben?

leeand00
quelle
7
"Das klingt viel einfacher und schneller als Unit-Tests". Ja, hört sich an. In der Realität ist dies für die meisten Softwareprodukte praktisch unmöglich. Und warum erwähnt der Titel die Modularität, aber Sie sprechen von Verifizierung?
Euphoric
@Euphoric In Unit Testing in OOP schreiben Sie Tests zur Überprüfung ... Überprüfung, ob ein Teil der Software ordnungsgemäß funktioniert, aber auch Überprüfung, ob Ihre Bedenken getrennt sind ... dh Modularität und Wiederverwendbarkeit ... wenn ich das richtig verstehe.
leeand00
2
@Euphoric Nur wenn Sie Mutation und Vererbung missbrauchen und in Sprachen mit fehlerhaften Typsystemen arbeiten (dh haben null).
Doval
@ leeand00 Ich denke, Sie missbrauchen den Begriff "Verifikation". Modularität und Wiederverwendbarkeit werden nicht direkt durch Softwareüberprüfung überprüft (obwohl natürlich mangelnde Modularität die Wartung und Wiederverwendung der Software erschweren kann, wodurch Fehler auftreten und der Überprüfungsprozess fehlschlägt).
Andres F.
Es ist viel einfacher, Teile von Software zu überprüfen, wenn sie modular geschrieben sind. So können Sie wirklich beweisen, dass die Funktion für einige Funktionen korrekt funktioniert, für andere können Sie Komponententests schreiben.
Grizwako

Antworten:

22

Ein Beweis ist in der OOP-Welt aufgrund von Nebenwirkungen, uneingeschränkter Vererbung und nullder Zugehörigkeit zu jedem Typ viel schwieriger . Die meisten Beweise beruhen auf einem Induktionsprinzip, um zu zeigen, dass Sie alle Möglichkeiten abgedeckt haben, und alle drei dieser Dinge erschweren den Beweis.

Nehmen wir an, wir implementieren Binärbäume, die ganzzahlige Werte enthalten (um die Syntax einfacher zu halten, werde ich keine generische Programmierung einbringen, obwohl dies nichts ändern würde.) In Standard ML würde ich das wie folgt definieren Dies:

datatype tree = Empty | Node of (tree * int * tree)

Dies führt einen neuen Typ namens ein, treedessen Werte in genau zwei Varianten (oder Klassen, nicht zu verwechseln mit dem OOP-Konzept einer Klasse) vorliegen können - ein EmptyWert, der keine Informationen enthält, und NodeWerte, die ein 3-Tupel enthalten, dessen erster und letzter Elemente sind trees und deren mittleres Element ist ein int. Die nächste Annäherung an diese Erklärung in OOP würde folgendermaßen aussehen:

public class Tree {
    private Tree() {} // Prevent external subclassing

    public static final class Empty extends Tree {}

    public static final class Node extends Tree {
        public final Tree leftChild;
        public final int value;
        public final Tree rightChild;

        public Node(Tree leftChild, int value, Tree rightChild) {
            this.leftChild = leftChild;
            this.value = value;
            this.rightChild = rightChild;
        }
    }
}

Mit der Einschränkung, dass Variablen vom Typ Tree niemals sein können null.

Schreiben wir nun eine Funktion zur Berechnung der Höhe (oder Tiefe) des Baums und nehmen an, dass wir Zugriff auf eine maxFunktion haben, die die größere von zwei Zahlen zurückgibt:

fun height(Empty) =
        0
 |  height(Node (leftChild, value, rightChild)) =
        1 + max( height(leftChild), height(rightChild) )

Wir haben die heightFunktion nach Fällen definiert - es gibt eine Definition für EmptyBäume und eine Definition für NodeBäume. Der Compiler weiß, wie viele Baumklassen vorhanden sind, und gibt eine Warnung aus, wenn Sie nicht beide Fälle definiert haben. Der Ausdruck Node (leftChild, value, rightChild)in der Funktion Unterschrift bindet die Werte des 3-Tupels zu den Variablen leftChild, valueund rightChildjeweils so dass wir sie in der Funktionsdefinition beziehen. Es ist vergleichbar damit, lokale Variablen wie diese in einer OOP-Sprache deklariert zu haben:

Tree leftChild = tuple.getFirst();
int value = tuple.getSecond();
Tree rightChild = tuple.getThird();

Wie können wir nachweisen, dass wir heightrichtig implementiert haben? Wir können eine strukturelle Induktion verwenden , die aus Folgendem besteht: 1. Beweisen Sie, dass die Basisfälle heightunseres treeTyps ( Empty) heightkorrekt sind ( ). 2. Unter der Annahme, dass rekursive Aufrufe korrekt sind, beweisen Sie, dass sie heightfür die Nicht-Basisfälle korrekt sind ) (wenn der Baum tatsächlich a ist Node).

In Schritt 1 können wir sehen, dass die Funktion immer 0 zurückgibt, wenn das Argument ein EmptyBaum ist. Dies ist per Definition der Höhe eines Baumes korrekt.

Für Schritt 2 kehrt die Funktion zurück 1 + max( height(leftChild), height(rightChild) ). Angenommen, die rekursiven Aufrufe geben tatsächlich die Größe der Kinder zurück, können wir sehen, dass dies auch richtig ist.

Und das vervollständigt den Beweis. Die Schritte 1 und 2 zusammen schöpfen alle Möglichkeiten aus. Beachten Sie jedoch, dass wir keine Mutation, keine Nullen und genau zwei Baumarten haben. Nehmen Sie diese drei Bedingungen weg und der Beweis wird schnell komplizierter, wenn nicht unpraktisch.


EDIT: Da diese Antwort ganz oben angekommen ist, möchte ich ein weniger triviales Beispiel für einen Beweis hinzufügen und die strukturelle Induktion etwas gründlicher behandeln. Oben haben wir bewiesen, dass bei heightRückgabe der Rückgabewert korrekt ist. Wir haben jedoch nicht bewiesen, dass es immer einen Wert zurückgibt. Wir können die strukturelle Induktion auch verwenden, um dies (oder eine andere Eigenschaft) zu beweisen. Auch in Schritt 2 dürfen wir davon ausgehen, dass die Eigenschaften der rekursiven Aufrufe gültig sind, solange die rekursiven Aufrufe alle auf ein direktes untergeordnetes Element der Baum.

Eine Funktion kann in zwei Situationen keinen Wert zurückgeben: wenn sie eine Ausnahme auslöst und wenn sie für immer wiederholt wird. Lassen Sie uns zunächst beweisen, dass die Funktion beendet wird, wenn keine Ausnahmen ausgelöst werden:

  1. Beweisen Sie, dass (wenn keine Ausnahmen ausgelöst werden) die Funktion für die Basisfälle ( Empty) beendet wird. Da wir bedingungslos 0 zurückgeben, wird es beendet.

  2. Beweisen Sie, dass die Funktion in den Nicht-Basisfällen endet ( Node). Es gibt drei Funktionsaufrufe hier: +, max, und height. Wir wissen das +und maxbeenden es, weil sie Teil der Standardbibliothek der Sprache sind und so definiert sind. Wie bereits erwähnt, dürfen wir davon ausgehen, dass die Eigenschaft, die wir zu beweisen versuchen, bei rekursiven Aufrufen wahr ist, solange sie auf unmittelbaren Teilbäumen ausgeführt werden. Daher müssen Aufrufe auch heightbeendet werden.

Damit ist der Beweis abgeschlossen. Beachten Sie, dass Sie die Beendigung mit einem Komponententest nicht nachweisen können. Jetzt heightmuss nur noch gezeigt werden, dass keine Ausnahmen ausgelöst werden.

  1. Beweisen Sie, dass heightim Basisfall keine Ausnahmen auftreten ( Empty). Die Rückgabe von 0 kann keine Ausnahme auslösen, also sind wir fertig.
  2. Beweisen Sie, dass heightbeim Nicht-Basisfall ( Node) keine Ausnahme ausgelöst wird . Nehmen wir noch einmal an, wir kennen +und maxwerfen keine Ausnahmen. Und die strukturelle Induktion erlaubt es uns anzunehmen, dass die rekursiven Aufrufe auch nicht werfen (weil sie die unmittelbaren Kinder des Baumes operieren). Aber warten Sie! Diese Funktion ist rekursiv, aber nicht rekursiv . Wir könnten den Stapel sprengen! Unser Beweisversuch hat einen Fehler aufgedeckt. Wir können das Problem beheben, indem wir es so ändern height, dass es rekursiv ist .

Ich hoffe, dies zeigt, dass Beweise nicht beängstigend oder kompliziert sein müssen. Tatsächlich haben Sie beim Schreiben von Code informell einen Beweis in Ihrem Kopf erstellt (andernfalls wären Sie nicht davon überzeugt, dass Sie die Funktion nur implementiert haben). Indem Sie Null, unnötige Mutation und uneingeschränkte Vererbung vermeiden, können Sie beweisen, dass Ihre Intuition ist ziemlich leicht zu korrigieren. Diese Einschränkungen sind nicht so streng, wie Sie vielleicht denken:

  • null ist ein Sprachfehler und es ist bedingungslos gut, ihn zu beseitigen.
  • Mutationen sind manchmal unvermeidlich und notwendig, aber sie werden viel seltener benötigt, als Sie denken - insbesondere, wenn Sie über dauerhafte Datenstrukturen verfügen.
  • Eine endliche Anzahl von Klassen (im funktionalen Sinne) / Unterklassen (im OOP-Sinne) gegenüber einer unbegrenzten Anzahl von Klassen zu haben, ist ein Thema, das für eine einzelne Antwort zu groß ist . Es genügt zu sagen, dass es dort einen Kompromiss zwischen Design gibt - Beweisbarkeit der Korrektheit gegenüber Flexibilität der Erweiterung.
Doval
quelle
8
  1. Es ist viel einfacher, über Code nachzudenken, wenn alles unveränderlich ist . Infolgedessen werden Schleifen häufiger als Rekursion geschrieben. Im Allgemeinen ist es einfacher, die Richtigkeit einer rekursiven Lösung zu überprüfen. Oft liest sich eine solche Lösung auch sehr ähnlich wie eine mathematische Definition des Problems.

    In den meisten Fällen besteht jedoch nur eine sehr geringe Motivation, einen tatsächlichen formalen Korrektheitsnachweis zu erbringen. Beweise sind schwierig, nehmen viel (menschliche) Zeit in Anspruch und haben einen niedrigen ROI.

  2. Einige funktionale Sprachen (insbesondere aus der ML-Familie) verfügen über äußerst ausdrucksstarke Typsysteme, die viel umfassendere Garantien für ein C-Typ-System bieten können (aber einige Ideen wie Generika sind auch in den gängigen Sprachen üblich geworden). Wenn ein Programm eine Typprüfung besteht, ist dies eine Art automatisierter Beweis. In einigen Fällen kann dies einige Fehler erkennen (z. B. das Vergessen des Basisfalls in einer Rekursion oder das Vergessen, bestimmte Fälle in einer Musterübereinstimmung zu behandeln).

    Andererseits müssen diese Typsysteme sehr begrenzt gehalten werden, um sie entscheidbar zu halten . In gewissem Sinne erhalten wir statische Garantien, indem wir auf Flexibilität verzichten - und diese Einschränkungen sind ein Grund, warum komplizierte wissenschaftliche Arbeiten im Sinne von „ Eine monadische Lösung für ein gelöstes Problem in Haskell “ existieren.

    Ich mag sowohl sehr liberale als auch sehr eingeschränkte Sprachen und beide haben ihre jeweiligen Schwierigkeiten. Aber es ist nicht so, dass man „besser“ wäre, jeder ist einfach bequemer für eine andere Art von Aufgabe.

Dann muss darauf hingewiesen werden, dass Proofs und Unit-Tests nicht austauschbar sind. Beide erlauben es uns, der Richtigkeit des Programms Grenzen zu setzen:

  • Das Testen legt eine Obergrenze für die Richtigkeit fest: Wenn ein Test fehlschlägt, ist das Programm falsch. Wenn keine Tests fehlschlagen, sind wir sicher, dass das Programm die getesteten Fälle behandelt, aber es können immer noch unentdeckte Fehler auftreten.

    int factorial(int n) {
      if (n <= 1) return 1;
      if (n == 2) return 2;
      if (n == 3) return 6;
      return -1;
    }
    
    assert(factorial(0) == 1);
    assert(factorial(1) == 1);
    assert(factorial(3) == 6);
    // oops, we forgot to test that it handles n > 3…
    
  • Beweise legen eine Untergrenze für die Richtigkeit fest: Es kann unmöglich sein, bestimmte Eigenschaften nachzuweisen. Zum Beispiel kann es leicht sein zu beweisen, dass eine Funktion immer eine Zahl zurückgibt (das ist, was Typsysteme tun). Es kann jedoch unmöglich sein zu beweisen, dass die Zahl immer sein wird < 10.

    int factorial(int n) {
      return n;  // FIXME this is just a placeholder to make it compile
    }
    
    // type system says this will be OK…
    
amon
quelle
1
"Es kann unmöglich sein, bestimmte Eigenschaften zu beweisen ... Aber es kann unmöglich sein zu beweisen, dass die Zahl immer <10 sein wird." Wenn die Richtigkeit des Programms davon abhängt, dass die Zahl unter 10 liegt, sollten Sie dies nachweisen können. Es ist wahr, dass das Typsystem dies nicht kann (zumindest nicht, ohne eine Menge gültiger Programme auszuschließen) - aber Sie können.
Doval
@Doval Ja. Das Typsystem ist jedoch nur ein Beispiel für ein System für einen Beweis. Typsysteme sind sehr sichtbar eingeschränkt und können die Wahrheit bestimmter Aussagen nicht beurteilen. Eine Person kann weitaus komplexere Beweise durchführen, ist aber immer noch in dem begrenzt, was sie beweisen kann. Es gibt immer noch eine Grenze, die nicht überschritten werden kann, sie ist nur weiter entfernt.
Amon
1
Einverstanden, ich denke nur, dass das Beispiel etwas irreführend war.
Doval
2
In abhängig getippten Sprachen wie Idris könnte es sogar möglich sein zu beweisen, dass es weniger als 10 zurückgibt.
Ingo
2
Ein besserer Weg, um die von @Doval angesprochenen Bedenken auszuräumen, wäre möglicherweise die Feststellung, dass einige Probleme unentscheidbar sind (z. B. das Anhalten des Problems), zu viel Zeit zum Nachweis benötigen oder dass neue Mathematik entdeckt werden muss, um das Ergebnis zu beweisen. Meine persönliche Meinung ist, dass Sie klarstellen sollten, dass es nicht erforderlich ist , einen Unit-Test durchzuführen , wenn sich herausstellt, dass etwas wahr ist . Der Beweis legt bereits eine Ober- und Untergrenze fest. Der Grund, warum Beweise und Tests nicht austauschbar sind, liegt darin, dass ein Beweis zu schwer oder einfach unmöglich zu machen sein kann. Auch Tests können automatisiert werden (wenn sich der Code ändert).
Thomas Eding
7

Hier kann ein warnendes Wort angebracht sein:

Während es im Allgemeinen wahr ist, was andere hier schreiben - kurz gesagt, dass fortschrittliche Typsysteme, Unveränderlichkeit und referenzielle Transparenz viel zur Korrektheit beitragen -, ist es nicht so, dass Tests nicht in der Funktionswelt durchgeführt werden. Im Gegenteil !

Dies liegt daran, dass wir Tools wie Quickcheck haben, die Testfälle automatisch und zufällig generieren. Sie geben lediglich die Gesetze an, denen eine Funktion entsprechen muss, und dann werden diese Gesetze durch Quickcheck auf Hunderte von zufälligen Testfällen überprüft.

Sie sehen, dies ist ein etwas höheres Niveau als triviale Gleichheitsprüfungen für eine Handvoll Testfälle.

Hier ist ein Beispiel aus einer Implementierung eines AVL-Baums:

--- A generator for arbitrary Trees with integer keys and string values
aTree = arbitrary :: Gen (Tree Int String)


--- After insertion, a lookup with the same key yields the inserted value        
p_insert = forAll aTree (\t -> 
             forAll arbitrary (\k ->
               forAll arbitrary (\v ->
                lookup (insert t k v) k == Just v)))

--- After deletion of a key, lookup results in Nothing
p_delete = forAll aTree (\t ->
            not (null t) ==> forAll (elements (keys t)) (\k ->
                lookup (delete t k) k == Nothing))

Das zweite Gesetz (oder die zweite Eigenschaft) kann wie folgt gelesen werden: Für alle beliebigen Bäume tgilt Folgendes: Wenn tes nicht leer ist, enthält es für alle Schlüssel kdieses Baums das Nachschlagen kin dem Baum, das das Ergebnis des Löschens ist kvon twird das Ergebnis sein Nothing(was anzeigt: nicht gefunden).

Dadurch wird die ordnungsgemäße Funktionalität zum Löschen eines vorhandenen Schlüssels überprüft. Welche Gesetze sollten das Löschen eines nicht vorhandenen Schlüssels regeln? Wir möchten auf jeden Fall, dass der resultierende Baum mit dem Baum übereinstimmt, aus dem wir gelöscht haben. Wir können dies leicht ausdrücken:

p_delete_nonexistant = forAll aTree (\t ->
                          forAll arbitrary (\k -> 
                              k `notElem` keys t ==> delete t k == t))

Auf diese Weise macht das Testen wirklich Spaß. Sobald Sie das Lesen von Quickcheck-Eigenschaften gelernt haben, dienen diese außerdem als maschinenprüfbare Spezifikation .

Ingo
quelle
4

Ich verstehe nicht genau, was die verknüpfte Antwort bedeutet "Modularität durch mathematische Gesetze erreichen", aber ich glaube, ich habe eine Vorstellung davon, was gemeint ist.

Check out Functor :

Die Functor-Klasse ist wie folgt definiert:

 class Functor f where
   fmap :: (a -> b) -> f a -> f b

Es kommt nicht mit Testfällen, sondern mit ein paar Gesetzen, die erfüllt werden müssen.

Alle Instanzen von Functor sollten Folgendes befolgen:

 fmap id = id
 fmap (p . q) = (fmap p) . (fmap q)

Angenommen, Sie implementieren Functor( Quelle ):

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

Das Problem besteht darin, zu überprüfen, ob Ihre Implementierung den Gesetzen entspricht. Wie machst du das?

Ein Ansatz besteht darin, Testfälle zu schreiben. Die grundlegende Einschränkung dieses Ansatzes besteht darin, dass Sie das Verhalten in einer begrenzten Anzahl von Fällen überprüfen (viel Glück beim ausführlichen Testen einer Funktion mit 8 Parametern!). Daher kann das Bestehen von Tests nichts anderes garantieren, als dass die Tests bestanden werden.

Ein anderer Ansatz besteht darin, mathematisches Denken zu verwenden, dh einen Beweis, der auf der tatsächlichen Definition basiert (anstelle des Verhaltens in einer begrenzten Anzahl von Fällen). Die Idee hier ist, dass ein mathematischer Beweis effektiver sein kann; Dies hängt jedoch davon ab, wie gut Ihr Programm für mathematische Beweise geeignet ist.

Ich kann Sie nicht durch einen tatsächlichen formalen Beweis führen, dass die obige FunctorInstanz den Gesetzen entspricht, aber ich werde versuchen, einen Überblick darüber zu geben, wie der Beweis aussehen könnte:

  1. fmap id = id
    • wenn wir haben Nothing
      • fmap id Nothing= Nothingnach Teil 1 der Implementierung
      • id Nothing= Nothingnach der Definition vonid
    • wenn wir haben Just x
      • fmap id (Just x)= Just (id x)= Just xdurch Teil 2 der Implementierung, dann durch die Definition vonid
  2. fmap (p . q) = (fmap p) . (fmap q)
    • wenn wir haben Nothing
      • fmap (p . q) Nothing= Nothingnach Teil 1
      • (fmap p) . (fmap q) $ Nothing= (fmap p) $ Nothing= Nothingdurch zwei Anwendungen von Teil 1
    • wenn wir haben Just x
      • fmap (p . q) (Just x)= Just ((p . q) x)= Just (p (q x))nach Teil 2, dann nach der Definition von.
      • (fmap p) . (fmap q) $ (Just x)= (fmap p) $ (Just (q x))= Just (p (q x))durch zwei Anwendungen von Teil zwei

quelle
-1

"Hüten Sie sich vor Fehlern im obigen Code. Ich habe es nur als richtig erwiesen, nicht ausprobiert." - Donald Knuth

In einer perfekten Welt sind Programmierer perfekt und machen keine Fehler, daher gibt es keine Fehler.

In einer perfekten Welt sind auch Informatiker und Mathematiker perfekt und machen auch keine Fehler.

Aber wir leben nicht in einer perfekten Welt. Wir können uns also nicht darauf verlassen, dass Programmierer keine Fehler machen. Wir können jedoch nicht davon ausgehen, dass ein Informatiker, der einen mathematischen Beweis für die Richtigkeit eines Programms liefert, bei diesem Beweis keine Fehler gemacht hat. Ich würde also niemandem Aufmerksamkeit schenken, der versucht zu beweisen, dass sein Code funktioniert. Schreiben Sie Unit-Tests und zeigen Sie mir, dass sich der Code gemäß den Spezifikationen verhält. Alles andere wird mich von nichts überzeugen.

Philipp
quelle
5
Unit-Tests können ebenfalls Fehler enthalten. Noch wichtiger ist, dass Tests nur das Vorhandensein von Fehlern anzeigen können - niemals deren Abwesenheit. Wie @Ingo in seiner Antwort sagte, machen sie großartige Sanitätsprüfungen und ergänzen Beweise gut, aber sie sind kein Ersatz für sie.
Doval