Extensionalität von Lambda-Kalkülmodellen

11

Ich übersetze ein Buch über LISP und es berührt natürlich einige Elemente des Kalküls. Daher wird dort neben einigen Modellen des λ- Kalküls ein Begriff der Extensionalität erwähnt , nämlich: P ω und D (ja, mit der Unendlichkeit oben). Und es wird gesagt, dass P ω eine Dehnung ist, während D nicht ist.λλPωDPωD

Aber ... Ich habe den Lambda-Kalkül von Barendregt durchgesehen , es ist Syntax und Semantik , und (hoffentlich richtig) genau das Gegenteil gelesen: ist nicht extensional, D ist.PωD

Kennt jemand dieses seltsame Modell ? Könnte es genau das gleiche Modell wie D ∞ sein , aber falsch geschrieben? Habe ich Recht mit der Erweiterbarkeit der Modelle?DD

Vielen Dank.

Chris
quelle
Würde es Ihnen etwas ausmachen, einen Kontext für das LISP-Buch anzugeben? Hat es Referenzen für die Ergebnisse oder die Modelle, auf die es sich bezieht?
Cody
1
Ja, es ist Christian Queinnecs LISP in kleinen Stücken , p. 153. Der Auszug mit der Erwähnung: [...] Seitdem wurden die Eigenschaften auf verschiedene Weise erweitert, wodurch verschiedene Modelle entstanden: oder P ω in [Sco76, Sto77]. [...] Seltsamerweise ist P ω eine Erweiterung, weil zwei Funktionen, die an jedem Punkt dasselbe berechnen, gleich sind, während D keine Erweiterung ist. [...] Sco76 steht für Dana Scotts ' Datentypen als Gitter . Sto77 steht für Joseph Stoys ' Denotational Semantics: The Scott-Stachey Approach to Programming Language Theory . DPωPωD
Chris
1
Vielen Dank! In diesem Fall ist es wahrscheinlich, dass es einen Tippfehler gab, dass für D ∞ steht und dass P ω nicht dehnbar ist. DDPω
Cody

Antworten:

14

Ich nehme an , dass Sie mit Extensionalität das Gesetz meinen Wenn das istwas meinen Sie dann das Diagramm Modell P ω istnichtextensional, während Dana Scotts D (I presume D ist Dana Scotts Modell des & bgr; & xgr; & eegr; & lgr; Kalkül).

(x.fx=gx)f=g.
PωDDβξηλ

Um dies zu sehen, sei daran erinnert, dass ein algebraisches Gitter mit der Eigenschaft ist, dass sein Raum aus kontinuierlichen Karten [ P ω P ω ] ein geeigneter Rückzug von P ω ist , dh es gibt kontinuierliche Karten Λ : P ω [ P ω P ω ] und Γ : [ P ω P ω ] P ω derart , daß & Lgr; Γ = i d aber ΓPω[PωPω]Pω

Λ:Pω[PωPω]
Γ:[PωPω]Pω
ΛΓ=id . Bei u , v P ω wird die Anwendung u v als Λ ( u ) ( v ) interpretiert. Nun nehmen Sie u und u ' , so dass u u ' aber Λ ( u ) = Λ ( v ) (diese existierenweil & Ggr; Λ i d ). Dannhaben wirfür alle vΓΛidu,vPωuvΛ(u)(v)uuuuΛ(u)=Λ(v)ΓΛidv noch u u ' . Extensionalität wird verletzt.uv=uvuu

[DD]D

Λ:D[DD]
Γ:[DD]D
u,uDuv=uvvDΛ(u)(v)=Λ(u)(v)vDΛ(u)=Λ(u)u=Γ(Λ(u))=Γ(Λ(u))=u

ΓΛ=idΛΓ=idλ

λX.u(X)=Γ(vu(v))
u(X)Xvu(v)λλX.u(X)ΓΛΓ=id
(λX.u(X))w=Λ(Γ(vu(v)))(w)=(vu(v))(w)=u(w)
β
Andrej Bauer
quelle
Vielen Dank. Dann gehe ich davon aus, dass das Buch einen sachlichen Fehler enthält. Dies kann möglich sein, da das Buch selbst eine Übersetzung aus dem Französischen ist und in diesem Absatz des Originalbuchs möglicherweise einige doppelte Negationsshenanigans oder ähnliches enthalten sind. Leider habe ich kein französisches, um es zumindest zu überprüfen.
Chris
Französisch ist irrelevant, Sie haben den Beweis vor Augen.
Andrej Bauer
λ