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

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?

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.

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…
  

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 .

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

"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.