Bisakah semua kode direpresentasikan sebagai rangkaian operasi Peta / Filter / Kurangi?

16

Saya baru-baru ini refactoring potongan besar kode dan menggantinya dengan permintaan Linq.

Menghapus bias bahasa - Linq pada dasarnya adalah seperangkat Map / Filter dan Mengurangi operasi yang beroperasi pada urutan data.

Ini membuat saya berpikir, sejauh mana saya secara teoritis dapat mengambil ini. Apakah saya dapat menulis ulang seluruh basis kode menjadi serangkaian (atau bahkan satu) dari Map / Filter dan Mengurangi operasi.

Sayangnya saya dibayar untuk melakukan hal-hal yang berguna, jadi saya belum bisa bereksperimen lebih jauh, tetapi saya tidak bisa memikirkan struktur kode apa pun yang tidak dapat disusun ulang seperti itu. Kode efek samping dapat ditangani melalui monads .. Bahkan keluaran pada dasarnya memetakan alamat memori ke alamat layar.

Apakah ada sesuatu yang tidak bisa (secara teoritis) ditulis ulang sebagai permintaan Linq?

computer-science Mongus Pong
sumber
Untuk pohon lihat di sini: stackoverflow.com/questions/250377/…
blueberryfields
Saya selalu berpikir bahwa "mengurangi" sudah cukup untuk menjamin penyelesaian Turing (peta dan filter dapat diimplementasikan sebagai operasi pengurangan, bukan?) - setidaknya, bahasa fungsional yang setara dengan pengurangan. Saya tidak cukup tahu tentang Linq untuk memastikan seberapa dekat implementasi di sana mengikuti yang fungsional.
blueberryfields
1
Saya tidak tahu, tetapi aturan dasar yang kasar adalah bahwa apa pun yang akan dipertimbangkan siapa pun untuk menulis semua kode mereka akan menjadi Turing lengkap. Tetapi akibatnya adalah menjadi Turing yang lengkap tidak terlalu menarik.
psr
1
Saya setuju dengan psr; Saya pikir jawaban yang valid untuk pertanyaan ini perlu membahas kelengkapan Turing. Bukti mungkin mencoba untuk mengimplementasikan mesin Turing hanya menggunakan operasi ini.
Rob
Berpikir idle: Bahkan jika kita membiarkan omong kosong seperti my_list.map(_ignored => a copy of my_list), sepertinya ruang penggunaan program seperti itu dibatasi oleh beberapa polinomial (tergantung pada panjang program). Maka bahasa seperti itu tentu tidak bisa menghitung masalah yang tidak ada di PSPACE. Namun, karena banyak masalah dalam PSPACE dianggap tidak dapat ditangani, untuk mengatakan tidak ada kelas yang lebih besar, ini mungkin bukan pembatasan yang sangat serius.

Jawaban:

1

Ini disebut pemrograman fungsional, dan dianggap oleh banyak orang sebagai konsep dasar. inilah intro yang bagus tentang Joel On Software . Jawaban yang lebih teknis ada, tidak ada cara yang dikenal saat mengajukan pertanyaan komputer Anda (dengan cara yang didefinisikan dengan baik) yang tidak bisa dijawab melalui SKI kalkulus.

JP Mcgrady
sumber
1
Ada jauh lebih banyak untuk pemrograman fungsional daripada fungsi map, filterdan reduce(ini berjalan tiga kali jika kita mengabaikan kelengkapan turing dan menggunakan bahasa FP praktis). Bahkan, mereka kebetulan agak umum dan dengan demikian umumnya bermanfaat, tetapi sebenarnya aplikasi pemrograman fungsional sangat sederhana. Kalkulus lambda minimum dapat mendefinisikan fungsi-fungsi itu di antara banyak fungsi lainnya, bukan sebaliknya.
"Inilah intro yang bagus tentang Joel On Software" - yang berhasil membingungkan Fortran dengan Basic, jadi saya tidak akan menaruh banyak kepercayaan pada fakta-fakta lain di dalamnya.
quant_dev