Bisakah * program * apa saja diekspresikan tanpa status?

13

Ini adalah pertanyaan teoretis, tetapi setelah bertahun-tahun pemrograman dalam apa yang sekarang saya sadari adalah teknik imperatif "normal", terutama menggunakan C ++, saya telah menemukan dunia pemrograman fungsional lain ini, yang saya temukan secara tidak sengaja ketika saya belajar JavaScript dengan santai.

Hal ini membuat saya bertanya-tanya apakah Anda secara teknis dapat mengganti program berorientasi negara lengkap dengan implementasi berbeda yang murni fungsional dan tanpa negara?

Ini adalah ide yang menarik dan saya harus mengakui bahwa ada kejelasan dan keanggunan dalam pemrograman fungsional yang benar-benar mengejutkan pikiran saya.

javascript functional-programming haskell state turing-completeness pembuat johnbakers
sumber
1
Jawaban StackOverflow yang relevan: stackoverflow.com/questions/3722084/...
jfriend00
Ada atau tidaknya keadaan yang bertahan dari satu titik waktu ke titik berikutnya tidak tergantung pada paradigma pemrograman apa yang Anda gunakan, tetapi pada masalah atau tugas apa yang Anda koding. Jika Anda menghitung berapa kali tombol diklik, maka jelas ada keadaan untuk mencatat penghitung itu dan tidak masalah teknik pengkodean apa yang Anda gunakan, harus ada status untuk melacak hitungan selama proses. Jadi, tugas tertentu itu tidak dapat diselesaikan tanpa status di sepanjang jalan tidak peduli bagaimana Anda mengkodekannya.
jfriend00
6
Jika Anda ingin membahas keadaan; jelas menyatakan diperlukan, jika hanya untuk program itu sendiri. Kedengarannya seperti Anda berpikir keadaan berubah-ubah vs tidak berubah - Anda mungkin ingin menunjukkan yang Anda maksud dalam pertanyaan.
Billy ONeal
1
Itu seperti menanyakan apakah semua program dapat dikonversi menjadi mesin Turing sejati. Secara teknis ya, bahkan program yang menyimpan dan memuat dari basis data namun menjadi lebih sulit untuk mensimulasikan perilaku ini dalam mesin Turing. Demikian juga, Anda dapat memiliki program yang sisi pengontrol dalam arsitektur MVC dihapus dan Anda melakukan semua panggilan, meskipun sekali lagi, itu menjadi lebih sulit untuk ditangani (Anda pada dasarnya menjadi pengontrol untuk membuat program tanpa kewarganegaraan).
Neil

Jawaban:

17

Jawaban singkat: ya. Menurut Wikipedia, kesetaraan kalkulus lambda ke mesin Turing sebagai model komputasi universal ditunjukkan pada 1937 oleh Alan Turing. Model komputasi mesin Turing adalah apa yang biasanya Anda pikirkan ketika berbicara tentang pemrograman imperatif atau stateful, dan kalkulus lambda adalah formalisasi matematis dari "pemrograman fungsional murni".

Dugaan bahwa setiap model perhitungan yang efektif dapat melakukan perhitungan yang sama seperti mesin Turing, dan sebaliknya. Ini disebut tesis Church-Turing . Namun, penolakan ini tidak dapat dibuktikan, karena istilah "model perhitungan efektif" yang intuitif atau kurang lebih intuitif (mungkin seseorang akan menemukan model baru di masa mendatang?)

Doc Brown
sumber
2
Argumen Anda yang sama dapat dikembalikan dengan mengatakan bahwa menjadi lamba calculus setara dengan mesin tur, setiap perhitungan harus memiliki status (kurang lebih tersembunyi). Apakah diwakili sebagai eksternal ke kode (melalui variabel) atau internal ke aliran (melalui panggilan fungsi berbasis stack) selalu "negara" adalah.
Emilio Garavaglia
3
Kalkulus Lambda memiliki status; Kendalanya adalah bahwa negara tidak dapat diubah. Keadaan yang tidak dapat berubah masih merupakan keadaan. Parameter untuk fungsi, termasuk lambdas, masih menyatakan; mungkin Anda ingin fungsi memiliki perilaku yang berbeda dengan parameter yang berbeda.
Billy ONeal
@emilio Menyatakan bahwa ada solusi berbasis negara setara untuk masalah (seperti yang Anda jelaskan) bukan bukti bahwa tidak ada versi stateless dari solusi itu ada.
Billy ONeal
2
@EmilioGaravaglia Anda kemudian merujuk pada status penerjemah kalkulus lambda. Saat berargumen dalam kalkulus lambda, tidak perlu beralasan tentang keadaan. Juga aspek "Mutabilitas" berbeda.
wirrbel
1
@EmilioGaravglia: Status dalam pemrograman imperatif adalah konfigurasi memori pada suatu waktu, di sini ruang parameter diberikan oleh semua nilai memori yang mungkin dan status adalah satu konfigurasi pada satu waktu (pita dari mesin turing). Saat menulis program dalam kalkulus lambda, tidak ada entitas langsung seperti bidang memori. Eksekusi program adalah penerapan transformasi lambda. Langkah-langkah menengah mungkin menyerupai "negara", namun mereka hanya ekspresi setara dengan nilai yang sama. Tidak ada yang berubah selama evaluasi, ekspresi hanya ditulis ulang dan diproses menjadi bentuk "sederhana".
wirrbel
14

Dalam sistem dinamis apa pun, "keadaan" adalah yang membuat masa kini Anda dipengaruhi oleh masa lalu atau masa depan Anda (panah waktu bukanlah masalah matematika, hanya kendala fisik).

Apakah Anda memiliki sesuatu untuk "diingat" atau itu tergantung pada apa yang Anda lakukan, Anda memiliki keadaan.

Sistem tanpa status bukan "dinamis": itu hanya fungsi kombinatorial. Itu mungkin tidak memiliki keadaan, tetapi - untuk menghasilkan hasil yang berbeda - perlu suatu keadaan yang disediakan.

Sekarang, tergantung pada model komputasi yang Anda rujuk, negara dapat diwakili secara eksplisit (dalam bentuk variabel) atau secara implisit (dalam bentuk "alamat pengirim").

ketika Anda melakukannya, fna(fnb(x))Anda memberikan status ke fnb yang pada gilirannya akan menghasilkan keadaan untuk fna. Hal ini disebabkan oleh fakta yang xada sebelum fnb disebut (jadi, itu berasal dari "masa lalu" sendiri).

Ini bukan masalah "keberadaan negara" atau "negara tidak ada". Ini adalah mater dari "Saya peduli" atau "Saya tidak".

Emilio Garavaglia
sumber
0

Keadaan berarti kemampuan untuk menanggapi rangsangan saat ini dengan cara yang tergantung pada rangsangan masa lalu, bukan hanya berdasarkan rangsangan saat ini.

Program murni fungsional hanyalah fungsi. Jadi untuk aplikasi praktis, program yang murni fungsional ini memasangkan sepasang (old_state * present_stimulus) dan mengeluarkan pasangan (new_state * present_response). Sebuah "looper" eksternal yang diperlukan diperlukan untuk menunggu stimulus berikutnya dan menyebarkan negara.

Program yang murni fungsional tidak memiliki status intrinsik, dan -tidak dapat digunakan untuk aplikasi praktis secara langsung.

Dengan demikian, tidak ada program yang berorientasi negara dapat diganti dengan implementasi yang berbeda yang murni fungsional dan tanpa negara.

Atsby
sumber
0

Anda dapat menghindari keadaan yang bisa berubah secara eksplisit selama Anda tidak harus berinteraksi dengan dunia luar.

Dalam JavaScript agar program Anda benar-benar memiliki efek di luar mengambil siklus prosesor, Anda harus memodifikasi Dom atau objek Window, dan API ini stateful. Tapi saya kira Anda bisa membuat pembungkus yang melewati objek Dom dan Window sebagai parameter ke kode JavaScript, dan kemudian menerima Dom / Window baru sebagai output. Ini akan mengisolasi kode JavaScript dari keadaan bisa berubah.

Tentu saja Anda masih mengandalkan negara, karena jendela browser dan DOM secara alami. Setiap aplikasi interaktif secara inheren stateful, tetapi Anda masih dapat menyusun kode Anda sedemikian rupa untuk meminimalkan keadaan eksplisit.

Pertanyaan yang berbeda adalah apakah itu ide yang bagus. Bahkan Haskell, yang merupakan bahasa fungsional murni dengan desain, termasuk 'state' monad, yang memungkinkan Anda untuk mensimulasikan keadaan yang bisa berubah. Ini menunjukkan bahwa keadaan yang dapat berubah secara eksplisit terkadang benar-benar merupakan pola yang diinginkan.

JacquesB
sumber
0

Pikirkan tentang bagaimana Anda akan mengimplementasikan "mesin negara" dalam bahasa pemrograman tanpa negara.

Anda mungkin benar-benar bisa melakukannya tetapi Anda akhirnya akan menggunakan nama fungsi sebagai penyimpanan. Diakhiri dengan gobblyday gook seperti:

if (sm.atBegining()) sm.start() else if (sm.done()) sm.stop() ) else sm.progress()
James Anderson
sumber