Hubungan Historis antara Kalkulus Typed Lambda dan Lisp?

16

Saya sedang berdiskusi dengan seorang teman baru-baru ini (yang merupakan penganjur bahasa yang sangat diketik). Dia membuat komentar:

Para penemu Lambda Calculus selalu berniat untuk mengetik.

Sekarang kita dapat melihat bahwa Gereja dikaitkan dengan yang Cukup Diketik Lambda Kalkulus . Memang, tampaknya ia menjelaskan Kalkulus Lambda Cukup Ketik untuk mengurangi kesalahpahaman tentang Kalkulus Lambda.

Sekarang ketika John McCarthy menciptakan Lisp - ia mendasarkannya pada Kalkulus Lambda . Ini dengan pengakuannya sendiri ketika ia menerbitkan "Fungsi rekursif dari ekspresi simbolik dan perhitungannya dengan mesin, Bagian I" . Anda bisa membacanya di sini .

McCarthy tampaknya tidak membahas Kalkulus Lambda Cukup Ketik. Ini sepertinya dikuasai oleh Robyn Milner dengan ML .

Ada beberapa diskusi tentang hubungan antara Lisp dan Lambda Calculus di sini , tetapi mereka tidak benar-benar memahami mengapa McCarthy memilih untuk membiarkannya tanpa mengetik.

Pertanyaan saya adalah - Jika McCarthy mengakui dia tahu tentang Lambda Calculus - mengapa dia mengabaikan Typed Lambda calculus? (yaitu - apakah benar-benar jelas bahwa Lambda Calculus dimaksudkan untuk diketik? Tampaknya tidak seperti itu)

Hawkeye
sumber
1
Mungkin ada hubungannya dengan Calculus Lambda diketik tidak menjadi Turing-lengkap.
Jan Johannsen
Terima kasih @JanJohannsen - bisakah Anda mengembangkannya?
hawkeye

Jawaban:

17

Pertama, teman Anda salah tentang sejarah λ kalkulus. Gereja menciptakan kalkulus yang belum diketik terlebih dahulu, yang ia maksudkan sebagai dasar untuk matematika. Cukup cepat, ditemukan bahwa logika yang berasal dari kalkulus ini tidak konsisten (karena ada program non-terminating). Akhirnya Gereja mengembangkan teori jenis yang sederhana juga, dan banyak hal lainnya di samping itu, tetapi itu bukan poin asli dari sistem.

Ikhtisar sejarah yang luar biasa ditemukan dalam makalah ini .

λ

Sam Tobin-Hochstadt
sumber
Wow - dijawab oleh orang yang paling memenuhi syarat di dunia tentang topik ini. Terima kasih @ Sam. Mungkin saya akan mendapatkan aplikasi Phd untuk Anda pada akhir tahun ini. (Kedengarannya seperti Ambrose BS menantikan untuk bekerja sama dengan kalian).
hawkeye
3
Saya benar-benar sangat jauh dari orang yang paling memenuhi syarat di dunia tentang topik ini.
Sam Tobin-Hochstadt
Tautan tampaknya rusak. Saya percaya ini adalah makalah yang sama: hope.simons-rock.edu/~pshields/cs/cmpt312/cardone-hindley.pdf
bmaddy