Apakah Lambda Calculus murni sintaksis?

29

Saya telah membaca selama beberapa minggu tentang Kalkulus Lambda, tetapi saya belum melihat sesuatu yang secara material berbeda dari fungsi matematika yang ada, dan saya ingin tahu apakah itu hanya masalah notasi, atau apakah ada yang baru properti atau aturan yang dibuat oleh aksioma kalkulus lambda yang tidak berlaku untuk setiap fungsi matematika. Jadi, misalnya, saya pernah baca itu:

"Mungkin ada fungsi anonim" : Fungsi Lambda bukan anonim, semuanya hanya disebut lambda. Diijinkan dalam notasi matematika untuk menggunakan variabel yang sama untuk fungsi yang berbeda jika namanya tidak penting. Misalnya, dua fungsi dalam Koneksi Galois sering keduanya disebut *.

"Fungsi dapat menerima fungsi sebagai input" : Bukan hal baru yang dapat Anda lakukan dengan fungsi biasa.

"Functions is black box" : Hanya input dan output juga deskripsi yang valid dari fungsi matematika ...

Ini mungkin tampak seperti diskusi atau pertanyaan yang dikemukakan tetapi saya percaya bahwa harus ada jawaban yang "benar" untuk pertanyaan ini. Saya ingin tahu apakah kalkulus lambda hanya notasi, atau konvensi sintaksis untuk bekerja dengan fungsi matematika, atau apakah ada perbedaan substansial atau semantik antara lambda dan fungsi biasa.

Neil
sumber
2
Saya tidak ingin membuat jawaban penuh darinya, tetapi fungsi tidak dapat menerima fungsi sebagai input. Saya dapat menulis f (g (0)), tetapi saya tidak dapat menulis f (g, 0). Yang terakhir disebut "fungsional," dan membutuhkan aturan yang berbeda.
Cort Ammon - Kembalikan Monica
Fungsionalitas @CortAmmon adalah fungsi. Fungsi adalah hanya seperangkat pasangan (meskipun, sebenarnya, itu adalah tiga (D, R, G) di mana D adalah domain R adalah kisaran dan G adalah grafik (set pasangan), masalah kecil lain yang saya miliki dengan jawaban yang diterima, tetapi itu bukan di sini atau di sana). Jadi jika D adalah seperangkat fungsi dan Anda mengambil pasangan di mana elemen pertama adalah fungsi di D, maka Anda memiliki fungsi. Periksa Wikipedia: "Fungsional adalah pemetaan [fungsi] ..."
Neil
Yaitu Semua fungsional adalah fungsi, tidak semua fungsi adalah fungsional. Tetapi semua aturan yang berlaku untuk fungsi berlaku untuk fungsional
Neil

Jawaban:

63

Ironisnya, judulnya ada pada poin tetapi tidak dalam cara Anda tampaknya bersungguh-sungguh yang "adalah kalkulus lambda hanya konvensi notasi" yang tidak akurat.

Istilah Lambda bukan fungsi 1 . Mereka adalah potongan-potongan sintaksis, yaitu koleksi simbol pada halaman. Kami memiliki aturan untuk memanipulasi koleksi simbol ini, yang paling signifikan adalah pengurangan beta. Anda dapat memiliki beberapa berbeda istilah lambda yang sesuai dengan yang sama fungsi. 2

Saya akan membahas poin Anda secara langsung.

Pertama, lambda bukan nama yang digunakan kembali. Tidak hanya itu akan sangat membingungkan, tetapi kita tidak menulis λ(x) (atau (λ x) ) yang akan kita lakukan jika λ adalah nama untuk suatu fungsi, sama seperti kita menulis f(x) . Dalam f(x) kita bisa mengganti f (jika didefinisikan oleh istilah lambda) dengan istilah lambda menghasilkan sesuatu seperti (λy.y)(x) berarti (λy.y) adalah ekspresi yang dapat mewakili suatu fungsi, bukan deklarasi yang mendeklarasikan suatu fungsi (dinamaiλ atau yang lainnya). Bagaimanapun, ketika kita membebani terminologi / notasi, itu (satu harapan) dilakukan dengan cara di mana ia dapat disatukan melalui konteks, yang tentu saja tidak dapat menjadi kasus untuk istilah lambda.

Poin Anda berikutnya baik-baik saja tetapi agak tidak relevan. Ini bukan kompetisi di mana ada Syarat Tim dan Fungsi Tim, dan hanya satu yang bisa menang. Aplikasi utama istilah lambda adalah mempelajari dan memahami beberapa jenis fungsi tertentu. Polinomial bukan fungsi meskipun kita sering mengidentifikasi mereka dengan sembrono. Mempelajari polinomial tidak berarti orang berpikir bahwa semua fungsi harus polinomial, juga bukan berarti polinomial harus "melakukan" sesuatu "baru" agar layak dipelajari.

Mengatur fungsi teoretis bukan kotak hitam, meskipun mereka sepenuhnya ditentukan oleh hubungan input-output mereka. (Mereka benar - benar adalah hubungan input-output mereka.) Istilah Lambda juga bukan kotak hitam dan mereka tidak didefinisikan oleh hubungan input-output mereka. Seperti yang saya sebutkan sebelumnya, Anda dapat memiliki istilah lambda berbeda yang menghasilkan hubungan input-output yang sama. Ini juga menggarisbawahi fakta bahwa istilah lambda tidak dapat berfungsi, meskipun mereka dapat menginduksi fungsi. 2

F2 F2F24F2F2F2F22N2N

Ini berlaku untuk istilah lambda juga, kita dapat menafsirkan keduanya sebagai hal selain fungsi. Keduanya juga merupakan objek yang jauh lebih bisa ditelusuri untuk dikerjakan daripada set fungsi yang tak terhitung jumlahnya. Keduanya jauh lebih komputasi daripada fungsi sewenang-wenang. Saya dapat menulis sebuah program untuk memanipulasi polinomial (dengan koefisien yang setidaknya dapat diwakili secara komputabel) dan istilah lambda. Memang, istilah lambda yang tidak diketik adalah salah satu model asli dari fungsi yang dapat dihitung. Perspektif yang lebih simbolis / sintaksis, kalkulasi / komputasional ini biasanya lebih ditekankan, terutama untuk kalkulus lambda yang tidak diketik , daripada interpretasi yang lebih semantik dari kalkulus lambda. Diketikistilah lambda adalah hal-hal yang jauh lebih mudah dikelola dan biasanya (tetapi tidak selalu) dapat dengan mudah diartikan sebagai fungsi teoretis yang ditetapkan, tetapi biasanya juga dapat diartikan ke dalam kelas yang lebih luas dari hal-hal selain fungsi daripada kalkulus lambda yang tidak diketik. Mereka juga memiliki teori sintaksis yang kaya dan hubungan yang sangat mendalam dengan logika .

1 Mungkin masalahnya mungkin terjadi sebaliknya. Mungkin Anda memiliki kesalahpahaman tentang apa fungsi itu.

DDDDDD, dan untuk kategori set tidak ada objek refleksif non-sepele. Ceritanya agak sedikit berbeda dengan istilah lambda yang diketik , tetapi masih bisa tidak sepele.

3 Jika Anda jelas tentang perbedaan ini, maka analoginya harus cukup informatif.

4 Masalah ini tidak terjadi dengan bidang karakteristik 0, seperti bilangan kompleks, real, rasional, atau bilangan bulat, sehingga perbedaannya tidak setajam, meskipun masih ada.

Derek Elkins
sumber
8
Ini adalah respons yang luar biasa yang harus saya katakan. Benar-benar menghapus beberapa kesalahpahaman yang lama bagi saya. Terima kasih!
the0ther
4
Saya berharap saya bisa menanggapi ini secara detail! Banyak hal yang ingin saya tindak lanjuti. Secara keseluruhan, meskipun ini sangat berguna bagi saya, dan tampaknya juga untuk beberapa orang, jadi terima kasih atas jawaban yang cermat dan dipertimbangkan.
Neil
1
Hanya ada satu poin yang akan saya bahas di sini, yaitu klaim Anda bahwa polinomial tidak harus "melakukan" sesuatu "baru" agar layak dipelajari. Tentu saja! Tentu saja, tergantung pada bidang Anda, "baru" dapat memiliki arti yang berbeda (Jadi, misalnya matematikawan murni tidak akan membedakan antara vektor kolom dan vektor baris karena isomorfiknya, tetapi ahli statistik dapat menganggap perbedaan itu berguna untuk tujuan perhitungan). Formalisme baru apa pun harus membenarkan dirinya sendiri.
Neil
2
@Neil: Catatan Kaki # 2 secara khusus menawarkan beberapa bukti yang sangat jelas bahwa kalkulus lambda "melakukan sesuatu yang baru" yang tidak bisa dilakukan oleh fungsi "biasa". " Untuk contoh yang lebih konkret dari ekspresi lambda yang tidak beralasan, lihat kombinator titik tetap . The angka Gereja juga membuat untuk membaca menarik, terutama fungsi pendahulunya.
Kevin
1
Saya akan menambahkan bahwa lambdas sebagai fungsi tidak melakukan apa pun yang bermanfaat. Satu-satunya hal yang dapat Anda lakukan dengan lambda adalah memberikannya lambda dan mengembalikan lambda. Anda tidak memiliki cara untuk menguji apa yang dilakukan lambda yang dihasilkan. Anda hanya dapat memberikannya lambda lain untuk mendapatkan lambda lain sebagai imbalan. Sebagai fungsi, himpunan "fungsi lambda" berperilaku persis seperti himpunan tunggal yang hanya berisi fungsi identitas. Hanya dengan mempertimbangkan input dan output dari lambda sebagai ekspresi Anda dapat membedakan lambda.
Florian F
0

Pikirkan konsep variabel. Dalam bahasa lama seperti dasar, Anda tidak memiliki alokasi dinamis dan Anda memerlukan satu nama untuk setiap variabel. (Ini tidak sepenuhnya akurat karena Anda memiliki array, tetapi idenya adalah bahwa ...) dalam banyak masalah, Anda harus dapat mengalokasikan variabel sebanyak yang Anda inginkan, tanpa dibatasi oleh jumlah nama yang ditentukan oleh program Anda.

Fungsi Lambda memungkinkan Anda untuk menyingkirkan batasan yang sama tentang nama fungsi, memungkinkan program Anda untuk mendefinisikan sebanyak mungkin fungsi yang dibutuhkan dan "menyimpan" mereka di struktur data kompleks yang sama dengan variabel lainnya. Ini bukan sesuatu yang bisa Anda lakukan dengan fungsi bernama konvensional.

Truk
sumber
Mengapa saya tidak bisa melakukan ini dengan fungsi bernama konvensional? Jika saya menulis f(x)=let g(y)=x+y in g, setiap matematikawan akan langsung tahu apa yang dimaksud dan setuju bahwa ini adalah objek matematika yang masuk akal (mungkin hingga beberapa quibble tentang kejelasan tentang domain f). Mereka juga akan sangat senang jika saya kemudian menulis set {f(n) | n ∈ ℕ}, yang berisi banyak sekali fungsi dan khususnya tidak dibatasi dengan hanya memiliki jumlah nama yang terbatas untuk digunakan.
Daniel Wagner
Pertanyaannya adalah tentang kalkulus lambda. Sementara terkait, itu tidak sama dengan fungsi lambda dalam bahasa pemrograman.
Andy Dent