Lambda Calculus: Bagaimana konteks evaluasi "bekerja"

Dalam kalkulus lambda murni, kita memiliki seperangkat istilah yang didefinisikan secara induktif (tata bahasa):

$$e::= x \mid \lambda x . e \mid e_1 e_2$$

Di bawah strategi evaluasi panggilan-oleh-nilai, kami memiliki aturan inferensi untuk pengurangan beta dan aturan tentang cara mengevaluasi aplikasi (aturan kongruensi). Saya mencoba memahami bagaimana konteks evaluasi dapat menggantikan aturan kongruensi tanpa benar-benar mengubah sintaks bahasa. Tanpa konteks evaluasi, kami memiliki yang berikut:

$$\frac{e_1 \rightarrow e_1'}{e_1e_2 \rightarrow e_1'e_2}$$ dan $$\frac{e_2 \rightarrow e_2'}{ve_2 \rightarrow ve_2'}.$$

Ini masuk akal, karena jika kita memiliki turunan dari ekspresi , jelas bahwa itu adalah dari formulir dan dengan demikian$t = (\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w$$e_1e_2 \rightarrow e_1'e_2$

$$(\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w \rightarrow (\lambda f . \lambda x. f x)(\lambda z .z)\lambda w.w$$

Jika kita mengganti aturan kongruensi dengan konteks evaluasi: maka kita hanya perlu satu aturan untuk mengekspresikan aturan kongruensi bahasa:

$$E::= [\cdot] \mid Ee \mid vE$$ $$\frac{e \rightarrow e'}{E[e] \rightarrow E[e']}.$$

Saya bingung bagaimana konteks evaluasi dapat memberi tahu kami cara mengevaluasi ekspresi $t$ dari atas tanpa mengubah sintaksis bahasa. Saya tidak mengerti bagaimana konteks evaluasi "bekerja" tanpa menulis ulang $t$ as

$$E_t = (\lambda f . \lambda x. f x)[\cdot]\lambda w.w$$

di mana $t = E_t[((\lambda y .y)\lambda z .z)]$ . Tidak ada alasan apriori untuk mengevaluasi $t$ bawah nilai-panggilan tanpa pengetahuan $E_t$ . Saya benar-benar tidak tahu di mana saya salah. Dapatkah seseorang membantu memperbaiki pemikiran saya?

Kehalusannya terletak pada di mana perbedaan antara bahasa dan bahasa logam dibuat. Seperti yang ditulis oleh René Magritte :

$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z)) (\lambda w.w)$ adalah istilah lambda, ditulis dalam sintaks untuk istilah lambda. Sebut saja istilah lambda ini . Biarkan menjadi istilah lambda . Saya dapat menulis (dan ini adalah kesetaraan sejati): semua yang saya lakukan adalah memberi nama pada sebuah subterm. Jika Anda mempertimbangkan sisi kanan persamaan ini “ ”, itu tidak ditulis dalam sintaksis istilah-istilah lambda; itu ditulis dalam notasi matematika di mana kami mengizinkan surat untuk berdiri untuk istilah lambda.$t$$M$$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z))$$t = M \, (\lambda w.w)$$M \, (\lambda w.w)$

Ketika kita menulis aturan seperti ia menyatakan aksioma berikut: untuk istilah lambda dan dan nilai apa saja , jika dikurangi menjadi lalu dikurangi menjadi . Di sini kita kembali menggunakan meta-notasi (yaitu notasi matematis untuk alasan tentang suatu bahasa): panah untuk menyatakan relasi reduksi; metavariables di mana huruf menunjukkan jenis ( untuk istilah lambda,

$$\frac{e_2 \to e_2'}{v \, e_2 \to v \, e_2'}$$ $e_2$$e_2'$$v$$e_2$$e_2'$$v \, e_2$$v \, e_2'$$\to$$e$$v$untuk nilai) dan subskrip dan bilangan prima membedakan metavariabel dengan jenis yang sama; notasi pecahan untuk menulis aksioma induktif.

Ketika kita menulis aturan sekali lagi adalah meta-notasi, bagian dari bahasa logam dan bukan dari lambda sintaks jangka panjang. Aturannya berarti: untuk setiap istilah lambda dan dan setiap konteks evaluasi , jika dikurangi menjadi maka dikurangi menjadi .

$$\frac{e \to e'}{E[e] \to v E[e']}$$ $E[\cdot]$$e$$e'$$E[\cdot]$$e$$e'$$E[e]$$E[e']$

Jika kita memanggil konteks dengan nama (meta-) , maka . Sekali lagi, ini adalah persamaan antara dua istilah lambda, yaitu istilah lambda yang sama ada di kedua sisi dari tanda sama. Apa yang kita miliki di sebelah kiri dan di kanan adalah dua meta-notasi berbeda untuk istilah lambda yang sama : satu yang menggunakan nama yang kami berikan untuk itu, yang lain yang sedikit lebih rumit melibatkan konteks yang kami beri nama.$(\lambda f. \lambda x. f x)[\cdot] (\lambda w.w)$$E_t$$t = E_t[(\lambda y.y)(\lambda z.z)]$$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z)) (\lambda w.w)$

Dengan istilah , bagaimana Anda menemukan cara mengurangi?$t$

• Dengan notasi menggunakan beberapa aturan, Anda harus menemukan pohon deduksi (secara umum - di sini derivasi adalah linier, jadi Anda hanya perlu menemukan rantai yang mengarah pada aksioma).
• Dengan notasi yang menggunakan konteks evaluasi, Anda harus menemukan konteks evaluasi yang sesuai.

Tata bahasa konteks evaluasi mengikuti struktur aturan evaluasi, jadi ini sebenarnya bukan dua metode tetapi dua cara berbeda untuk mengekspresikan definisi yang sama.

Untuk memahami hal ini, saya sangat merekomendasikan latihan berikut: dalam bahasa favorit Anda, terapkan evaluasi nilai-nilai-panggilan-lambda secara langsung, dengan tipe yang mewakili istilah-istilah lambda dan fungsi yang melakukan satu langkah reduksi.