Ekstensionalitas model kalkulus lambda

Saya menerjemahkan buku tentang LISP dan secara alami menyentuh beberapa elemen -kalkulus. Jadi, gagasan ekstensionalitas disebutkan di sana bersama beberapa model kalkulus, yaitu: dan (ya, dengan tak terhingga di atas). Dan dikatakan bahwa adalah ekstensional sedangkan tidak. $\lambda$ $\lambda$ $\mathcal{P}_\omega$ $D^\infty$ $\mathcal{P}_\omega$ $D^\infty$

Tapi ... saya melihat melalui Kalkulus Lambda Barendregt , Ini Sintaks dan Semantik , dan (mudah-mudahan, dengan benar) membaca di sana persis sebaliknya: tidak ekstensional, adalah. $\mathcal{P}_\omega$ $D_\infty$

Apakah ada yang tahu tentang model aneh ? Mungkinkah itu hanya model yang sama dengan , tetapi ditulis secara keliru? Apakah saya benar tentang ekstensionalitas model? $D^\infty$ $D_\infty$

Terima kasih.

lo.logic lambda-calculus formal-modeling extensionality Chris
sumber

Maukah Anda memberikan konteks untuk buku LISP? Apakah ada referensi untuk hasil atau model yang dirujuk?

cody

Ya, ini LISP Christian Queinnec di Small Pieces , hlm. 153. Kutipan dengan menyebutkan: [...] Sejak itu, properti telah diperluas dalam beberapa cara berbeda, menghasilkan beberapa model yang berbeda:

atau

dalam [Sco76, Sto77]. [...] Anehnya,

bersifat ekstensional karena dua fungsi yang menghitung hal yang sama di setiap titik adalah sama, sedangkan

tidak ekstensional. [...] Sco76 adalah singkatan dari Jenis Data Dana Scotts sebagai Kisi . Sto77 adalah singkatan dari Denantational Semantics Joseph Stoys : The Scott-Stachey Approach to Programming Language Theory .

D^{\infty}

$D^\infty$

P_{ω}

$P_\omega$

P_{ω}

$P_\omega$

D^{\infty}

$D^\infty$

Chris

Terima kasih! Dalam hal ini kemungkinan ada kesalahan ketik, bahwa

adalah singkatan dari

dan bahwa itu adalah

yang tidak ekstensional.

D^{\infty}

$D^\infty$

D_{\infty}

$D_\infty$

P_{ω}

$P_\omega$

cody

Jawaban:

Saya berasumsi bahwa secara ekstensionalitas yang Anda maksud adalah hukum Jika ini adalah apa yang Anda maksud maka model grafik adalahtidakekstensional, sementara Dana Scott adalah (saya nyana model Dana Scott dari kalkulus).

(\forall x . f x = g x) ⟹ f = g .

$(\forall x . f x = g x) \implies f = g.$

P ω

$\mathcal{P}\omega$

D_{\infty}

$D_\infty$

D^{\infty}

$D^\infty$

β ξ η λ

$\beta\xi\eta\lambda$

Untuk melihat ini, ingat bahwa adalah kisi aljabar dengan properti bahwa ruang peta kontinu adalah penarikan yang tepat dari , yaitu, ada peta kontinu dan sedemikian rupa sehingga tetapi $\mathcal{P}\omega$ $[\mathcal{P}\omega \to \mathcal{P}\omega]$ $\mathcal{P}\omega$

Λ : P ω \to [P ω \to P ω]

$\Lambda : \mathcal{P}\omega \to [\mathcal{P}\omega \to \mathcal{P}\omega]$

Γ : [P ω \to P ω] \to P ω

$\Gamma : [\mathcal{P}\omega \to \mathcal{P}\omega] \to \mathcal{P}\omega$

Λ \circ Γ = i d

$\Lambda \circ \Gamma = \mathrm{id}$

. Diberikan

, aplikasi

ditafsirkan sebagai

. Sekarang mengambil

dan

sehingga

tapi

(yang ada ini karena

). Kemudian untuk semua

kita memiliki

Γ \circ Λ \neq i d

$\Gamma \circ \Lambda \neq \mathrm{id}$

u, v \in P ω

$u, v \in \mathcal{P}\omega$

u v

$u v$

Λ (u) (v)

$\Lambda(u)(v)$

u

$u$

u^{'}

$u'$

u \neq u^{'}

$u \neq u'$

Λ (u) = Λ (v)

$\Lambda(u) = \Lambda(v)$

Γ \circ Λ \neq i d

$\Gamma \circ \Lambda \neq \mathrm{id}$

v

$v$

belum

. Ekstensionalitas dilanggar.

u v = u v^{'}

$u v = u v'$

u \neq u^{'}

$u \neq u'$

$[D_\infty \to D_\infty]$ $D_\infty$

Λ : D_{\infty} \to [D_{\infty} \to D_{\infty}]

$\Lambda : D_\infty \to [D_\infty \to D_\infty]$

Γ : [D_{\infty} \to D_{\infty}] \to D_{\infty}

$\Gamma : [D_\infty \to D_\infty] \to D_\infty$

u, u^{'} \in D_{\infty}

$u, u' \in D_\infty$

u v = u^{'} v

$u v = u' v$

v \in D_{\infty}

$v \in D_\infty$

Λ (u) (v) = Λ (u^{'}) (v)

$\Lambda(u)(v) = \Lambda(u')(v)$

v \in D_{\infty}

$v \in D_\infty$

Λ (u) = Λ (u^{'})

$\Lambda(u) = \Lambda(u')$

u = Γ (Λ (u)) = Γ (Λ (u^{'})) = u^{'}

$u = \Gamma(\Lambda(u)) = \Gamma(\Lambda(u')) = u'$

$\Gamma \circ \Lambda = \mathrm{id}$ $\Lambda \circ \Gamma = \mathrm{id}$ $\lambda$

λ X . u (X) = Γ (v \mapsto u (v))

$\lambda X. u(X) = \Gamma (v \mapsto u(v))$

u (X)

$u(X)$

X

$X$

v

$v$

u (v)

$u(v)$

λ

$\lambda$

λ X . u (X)

$\lambda X . u(X)$

Γ

$\Gamma$

Λ \circ Γ = i d

$\Lambda \circ \Gamma = \mathrm{id}$

(λ X . u (X)) w = Λ (Γ (v \mapsto u (v))) (w) = (v \mapsto u (v)) (w) = u (w)

$(\lambda X . u(X)) w = \Lambda (\Gamma (v \mapsto u(v))) (w) = (v \mapsto u(v))(w) = u(w)$

β

$\beta$

Andrej Bauer
sumber

Terima kasih banyak. Jadi saya akan berasumsi bahwa ada kesalahan faktual dalam buku ini. Itu mungkin, karena buku itu sendiri adalah terjemahan dari bahasa Prancis, dan mungkin ada beberapa penghinaan ganda dalam paragraf buku aslinya, atau semacamnya. Sayangnya, saya tidak punya yang Prancis setidaknya mencoba untuk memeriksa.

Chris

Bahasa Prancis tidak relevan, Anda memiliki bukti di depan mata Anda.

Andrej Bauer

λ

$\lambda$