“Urutan aplikatif” dan “Urutan normal” di lambda-calculus

Urutan yang berlaku: Selalu sepenuhnya mengevaluasi argumen dari suatu fungsi sebelum mengevaluasi fungsi itu sendiri, seperti -

$(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x. x^2(2+1))\rightarrow \ (\lambda x. x^2(3)) \rightarrow \ 3^2 \ \rightarrow \ 9$

Urutan normal: Ekspresi akan dikurangi dari luar, seperti -

$(\lambda x.x^2 (\lambda x.(x+1) \ 2)) \rightarrow \ (\lambda x.(x+1) \ \ \ 2)^ 2 \rightarrow\ (2+1)^2 \ \rightarrow 3^2 \ \rightarrow \ 9$

Misalkan $M = (\lambda x.y \ (\lambda x.(x \ \ x) \ \lambda x.(x \ \ x)))$

Mengapa dengan urutan aplikatif, loop tak terbatas, tetapi dalam urutan normal, M → y ?$M \rightarrow$
$M \rightarrow y$

adalah loop tak terhingga karena λ x . ( x x ) λ x . ( x x ) → λ x . ( x x ) λ x . ( x x ) Perhatikan bahwa λ x . ( $(\lambda x.y \ (\lambda x.(x \ \ x) \ \lambda x.(x \ \ x)))$

Istilah yang Anda kurangi adalah mana K y adalah fungsi konstan λ x . y (selalu mengembalikan y , mengabaikan argumennya) dan Ω = ( λ x . ( $(K_y \Omega)$$K_y$$\lambda x. y$$y$ adalah istilah yang tidak berakhir. Dalam beberapa hal Ω adalah istilah non-terminasi terakhir: ini beta-reduksi ke dirinya sendiri, yaitu Ω → Ω . (Pastikan untuk mengerjakannya di atas kertas setidaknya satu kali dalam hidup Anda.)$\Omega = (\lambda x. (x \, x) \: \lambda x. (x \, x))$$\Omega$$\Omega \to \Omega$

Pengurangan order yang berlaku harus mengurangi argumen fungsi ke bentuk normal, sebelum dapat mengevaluasi redex tingkat atas. Karena argumen tidak memiliki bentuk normal, pengurangan urutan aplikatif tidak terbatas. Secara umum, untuk istilah M , M Ω → M Ω , dan ini adalah pengurangan yang dipilih oleh strategi urutan aplikatif.$\Omega$$M$$M \Omega \to M \Omega$

Reduksi urutan normal dimulai dengan mengurangi redex tingkat atas (karena fungsi sudah dalam bentuk normal). Karena K y mengabaikan argumennya, ( K y Ω ) → y dalam satu langkah. Secara umum, K y N → y untuk istilah N apa pun , dan ini adalah pengurangan yang dipilih oleh strategi urutan normal.$K_y$$K_y$$(K_y \Omega) \to y$$K_y N \to y$$N$

Kasus ini menggambarkan fenomena yang lebih umum: pengurangan pesanan yang aplikatif hanya pernah menemukan bentuk normal jika istilah tersebut sangat normal, sedangkan pengurangan urutan normal selalu menemukan bentuk normal jika ada. Ini terjadi karena urutan aplikatif selalu mengevaluasi argumen sepenuhnya terlebih dahulu, dan karena itu melewatkan kesempatan untuk argumen yang ternyata tidak digunakan; sedangkan urutan normal mengevaluasi argumen selambat mungkin, dan selalu menang jika argumen ternyata tidak digunakan.

(Sisi sebaliknya adalah bahwa urutan aplikatif cenderung lebih cepat dalam praktik, karena relatif jarang argumen tidak digunakan; sedangkan argumen umum digunakan beberapa kali, dan di bawah urutan aplikatif argumen hanya dievaluasi satu kali. Normal order mengevaluasi argumen sesering yang digunakan, baik 0, 1 atau berkali-kali.)