Parsen statt Validieren (2019)

 (lexi-lambda.github.io)
3 Punkte von GN⁺ 2024-07-23 | 1 Kommentare | Auf WhatsApp teilen
  • In der typsicheren, typgetriebenen Entwicklung erhöht Parsen – also Prüfresultate in einem präziseren Typ festzuhalten – die Sicherheit des nachfolgenden Codes stärker als bloßes Validieren, bei dem Eingaben nur geprüft und dann verworfen werden.
  • Funktionen wie head :: [a] -> a, die bei manchen Eingaben fehlschlagen, können zwar durch einen schwächeren Rückgabetyp entschärft werden, doch der Aufrufer muss dann weiterhin unnötige Fehlerzweige mittragen.
  • NonEmpty a bewahrt im Typ, dass eine Liste nicht leer ist, und reduziert dadurch doppelte Prüfungen und Fehlerbehandlung für Fälle, die „niemals eintreten sollten“.
  • Wenn im gesamten Verarbeitungscode provisorische Validierungen verteilt werden, entsteht shotgun parsing: Eingabefehler werden dann womöglich erst nach einigen Zustandsänderungen entdeckt.
  • In der Praxis sollte man zuerst die gewünschte Datenrepräsentation in der Funktionssignatur ausdrücken und Invarianten mit Map, abstrakten Typen, Smart Constructors usw. an die Typgrenze verlagern.

Der Ausgangspunkt typgetriebener Entwicklung

  • „Parse, don’t validate“ ist eine Formulierung, die typgetriebene Entwicklung in drei Worte fasst.
  • Ein statisches Typsystem macht schon vor dem Schreiben des Codes sichtbar, ob sich eine Funktion überhaupt implementieren lässt.
  • Im Haskell-Beispiel foo :: Integer -> Void lässt sich kein echter Wert erzeugen, weil Void keine Werte besitzt.
  • Auch head :: [a] -> a ist nicht für alle Eingaben definiert, da eine leere Liste [] übergeben werden kann.
    • GHC warnt davor, dass das Pattern Matching [] nicht behandelt.
    • Es handelt sich also um eine partielle Funktion, die nicht für alle möglichen Eingaben definiert ist.

Zwei Wege, partielle Funktionen in totale Funktionen zu verwandeln

  • Den Rückgabetyp abschwächen

    • Wenn man head :: [a] -> Maybe a verwendet, kann bei einer leeren Liste Nothing zurückgegeben werden, und die Funktion wird total.
    • Die Implementierung wird dadurch einfacher, aber der Aufrufer muss immer die Möglichkeit von Nothing behandeln.
    • Im Beispiel wird die Umgebungsvariable CONFIG_DIRS gelesen und bereits darauf geprüft, dass die Liste nicht leer ist; trotzdem muss main den Nothing-Zweig des head-Ergebnisses erneut behandeln.
    • Doppelte Prüfungen machen den Code unübersichtlich und können sich in komplexeren Fällen auch als Performance-Kosten summieren.
    • Selbst wenn die vorgelagerte Prüfung entfernt wird, wird der weiter hinten liegende Fehlerfall, der „niemals eintreten sollte“, nicht als Typproblem sichtbar.
    • Am Ende entsteht also ein Loch im Typsystem, und das Auffinden von Bugs hängt stärker von Tests oder manueller Prüfung ab.

  • Den Argumenttyp stärken

    • Statt den Rückgabetyp abzuschwächen, kann man den Argumenttyp stärken und so ausschließen, dass head jemals mit einer leeren Liste aufgerufen wird.
    • NonEmpty a aus Data.List.NonEmpty steht für eine nicht leere Liste.
    • Die Definition lautet data NonEmpty a = a :| [a].
    • Das erste Element a und der Rest der Liste [a] sind getrennt, sodass selbst bei leerem Rest immer ein erstes Element vorhanden ist.
    • head :: NonEmpty a -> a lässt sich mit einem einzigen Pattern implementieren und wird damit total.
    • Wenn man etwa den Rückgabetyp zu getConfigurationDirectories :: IO (NonEmpty FilePath) ändert, bleibt die Information „nicht leer“ im Typ erhalten.
    • nonEmpty :: [a] -> Maybe (NonEmpty a) wandelt eine normale Liste in NonEmpty um.
    • Die Behandlung von Nothing erfolgt nur einmal an der Eingabegrenze.
    • In main kann man dann initializeCache (head configDirs) ohne doppelte Verzweigungen verwenden.
    • Falls getConfigurationDirectories später nicht mehr garantieren sollte, dass die Liste nicht leer ist, müsste sich auch der Rückgabetyp ändern, und main würde die Typprüfung nicht mehr bestehen.

Der Unterschied zwischen Validieren und Parsen

  • validateNonEmpty :: [a] -> IO () und parseNonEmpty :: [a] -> IO (NonEmpty a) prüfen beide auf eine leere Liste und schlagen im Fehlerfall fehl.
  • Der Unterschied liegt im Rückgabetyp.
    • validateNonEmpty gibt das informationslose () zurück und verwirft damit das Ergebnis der Prüfung.
    • parseNonEmpty gibt NonEmpty a zurück und bewahrt das durch die Prüfung gewonnene Wissen im Typsystem.
  • Ein Parser lässt sich als Funktion verstehen, die weniger strukturierte Eingaben konsumiert und stärker strukturierte Ausgaben erzeugt.
  • In diesem Sinn ist parseNonEmpty ein einfacher Parser, der eine Liste in eine nicht leere Liste parst.
  • Parsen sorgt dafür, dass Prüfungen an der Grenze zwischen Programm und Außenwelt früh abgeschlossen werden und später nicht immer wiederholt werden müssen.

Parsing-Grenzen im Haskell-Ökosystem

  • Haskell-Anwendungen verwenden an den Übergängen zur Außenwelt verschiedene Arten von Parsern.
    • aeson: stellt den Typ Parser bereit, um JSON-Daten in Domänentypen zu parsen.
    • optparse-applicative: bietet Parser-Kombinatoren für Kommandozeilenargumente.
    • persistent, postgresql-simple: bieten Mechanismen zum Parsen von Werten aus externen Datenspeichern.
    • servant: parst Haskell-Datentypen aus Pfadbestandteilen, Query-Parametern, HTTP-Headern usw.
  • Die Außenwelt spricht nicht in Produkt- und Summentypen, sondern in Bytestreams; deshalb ist Parsing unvermeidlich.
  • Wenn Daten bereits vor ihrer Verwendung vorgelagert geparst werden, lassen sich viele Arten von Bugs vermeiden, von denen manche sogar zu Sicherheitslücken führen können.
  • Um alles früh zu parsen, muss man Werte unter Umständen deutlich früher parsen, als sie tatsächlich gebraucht werden.
  • In einem statischen Typsystem kompiliert ein Programm nicht, wenn Parsing-Logik und Verarbeitungscode auseinanderlaufen.

Risiken eines validierungszentrierten Ansatzes

  • Ad-hoc-Validierungen können zu shotgun parsing führen, einem Begriff aus dem Bereich language-theoretic security.
  • Im Paper von 2016 The Seven Turrets of Babel: A Taxonomy of LangSec Errors and How to Expunge Them wird shotgun parsing als Antipattern beschrieben, bei dem Parsing- und Eingabevalidierungscode verstreut zwischen Verarbeitungscode vermischt werden.
  • Wenn Eingaben nicht vollständig im Voraus geparst werden, kann das Programm zunächst einige gültige Teile verarbeiten und Fehler in anderen Teilen erst spät entdecken.
    • In diesem Fall müssen bereits ausgeführte Zustandsänderungen rückgängig gemacht werden.
    • In manchen Fällen ist das möglich, etwa mit RDBMS-Transaktionen, aber allgemein ist das nicht immer machbar.
  • Ein validierungsbasierter Ansatz macht es schwierig oder unmöglich zu überprüfen, ob wirklich alle Validierungen bereits im Voraus abgeschlossen wurden.
  • Parsen trennt ein Programm in eine Parsing-Phase und eine Ausführungsphase und beschränkt Fehler durch ungültige Eingaben auf die erste Phase.

Anwendung in der Praxis

  • Beim Entwurf schreibt man zuerst die gewünschte Datenrepräsentation in die Typsignatur und überbrückt dann die Differenz zur aktuell vorliegenden Repräsentation.
  • Wenn eine Funktion eine Liste [(k, v)] erhält, in der doppelte Schlüssel nicht erlaubt sein sollen, kann eine separate Prüfung wie checkNoDuplicateKeys :: ... => [(k, v)] -> m () leicht vergessen werden.
  • Besser ist es, die Funktion direkt ein Map als Argument annehmen zu lassen, das doppelte Schlüssel strukturell nicht zulässt.
    • An der Aufrufstelle kann dann die Typprüfung fehlschlagen.
    • Entlang der Aufrufkette wird die Umwandlung von der Liste in ein Map immer weiter nach oben verschoben.
    • Dort, wo Werte erzeugt werden oder wo Duplikate tatsächlich erlaubt sein müssen, fügt man dann eine Prüfung in der Form [(k, v)] -> m (Map k v) ein.
  • Dabei ist das Ergebnis der Prüfung für die spätere Ausführung notwendig, sodass die Prüfung nicht einfach ausgelassen werden kann.
  • Immer wieder tauchen zwei Prinzipien auf.
    • Datenstrukturen verwenden, die unmögliche Zustände nicht darstellbar machen.
    • Die Beweislast so weit wie möglich nach oben verlagern, aber nicht weiter als bis zu dem Punkt, an dem sie tatsächlich gebraucht wird.

Zusätzliche Entwurfsrichtlinien und Grenzen

  • Datentypen sollten den Code führen, und man sollte der Versuchung widerstehen, nur wegen der gerade implementierten Funktion einfach ein Bool in einen Record zu stecken.
  • Funktionen mit Rückgabewert m () sollte man mit Skepsis betrachten.
    • Wenn sie nur imperative Effekte ausführen und kein sinnvolles Ergebnis haben, können sie notwendig sein.
    • Wenn ihr Hauptzweck darin besteht, Fehler auszulösen, gibt es wahrscheinlich eine bessere Lösung.
  • Man muss keine Angst davor haben, Daten in mehreren Schritten zu parsen.
    • Shotgun parsing zu vermeiden bedeutet nicht, auf Eingabedaten zu reagieren, bevor sie vollständig geparst sind.
    • Es ist durchaus möglich, anhand eines Teils der Eingabe zu entscheiden, wie andere Teile geparst werden sollen.
  • Denormalisierte Datenrepräsentationen sollte man vermeiden, besonders wenn sie veränderbar sind.
    • Wenn dieselben Daten an mehreren Stellen dupliziert werden, entstehen leicht voneinander abweichende Zustände.
    • Wenn Denormalisierung unvermeidlich ist, sollte sie hinter einer Abstraktionsgrenze verborgen werden, sodass nur ein kleines vertrauenswürdiges Modul für die Synchronisierung verantwortlich ist.
  • Wenn sich bestimmte Invarianten mit den Haskell-Werkzeugen allein nur schwer ausdrücken lassen, kann man mit abstrakten newtypes und Smart Constructors Validatoren wie Parser aufbauen.
  • Es ist nicht nötig, singletons einzuführen und die gesamte Anwendung zu refaktorieren, nur um jedes error "impossible" zu eliminieren; in solchen Fällen sollte man aber sorgfältig vorgehen und Invarianten etwa in Kommentaren festhalten.

Weiterführende Lektüre und praktische Vorsicht

  • Um das Haskell-Typsystem gut zu nutzen, braucht man weder einen PhD noch zwingend die neuesten GHC-Spracherweiterungen.
  • Der Ausgangspunkt ist eher das einfache Prinzip „Schreibe totale Funktionen“, auch wenn die Anwendung dieses Prinzips im echten Code nicht immer leicht ist.
  • Die Haskell-Community ist klein, daher bleiben Entwurfsmuster und Techniken oft eher mündlich überliefert als gut dokumentiert.
  • Als weiterführendes Material wird Matt Parsons Type Safety Back and Forth genannt.
  • Für fortgeschrittenere Themen behandelt Matt Noonans Paper von 2018 Ghosts of Departed Proofs Techniken, um komplexere Invarianten im Typsystem auszudrücken.
  • In realen Programmen kann es schwierig sein, bestimmte Invarianten im Typsystem abzubilden; diese Prinzipien sind daher eher ein anzustrebendes Ideal als starre Anforderungen.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-07-23
Kommentare auf Hacker News

  • Sehr guter Rat und ein hervorragender Artikel. Es gibt einen Grund, warum er auf dieser Seite gelegentlich wieder hochkommt.
    Diese Idee geht über Paradigmen hinaus, auch für Leute, die keine statisch typisierten funktionalen Sprachen verwenden. In der objektorientierten Literatur der 80er und 90er, etwa bei Design by Contract, findet man sehr ähnliche Konzepte, und vermutlich auch in noch älteren Papers, Diskussionen und Spezifikationen.
    Auch TypeScript wird meines Erachtens oft so geschrieben, dass Typen zur Laufzeit schrittweise eingegrenzt werden. Design by Contract dürfte auch Clojures spec beeinflusst haben, obwohl Clojure eine dynamische Sprache ist.
    Im Kern geht es um Annahmen und Garantien. Wenn man bestimmte Annahmen prüfen und daraus Garantien ableiten kann, müssen andere Teile des Programms dieselben Annahmen nicht erneut prüfen.
    Am verwirrendsten ist es, wenn man beim Lesen von Code sieht, dass an anderer Stelle Eigenschaften erneut geprüft werden, die bereits garantiert sind. Das macht Schlussfolgerungen und Verbesserungen schwieriger.

    • Diese „bereits garantierte Eigenschaft“ kann irgendwann verschwinden. Genauer gesagt: Der Prozess, der diese Garantie implementiert und ausführt, kann aus irgendeinem Grund seine Aufgabe nicht mehr erfüllen.
      Statistisch gesehen passiert so etwas irgendwann, und dann geraten andere Prozesse, Skripte und Code, die sich auf den „ursprünglichen“ Validierungsprozess verlassen haben, in große Schwierigkeiten.
    • In Sprachen mit starkem Typsystem wird das mit wachsender Größe und Komplexität des Programms letztlich zu einem der praktischen Vorteile, die Freiheit geben.
      Man muss es allerdings auch tatsächlich nutzen. Zum Beispiel mit Klassen wie UncheckedEmail, ValidEmail und VerifiedEmail, sodass der Übergang von einer Stufe zur nächsten zwingend den Prozess der E-Mail-Verifizierung durchlaufen muss.
      Dann muss man nicht raten, ob eine E-Mail-Adresse ungeprüft, formal gültig oder verifiziert ist, und man braucht auch kein Boolean wie is_email_verified, dessen Aktualisierung oder Prüfung man vergessen kann. Wenn man an der falschen Stelle den falschen Wert verwendet, schreit der Typprüfer, und Menschen können sich auf Wichtiges konzentrieren.
    • Wenn man die Kommentare zu älteren Einreichungen überfliegt, scheint eines der größten Probleme dieses Artikels der Titel zu sein. Der Titel wirkt wie ein Anker, sodass viele Leute gegen Dinge argumentieren, die im Text nicht stehen und die nur der Titel ohne Kontext andeutet.
      Deshalb wird es manchmal so verstanden, als wolle die Autorin bzw. der Autor überhaupt nicht validieren, sondern nur parsen. Tatsächlich geht es im Artikel darum, wo Daten validiert werden und was man mit dem Ergebnis macht. Es ist kein Plädoyer dafür, jede Validierung abzuschaffen.

  • Der Artikel ist von 2019, aber immer noch ziemlich guter Rat. Dieses Pattern passt auch sehr gut zu modernem C#, und weil man explizite Variablendeklarationen weglassen kann, spart es zudem Platz.
    if(!Whatever.TryParse(input, out var output)) output = some-sane-default;
    oder
    if(!Whatever.TryParse(input, out var output)) throw new ApplicationException($"Not a valid Thingy: {input}");
    Profi-Tipp: Letzteres nicht in einem Kernel-Mode-Treiber tun.

    • Profi-Tipp: Beides nicht tun. Besonders das erste auf keinen Fall.
      Eine explizite Behandlung ist immer besser als ein impliziter Defaultwert, der anstelle eines Werts verwendet wird, den man für richtig hielt, der aber falsch war.
      Was man tun sollte: früh die Hand heben, den Fall als Parsing-Fehler behandeln und den Ablauf sowie das Protokoll für nicht ladbare Dateien sehr klar definieren. Dann stellt man sich automatisch die schwierigen Fragen, die von den beiden Optionen oben nicht behandelt werden.
      Das eigentliche Problem beim jüngsten CrowdStrike-Kernel-Mode-Treiber, der beim Parsen irgendeiner def/config-Datei scheiterte, war, dass Entwickler, Product Owner und Business-Analysten nicht gefragt haben: „Was passiert, wenn versucht wird, eine ungültige Datei zu laden?“
    • Warum nur „ziemlich gut“? Und was hat das mit dem Veröffentlichungsjahr zu tun? Heißt das, der Rat des Artikels wäre maßgeblicher gewesen, wenn er vor 2019 veröffentlicht worden wäre?
    • Ich wünschte, man würde den ersten Ansatz nicht verwenden. Der schlechte Fall muss behandelt werden. Ein Rückfall auf einen „vernünftigen Defaultwert“ sollte äußerst selten sein.
      Explizite Behandlung > implizite Behandlung
    • if(!Whatever.TryParse(input, out var output)) output = some-sane-default;
      Diesen Ansatz mag ich wirklich nicht. Meiner Ansicht nach sollte ein Fehler durch ungültige Eingaben außerhalb der Parsing-Funktion behandelt werden. In F# ist das einfach.
      type Whatever =
      static member create input =
      match input with
      | ValidWhatever x -> Some x
      | _ -> None
      match Whatever.create input with
      | Some x -> // geparste Daten verarbeiten
      | None -> // Fall behandeln, in dem nicht korrekt geparst wurde
      Oder man kann mit Option.map/Option.bind auch eine Pipeline für verkettete Operationen bequemer machen.
      So lassen sich Instanzen nur über die create-Methode erzeugen, die die Eingabe parst.
      In der Praxis wird man vermutlich eher result statt option verwenden wollen, aber das ist hier nur ein Nebenthema.
    • Mir fällt kaum, vielleicht gar kein Szenario ein, in dem ich Code wie if(!Whatever.TryParse(input, out var output)) output = some-sane-default; sehen möchte.
      Wenn eine Eingabe überhaupt nicht angegeben wurde, also ein Parameter optional ist, ergibt ein vernünftiger Defaultwert Sinn.
      Wenn aber eine falsche Eingabe angegeben wurde, sollte man nicht so tun, als sei alles in Ordnung.
      Wenn jemand in einen Blumenladen kommt und nach Kaffee fragt, ist die richtige Antwort nicht, ihm Rosen zu geben. Wenn er versucht, sie zu trinken, zerreißt er sich den Mund.
      Für diese Eingabemenge haben Methode, Modul oder Programm keine definierte Ausgabe. Man sollte das deutlich sichtbar machen, statt stillschweigend etwas Falsches oder Unklares zu tun und das Programm dadurch schnell nicht mehr nachvollziehbar zu machen. Es ist auch für einen selbst besser, das Problem klar auszulösen und einen Stacktrace zu hinterlassen, der direkt zur Problemstelle führt, statt es Monate später als Bug mit merkwürdigem Verhalten auftauchen zu lassen.

  • Der Rat lautet, ein starkes Typsystem zu nutzen, um Fehlerzustände unmöglich darstellbar zu machen. Das ist sehr gut, um Bugs in Software insgesamt zu reduzieren.
    Es kostet mehr Zeit, das Problem gründlicher zu durchdenken und ein solches Design zu entwerfen, aber in vielen Fällen ist diese Zeit es absolut wert.

    • Für Sprachen mit Unterstützung für algebraische Datentypen würde ich sogar kühn behaupten, dass dieser Ansatz nicht mehr Zeit kostet. Es ergibt sich einfach ganz natürlich so.
      Natürlich kostet es mehr Zeit, wenn es sich um Sprachen handelt, die beim Modellieren von Daten viele bewusste Schritte erfordern, wie C++, Java, C#, Python, Go oder JavaScript.

  • „Jetzt habe ich ein kurzes, starkes Motto dafür, was typgetriebenes Design für mich bedeutet, und noch besser: Es sind nur drei Wörter: Parse, don’t validate.“
    Mein Motto wäre eher immer nur in einem einzigen Konstruktor validieren. Eine Konstruktorfunktion ist auch in Ordnung.
    Dann können ungültige Objekte von Anfang an gar nicht existieren, und es gibt immer eine Single Source of Truth. Wenn man ein Objekt ändern möchte, kann man es so implementieren, dass derselbe Konstruktor erneut aufgerufen wird, um einen neuen Zustand zu erzeugen.

    • Das ist nicht dasselbe.
      Der Kernpunkt ist, dass die Information später verschwindet, wenn man nur validiert.
      Wenn man zum Beispiel nur prüft, ob ein bestimmter int positiv ist, ist der Nutzen begrenzt. Denn wenn man diesen Wert nicht als positive ganze Zahl parst, bleibt diese Information später auf Typebene nicht erhalten. Dasselbe gilt für nicht leere Arrays oder Listen: Ein späterer Consumer muss möglicherweise erneut prüfen, ob diese Liste wirklich nicht leer ist.
      Informationen dieser Art lassen sich nicht immer in einem Objekt oder Konstruktor codieren.

  • Verwandtes Material: Richard Feldmans Making Impossible States Impossible
    https://www.youtube.com/watch?v=IcgmSRJHu_8

  • Auch früher gab es schon gute Diskussionen
    https://news.ycombinator.com/item?id=35053118
    https://news.ycombinator.com/item?id=21476261

  • Jedes Mal, wenn dieses Thema aufkommt, muss ich an Abschnitt 5 von https://cr.yp.to/qmail/guarantee.html denken. Dort stehen Sätze wie „Nicht parsen“ und „In der Welt der Computer gibt es zwei Arten von Befehlsschnittstellen: gute Schnittstellen und Benutzerschnittstellen“.
    Wenn ich einen Kurs über Programmierung mittlerer Größe unterrichten würde, nicht über kleine oder große Systeme, würde ich den Studierenden als Aufgabe geben, diese Vorschläge in einem Essay zu vergleichen und gegenüberzustellen. Aus jedem lässt sich etwas lernen, und vielleicht widersprechen sie sich nicht so sehr, wie es auf den ersten Blick scheint.

  • Ich muss an einen Kommentar denken, den ich Mitte der 2000er während des XML-Hypes gesehen habe. Darin hieß es, dass viele Organisationen domänenspezifische Sprachen, einschließlich Konfigurationssprachen, deshalb in XML implementierten, weil XML einen Parser mitbrachte und die meisten Organisationen keinen eigenen Parser schreiben wollten.
    Ich weiß nicht, warum Leute so ungern Parser schreiben. Parser zu schreiben ist nicht so schwer und macht ziemlich viel Spaß.

  • Das ist einer meiner Lieblingstexte, die ich in meiner Laufbahn gelesen habe. Ich habe oft gesehen, dass Leute nur den Titel lesen und annehmen, Parsing und Validierung seien somehow gegenseitig ausschließend, aber in Wirklichkeit ist das nicht so. Parsing beinhaltet oft Validierung.
    Das wird im Abschnitt „Use abstract datatypes to make validators ‘look like’ parsers“ des Artikels behandelt.
    Es gehört in denselben Themenbereich wie die Idee, Primitive Obsession zu vermeiden.