Kalkulus Lambda di luar pemrograman fungsional?

21

Saya seorang mahasiswa, dan kami sedang mempelajari Lambda Calculus. Namun, saya masih kesulitan memahami dengan tepat mengapa ini berguna bagi saya. Saya menyadari jika Anda melakukan banyak pemrograman fungsional mungkin berguna, namun saya rasa itu tidak benar-benar diperlukan untuk belajar pemrograman fungsional, bagaimana menurut Anda?

Kedua, apakah ada gunanya untuk Kalkulus Lambda dalam bidang Ilmu Komputer tetapi di luar bahasa pemrograman fungsional?

lambda-calculus functional-programming Yakub
sumber

15

Kalkulus lambda adalah dasar dalam logika, teori kategori, teori tipe, verifikasi formal, ... Pada dasarnya, ada hubungannya dengan semantik bahasa pemrograman dan logika formal. Ini adalah formalisme mendasar sehingga orang yang bekerja di bidang ini bahkan tidak mempertanyakan manfaatnya.

Saya pikir itu sangat berguna untuk memahami pemrograman fungsional karena memberi Anda esensi pemrograman fungsional. Fungsi, aplikasi, substitusi. Berdasarkan ini, Anda dapat membangun keterampilan Anda dalam bernalar tentang program fungsional dan transformasi mereka. Fungsi tingkat tinggi sangat mudah.

Tentu Anda bisa belajar pemrograman fungsional tanpa kalkulus lambda, tetapi Anda tidak akan pernah benar-benar memahami pemrograman fungsional tanpa itu.

Dave Clarke
sumber

Terima kasih banyak atas tanggapan Anda Dave. Saya pikir verifikasi formal adalah alasan terbaik, mengapa kalkulus lambda berguna bagi saya untuk belajar, dan cukup lucu, saya akan melakukan kursus verifikasi formal semester depan. Apakah Anda juga menggunakan kalkulus lambda untuk melakukan verifikasi formal terhadap perangkat lunak yang ditulis dalam bahasa apa pun, misalnya imperatif atau berorientasi objek?

Yakub

1

Anda tidak boleh menggunakan kalkulus lambda secara langsung ketika melakukan verifikasi formal, tetapi akan muncul di dasar verifikasi formal. Spesifikasi penulisan seringkali melibatkan penulisan dalam bahasa fungsional, bahkan untuk kode imperatif / OO.

Dave Clarke

Oke itu menarik terima kasih banyak, sekarang saya punya sedikit alasan untuk mempelajari ini. Apakah Anda tahu jika lambda calculus digunakan untuk merancang bahasa yang tidak berfungsi (pada level yang lebih rendah)?

Yakub

1

ALGOL. Scala. Pada akhirnya, pertanyaan Anda sulit dijawab. Kalkulus lambda telah menjadi bagian dari pengetahuan umum bagi (sebagian besar) perancang bahasa dan karena itu memengaruhi desain bahasa, bahkan jika itu tidak digunakan secara eksplisit. Pertimbangkan blok di Smalltalk atau Ruby, kelas anonim di Jawa. Ini adalah penutupan, yang terkait erat dengan fungsi tingkat tinggi dalam kalkulus lambda.

Dave Clarke

Oke, terima kasih banyak, Dave, itu sangat dihargai.

Jacob

17

Anda meminta aplikasi di luar ilmu komputer dan logika. Yang mudah ditemukan, misalnya dalam topologi aljabar, adalah nyaman untuk memiliki kategori ruang tertutup kartesian, lihat kategori ruang topologi yang nyaman di nLab. Bahasa formal yang sesuai dengan kategori tertutup kartesian adalah tepatnya kalkulus. Izinkan saya mengilustrasikan dengan contoh yang sangat sederhana bagaimana ini berguna. $\lambda$

Pertama, sebagai latihan pemanasan, misalkan seseorang bertanya kepada Anda apakah fungsi didefinisikan oleh dapat dibedakan. Anda tidak benar-benar harus membuktikan bahwa itu adalah, Anda hanya mengamati bahwa itu adalah komposisi fungsi yang dapat dibedakan, oleh karena itu dapat dibedakan. Dengan kata lain, Anda membuat kesimpulan yang mudah berdasarkan pada bentuk definisi. $f : \mathbb{R} \to \mathbb{R}$ $f(x) = x^2 e^x + \log (1 + x^2)$

Sekarang untuk contoh nyata. Misalkan seseorang meminta Anda apakah fungsi didefinisikan oleh $f : \mathbb{R} \to \mathbb{R}$

f (x) = (λ f : C (R) . \int_{- x}^{x} f (1 + t^{2}) d t) (λ y : R . maks (x, dosa (y + 3))

$f(x) = \left(\lambda f : \mathcal{C}(\mathbb{R}) . \int_{-x}^{x} f(1 + t^2) dt\right)(\lambda y : \mathbb{R} . \max(x, \sin(y + 3))$ kontinu. Sekali lagi, kita dapat langsung menjawab "ya" karena fungsi didefinisikan menggunakan

-kalkulus dan mulai dari peta kontinu

,

, dll.

λ

$\lambda$

max

$\max$

\int

$\int$

\sin

$\sin$

Berbagai ekstensi -kalkulus memungkinkan untuk melakukan hal yang sama di area lain. Misalnya, karena topos yang halus adalah kategori tertutup kartesius, peta apa pun yang didefinisikan menggunakan -kalkus, mulai dari turunan dan struktur cincin real (dan Anda dapat melempar fungsi eksponensial jika diinginkan) secara otomatis mulus . (Sebenarnya, dorongan utama topos yang halus adalah adanya infinitesimal nilpotent yang memungkinkan Anda untuk mengatakan hal-hal seperti "kami membuat disk menjadi segitiga sama kaki tipis sama sekali tak terbatas".) $\lambda$ $\lambda$

Andrej Bauer
sumber

1

Terima kasih atas tanggapannya yang terperinci. Sebenarnya saya sedang berusaha menemukan penggunaan kalkulus lambda dalam ilmu komputer tetapi di luar pemrograman fungsional, permintaan maaf jika ini tidak jelas. Saya telah mengubah pertanyaan untuk lebih jelas menyatakan ini.

Yakub

Ah, sayang sekali, saya akan menulis tanggapan yang rumit tentang itu.

Andrej Bauer

Maaf tentang itu. Jangan ragu untuk menambahkan komentar jika Anda ingin menambahkan info tambahan :)

Jacob

2

λ

$\lambda$

7

$\lambda$ $\lambda$

$\lambda$

Martin Berger
sumber

5

$\lambda$

Peter Wone
sumber

2

Tanpa tahu lebih banyak tentang itu, saya mendengar bahwa ahli bahasa menggunakan kalkulus lambda.

http://www.sfu.ca/~jeffpell/Ling406/LambdaAbstractionOH.pdf , https://files.nyu.edu/cb125/public/Lambda/

Lukas Rytz
sumber

11

Bisakah Anda meringkas apa yang ada di balik tautan? Mereka memiliki kecenderungan untuk istirahat. Itu juga akan membuat jawaban Anda lebih mandiri.

Juho

Kalkulus Lambda di luar pemrograman fungsional?

Jawaban: