Apa tujuan kalkulus kombinator SKI (atau bahkan kalkulus lambda)? Apa saja contoh kehidupan nyata dari penggunaannya?

Saya mengerti apa itu, tapi saya tidak melihat bagaimana itu digunakan untuk algoritma atau apa pun. Mungkin saya kehilangan sesuatu. Saya butuh seseorang untuk memberi saya contoh bagaimana itu bisa digunakan sehingga saya bisa memahaminya dengan lebih baik.

algorithms lambda-calculus combinatory-logic Kenneth Onyebinachi
sumber

Ada beberapa bahasa pemrograman esoterik berdasarkan logika kombinatorial, misalnya Unlambda . Lihat juga di sini . Anda dapat menemukan informasi lebih lanjut dengan menjelajahi tautan dalam artikel.

Anton Trunov

Jawaban:

Aplikasi kalkulus lambda yang jelas adalah bahasa pemrograman fungsional apa pun (misalnya, Lisp, ML, Haskell), dan bahasa apa pun yang mendukung fungsi anonim.

Sedangkan untuk kalkulus kombinator, apakah harus ada "aplikasi dunia nyata"? Mesin Turing, misalnya, hampir tidak pernah digunakan "di dunia nyata" tetapi mereka membentuk dasar teori komputasi. Salah satu fitur berguna dari kalkulus kombinator adalah mereka lebih sederhana daripada sistem, misalnya, mesin Turing. Jika Anda ingin membuktikan bahwa beberapa sistem lain adalah Turing-complete, mungkin lebih mudah untuk menunjukkan bagaimana ia dapat mensimulasikan kombinatorator daripada menunjukkannya dapat mensimulasikan mesin Turing.

David Richerby
sumber

Tentu saja, combinators yang digunakan dalam penyusunan bahasa fungsional (meskipun bukan SKI kalkulus itu sendiri).

cody

@cody Silakan posting jawaban tentang itu! Itu bukan sesuatu yang saya ketahui jadi saya lebih suka tidak mengedit jawaban saya.

David Richerby

Sebagai contoh, sistem tipe Scala telah terbukti Turing-complete dengan memasukkan SK-kalkulus di dalamnya. Saya bahkan tidak bisa membayangkan kompleksitas yang tidak masuk akal dari menanamkan Mesin Turing (Universal). Ironisnya (diberi nama) Kelengkapan turinf jarang ditunjukkan dengan Mesin Turing. SQL ditunjukkan sebagai TC dengan menerapkan Sistem Tag Siklik, HTML + CSS dengan Aturan 101, MMU Intel dengan mengkodekan instruksi "Pindahkan, Cabang jika Nol, Penurunan".

Jörg W Mittag

@ JörgWMittag re: " HTML + CSS dengan Rule 101 " maksud Anda " Rule 110 "?

RBarryYoung

@RarryYoung: Tentu saja, kesalahan ketik bodoh. Kode ini ada di sini: github.com/elitheeli/stupid-machines

Jörg W Mittag

Saya menemukan SKI berguna untuk memahami beberapa aksioma logis.

Sebagai contoh, aksioma gaya Hilbert dari implikasi (intuitionistic) adalah

\begin{array}{l} (a \to b \to c) \to (a \to b) \to a \to c \\ a \to (b \to a) \end{array}

$\begin{array}{l} (a \rightarrow b \rightarrow c) \rightarrow (a \rightarrow b) \rightarrow a \rightarrow c \\ a \rightarrow (b \rightarrow a) \end{array}$

Pertama kali saya melihat aksioma ini, saya bertanya-tanya mengapa mereka harus bekerja. Tentu, mudah untuk memeriksa bahwa mereka pegang. Tetapi mengapa ini harus cukup, yaitu mengapa menggunakan dua postulat ini saja sudah cukup untuk membuktikan (melalui modus ponens) semua tautologi implikasi lainnya? Misteri ... atau itu?

Nah, ternyata setiap tautologi harus sesuai dengan jenis istilah lambda, berkat isomorfisme Curry-Howard. Tetapi kata istilah lambda dapat secara setara ditulis ulang dalam istilah combinators saja. Jadi, jenis dan harus menghasilkan, melalui aplikasi, jenis tautologi apa pun. Dan memang, dua aksioma di atas adalah tipe yang paling umum untuk $S,K$ $S$ $K$ $S$ dan $K$ .

chi
sumber

Lihatlah Microsoft's LINQ (Language INtegrated Query). Itu membuat ekstensif dan cukup langsung menggunakan kalkulus lambda untuk memanipulasi dan mengubah pohon ekspresi. Mungkin contoh yang paling lengkap dan canggih adalah Linq2SQL (implementasi SQL Server) yang secara efisien melakukan transformasi kompleks yang memisahkan bagian-bagian dari pohon ekspresi yang dapat didelegasikan ke server database.

Ini bukan teknologi pertama yang memungkinkan query yang menggabungkan data dari beberapa sumber, tetapi mungkin yang pertama mengotomatiskan penguraian dependensi untuk meningkatkan kemampuan manipulasi massal dari server database. Ini tidak sempurna (kadang-kadang Anda harus membantunya) tetapi itu bekerja kasar dengan sangat baik dan dengan perhatian pada detail Anda tidak akan dapatkan dari manusia.

Bila Anda lakukan harus membantu keluar, memahami kalkulus akan membawa Anda jauh ke arah mencari tahu apa yang mengganggu itu - sehingga selain Apa gunanya? ada jawaban Anda untuk Mengapa saya harus belajar ini ketika mesin akan melakukannya untuk saya?

Peter Wone
sumber