Wie ein Lean-Beweis funktioniert – erklärt für Softwareentwickler

Anatomy of a Lean proof for software engineers

Ein Blogbeitrag zeigt anhand eines Problems aus Sipsers Lehrbuch, wie man in Lean einen formalen Beweis für die Regularität einer Sprache führt. Der Autor baut einen DFA, der die Umkehrung der Sprache erkennt, und nutzt Mathlib, um den Beweis zu vervollständigen. Der Beitrag richtet sich an Entwickler mit Kenntnissen in statisch typisierten Sprachen, binärer Arithmetik und Induktionsbeweisen.

Der schwierige Teil ist, dass wir das mit einer festen Menge an Speicher für beliebig lange Zeichenketten tun müssen.
  1. thom

    Das ist also alles großartig, aber wenn man uns bittet, Lean-Beweise mit über 500.000 Zeilen zu akzeptieren, die zwar geprüft werden, aber leicht schwerwiegende semantische Fehler enthalten könnten, wie sieht dann der Plan aus? Diese scheinen einzigartig fragile Softwareartefakte zu sein, trotz der exzellenten und robusten Versprechungen der Laufzeitumgebung.

  2. WalterGR

    OP: Dein Artikel zeigt „[Contents]“, wo vermutlich das Inhaltsverzeichnis angezeigt werden soll.

  3. fooker

    Bitte versuche nicht, Lean oder Beweisassistenten zu verstehen, ohne zuerst ein grundlegendes Verständnis der zugrunde liegenden Logik zu erlangen. Dieser Artikel überspringt das so ein bisschen, was vernünftig ist, weil es ziemlich komplex ist.

    Selbst wenn du eine große Anzahl mathematischer Beweise geschrieben hast, hast du normalerweise nicht die Sprache oder Logik der Beweise selbst gelernt. Und selbst wenn du ein versierter Informatiker bist, ist Logik nicht nur AND, OR, NOT.

    Hier ist etwas notwendige Lektüre; fühl dich frei, bessere Quellen zu finden, aber Wikipedia ist auch gut.

    * Beweisbäume – https://en.wikipedia.org/wiki/Method_of_analytic_tableaux

    * Konstruktive/Intuitionistische Logik – https://en.wikipedia.org/wiki/Intuitionistic_logic

    * Proofs and Types – https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...

    * (Un)Vollständigkeit – https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...

    * Kompaktheit – https://en.wikipedia.org/wiki/Compactness_theorem

  4. whattheheckheck

    Die Schnittstelle zwischen Spezifikation und Beweis ist nicht so klar, da man oft den Beweis ansehen muss, um die Spezifikation zu verstehen. Und wenn wir etwas Seltsames im Beweis sehen, ist das ein guter Hinweis darauf, dass etwas nicht stimmt.

    Ja, das ist wie wenn ich sage, etwas ist grün – woher weißt du, dass mein Grün dein Grün ist? Der Beweis des mathematisch modellierten Systems ist in keiner Weise an die Symbole gebunden, die es implementieren, es sei denn, es ist dasselbe Programm oder man macht Trace-Refinement. Und dann gibt es keine Möglichkeit zu beweisen, dass das Programm die Geschäftsfunktion korrekt erfüllt, es sei denn, man führt es aus. Ziemlich computational irreducibility, die Zustandsmaschine zum Bauen von Zustandsmaschinen.

  5. woggy

    Ich bin neugierig, ob man Lean primär als Software-Spezifikationssprache verwenden kann, ohne unbedingt alles beweisen zu wollen.

    Können wir es nutzen, um Modulbedeutungen und -gesetze zu spezifizieren, um das Design präzise und überprüfbar zu machen, und es uns ermöglichen, property-basierte Tests für diese Gesetze in unserer Implementierung zu schreiben? Lean wird zu einem Werkzeug für präziseres Denken über das Design.

Mehr von diesem Tag

2026-10-02