Apa itu kombinator dan bagaimana mereka diterapkan pada proyek pemrograman? (penjelasan praktis)

Apa itu kombinator?

Saya mencari:

• penjelasan praktis
• contoh bagaimana mereka digunakan
• contoh bagaimana kombinator meningkatkan kualitas / generalisasi kode

Saya tidak mencari:

• penjelasan tentang kombinator yang tidak membantu saya menyelesaikan pekerjaan (seperti kombinator-Y)

Dari sudut pandang praktis, kombinator adalah jenis konstruksi pemrograman yang memungkinkan Anda untuk menyatukan potongan-potongan logika dengan cara yang menarik dan sering maju. Biasanya menggunakannya tergantung pada kemungkinan untuk dapat mengemas kode yang dapat dieksekusi ke objek, sering disebut (karena alasan historis) fungsi lambda atau ekspresi lambda, tetapi jarak tempuh Anda dapat bervariasi.

Contoh sederhana dari kombinator (berguna) adalah yang mengambil dua fungsi lambda tanpa parameter, dan membuat yang baru yang menjalankannya secara berurutan. Combinator yang sebenarnya terlihat dalam pseudocode generik seperti ini:

func in_sequence(first, second):
  lambda ():
    first()
    second()

Hal penting yang menjadikan ini sebagai kombinator adalah fungsi anonim (fungsi lambda) pada baris kedua; ketika Anda menelepon

a = in_sequence(f, g)

objek yang dihasilkan a bukan hasil dari menjalankan pertama f () dan kemudian g (), tetapi itu adalah objek yang dapat Anda panggil nanti untuk mengeksekusi f () dan g () secara berurutan:

a() // a is a callable object, i.e. a function without parameters

Anda juga dapat memiliki kombinator yang menjalankan dua blok kode secara paralel:

func in_parallel(first, second):
  lambda ():
    t1 = start_thread(first)
    t2 = start_thread(second)
    wait(t1)
    wait(t2)

Dan lagi,

a = in_parallel(f, g)
a()

Yang keren adalah bahwa 'in_parallel' dan 'in_ berikutnyaence' keduanya adalah kombinator dengan tipe / tanda tangan yang sama, yaitu mereka berdua mengambil dua objek fungsi tanpa parameter dan mengembalikan yang baru. Anda sebenarnya dapat menulis hal-hal seperti

a = in_sequence(in_parallel(f, g), in_parallel(h, i))

dan itu berfungsi seperti yang diharapkan.

Pada dasarnya kombinator memungkinkan Anda untuk membangun alur kontrol program Anda (antara lain) secara prosedural dan fleksibel. Misalnya, jika Anda menggunakan kombinator in_parallel (..) untuk menjalankan paralelisme di program Anda, Anda bisa menambahkan debugging yang terkait dengan implementasi kombinator in_parallel itu sendiri. Nantinya, jika Anda mencurigai bahwa program Anda memiliki bug yang terkait dengan paralelisme, Anda dapat benar-benar mengimplementasikan kembali in_parallel:

in_parallel(first, second):
  in_sequence(first, second)

dan dengan satu pukulan, semua bagian paralel telah diubah menjadi yang berurutan!

Combinator sangat berguna jika digunakan dengan benar.

Namun, kombinator Y tidak diperlukan dalam kehidupan nyata. Ini adalah kombinator yang memungkinkan Anda untuk membuat fungsi rekursif diri, dan Anda dapat membuatnya dengan mudah dalam bahasa modern apa pun tanpa kombinator Y.

Adalah salah untuk menganggap Y-combinator sebagai sesuatu yang tidak akan "membantu menyelesaikan pekerjaan". Saya merasa sangat berguna dalam beberapa kesempatan. Kasus yang paling jelas adalah ketika Anda harus bootstrap dengan cepat beberapa bahasa yang ditafsirkan tertanam. Jika Anda memberikan seperangkat minimal primitif, yaitu sequence, select, call, constdan closure allocation, itu sudah cukup untuk membangun sebuah bahasa yang kompleks sewenang-wenang lengkap. Tidak diperlukan dukungan khusus untuk rekursi - ini dapat ditambahkan melalui kombinator titik tetap. Kalau tidak, Anda akan membutuhkan primitif yang jauh lebih rumit.

Kasus lain yang jelas untuk combinator adalah kebingungan. Kode yang diterjemahkan ke dalam kalkulus SKI praktis tidak dapat dibaca. Jika Anda benar-benar harus mengaburkan implementasi suatu algoritma, pertimbangkan untuk menggunakan kombinator, berikut adalah contohnya .

Dan, tentu saja, kombinator adalah alat penting untuk menerapkan bahasa fungsional. Pendekatan termudah (seperti pada contoh di atas) adalah melalui SKI atau kalkulus setara. Supercombinators digunakan dalam beberapa implementasi lainnya. Buku ini membahasnya secara mendalam.

Ini adalah lelucon , tetapi lelucon ini patut dibaca dengan sangat hati-hati, karena banyak teknik dan teori pemrograman misterius dibahas di sana.

Menggali sedikit, saya menemukan pertanyaan StackOverflow, Penjelasan yang bagus tentang "Combinators" (Untuk non matematikawan) itu adalah sepupu dekat dari pertanyaan ini. Salah satu jawaban menunjuk ke blog Reginald Braithwaite, Homoiconic , yang menghubungkan ke beberapa contoh yang berguna dari kombinator dalam kode (mis . K kombinator , diimplementasikan oleh Object#tapmetode Ruby - baca halaman untuk contoh mengapa itu berguna).

The Wikipedia halaman di combinatory Logic menggambarkan combinators lebih global.