Klassifikation typisierter / untypisierter Lambda-Kalküle

18

Kann jemand kurz erklären (wenn das möglich ist!) Oder mich auf eine Referenz verweisen, in der die Unterschiede zwischen untypisiertem Lambda-Kalkül und den gebräuchlicheren typisierten Lambda-Kalkülen zusammengefasst sind?

Ich suche insbesondere nach Aussagen über ihre Ausdruckskraft, Äquivalenzen zu logischen / arithmetischen Systemen oder Berechnungsmethoden und Analogien zu Programmiersprachen, falls zutreffend.

Während ich sicherlich vorhabe zu lesen, wäre so etwas wie eine Referenztabelle, in der die Kalküle und ihre Äquivalenzen / Unterschiede / Stellen in der Hierarchie aufgeführt sind, eine RIESIGE Referenz, um mich beim Aussortieren zu unterstützen.

Nicht zu sagen, dass das Folgende richtig ist, sondern nur zu versuchen, einige der Eindrücke zusammenzufassen, die ich sehen muss, um zu sehen, ob sie zumindest als Ausgangspunkt dienen (oder etwas, das korrigiert werden muss!).

Untypisierte Lambda-Rechnung - Gl. Logik erster Ordnung - kann nicht X tun

Einfach getippte Lambda-Rechnung - Gl. Zu ... Logik, verwandt mit Lisp?

'Polymorphes' Lambda Calc - usw.

Konstruktionsrechnung - intutionistische Logik?

Combinatory Logic - vergleichbar mit ??? typisierte Lambda-Rechnung, bezogen auf APL / J-Sprachen

Wenn dies mit dem Lambda-Würfel und seinen drei Achsen verbunden ist, umso besser.

Während ich mit den Grundlagen der Lambda-Berechnung und der Programmierung mit funktionalen Sprachen vertraut bin, habe ich mich noch nie mit den beteiligten Typsystemen und den verschiedenen Geschmacksrichtungen von Lambda (und möglicherweise pi?) - Kalkül beschäftigt oder signifikante Verbindungen zu diesen hergestellt.

Wenn ich versuche, dies zu recherchieren, kann ich nicht anders, als abgelenkt zu sein, viele Browser-Registerkarten zu öffnen und in so viele Richtungen zu verzweigen, dass ich nie in eine von ihnen mit irgendeiner Tiefe komme!

Ich bin mir nicht sicher, ob das, wonach ich frage, vernünftig ist, aber hoffentlich habe ich zumindest genug von einem Bild gemalt, um eine Lektüre vorzuschlagen, die erklären kann, wonach ich suche?

jon_darkstar
quelle
1
wenn auch vielleicht mit Bezug auf sie kann eine Visualisierung von Lambda - Würfel, Hilfe bei der Erklärung rbjones.com/rbjpub/logic/cl/tlc001.htm
jon_darkstar
3
Eine persönliche Geschichte: Als ich zum ersten Mal typisierte und untypisierte Lambda-Kalküle lernte, war ich immer verwirrt darüber, warum ich mich für die typisierten nicht-Turing-vollständigen Kalküle interessieren sollte. Dadurch verlor ich oft das Interesse. Andererseits hat mich das nie gestört, wenn ich über Komplexität und effiziente Berechnung nachdachte. Irgendwann hat jemand in dieser Antwort die beiden Stränge für mich verbunden , und jetzt kann ich besser verstehen, warum so viel Zeit darauf verwendet wurde, mir typisierte Lambda-Berechnungen beizubringen.
Artem Kaznatcheev
Ich sehe, dass ein lo.logicTag hinzugefügt wurde. wahrscheinlich eine blöde frage, aber wofür genau steht das?
jon_darkstar
"Wenn ich versuche, dies zu recherchieren, kann ich nicht anders, als abgelenkt zu sein, viele Browser-Registerkarten zu öffnen und in so viele Richtungen zu verzweigen, dass ich nie in eine von ihnen mit irgendeiner Tiefe komme!" <- Das bin ich die ganze Zeit! Vielen Dank für die Frage , was ich habe nachgedacht ...
agam

Antworten:

26

Ihr Tisch ist ein bisschen verwirrt; Hier ist eine bessere.

  • Untypisierte Lambda-Rechnung - keine logische Interpretation, wie Andrej bemerkt
  • Einfach getippte Lambda-Rechnung - intuitionistische Aussagenlogik
  • Polymorpher Lambda-Kalkül - reine Logik zweiter Ordnung (dh ohne Quantifizierer erster Ordnung)
  • Abhängige Typen - Verallgemeinerung der Logik erster Ordnung
  • Konstruktionsrechnung - Verallgemeinerung der Logik höherer Ordnung

Die Typabhängigkeit ist allgemeiner als die Quantifizierung erster Ordnung, da Beweise in Objekte umgewandelt werden, über die Sie quantifizieren können. Es gibt Lambda-Kalküle, die einer gewöhnlichen intuitionistischen FOL entsprechen, die jedoch nicht häufig genug verwendet werden, um einen bestimmten Namen zu erhalten. Die Menschen tendieren dazu, direkt zu abhängigen Typen zu wechseln.

Sie können die syntaktische Form eines Kalküls auch auf logische Systeme beziehen.

  • Kombinatorsteine ​​(z. B. SKI-Kombinatoren) - Hilbert-artige Systeme
  • A-Normalform - Folgerechnung
  • Gewöhnlicher typisierter Lambda-Kalkül - natürlicher Abzug
Neel Krishnaswami
quelle
Fantastisch! Vielen Dank. hilft mir, die Motivation / Unterscheidung für diese verschiedenen Kalküle zu erkennen und wird mir sicherlich helfen, ein
grundlegendes
Ich würde auch typisierte Lambda-Kalküle ohne logische Interpretation wie PCF einbeziehen. Es gibt auch viele coole Lambda-Kalküle, die einer anderen Logik entsprechen, wie zum Beispiel der linearen Lambda-Kalküle.
Sam Tobin-Hochstadt
@Sam: Guter Punkt. "Keine logische Interpretation" ist wirklich zu stark, da es wirklich "uneingeschränkte Selbstreferenz erlaubt" bedeutet, was in Kombination mit variabler Wiederverwendung zu Inkonsistenz führt. Einige auf linearer Logik basierende Mengen-Theorien unterstützen jedoch naive Verständnisschemata ohne Inkonsistenz.
Neel Krishnaswami
Auf einige Arten können Sie dem Lambda-Kalkül einige Dinge hinzufügen, ohne inkonsistent zu sein. Aber es gibt viele interessante, typisierte Lambda-Kalküle ohne logische Interpretation genau im Sinne der untypisierten Lambda-Kalküle.
Sam Tobin-Hochstadt
20

Reiner untypisierter Kalkül ist Turing-vollständig, dh eine partiell zahlentheoretische Abbildung ist nur dann berechenbar, wenn sie im untypisierten Kalkül definierbar ist. Die Rechenleistung von typisiertem Kalkül ist viel geringer. Wenn wir beispielsweise dem typisierten Kalkül eine Art natürlicher Zahlen zusammen mit , Nachfolger und primitiver Rekursion hinzufügen , erhalten wir das, was allgemein als Gödels . Es werden nur die primitiven rekursiven Funktionen berechnet (und alle sind total).λ λ λ 0 Tλλλnatλ0T

Der untypisierte Kalkulus hat nach der Curry-Howard-Entsprechung keine vernünftige Interpretation, während der typisierte Kalkulus genau dem intuitionistischen Aussagenkalkül entspricht.λλλ

Modelle des typisierten Kalkulus sind genau die kartesisch geschlossenen Kategorien. Modelle des untypisierten Kalküls verhalten sich weniger gut. Es ist zwar möglich, über sie zu sprechen, aber sie werden sicherlich nicht so umfassend untersucht wie kartesisch abgeschlossene Kategorien.λλλ

Wir können uns auch unterhalten, indem wir fragen: "Was ist allgemeiner?" Auf den ersten Blick scheint der untypisierte Kalkül allgemeiner zu sein, da es einfach ist, den typisierten in den untypisierten einzubetten (indem man die Typen vergisst). Wir können aber den untypisierten Kalkulus in den typisierten Kalkulus einbetten, indem wir einen primitiven Typ zusammen mit Isomorphismen und setzen . Auf der semantischen Seite entspricht dies Dana Scotts Beobachtung, dass jedes Modell des untypisierten Kalküls als reflexives Objekt in einer kartesischen geschlossenen Kategorie auftritt, dh wenn ein Modell des untypisierten Kalküls gegeben ist, das wir können finde eine Kategorieλ λ λ U λ C U U [ C o p , S e t ] UU UλλλUlambda : U -> (U -> U)gamma : (U -> U) -> UλUλC(Wenn mein Gedächtnis mir recht tut , ist es die idempotente Aufteilung von ), so dass als Objekt der Präkollektivkategorie (über Yoneda-Einbettung), wobei die Gleichung erfüllt wird .UU[Cop,Set]UUU

Verweise:

Andrej Bauer
quelle