Apa kontribusi kalkulus lambda pada bidang teori perhitungan?

85

Saya hanya membaca di lambda calculus untuk "mengenalnya". Saya melihatnya sebagai bentuk komputasi alternatif sebagai lawan dari Mesin Turing. Ini adalah cara menarik untuk melakukan sesuatu dengan fungsi / reduksi (secara kasar). Beberapa pertanyaan terus mengganggu saya:

Apa gunanya kalkulus lambda? Mengapa harus melalui semua fungsi / reduksi ini? Apa tujuannya?
Akibatnya saya bertanya-tanya: Apa yang sebenarnya dilakukan lambda calculus untuk memajukan teori CS? Kontribusi apa yang memungkinkan saya memiliki momen "aha" untuk memahami kebutuhan akan keberadaannya?
Mengapa kalkulus lambda tidak tercakup dalam teks tentang teori automata? Rute umum adalah melalui berbagai automata, tata bahasa, Turing Machines, dan kelas kompleksitas. Kalkulus Lambda hanya termasuk dalam silabus untuk kursus gaya SICP (mungkin tidak?). Tetapi saya jarang melihatnya sebagai bagian dari kurikulum inti CS. Apakah ini menyiratkan itu tidak terlalu berharga? Mungkin tidak dan saya mungkin melewatkan sesuatu di sini?

Saya sadar bahwa bahasa pemrograman fungsional didasarkan pada kalkulus lambda, tetapi saya tidak menganggapnya sebagai kontribusi yang valid, karena ia dibuat jauh sebelum kami memiliki bahasa pemrograman. Jadi, sungguh apa gunanya mengetahui / memahami lambda calculus, apakah aplikasi / kontribusinya terhadap teori?

soft-question big-picture lambda-calculus ho.history-overview PhD
sumber

6

Seperangkat jawaban terkait menjelaskan perbedaan kekuatan antara -calculus dan TM: cstheory.stackexchange.com/questions/1117/…

λ

$\lambda$

Suresh Venkat

4

Mungkin pembahasan alasan historis untuk adopsi Turing Machine sebagai model utama perhitungan juga menarik.

Martin Berger

5

Di satu sisi, kontribusinya adalah menciptakan lapangan. Jangan lupa bahwa Gereja datang dengan kalkulus lambda pertama, tetapi pada awalnya tidak dilihat sebagai model perhitungan universal.

Dan Hulme

Dalam studi inti saya, saya Functional Programmingmembahas Haskell dan sedikit Lisp. Penggantinya adalah Principles of Programming Languages, yang menggunakan ML dan memperkenalkan kalkulus lambda. Seperti yang ditunjukkan oleh beberapa jawaban, itu benar-benar tempat kalkulus lambda berada: di kelas tentang bahasa pemrograman, pengetikan, dll.

Shaz

pertanyaan ini adalah hubungan yang serupa antara kalkulus TM & Lambda & juga membahas prioritas historis kalkulus Lambda

vzn

96

-kalkulus memiliki dua peran utama. $\lambda$

Ini adalah dasar matematika sederhana dari perilaku komputasi sekuensial, fungsional, tingkat tinggi.
Ini adalah representasi bukti dalam logika konstruktif.

Ini juga dikenal sebagai korespondensi Curry-Howard . Bersama-sama, pandangan ganda -kalkulus sebagai bukti dan sebagai bahasa pemrograman (berurutan, fungsional, tingkat tinggi), diperkuat oleh nuansa aljabar kalkulus (yang tidak digunakan bersama oleh mesin Turing), telah mengarah pada transfer teknologi besar-besaran antara logika, dasar-dasar matematika, dan pemrograman. Transfer ini masih berlangsung, misalnya dalam teori tipe homotopy . Khususnya pengembangan bahasa pemrograman secara umum, dan pengetikan disiplin ilmu khususnya, tidak dapat dipahami tanpa $\lambda$ $\lambda$ $\lambda$ -kalkulus. Sebagian besar bahasa pemrograman berutang beberapa derajat kepada Lisp dan ML (mis. Pengumpulan sampah diciptakan untuk Lisp), yang merupakan turunan langsung dari -calculus. Untaian pekerjaan kedua yang sangat dipengaruhi oleh calculus adalah asisten bukti interaktif . $\lambda$ $\lambda$

Apakah kita harus tahu -kalkulus untuk menjadi programmer yang kompeten, atau bahkan ahli teori ilmu komputer? Tidak. Jika Anda tidak tertarik pada jenis, verifikasi, dan bahasa pemrograman dengan fitur tingkat tinggi, maka itu mungkin model perhitungan yang tidak terlalu berguna bagi Anda. Secara khusus, jika Anda tertarik pada teori kompleksitas, maka -kalkulus mungkin bukan model yang ideal karena langkah reduksi dasar sangat kuat: ia dapat membuat angka acak salinan pada , jadi $\lambda$ $\lambda$

(λ x . M.) N \to_{β} M. [N / x]

$(\lambda x.M) N \rightarrow_{\beta} M[N/x]$

N

$N$

\to_{β}

$\rightarrow_{\beta}$ adalah gagasan dasar yang tidak realistis dalam akuntansi untuk biaya perhitungan mikroskopis. Saya pikir ini adalah alasan utama mengapa Teori A tidak begitu terpikat pada

-kalkulus. Sebaliknya, mesin Turing tidak sangat inspiratif untuk pengembangan bahasa pemrograman, karena tidak ada pengertian alami komposisi mesin, sedangkan dengan

kalkulus, jika

dan

adalah program, kemudian jadi adalah

. Pandangan aljabar komputasi ini secara alami berkaitan dengan bahasa pemrograman yang digunakan dalam praktik, dan banyak pengembangan bahasa dapat dipahami sebagai pencarian, dan investigasi operator komposisi program baru.

λ

$\lambda$

λ

$\lambda$

M

$M$

N

$N$

M N

$MN$

Untuk ikhtisar ensiklopedis dari sejarah kalkulus lihat Sejarah Lambda-kalkulus dan Logika Combinatory oleh Cardone dan Hindley . $\lambda$

Martin Berger
sumber

8

Ini jawaban yang sangat bagus.

Suresh Venkat

9

Mengenai "tidak realistis" pengurangan-

: Beniamino Accattoli dan Ugo Dal Lago baru-baru ini membuktikan hasil yang mengejutkan yang menyatakan bahwa jumlah

ke bentuk normal dalam setiap strategi pengurangan standar (misalnya, paling kiri-terluar) adalah ukuran kompleksitas invarian. Ini berarti bahwa, bahkan jika menerapkan pengurangan

per se mahal, menghitung jumlah pengurangan bukanlah ukuran kompleksitas yang tidak realistis (misalnya, itu tidak akan mempengaruhi definisi kelas

).

β

$\beta$

β

$\beta$

β

$\beta$

P

$\mathsf P$

Damiano Mazza

5

@DamianoMazza Karena ini adalah hasil baru, itu tidak mungkin berpengaruh dalam sejarah Teori A. Selain itu, saya pikir hasil ini hanya berlaku untuk beberapa gagasan pengurangan. Makalah IIRC Asperti P = NP, hingga berbagi menunjukkan bahwa P dan NP runtuh jika Anda memiliki strategi pengurangan 'optimal' dalam arti J.-J. Retribusi.

Martin Berger

6

@ MartinBerger: ya tentu saja. Komentar saya dimaksudkan untuk menambahkan informasi tentang kerumitan pengurangan

, sama sekali tidak untuk "mengoreksi" pernyataan Anda tentang kurangnya pengaruh pada Teori A (yang saya ulangi dalam jawaban saya). Ngomong-ngomong, hasil Accattoli dan Dal Lago berlaku untuk pengurangan

biasa, paling jauh paling kiri ( lih. Hal.2, c.2, l.11 dari makalah mereka). Itu sebabnya sangat menarik (dan layak disebut). Hasil Asperti menyangkut, seperti yang Anda katakan, pengurangan optimal-Lévy, yang bukan merupakan strategi pengurangan

(khususnya, paling kiri-terluar bukan optimal-Lévy).

β

$\beta$

β

$\beta$

β

$\beta$

Damiano Mazza

27

$\lambda$ $\lambda$

$\lambda$ $\mu$
$\lambda$
$\mu$ $\lambda$

Bruno
sumber

20

$\lambda$

Apa sebenarnya yang dilakukan kalkulus lambda untuk memajukan teori CS?

$\lambda$ $\lambda$ $\lambda$

$\lambda$

Damiano Mazza
sumber

2

λ

$\lambda$

λ

$\lambda$

π

$\pi$

π

$\pi$

5

Jika saya bisa mengkloning diri saya sendiri, saya akan membuat duplikat untuk melihat ke P / NP menggunakan BLL dan realisasi. Hubungan logis tampaknya bukan "bukti alami", disiplin tipe linier memastikan Anda tidak dapat melakukan relativisasi, dan teorema kelengkapan polytime BLL tampaknya membuat Anda menghindari khawatir tentang ada atau tidaknya kelas algoritma yang Anda lewatkan. Hubungan antara linearitas dan teori representasi menyarankan koneksi ke GCT juga. Saya kira semua ini sebabnya Anda tergoda dan frustrasi. :)

Neel Krishnaswami

1

Hei @NeelKrishnaswami bisakah Anda mengarahkan saya ke bahan bacaan yang berhubungan dengan BLL (logika linear terbatas) dan bukti alami?

Martin Berger

B B vs A: lambda-calculus hanya tentang penataan komputasi yang sama lebih baik, tetapi tidak bisa, misalnya, menghasilkan algoritma yang lebih baik. Dengan cut-elimination dan properti subformula pada hasilnya, program apa pun dengan tipe orde pertama dapat ditulis tanpa fungsi kelas satu. Tetapi cut-elimination berhubungan dengan duplikasi kode: jadi kami menemukan lagi bahwa Anda tidak memerlukan fungsi tingkat tinggi jika Anda bersedia melakukan cukup copy-paste. (Defungsionalisasi Reynolds memungkinkan Anda untuk menghindari bahkan copy-paste, tetapi merupakan transformasi global, jadi lebih baik diserahkan kepada kompiler).

Blaisorblade

Secara anekdot, komentar saya termotivasi oleh pemrograman dengan algoritme - dia hebat, tapi dia tampaknya abstrak jauh lebih sedikit daripada yang saya inginkan. Saya tidak mengklaim itu umum, tetapi saya mengklaim bahwa abstraksi dalam kode sering tidak diperlukan / ditekankan saat menulis algoritma. (Pertimbangkan berapa banyak implementasi quicksort yang sesuai dengan fungsi partisi - saya rasa itu tidak dapat diterima).

Blaisorblade

13

Pertanyaan Anda dapat didekati dari berbagai sisi. Saya ingin meninggalkan aspek historis dan filosofis di samping dan menjawab pertanyaan utama Anda, yang saya anggap sebagai ini:

Apa gunanya kalkulus lambda? Mengapa harus melalui semua fungsi / reduksi ini?

Apa gunanya Aljabar Boolean, atau Aljabar Relasional, atau Logika Orde Pertama, atau Tipe Teori, atau teori / formalisme matematika lainnya? Jawabannya adalah bahwa mereka tidak memiliki tujuan yang melekat pada mereka, bahkan jika desainer mereka menciptakannya untuk tujuan tertentu. Leibniz, ketika mendirikan fondasi Aljabar Boolean, memiliki proyek filosofis tertentu dalam pikirannya; Boole mempelajarinya karena alasannya sendiri. Karya de Morgan tentang Relational Algebra juga dimotivasi oleh berbagai proyeknya; Peirce dan Frege memiliki motivasi sendiri untuk menciptakan logika modern.

Intinya adalah: apa pun alasan yang dimiliki Gereja ketika membuat kalkulus lambda, titik kalkulus lambda bervariasi dari satu praktisi ke praktisi lainnya.

Untuk seseorang itu adalah notasi yang nyaman untuk berbicara tentang perhitungan; alternatif untuk Mesin Turing, dan sebagainya.
Bagi yang lain, ini adalah dasar matematika yang kuat untuk membangun bahasa pemrograman yang lebih canggih (mis. McCarthy, Stanley).
Bagi orang ketiga, ini adalah alat yang ketat untuk memberikan semantik bahasa pemrograman serta alami (misalnya Montague, Fitch, Kratzer).

Saya pikir kalkulus Lambda adalah bahasa formal yang layak dipelajari untuk kepentingannya sendiri. Anda dapat mempelajari fakta bahwa dalam kalkulus lambda yang tidak diketik, kita memiliki binatang kecil bernama 'Y-combinators', dan bagaimana mereka membantu kita mendefinisikan fungsi rekursif dan membuat bukti ketidakjelasan sangat elegan dan sederhana. Anda dapat mempelajari fakta menakjubkan bahwa ada korespondensi intim antara kalkulus lambda yang diketik sederhana dan sejenis logika intuitionistic . Ada banyak topik menarik lainnya untuk dijelajahi (misalnya bagaimana kita harus memberikan semantik kalkulus lambda? Bagaimana kita dapat mengubah kalkulus lambda menjadi sistem deduktif seperti FOL?)

Lihat Pengantar Hindley & Seldin untuk Combinators dan λ – Calculus untuk pengantar. Barendregt, The Lambda Calculus, adalah Alkitab, jadi jika Anda tertarik dengan Hindley & Seldin, ada banyak topik yang bersifat semantik dan sintaksis untuk dijelajahi.

Hunan Rostomyan
sumber

6

Saya tidak membeli argumen "untuk kepentingannya sendiri". Inti formalisme matematika adalah menjelaskan pemahaman kita tentang beberapa konsep. Apa yang dijelaskan dapat berkembang dari waktu ke waktu, tetapi kecuali jika formalisme membantu kita berpikir lebih jernih tentang suatu gagasan, biasanya itu akan hilang. Dalam pengertian itu sah untuk aks bagaimana lambda calculus menjelaskan konsep perhitungan dengan cara yang tidak dimasukkan oleh TM.

Sasho Nikolov

1

Saya pikir orang dapat mempelajari kalkulus lambda tanpa pernah berpikir pengurangan dan penggantian sebagai perhitungan. Jika saya benar dan itu sebenarnya mungkin, maka kita dapat memiliki minat pada lambda kalkulus bahkan jika kita tidak tertarik pada perhitungan sama sekali. Tetapi terima kasih atas komentar Anda; Saya akan mencoba mengedit jawaban saya sesuai segera setelah saya mendapat kesempatan.

Hunan Rostomyan

@SashoNikolov - "dengan cara yang tidak dimasukkan oleh TM." Menurut definisi, itu tidak mungkin, karena LC dan TM setara. Apa pun yang Anda bisa ungkapkan atau buktikan dengan satu, Anda bisa dengan yang lain (dan sebaliknya). Jadi mereka membuat satu sama lain mubazir (seperti yang mereka berdua lakukan dengan teori rekursif umum, formalisme lain yang setara dengan TM). Apakah itu berarti kita harus membuang semua sistem yang setara dengan TM kecuali TM itu sendiri? Saya tidak akan mengatakannya, karena kadang-kadang hal-hal lebih mudah untuk diekspresikan dalam LC daripada TM atau sebaliknya. Ini hanyalah cara lain untuk berbicara tentang kemampuan komputasi.

Gabriel L.

1

@GabrielL. Jika Anda membaca seluruh kalimat, katanya "bagaimana lambda calculus menjelaskan konsep perhitungan dengan cara yang tidak dimasukkan oleh TM". Dua definisi matematika yang secara formal setara mungkin masih menjelaskan konsep dasar yang sama dengan cara yang berbeda dan saling melengkapi. Komentar saya berarti masuk akal untuk menanyakan kejelasan apa yang diperoleh dengan menyatakan komputabilitas dalam hal kalkulus lambda, bukan dalam hal TM. Ini sama sekali bukan tentang kesetaraan formal.

Sasho Nikolov

Mengerti - berhasil melewatkan kata kunci di sana. Terima kasih balasannya.

Gabriel L.

12

Turing berpendapat bahwa Matematika dapat direduksi menjadi kombinasi simbol baca / tulis, dipilih dari himpunan terbatas, dan beralih di antara sejumlah 'kondisi' mental yang terbatas. Dia menegaskan ini di Mesin Turing, di mana simbol direkam dalam sel pada kaset dan robot melacak negara.

Namun, mesin Turing bukan merupakan bukti konstruktif dari pengurangan ini. Dia berpendapat bahwa 'prosedur efektif' apa pun dapat diterapkan oleh beberapa Mesin Turing, dan menunjukkan bahwa Mesin Universal Turing dapat menerapkan semua mesin lain itu, tetapi dia tidak benar-benar memberikan satu set simbol, status, dan memperbarui aturan yang menerapkan Matematika. dengan cara yang dia berargumen. Dengan kata lain, dia tidak mengusulkan 'Mesin Turing standar', dengan seperangkat simbol standar yang dapat kita gunakan untuk menuliskan Matematika kita.

Sebaliknya, Lambda Calculus adalah persis seperti itu. Gereja secara khusus berusaha menyatukan notasi yang digunakan untuk menuliskan Matematika kita. Setelah ditunjukkan bahwa LC dan TM setara, kita dapat menggunakan LC sebagai 'Mesin Turing standar' kami dan semua orang akan dapat membaca program kami (well, dalam teori;)).

Sekarang, kita bisa bertanya mengapa memperlakukan LC sebagai primitif, bukan sebagai dialek TM? Jawabannya adalah bahwa semantik LC adalah denotasional : Istilah LC memiliki makna 'intrinsik'. Ada angka Gereja, ada fungsi untuk penambahan, perkalian, rekursi, dll. Ini membuat LC sangat selaras dengan bagaimana (formal) Matematika dipraktikkan, itulah sebabnya mengapa banyak (fungsional) algoritma masih disajikan langsung dalam LC.

Di sisi lain, semantik program TM bersifat operasional : artinya didefinisikan sebagai perilaku mesin. Dalam hal ini, kita tidak dapat memotong beberapa bagian rekaman dan mengatakan "ini adalah tambahan", karena itu tergantung konteks. Perilaku mesin, ketika menyentuh bagian pita itu, tergantung pada kondisi mesin, panjang / offset / dll. dari argumen, berapa banyak kaset yang akan digunakan untuk hasilnya, apakah ada operasi sebelumnya telah merusak bagian rekaman itu, dll. Ini adalah cara kerja yang menghebohkan ("Tidak ada yang mau memprogram Mesin Turing"), itulah sebabnya mengapa banyak algoritma (imperatif) disajikan sebagai pseudocode.

Warbo
sumber

5

jawaban lain baik, berikut adalah satu sudut / alasan tambahan untuk pertimbangan yang menyatu dengan yang lain namun mungkin lebih definitif, namun mungkin lebih sulit untuk diingat dengan jelas karena asal-usul lama hilang sedikit di pasir waktu:

prioritas sejarah!

Kalkulus Lambda diperkenalkan setidaknya pada awal 1932 dalam referensi berikut:

A. Gereja, "Seperangkat postulat untuk landasan logika", Annals of Mathematics, Series 2, 33: 346-366 (1932).

yang Turing Machine diperkenalkan pada ~ 1936 , sehingga Lambda Kalkulus mendahului penampilan TM dengan beberapa tahun!

Turing, AM (1936). "Pada Nomor yang Dapat Dihitung, dengan Aplikasi untuk masalah Entscheidungs". Prosiding Masyarakat Matematika London. 2 (1937) 42: 230–265. doi: 10.1112 / plms / s2-42.1.230

jadi dengan kata lain jawaban dasar adalah bahwa Lambda Calculus dalam banyak hal merupakan sistem warisan tertinggi TCS. masih ada dalam banyak cara yang sama bahwa Cobol meskipun tidak banyak perkembangan baru dalam bahasa! tampaknya merupakan sistem perhitungan Turing Lengkap paling awal yang diperkenalkan dan bahkan mendahului gagasan dasar Turing Completeness. hanya analisis retrospektif kemudian yang menunjukkan bahwa Lambda Calculus, mesin Turing, dan Post Correspondence Problem adalah setara dan memperkenalkan konsep kesetaraan Turing dan tesis Church-Turing .

Kalkulus Lambda hanyalah cara untuk mempelajari perhitungan dari pov logika-sentris lebih dalam hal merepresentasikannya sebagai teorema matematika & derivasi rumus logis dan sebagainya. itu juga menunjukkan hubungan yang mendalam antara komputasi dan rekursi dan penggabungan yang lebih erat dengan induksi matematika .

ini adalah fakta yang agak luar biasa karena ini menunjukkan bahwa dalam banyak hal asal (setidaknya teoretis ) komputasi secara fundamental dalam logika / matematika , tesis maju / diperluas secara terperinci oleh Davis dalam bukunya Engines of Logic / Mathematicians dan asal-usul komputer . (tentu saja asal-usul & peran dasar aljabar Boolean juga semakin memperkuat kerangka historis konseptual itu.)

karenanya, secara dramatis, orang mungkin bahkan mengatakan kalkulus Lambda sedikit seperti mesin waktu pedagogis untuk menjelajahi asal mula komputasi!

vzn
sumber

1

Selain itu, kalkulus Lambda juga tampaknya telah sangat dipengaruhi oleh Principia Mathematica oleh Whitehead / Russell yang juga merupakan inspirasi utama bagi Godels thm . beberapa penelitian ini juga terinspirasi oleh masalah Hilberts ke-10 di pergantian abad yang meminta solusi algoritmik sebelum "algoritme" didefinisikan (secara matematis), dan pada kenyataannya bahwa pencarian sebagian besar mengarah pada definisi teknis yang tepat kemudian.

vzn

btw / klarifikasi / iiuc itu sebenarnya sistem kanonik Post yang dipelajari 1 oleh Post dan tampaknya Post Correspondence Problem yang lebih sederhana adalah kasus khusus. juga itu Kleene yang berperan dalam mengembangkan konsep kelengkapan Turing (tidak ada di bawah nama itu) dengan membantu membuktikan semua 3 sistem utama dapat dipertukarkan / setara (TM, Lambda Calculus, Post canonical system).

vzn

lihat juga History of the Church-Turing wikipedia thesis yang melacak banyak detail / keterkaitan historis

vzn

4

Saya mengalami kesulitan untuk tidak tersinggung dengan perbandingan Cobol.

Neil Toronto

-2

Saya baru saja menemukan posting ini dan meskipun posting saya agak terlambat pada hari (tahun!), Saya berpikir bahwa mungkin "nilai sen" saya mungkin berguna.

Sementara mempelajari subjek di universitas, saya memiliki pemikiran yang sama tentang masalah ini; jadi, saya mengajukan pertanyaan "mengapa" kepada dosen dan jawabannya adalah: "penyusun". Segera setelah dia menyebutkannya, kekuatan di balik reduksi dan seni menilai cara terbaik untuk memanipulasinya tiba-tiba menjadikan seluruh tujuan mengapa hal itu dan masih merupakan alat yang berpotensi bermanfaat.

Nah, itu bisa dikatakan adalah momen "aha" saya.

Menurut pendapat saya, kita sering menganggap bahasa tingkat tinggi, pola, automata, algoritma-kompleksitas dll berguna karena kita dapat menghubungkannya dengan 'tugas' yang ada; sedangkan lamdba calculus tampaknya agak terlalu abstrak. Namun, masih ada orang-orang di luar sana yang bekerja dengan bahasa pada tingkat rendah - dan saya membayangkan lambda kalkulus, kalkulus objek, dan formalisasi terkait lainnya telah membantu mereka untuk memahami dan mungkin mengembangkan teori dan teknologi baru yang dapat dimanfaatkan oleh programmer rata-rata. Memang, itu mungkin bukan modul inti untuk alasan itu, tetapi (untuk alasan yang telah saya nyatakan) akan ada beberapa yang aneh - selain akademisi - yang mungkin menemukannya integral dengan jalur karir yang mereka pilih dalam komputasi.

pengguna30412
sumber

Apa "aha" pada kompiler ?

PhD

Paragraf terakhir Anda tampaknya sepenuhnya spekulatif dan Anda tidak pernah benar-benar menjelaskan mengapa satu kata "penyusun" menjawab pertanyaan.

David Richerby

@ PHD: Pengurangan beta & subtitusi tidak digunakan saat menjalankan program, tetapi digunakan di dalam mengoptimalkan kompiler. Itu bukan kepentingan utama lambda-calculus, tetapi ini adalah aplikasi yang sangat konkret.

Blaisorblade

Apa kontribusi kalkulus lambda pada bidang teori perhitungan?

Jawaban: