Beziehung zwischen Russellscher Typentheorie und Typensystemen
12
Ich habe kürzlich festgestellt, dass es eine Beziehung zwischen der Russellschen Typentheorie und Typensystemen gibt, wie sie zB in Haskell zu finden sind. Tatsächlich scheint ein Teil der Notation für Typen in Haskell Vorläufer in der Typentheorie zu haben. Aber meiner Meinung nach war Russell 1908 motiviert, Russells Paradoxon zu umgehen, und ich bin mir nicht sicher, wie das mit Typsystemen in der Informatik zusammenhängt.
Ist Russells Paradoxon in der einen oder anderen Form etwas, über das wir uns Sorgen machen müssten, wenn wir in einer bestimmten Sprache kein gutes Typensystem hätten?
`` Typentheorie "im Sinne von Programmiersprachen und im Sinne von Russell sind eng miteinander verwandt. Tatsächlich zielt das moderne Gebiet der abhängigen Typentheorie darauf ab, konstruktive Grundlagen für die Mathematik zu schaffen. Anders als die Mengenlehre basieren die meisten Untersuchungen auf der Typentheorie Die Mathematik wird mit Proofassistenten wie Coq, NuPRL oder Agda durchgeführt. Daher sind die in diesen Systemen durchgeführten Proofs nicht nur "formalisierbar", sondern auch vollständig formalisiert und maschinell überprüft. Mit Hilfe von Taktiken und anderen Proofautomatisierungstechniken versuchen wir, Beweise mit diesen zu erstellen Systeme "auf hohem Niveau" und ähneln damit informeller Mathematik, aber weil alles überprüft wird, haben wir viel bessere Garantien für die Richtigkeit.
Typen in gewöhnlichen Programmiersprachen sind tendenziell eingeschränkter, aber die Metatheorie ist dieselbe.
Ähnliches wie Russells Paradoxon ist ein Hauptproblem in der Theorie der abhängigen Typen. Insbesondere mit
Type : Type
führt in der Regel zu Widersprüchen. Coq und ähnliche Arbeiten durch Verschachtelung von Universen
Type_0 : Type_1
In Coq sind diese Zahlen jedoch standardmäßig implizit, da sie für den Programmierer normalerweise keine Rolle spielen.
In einigen Systemen (Agda, Idris) wird die Typ-in-Typ-Regel über ein Kompilierungsflag aktiviert. Dies macht die Logik inkonsistent, erleichtert jedoch häufig das explorative Programmieren / Testen.
Sogar in den gängigsten Sprachen zeigt sich gelegentlich Russells Paradoxon. Zum Beispiel ist in Haskell eine Codierung von Russells Paradox möglich, die Impredikativität und Groß- und Kleinschreibung kombiniert, sodass abweichende Terme ohne Rekursion auch auf der Typebene erstellt werden können. Haskell ist "inkonsistent" (wenn es wie gewohnt als Logik interpretiert wird), da es sowohl die Typ- als auch die Wertebenenrekursion unterstützt, ganz zu schweigen von Ausnahmen. Dennoch ist dieses Ergebnis ziemlich interessant.
Vielen Dank für Ihre ausführliche Antwort. Was den Beweis angeht, gibt es immer noch keine Tools, mit denen die Richtigkeit von Programmen in wichtigen Sprachen wie C ++ oder Java überprüft werden kann. Ich würde gerne eine davon in die Hand nehmen ... Mir ist klar, dass dies eine völlige Tangente ist. Ich kenne Coq und Agda, aber sie schienen nicht die richtigen Werkzeuge zu sein, um die Korrektheit von in C ++ oder Java geschriebenen Programmen zu beweisen.
Frank
3
Es gibt einige Werkzeuge. Ein paar für C, viele für Java und Tonnen für Ada. Siehe zum Beispiel: Why (Java, C, Ada), Krakatoa (Java) oder SPARK (Ada-Teilmenge mit sehr guten Werkzeugen). Für C ++ allerdings nicht so sehr. Sie sind vielleicht auch an YNot (Coq DSL) interessiert.
Philip JF
3
Sie haben Recht mit Russells Motivation. Sein Paradoxon plagt alle Mengen-Theorien, die uneingeschränkte Verständnis-Axiome zulassen, dahingehend, dass: jede Satzfunktion eine Menge bestimmt, nämlich die aller Entitäten, die die Funktion erfüllen. Zu den Theorien von oder basierend auf Mengen, die diesen Fehler aufwiesen, gehörten Cantors naive Mengenlehre und Freges System der Grundgesetze (genauer: Axiom 5).
Da Typen als besondere Arten von Mengen betrachtet werden, kann sich ein ähnliches Paradox in ein Typensystem einschleichen, wenn man nicht aufpasst. Allerdings sind mir keine Typensysteme bekannt, die ein solches Schicksal erlitten haben. Ich kann mich nur an die frühen Versuche von Church erinnern, Lambda-Kalkül in den 30er Jahren zu formulieren, der sich als inkonsistent herausstellte (Kleene-Rosser-Paradoxon), aber dieser war weder typbedingt noch mit Russells Paradoxon verwandt.
Update : Eine aktuelle Antwort auf Ihre Frage finden Sie in der Antwort von Philip.
Danke für deine Antwort. Es gibt wahrscheinlich Alternativen zu Typ-a-la-Russell, um Russell-Paradoxon zu vermeiden. Wäre eine dieser alternativen Lösungen interessant, um zu Computersprachen beizutragen? Mundane Typen sind sehr nützlich, um Verträge zwischen Teilen des Codes eindeutig zu spezifizieren und um Programmen überhaupt eine Semantik zu geben. Gibt es eine andere Semantik, die mit etwas anderem als Typen erhalten werden könnte? (Ich habe keine Ahnung, was das sein würde :-)
Frank
1
Ja, viele Alternativen (Quines NF, ZFC usw.), aber ich sehe keinen direkten Zusammenhang zwischen der Grundkrise und den Programmiersprachen. Wenn Sie die Typentheorie von Martin Lof als Programmiersprache betrachten, könnte ein Zusammenhang bestehen, der bis in den Intuitionismus zurückreicht. In Bezug auf die Semantik von Programmiersprachen gibt es einige Basissprachen wie PDL (Propositional Dynamic Logic), die eine Kripke-Semantik (oder eine mögliche Weltensemantik) haben. Aber Typen scheinen mir so grundlegend, dass sie möglicherweise nur hinter den Kulissen stehen :)
Hunan Rostomyan
1
Aber Typen sind ein bisschen blöd: Sie wollen und brauchen sie, aber Sie möchten sie nicht spezifizieren (daher, IMHO, warum wir Typinferenzsysteme in Sprachen wie Haskell oder Ocaml haben (ich liebe diese Sprachen)). Am anderen Ende des Spektrums fühlt sich Python sehr intuitiv an und es ist angenehm (und effizient in Bezug auf die Codierungszeit), sich nicht zu viele Gedanken über Typen in dieser Sprache machen zu müssen. Vielleicht ist die Typinferenz das Beste aus beiden Welten - aber das ist der Ingenieur, der spricht. Ich habe nur geträumt, dass Mathematik ein weiteres wichtiges Konzept (wie Typen) für die Informatik sein könnte :-)
Frank
1
@Frank Jedes Mal, wenn ich eine Sprache ohne statische Typen verwende (meistens Ruby), hasse ich diese Erfahrung, weil ich vermeidbare Laufzeitfehler hasse . Das scheint also meistens Geschmackssache zu sein. Ich bin damit einverstanden, dass leistungsstarke Typinferenz Ihnen das Beste aus beiden Welten bieten kann. Das ist wahrscheinlich der Grund, warum ich Scala so mag.
Raphael
Ich bin nicht davon überzeugt, dass es zu Laufzeitfehlern führt, wenn keine Typen "automatisch" vorhanden sind, wie Sie anscheinend implizieren :-) Ich hatte nie ein Problem in Python.
Frank
3
Da Sie Python erwähnen, ist die Frage nicht rein typentheoretisch. Deshalb versuche ich, eine breitere Perspektive auf Typen zu geben. Typen sind verschiedene Dinge für verschiedene Menschen. Ich habe mindestens 5 verschiedene (aber verwandte) Begriffe von Typen gesammelt:
Typsysteme sind logische Systeme und Mengen- theorien.
Ein Typensystem ordnet jedem berechneten Wert einen Typ zu. Durch Untersuchen des Flusses dieser Werte versucht ein Typensystem zu beweisen oder sicherzustellen, dass keine Typfehler auftreten können.
Typ ist eine Klassifizierung, die einen von verschiedenen Datentypen identifiziert, z. B. reelle Werte, Ganzzahlen oder Boolesche Werte, die die möglichen Werte für diesen Typ bestimmen. die Operationen, die mit Werten dieses Typs durchgeführt werden können; die Bedeutung der Daten; und wie Werte dieses Typs gespeichert werden können
Abstrakte Datentypen ermöglichen die Datenabstraktion in Hochsprachen. ADTs werden häufig als Module implementiert: Die Schnittstelle des Moduls deklariert Prozeduren, die den ADT-Operationen entsprechen. Diese Strategie zum Ausblenden von Informationen ermöglicht es, die Implementierung des Moduls zu ändern, ohne die Client-Programme zu stören.
In Implementierungen von Programmiersprachen werden Wertetypen verwendet, um den für die Werte erforderlichen Speicher und die Algorithmen für Operationen an den Werten auszuwählen.
Die Zitate stammen aus Wikipedia, aber ich kann Ihnen bei Bedarf bessere Referenzen zur Verfügung stellen.
Types-1 entstand aus Russels Werk, schützt aber heute nicht nur vor Paradoxen: Die typisierte Sprache der Homotopietypentheorie ist eine neue Art, Mathematik in einer formalen, maschinenverständlichen Sprache zu kodieren, und eine neue Art, wie Menschen Grundlagen verstehen können der Mathematik. (Der "alte" Weg ist das Codieren mit einer axiomatischen Mengenlehre).
Die Typen 2-5 ergaben sich aus verschiedenen Programmieranforderungen: Um Fehler zu vermeiden, Daten zu klassifizieren, mit denen Softwareentwickler und Programmierer arbeiten, große Systeme zu entwerfen und Programmiersprachen effizient zu implementieren.
Typsysteme in C / C ++, Ada, Java und Python sind nicht aus Russels Arbeit oder dem Wunsch entstanden, Fehler zu vermeiden. Sie entstanden aus der Notwendigkeit heraus, verschiedene Arten von Daten zu beschreiben (z. B. "Nachname ist eine Zeichenfolge und keine Zahl"), das Softwaredesign zu modularisieren und Darstellungen auf niedriger Ebene für Daten optimal auszuwählen. Diese Sprachen haben keine Typen-1 oder Typen-2. Java gewährleistet relative Sicherheit vor Fehlern nicht durch den Nachweis der Programmkorrektheit mithilfe des Typsystems, sondern durch ein sorgfältiges Design von Sprache (keine Zeigerarithmetik) und Laufzeitsystem (virtuelle Maschine, Bytecode-Überprüfung). Typsystem in Java ist weder ein logisches System noch eine Mengenlehre.
Das Typensystem in der Programmiersprache Agda ist jedoch eine moderne Variante von Russels Typensystem (basierend auf späteren Arbeiten oder Per Martin-Lof und anderen Mathematikern). Das Typensystem in Agda wurde entwickelt, um mathematische Eigenschaften von Programmen und Beweise dieser Eigenschaften auszudrücken. Es ist ein logisches System und eine Mengenlehre.
Hier gibt es keinen schwarz-weißen Unterschied: Viele Sprachen passen dazwischen. Zum Beispiel hat das Typensystem der Haskell-Sprache Wurzeln in Russels Arbeit, kann als vereinfachtes Agdas System angesehen werden, aber vom mathematischen Standpunkt aus gesehen ist es inkonsistent (selbst widersprüchlich), wenn es als logisches System oder als Mengenlehre betrachtet wird.
Als theoretisches Mittel, um Haskell-Programme vor Fehlern zu schützen, funktioniert es jedoch recht gut. Sie können sogar Typen verwenden, um bestimmte Eigenschaften und deren Proofs zu codieren. Es können jedoch nicht alle Eigenschaften codiert werden, und der Programmierer kann trotzdem die nachgewiesenen Eigenschaften verletzen, wenn er entmutigte schmutzige Hacks verwendet.
Das Typensystem von Scala ist noch weiter von Russels Werk und Agdas perfekter Beweissprache entfernt, hat aber immer noch Wurzeln in Russels Werk.
Es gibt viele Ansätze und Systeme, um Eigenschaften von Industriesprachen zu beweisen, deren Typsysteme nicht dafür ausgelegt waren.
Informationen zu interessanten, aber unterschiedlichen Ansätzen finden Sie im Coq- und Microsoft Boogie-Forschungsprojekt. Coq stützt sich auf die Typentheorie, um aus Coq-Programmen Imperativprogramme zu generieren. Boogie basiert auf der Annotation von Imperativprogrammen mit Eigenschaften und dem Nachweis dieser Eigenschaften mit dem Z3-Theorembeweiser unter Verwendung eines völlig anderen Ansatzes als Coq.
Sie haben Recht mit Russells Motivation. Sein Paradoxon plagt alle Mengen-Theorien, die uneingeschränkte Verständnis-Axiome zulassen, dahingehend, dass: jede Satzfunktion eine Menge bestimmt, nämlich die aller Entitäten, die die Funktion erfüllen. Zu den Theorien von oder basierend auf Mengen, die diesen Fehler aufwiesen, gehörten Cantors naive Mengenlehre und Freges System der Grundgesetze (genauer: Axiom 5).
Da Typen als besondere Arten von Mengen betrachtet werden, kann sich ein ähnliches Paradox in ein Typensystem einschleichen, wenn man nicht aufpasst. Allerdings sind mir keine Typensysteme bekannt, die ein solches Schicksal erlitten haben. Ich kann mich nur an die frühen Versuche von Church erinnern, Lambda-Kalkül in den 30er Jahren zu formulieren, der sich als inkonsistent herausstellte (Kleene-Rosser-Paradoxon), aber dieser war weder typbedingt noch mit Russells Paradoxon verwandt.
Update : Eine aktuelle Antwort auf Ihre Frage finden Sie in der Antwort von Philip.
quelle
Da Sie Python erwähnen, ist die Frage nicht rein typentheoretisch. Deshalb versuche ich, eine breitere Perspektive auf Typen zu geben. Typen sind verschiedene Dinge für verschiedene Menschen. Ich habe mindestens 5 verschiedene (aber verwandte) Begriffe von Typen gesammelt:
Typsysteme sind logische Systeme und Mengen- theorien.
Ein Typensystem ordnet jedem berechneten Wert einen Typ zu. Durch Untersuchen des Flusses dieser Werte versucht ein Typensystem zu beweisen oder sicherzustellen, dass keine Typfehler auftreten können.
Typ ist eine Klassifizierung, die einen von verschiedenen Datentypen identifiziert, z. B. reelle Werte, Ganzzahlen oder Boolesche Werte, die die möglichen Werte für diesen Typ bestimmen. die Operationen, die mit Werten dieses Typs durchgeführt werden können; die Bedeutung der Daten; und wie Werte dieses Typs gespeichert werden können
Abstrakte Datentypen ermöglichen die Datenabstraktion in Hochsprachen. ADTs werden häufig als Module implementiert: Die Schnittstelle des Moduls deklariert Prozeduren, die den ADT-Operationen entsprechen. Diese Strategie zum Ausblenden von Informationen ermöglicht es, die Implementierung des Moduls zu ändern, ohne die Client-Programme zu stören.
In Implementierungen von Programmiersprachen werden Wertetypen verwendet, um den für die Werte erforderlichen Speicher und die Algorithmen für Operationen an den Werten auszuwählen.
Die Zitate stammen aus Wikipedia, aber ich kann Ihnen bei Bedarf bessere Referenzen zur Verfügung stellen.
Types-1 entstand aus Russels Werk, schützt aber heute nicht nur vor Paradoxen: Die typisierte Sprache der Homotopietypentheorie ist eine neue Art, Mathematik in einer formalen, maschinenverständlichen Sprache zu kodieren, und eine neue Art, wie Menschen Grundlagen verstehen können der Mathematik. (Der "alte" Weg ist das Codieren mit einer axiomatischen Mengenlehre).
Die Typen 2-5 ergaben sich aus verschiedenen Programmieranforderungen: Um Fehler zu vermeiden, Daten zu klassifizieren, mit denen Softwareentwickler und Programmierer arbeiten, große Systeme zu entwerfen und Programmiersprachen effizient zu implementieren.
Typsysteme in C / C ++, Ada, Java und Python sind nicht aus Russels Arbeit oder dem Wunsch entstanden, Fehler zu vermeiden. Sie entstanden aus der Notwendigkeit heraus, verschiedene Arten von Daten zu beschreiben (z. B. "Nachname ist eine Zeichenfolge und keine Zahl"), das Softwaredesign zu modularisieren und Darstellungen auf niedriger Ebene für Daten optimal auszuwählen. Diese Sprachen haben keine Typen-1 oder Typen-2. Java gewährleistet relative Sicherheit vor Fehlern nicht durch den Nachweis der Programmkorrektheit mithilfe des Typsystems, sondern durch ein sorgfältiges Design von Sprache (keine Zeigerarithmetik) und Laufzeitsystem (virtuelle Maschine, Bytecode-Überprüfung). Typsystem in Java ist weder ein logisches System noch eine Mengenlehre.
Das Typensystem in der Programmiersprache Agda ist jedoch eine moderne Variante von Russels Typensystem (basierend auf späteren Arbeiten oder Per Martin-Lof und anderen Mathematikern). Das Typensystem in Agda wurde entwickelt, um mathematische Eigenschaften von Programmen und Beweise dieser Eigenschaften auszudrücken. Es ist ein logisches System und eine Mengenlehre.
Hier gibt es keinen schwarz-weißen Unterschied: Viele Sprachen passen dazwischen. Zum Beispiel hat das Typensystem der Haskell-Sprache Wurzeln in Russels Arbeit, kann als vereinfachtes Agdas System angesehen werden, aber vom mathematischen Standpunkt aus gesehen ist es inkonsistent (selbst widersprüchlich), wenn es als logisches System oder als Mengenlehre betrachtet wird.
Als theoretisches Mittel, um Haskell-Programme vor Fehlern zu schützen, funktioniert es jedoch recht gut. Sie können sogar Typen verwenden, um bestimmte Eigenschaften und deren Proofs zu codieren. Es können jedoch nicht alle Eigenschaften codiert werden, und der Programmierer kann trotzdem die nachgewiesenen Eigenschaften verletzen, wenn er entmutigte schmutzige Hacks verwendet.
Das Typensystem von Scala ist noch weiter von Russels Werk und Agdas perfekter Beweissprache entfernt, hat aber immer noch Wurzeln in Russels Werk.
Es gibt viele Ansätze und Systeme, um Eigenschaften von Industriesprachen zu beweisen, deren Typsysteme nicht dafür ausgelegt waren.
Informationen zu interessanten, aber unterschiedlichen Ansätzen finden Sie im Coq- und Microsoft Boogie-Forschungsprojekt. Coq stützt sich auf die Typentheorie, um aus Coq-Programmen Imperativprogramme zu generieren. Boogie basiert auf der Annotation von Imperativprogrammen mit Eigenschaften und dem Nachweis dieser Eigenschaften mit dem Z3-Theorembeweiser unter Verwendung eines völlig anderen Ansatzes als Coq.
quelle