Apa yang membuat kalkulus lambda relevan untuk dipelajari?

Saya memulai kursus ilmu komputer sarjana musim gugur mendatang, tetapi saya tidak dapat benar-benar memahami kalkulus dalam konteks pemrograman fungsional. Saya mungkin salah menafsirkan ini sepenuhnya, tetapi berdasarkan definisi ini dari Stanford Encyclopedia of Philosophy, itu hanyalah notasi lain untuk fungsi.

Jika adalah hanya itu, mengapa menguntungkan untuk menggunakan λ-kalkulus lebih notasi fungsi biasa untuk menghitung algoritma run time?

programming-languages lambda-calculus Jules
sumber

Ini bukan "hanya notasi lain untuk fungsi" tetapi "notasi pertama untuk fungsi".

Andrej Bauer

Terima kasih atas sarannya, @Kaveh. Saya akan mengingatnya untuk posting selanjutnya, namun jawaban mhelvens sangat baik, jadi tidak perlu crosspost.

Ini adalah objek yang didefinisikan secara formal. Saya tidak melihat apa masalah sebenarnya Anda.

Raphael

Saya tidak begitu mengerti terminologi atau mengapa hal itu dilakukan mereka dilakukan dalam pemrograman fungsional sampai saya belajar tentang lambda calculus. Itu membuat konstruksi perangkat lunak tampak jauh lebih tidak sewenang-wenang.

dansalmo

Jawaban:

Dalam ilmu komputer kami ingin menganalisis dan memahami kode sumber dengan ketelitian matematis. Itulah satu-satunya cara untuk membuktikan sifat menarik (seperti pemutusan hubungan kerja) dengan kepastian absolut. Untuk itu kita membutuhkan bahasa dengan makna yang sangat jelas untuk setiap konstruk.

Secara teori ini bisa berupa bahasa apa saja dengan semantik formal yang bagus . Tetapi untuk membuat hal-hal menjadi lebih mudah dan tidak rentan terhadap kesalahan, yang terbaik adalah menggunakan bahasa yang sesederhana mungkin tetapi masih dapat mengekspresikan program apa pun (yaitu Turing selesai ). Untuk alasan tentang kode imperatif, ada mesin Turing . Tetapi untuk alasan tentang pemrograman fungsional, ada -calculus. $\lambda$

Dasar -calculus seperti bahasa pemrograman fungsional, tetapi dengan banyak 'bagasi' diambil. Ini tidak penting bahwa ini menjadi bahasa yang baik untuk benar-benar menulis program, juga bukan bahasa yang efisien. Hanya saja itu sederhana dan ekspresif. Sebagai contoh, kita tidak memerlukan loop, karena kita dapat mensimulasikannya dengan rekursi. Dan kita tidak memerlukan fungsi dengan banyak parameter, karena kita dapat mensimulasikannya dengan Currying . $\lambda$

Sekarang, pada titik tertentu Anda mungkin ingin membuktikan properti tentang konstruksi yang bukan bagian dari dasar (tidak diketik) -calculus. Itu sebabnya para ilmuwan komputer telah memperluasnya ke berbagai arah selama bertahun-tahun. Sebagai contoh, untuk alasan tentang sistem tipe ada banyak sekali variasi dari typed -calculi . $\lambda$ $\lambda$

mhelvens
sumber

imo, beberapa ilmu komputer mungkin tentang memahami kode sumber, tetapi mengatakan itu benar pada umumnya terdengar seperti mengatakan fisika adalah tentang memahami roket dengan ketelitian matematika. ilmu komputer adalah tentang perhitungan. Keluhan terkait adalah bahwa efisiensi bahasa tidak masalah jika Anda ingin mempelajari efisiensi dan bukan kode sumber yang terbentuk dengan baik. Dalam hal itu, mungkin lebih baik untuk berpikir tentang TM sebagai cara untuk berpikir tentang efisiensi daripada model bahasa imperatif (dan untuk kedua tujuan kata-RAM mungkin menjadi pilihan yang lebih baik)

Sasho Nikolov

btw apa yang saya tulis di atas tidak berarti saya tidak suka jawaban Anda :)

Sasho Nikolov

Sepakat. ;-) Diperbaiki.

mhelvens

Turing mesin yang mengerikan di penalaran tentang kode penting, itu jauh lebih mudah untuk menggunakan bahasa mainan seperti sederhana sementara bahasa jenis. stackoverflow.com/questions/507310/the-while-language . Mesin Turing tetap sangat berguna untuk wawasan dalam teori kompleksitas.

cody

anehnya banyak buku berbicara tentang kalkulus tanpa menyebutkan Lisp atau Skema , bahasa pemrograman modern berdasarkan itu, meninggalkan siswa sayangnya dengan gagasan yang lama dan abstrak dan sebagian besar teoretis. mempelajari Lisp atau Skema bisa menjadi cara yang bagus untuk sangat membantu memahami calculus. $\lambda$ $\lambda$

Jika adalah hanya itu, mengapa menguntungkan untuk menggunakan λ-kalkulus lebih notasi fungsi biasa untuk menghitung algoritma run time?

ada banyak keuntungan menggunakan Lisp atau pemrograman fungsional dan menghitung run time algoritma hanya satu kemungkinan (walaupun akan sangat membantu jika Anda mengutip referensi untuk itu). karena ini sudah dalam notasi fungsional kadang-kadang menentukan rumus untuk run time melalui hubungan induksi atau perulangan mungkin memiliki hubungan yang lebih kuat atau lebih jelas dengan kode asli. jenis analisis algoritma lainnya juga disederhanakan.

Keuntungan utama lainnya adalah kesederhanaan sintaksis. parser untuk bahasa lain sangat kompleks tetapi parser Lisp sangat sederhana. jadi Lisp adalah bahasa yang bagus untuk mempelajari teori parsing.

aspek kunci lain menganalisis perangkat lunak yang lebih dari logika atau matematika lensa / view daripada perspektif "komputer ilmiah".

sebagai jawaban lain menunjukkan, Lisp adalah tentang rekursi, bukan iterasi dan rekursi sangat banyak di jantung CS.

lebih banyak advokasi untuk " view" dan detail dapat ditemukan di [1], ref online dan semi-terkenal gratis. $\lambda$

[1] Struktur & Interpretasi program komputer, oleh Abelson & Sussman

vzn
sumber