Kalkulus Lambda tampaknya tidak abstrak. Dan saya tidak bisa mengerti intinya

Pertanyaan mendasar:

Apa yang dilakukan kalkulus lambda bagi kita yang tidak dapat kita lakukan dengan properti fungsi dasar dan notasi yang umumnya dipelajari dalam aljabar sekolah menengah?

Pertama-tama, apa artinya abstrak dalam konteks kalkulus lambda? Pemahaman saya tentang kata abstrak adalah sesuatu yang terpisah dari mesin, ringkasan konsep dari suatu konsep.

Namun, fungsi lambda, dengan menghilangkan nama fungsi, mencegah tingkat abstraksi tertentu. Sebagai contoh:

f(x) = x + 2
h(x, y) = x + 5 y

Tetapi bahkan tanpa mendefinisikan mesin dari fungsi-fungsi ini, kita dapat dengan mudah berbicara tentang komposisi mereka. Sebagai contoh:

1. h(x, y) . f(x) . f(x) . h(x, y) or 
2. h . f . f . h

Kita bisa memasukkan argumen jika kita mau, atau kita bisa abstrak sepenuhnya untuk memberikan gambaran tentang apa yang terjadi. Dan kita dapat dengan cepat menguranginya menjadi satu fungsi. Mari kita lihat komposisi 2. Saya dapat memiliki lapisan detail siswa yang dapat saya tulis dengan tergantung pada penekanan saya:

g = h . f . f . h
g(x, y) = h(x, y) . f(x) . f(x) . h(x, y)
g(x, y) = h . f . f . h = x + 10 y + 4

Mari kita lakukan di atas dengan kalkulus lambda, atau setidaknya mendefinisikan fungsi. Saya tidak yakin ini benar, tetapi saya percaya bahwa penambahan ekspresi pertama dan kedua oleh 2.

(λuv.u(u(uv)))(λwyx.y(wyx))x

Dan untuk mengalikannya dengan 5y.

(λz.y(5z))

Alih-alih abstrak, ini tampaknya masuk ke dalam mesin apa artinya menambahkan, memperbanyak, dll. Abstraksi, dalam pikiran saya, berarti tingkat yang lebih tinggi daripada tingkat yang lebih rendah.

Lebih jauh, saya berjuang untuk melihat mengapa kalkulus lambda bahkan merupakan suatu hal. Apa kelebihannya?

(λuv.u(u(uv)))(λwyx.y(wyx))x

lebih

h(x) = x + 5 y

atau notasi gabungan

Hxy.x+5y

atau bahkan notasi Haskell

h x y = x + 5 * y

Sekali lagi, apa yang dilakukan kalkulus lambda untuk kita yang tidak bisa kita lakukan dengan properti fungsi gaya f (x) dan notasi yang banyak dikenal.

Ada banyak alasan mengapa kalkulus lambda sangat penting.

Alasan yang sangat penting adalah kalkulus lambda memungkinkan kita untuk memiliki model perhitungan di mana fungsi yang dapat dihitung adalah warga negara kelas satu.

Seseorang tidak dapat mengekspresikan fungsi tingkat tinggi dalam bahasa aljabar sekolah menengah.

Ambil contoh ungkapan lambda

Ungkapan sederhana ini menunjukkan kepada kita bahwa, dalam kalkulus lambda, komposisi fungsi itu sendiri adalah fungsi. Dalam aljabar sekolah menengah, ini tidak mudah diungkapkan.

Dalam kalkulus lambda, sangat mudah untuk menyatakan bahwa suatu fungsi akan mengembalikan fungsi sebagai hasilnya.

Ini adalah contoh kecil. Ekspresi (di mana saya di sini mengasumsikan kalkulus lambda yang diterapkan dengan konstanta penambahan dan integer)

akan berkurang menjadi

Perhatikan juga bahwa dalam kalkulus lambda, fungsi adalah ekspresi dan bukan definisi bentuk . Ini membebaskan kita dari kebutuhan untuk menamai fungsi dan untuk membedakan antara kategori ekspresi sintaksis dan kategori definisi sintaksis.$f(x) = e$

Juga, ketika menjadi tidak mungkin (atau hanya tidak praktis) untuk mengekspresikan fungsi tingkat tinggi, orang juga akan mengalami masalah dengan menetapkan tipe ke ekspresi.

Komposisi fungsi memiliki tipe polimorfik

dalam sistem jenis Hindley-Milner.

Nilai jual yang sangat kuat untuk kalkulus lambda adalah tepatnya gagasan kalkulus lambda yang diketik . Berbagai jenis sistem untuk bahasa pemrograman fungsional seperti Haskell dan keluarga ML didasarkan pada sistem tipe untuk kalkulus lambda, dan sistem tipe ini memberikan jaminan kuat dalam bentuk teorema matematika:

Jika suatu program diketik dengan baik dan e mengurangi ke residu e ′ , maka e ′ juga akan diketik dengan baik.$e$$e$$e'$$e'$

Dan jika diketik dengan baik, maka e tidak akan menunjukkan kesalahan tertentu.$e$$e$

The bukti sebagai program korespondensi sangat penting. Isomorfisme Curry-Howard (lihat misalnya https://www.rocq.inria.fr/semdoc/Presentations/20150217_PierreMariePedrot.pdf ) menunjukkan bahwa ada korespondensi yang sangat tepat antara kalkulus lambda yang diketik sederhana dan logika proposisi intuitionistic: Untuk setiap jenis sesuai formula logis φ T . Bukti ϕ T sesuai dengan istilah lambda dengan tipe T , dan pengurangan beta dari istilah ini terkait dengan melakukan eliminasi pemotongan dalam bukti.$T$$\phi_T$$\phi_T$$T$

Saya mendesak mereka yang merasa bahwa aljabar sekolah menengah adalah alternatif yang baik untuk kalkulus lambda untuk mengembangkan akun aljabar sekolah menengah yang diketik secara polimorfik bersama-sama dengan gagasan isomorfisma Curry-Howard yang sesuai. Jika Anda bahkan dapat menemukan asisten bukti interaktif berdasarkan aljabar sekolah menengah yang akan memungkinkan kami untuk membuktikan banyak teorema yang telah diformalkan menggunakan asisten bukti berbasis kalkulus lambda seperti Coq dan Isabelle, itu akan lebih baik. Saya kemudian akan mulai menggunakan aljabar sekolah menengah, dan jadi, saya yakin, akan banyak orang lain yang bersama saya.

Ketika fungsi pertama kali dijelaskan kepada anak-anak, mereka pada dasarnya diidentifikasi dengan grafik (plot), atau mungkin dengan rumus; ini adalah cara fungsi dipahami secara historis sebelum munculnya tren formalis dalam matematika. Saat ini fungsi, seperti yang diajarkan dalam kalkulus tahun pertama, adalah fungsi nyata, yaitu, fungsi dari ke R .$\mathbb{R}$$\mathbb{R}$

Fungsi dalam kalkulus lambda jauh lebih umum. Definisi yang tepat tergantung pada apakah kalkulus lambda Anda diketik atau tidak. Dalam kalkulus lambda murni yang belum diketik semuanya adalah fungsi. Ini jauh lebih umum daripada fungsi kalkulus yang sebenarnya.

Bahkan bahasa prosedural kadang-kadang menggunakan ide dari lambda calculus. Fungsi pengurutan dalam C menerima sebagai parameter fungsi perbandingan , yang digunakannya untuk membandingkan elemen. Kalkulus Lambda melangkah lebih jauh - fungsi tidak hanya menerima fungsi sebagai input, tetapi juga dapat menampilkannya.

Kalkulus Lambda adalah model komputasi yang setara dalam daya untuk mesin Turing. Ini adalah sistem yang lengkap untuk dirinya sendiri. Kalkulus lambda murni tidak memiliki "5" atau "+" sebagai istilah primitif - mereka dapat didefinisikan di dalam kalkulus, seperti "5" dan "+" bukan primitif dari teori himpunan. (Bahasa pemrograman praktis menerapkan bilangan asli secara alami karena alasan efisiensi.)

Saya menduga bahwa salah satu alasan mengapa Anda tidak terkesan dengan kalkulus lambda adalah bahwa idenya telah begitu menyebar dalam wacana pemrograman sehingga tidak lagi terlihat inovatif.

$x^2$$x$$x^2$

$\lambda x.x^2$$x^2$

$f$$f(x) = x^2$$f$

Penggunaan ekspresi lambda dalam bahasa pemrograman memiliki keunggulan yang sama; Anda dapat menulis apa fungsi tidak di sana di mana itu diperlukan daripada harus mendefinisikan fungsi baru di tempat lain dalam program Anda.

$\frac{d}{dx} x^2$$\frac{d}{dx}$$x^2$

$\theta : V \to V^{**}$

Banyak orang menganggap notasi evaluasi ganda ini membingungkan dan / atau meresahkan, juga penggunaan definisi fungsi secara langsung. Versi abstraksi lambda

tidak memiliki masalah itu.

Akhirnya, ada teorema abstrak omong kosong bahwa "cukup ketik lambda kalkulus" pada dasarnya adalah hal yang sama dengan "kategori tertutup cartesian" - jadi jika Anda pernah ingin melakukan perhitungan dalam kategori tertutup kartesius, mungkin ide yang baik untuk digunakan cukup ketik lambda kalkulus untuk melakukannya.

Saya akan mengatakan di muka saya bukan ahli dalam topik ini, tapi saya hanya menghabiskan sedikit waktu mempelajarinya dan salah satu hal yang paling menarik bagi saya dalam topik apa pun adalah sejarah di baliknya. Jadi bagi saya memahami sedikit sejarah di balik kalkulus lambda membantu menjelaskan mengapa ini berguna.

Ringkasan singkatnya adalah bahwa pada awal 1900-an setelah teori himpunan mulai lepas landas dan matematika direvisi berdasarkan pada himpunan, beberapa matematikawan memperhatikan bahwa sementara definisi himpunan teori memungkinkan Anda untuk mengklaim bahwa ada struktur tertentu, mereka tidak memberi tahu Anda bagaimana untuk membangun dan menghitungnya. Jadi definisi set-theoretik tidak konstruktif . Matematikawan mulai bertanya-tanya apakah ada cara untuk mengembangkan definisi konstruktif yang akan melampaui membuktikan bahwa sesuatu itu dan bukannya membuktikan bagaimana itu .

Dari Wikipedia :

Dalam matematika, bukti konstruktif adalah metode bukti yang menunjukkan keberadaan objek matematika dengan membuat atau menyediakan metode untuk membuat objek. Ini berbeda dengan bukti non-konstruktif (juga dikenal sebagai bukti keberadaan atau teorema keberadaan murni) yang membuktikan keberadaan jenis objek tertentu tanpa memberikan contoh.

$*$

Kemudian ditunjukkan bahwa kalkulus lambda dan mesin Turing dapat mewakili fungsi yang dapat dihitung dan karenanya setara.

Dalam teori setiap fungsi matematika atau konsep dapat dikodekan dalam lambda bentuk kalkulus dan dihitung. Ini berarti bahwa kalkulus lambda dapat menjadi dasar yang sepenuhnya terpisah untuk matematika, meskipun jelas yang sangat membosankan.

Kalkulus Lambda tidak "berguna" dalam arti bahwa Anda tidak akan menulis kode menggunakannya, tetapi itu membentuk dasar untuk semantik denotasional yang digunakan untuk menggambarkan program dan efek dinamisnya. Ini digunakan dalam diskusi tentang kebenaran program dan makna semantik. Ini juga jelas sangat mempengaruhi pengembangan bahasa pemrograman fungsional, yang menarik seluruh konsep eksekusi dari kalkulus lambda.

Semoga itu bisa membantu.

Sunting untuk ditambahkan: Saya baru saja menunjuk ke makalah ini yang menunjukkan hubungan antara topologi, kalkulus lambda, dan fisika. Melintas sebentar, saya menemukan pernyataan yang fantastis ini:

Sementara mesin Turing dapat dilihat sebagai model perangkat keras komputer yang ideal dan disederhanakan , kalkulus lambda lebih seperti model perangkat lunak sederhana . ... Secara puitis, kalkulus lambda menggambarkan alam semesta di mana segala sesuatu adalah sebuah program dan semuanya adalah data: program adalah data .

Intinya adalah bahwa kalkulus lambda adalah model perhitungan perangkat lunak yang ideal , dan karena itu tidak terikat pada implementasi tertentu dalam bahasa pemrograman apa pun. Ini model perhitungan murni .

$\lambda$

Kalkulus Lambda tidak dirancang untuk menjadi bahasa pemrograman. Memang, itu dibuat pada 1930-an, dekade sebelum kita bahkan memiliki komputer yang dapat diprogram. Alih-alih, itu dibuat sebagai model formal untuk mempelajari komputasi, itu sendiri. Jika Anda kecewa dengan betapa mudahnya mengekspresikan kode, atau fungsi matematika, itu karena bukan itu gunanya.

Kalkulus Lambda ada sehingga fungsi anonim (alias lambda) dapat dibuat. Jika Anda tidak menghilangkan nama fungsi, maka namespace bisa berantakan dan orang bisa kehabisan nama fungsi yang tersedia. Ini sangat penting ketika berhadapan dengan apa yang disebut "fungsi tingkat tinggi" yang mengembalikan fungsi (atau fungsi pointer) karena alasan yang jelas.

Pada dasarnya, fungsi lambda setara dengan variabel cakupan lokal. Pemrograman fungsional tanpa fungsi lambda analog dengan pemrograman prosedural tanpa variabel lokal, yaitu, ide yang mengerikan.

"mengapa kalkulus lambda bahkan adalah sesuatu" ahli matematika suka redundansi. kalkulus lambda jarang digunakan dalam matematika karena ketika Anda telah menemukan notasi tidak terlalu berguna.

"Jika Anda bahkan dapat mengerjakan asisten bukti interaktif berdasarkan aljabar sekolah menengah yang akan memungkinkan kami untuk membuktikan banyak teorema yang telah diformalkan menggunakan asisten bukti berbasis kalkulus lambda seperti Coq dan Isabelle, itu akan lebih baik. Saya akan kemudian mulai menggunakan aljabar sekolah menengah, dan karenanya, saya yakin, akan banyak orang lain yang ikut dengan saya. " Pernahkah Anda mendengar tentang metamath? Tidak ada kalkulus lambda yang terlibat di sana, dapat membuktikan banyak teorema coq / isabelle