Bayangkan sebuah bahasa pemrograman fungsional yang hanya tipe datanya berupa skalar numerik dan susunan array yang sewenang-wenang. Bahasa tidak memiliki sarana iterasi tanpa batas, jadi yang berikut ini tidak diizinkan:
- loop eksplisit (tidak banyak digunakan tanpa efek samping)
- pengulangan
- fungsi kelas satu yang arbitrer (tidak ada kombinator)
Namun, bahasa tersebut memiliki:
- fungsi tingkat atas
- ikatan mengikat lexically lexically
- kontrol aliran bercabang
- fungsi skalar matematika dan logika umum
- beberapa konstruktor array sederhana seperti isian (n, x) yang membuat array n-elemen dengan nilai identik x
- yang paling penting: seperangkat terbatas operator tingkat tinggi yang melakukan iterasi terstruktur paralel (seperti peta, perkecil, pindai, semua-pasangan).
Untuk lebih spesifik tentang operator paralel data:
- y = peta (f, x) => y [i] = f [i]
- y = mengurangi (f, a, x) => y = f (a, f (y [p [0]], f (y [p [1]], ...))) untuk beberapa permutasi p
- y = memindai (f, a, x) => y [i] = mengurangi (f, a, y [0 ... i-1])
- y = semua pasangan (f, x, y) => y [i, j] = f (x [i], y [j])
Kita dapat memiliki operator lain juga, tetapi untuk memenuhi syarat mereka harus memiliki waktu berjalan polinomial, dapat diimplementasikan di bawah beberapa model yang wajar dari perhitungan paralel data, dan digunakan di sebagian besar ruang polinomial.
Jelas ada beberapa konstruksi yang tidak dapat diekspresikan dalam bahasa ini, seperti:
while f(x) > tol:
x <- update(x)
Apa yang bisa kami ungkapkan dalam sistem ini? Apakah kita hanya terbatas pada masalah pencarian di FP? Bisakah kita menangkap semua algoritma waktu polinomial? Juga, apakah ada beberapa set minimal operator untuk kelas ini?
sumber
Jawaban saya yang lain menunjukkan kekurangan dalam bahasa yang digunakan. Dalam jawaban ini saya akan memberikan rincian lebih lanjut tentang masalah dengan koeksistensi lipatan dan terungkap dalam bahasa total. Kemudian saya akan mengusulkan resolusi dan menunjukkan bahwa semua masalah dalam P (dan memang banyak lagi) dapat diselesaikan dalam bahasa yang diperluas ini.
Melipat dalam bahasa total akan menggunakan daftar:
Berlangsung dalam bahasa total menghasilkan aliran, yang berpotensi tidak terikat:
Sayangnya, daftar dan aliran hidup di dunia yang berbeda, sehingga operator ini tidak dapat dikomposisikan. Kami membutuhkan korespondensi parsial:
Operator aliran menanamkan daftar ke aliran terbatas. Fungsi daftar mengekstrak elemen n pertama (atau lebih sedikit jika aliran berakhir sebelumnya) ke dalam daftar. Dengan demikian, kami memiliki persamaan berikut:
Sebagai optimalisasi efisiensi, kami sepenuhnya dapat memotong aliran sebagai struktur data perantara:
Sekarang saya akan membuat sketsa bukti bahwa ini (dengan operator lain sudah tersirat dalam pertanyaan awal) memungkinkan kita mensimulasikan algoritma waktu polinomial.
Menurut definisi, bahasa L adalah dalam P ketika ada mesin Turing M dan polinom p sehingga keanggotaan x dalam L dapat diputuskan dengan menjalankan M paling banyak iterasi p (n) di mana n = | x |. Dengan argumen standar, keadaan pita mesin dalam iterasi k dapat dikodekan dengan daftar panjang paling banyak 2k +1, meskipun pita mesin itu tak terbatas.
Idenya sekarang adalah untuk mewakili transisi M sebagai fungsi dari daftar ke daftar. Pengerjaan mesin akan dilakukan dengan membuka keadaan awal dengan fungsi transisi. Ini menghasilkan aliran daftar. Asumsi bahwa L dalam P berarti kita tidak perlu melihat lebih jauh dari elemen p (n) ke dalam aliran. Dengan demikian kita dapat menyusun lipatan dengan
list p(n)
untuk mendapatkan daftar yang terbatas. Akhirnya, kami melipatnya untuk memeriksa apakah jawaban untuk masalah keputusan itu ya atau tidak.Lebih umum, ini menunjukkan bahwa setiap kali kita memiliki algoritma yang waktu penghentiannya dapat dibatasi oleh fungsi yang dapat dihitung dalam bahasa, kita dapat mensimulasikannya. Ini juga menunjukkan mengapa sesuatu seperti fungsi Ackermann tidak dapat disimulasikan: itu adalah batasannya sendiri, jadi ada masalah ayam dan telur.
sumber
Ini adalah bahasa yang sangat berpalut. Coba pemrograman fungsi faktorial:
Masalahnya adalah bahasa Anda hanya memiliki lipatan tetapi tidak terbuka. Cara alami mengekspresikan faktorial adalah dengan menyusun lipatan n ke dalam daftar [1, 2, ..., n] dengan lipatan yang merobeknya sambil mengalikan.
Apakah Anda benar-benar tertarik dengan bahasa spesifik ini atau pada pemrograman fungsional total secara umum? Jelas bahwa bahasa Anda paling banyak dapat mengekspresikan algoritma waktu polinomial. Sistem F (kalkulus lambda polimorfik) dapat mengekspresikan monster seperti fungsi Ackermann dengan mudah. Bahkan jika minat Anda pada algoritma waktu polinomial, Anda sering membutuhkan ruang siku super polinomial untuk mengekspresikannya secara alami.
Sunting: Seperti yang ditunjukkan Dave, NESL adalah salah satu dari bahasa pemrograman paralel-fungsional data mani tetapi sangat jauh dari total (bahkan tidak mencoba). Keluarga APL memiliki jalur paralel evolusi dan memiliki subset aljabar total (hindari operator fixed-point). Jika fokus pertanyaan Anda adalah totalitas, David Turner telah menulis beberapa makalah yang bagus di bidang ini meskipun tidak secara khusus pada pemrograman data-paralel.
sumber