Bagaimana perbedaan mesin negara dengan program komputer lainnya?

Saya telah melihat beberapa implementasi "Mesin Negara" di github. Sejauh yang saya mengerti, mesin keadaan mengambil input yang mungkin atau mungkin tidak mengubah negaranya menjadi salah satu dari set terbatas negara lain. Apa bedanya dengan program komputer lainnya?

Jika Anda ingin menjadi benar-benar hebat, setiap program komputer adalah Mesin Hingga Negara, karena bahkan jika Anda mengubah semua materi di seluruh alam semesta menjadi komputer, itu masih akan hanya memiliki memori yang terbatas, sehingga sejumlah negara terbatas, dan terbatas jumlah transisi antara negara-negara tersebut.

State Machines adalah model, seperti Lambda Calculus, Turing Machines, Random-Access Machines, Actor System, Object System, dan sebagainya. Beberapa masalah cenderung dimodelkan oleh mesin negara, beberapa tidak.

Proses Bisnis sering dimodelkan sebagai Mesin Negara bahkan sebelum komputer ada. Mereka secara alami meminjamkan diri pada pemikiran semacam itu.

Dari sudut pandang teoretis, itu tidak berbeda sama sekali. Tentu saja, dari sudut pandang teoritis Anda dapat menulis program apa pun dalam bahasa assembly dan itu akan bekerja dengan baik.

Sementara komputer yang digunakan oleh kode Anda mungkin secara matematis setara dengan mesin negara yang sangat, sangat rumit, seperti halnya program lain yang berjalan pada komputer lain, ada banyak masalah yang solusinya paling elegan adalah mesin keadaan terbatas sederhana yang menyatakan dan transisi memiliki makna khusus domain yang dibuat oleh pemrogram (sebagai lawan dari kompiler atau perancang perangkat keras).

Misalnya, salah satu cara klasik menerapkan ekspresi reguler adalah menafsirkan ekspresi reguler sebagai spesifikasi untuk mesin keadaan terbatas, membuat mesin seperti itu, lalu mengumpankannya ke string untuk menerima atau menolak . Lebih umum, setiap kali Anda ingin objek dalam program Anda untuk selalu memiliki salah satu dari sejumlah negara terbatas, dan menegakkan bahwa transisi antara negara-negara selalu terjadi dengan cara tertentu, membangun mesin negara mungkin merupakan solusi yang paling elegan .

mesin keadaan mengambil input yang mungkin atau mungkin tidak mengubah negaranya menjadi salah satu dari set terbatas negara lain. Apa bedanya dengan program komputer lainnya?

Beberapa jawaban di sini menekankan bahwa di alam semesta kita yang terbatas (semuanya) terbatas, semua program komputer berjalan dalam waktu terbatas, oleh karena itu secara teknis semuanya adalah mesin keadaan-terbatas. Itu "secara teknis benar (jenis terbaik yang benar)", tetapi juga benar-benar kehilangan intinya.

Intinya adalah ini: - Beberapa program komputer membutuhkan lebih banyak memori kerja ketika mereka mendapatkan input yang lebih besar dan lebih kompleks. Beberapa tidak.

Jika Anda menyadari hal ini, Anda akan mendapatkan wawasan teoretis-informatika yang memungkinkan Anda untuk menulis program yang lebih efisien dan elegan ketika Anda menghadapi masalah yang diberikan. Ini juga akan memungkinkan Anda untuk mengenali jenis masalah di mana ini mungkin berlaku.

Berikut adalah dua contoh mainan:

Masalah 1: Suatu program menerima daftar karakter pada input standar. Setelah semua karakter diproses, program harus mencetak apakah jumlah karakter "x" dalam input itu ganjil atau genap .

Masalah 2: Suatu program menerima daftar karakter pada input standar. Setelah semua karakter diproses, program harus mencetak apakah jumlah karakter "x" dalam input lebih kecil , sama , atau lebih besar dari jumlah karakter "y".

Anda mungkin ingin berhenti membaca sekarang, menyelesaikan masalah dalam bahasa pemrograman favorit Anda (atau hanya kodesemu), dan kembali lagi nanti.

...

Hal penting yang mungkin Anda perhatikan adalah sebagai berikut: Untuk menerapkan solusi untuk masalah 1 dengan benar, Anda hanya perlu satu bit memori. Anda tidak harus menghitung berapa banyak "x" yang sudah Anda proses - hanya apakah jumlah "x" yang diproses sejauh ini ganjil atau genap. Saat Anda menemukan "x" lainnya, balikkan bitnya. Di akhir program, lihat bit dan cetak jawabannya.

Apakah input Anda mengandung selusin karakter? Ribuan karakter? Karakter Googolplex (tentu saja, secara hipotetis)? Tidak apa-apa; sedikit memori yang bekerja masih akan cukup.

Anda tidak dapat melakukan hal yang sama dengan masalah 2. Saat membaca karakter, Anda harus mengingat perbedaan antara jumlah yang sudah diproses "x" dan "y"; jika tidak, Anda tidak dapat mencetak jawaban yang benar dengan andal. Anda mungkin menyadari bahwa Anda benar-benar tidak perlu mengingat kedua jumlah "x" 's dan 'y'' s - satunya perbedaan mereka, sejauh; satu nilai integer yang akan Anda tingkatkan ketika Anda menemukan "x" lainnya, dan berkurang ketika Anda menemukan "y" lainnya - tetapi tetap saja, jika Anda memutuskan untuk menggunakan mis. 32 bit memori untuk mempertahankan nilai ini, Anda mungkin mendapatkan input ( beberapa miliar karakter) yang tidak dapat Anda proses dengan benar dengan jumlah memori terbatas yang diberikan.

Inilah yang kami maksud dengan mengatakan bahwa masalah 1 dapat diselesaikan dengan "mesin negara", dan masalah 2 tidak bisa. Jumlah memori yang terbatas sudah cukup untuk input ukuran apa pun.

(Tentu saja, Anda juga bisa menulis solusi yang tidak efisien untuk masalah 1, di mana Anda akan mencoba menghitung semua "x", dan kemudian Anda mungkin juga mendapatkan masalah kehabisan memori. Tetapi perbedaannya adalah bahwa solusi efisien untuk masalah 1 ada , sementara solusi sama efisien untuk masalah 2 tidak tidak .)

Mengapa ini penting dalam kehidupan nyata?

Pertama, tidak seperti dengan dua contoh mainan ini, dilema mungkin bukan antara satu bit dan satu nilai integer, tetapi antara beberapa struktur data yang besar dan beberapa bahkan lebih besar. Kadang-kadang struktur data "yang lebih besar" tidak sesuai dengan memori komputer, atau cukup memperlambat program, bahkan untuk input yang realistis.

Kedua, solusi menggunakan mesin negara mungkin akan jauh lebih cepat. Juga akan skala secara linear dengan panjang input; artinya, memproses input 10 kali lebih lama akan membutuhkan waktu 10 kali lebih banyak (berbeda dengan misalnya waktu 100 kali lebih banyak). Itu properti yang diinginkan ketika Anda perlu memproses banyak data.

Ketiga, penggunaan memori terbatas vs tidak terbatas berdampak pada keamanan . Jika Anda menulis sebuah program yang hanya membutuhkan memori terbatas, Anda tidak perlu khawatir tentang kelebihan memori dan bagaimana mereka berpotensi disalahgunakan untuk membahayakan keamanan seluruh sistem.

Keempat, ini adalah bagian dari apa yang seharusnya menjadi kurikulum ilmu komputer standar di sekolah yang layak: bahasa formal , automata , kompleksitas komputasi , dan lain-lain. Untuk memahami gambaran yang lebih besar di balik desain komputer, dan bukan sekadar "uhh, saya menggabungkan beberapa kode dari internet, saya sangat berharap ini berhasil, tetapi saya tidak bisa memastikan" pendekatan.

Untuk mengambil keuntungan dari teori ini, Anda tidak benar-benar membutuhkan mesin khusus, kerangka kerja atau pustaka ... Anda hanya perlu menyadari "oh, bagian dari masalah ini sebenarnya dapat diselesaikan dengan menggunakan jumlah memori yang terbatas" dan menulis program Anda (dalam bahasa pemrograman favorit Anda) sesuai. Tetapi dalam beberapa situasi lebih baik menggunakan perpustakaan yang ada, jadi Anda tidak perlu menemukan kembali roda.

Seperti yang ditunjukkan oleh jawaban lain, tidak ada yang istimewa tentang mesin negara. Namun, sering bermanfaat untuk secara eksplisit menyatakan bahwa program kami mengimplementasikan FSM.

Pemrograman terdiri dari banyak menemukan abstraksi yang cocok untuk suatu masalah. Menggunakan abstraksi menyiratkan berbicara dalam hal abstraksi daripada dalam hal implementasi. Banyak proses secara inheren stateful, misalnya proses pendaftaran di situs web, atau proses check-out dalam aplikasi e-commerce. Jika saya memodelkan proses-proses itu, saya akan menggambar kotak-kotak yang dihubungkan dengan panah ke papan tulis - diagram keadaan. Di sini, mesin negara akan menjadi semacam pola desain dan berbicara tentang mesin negara akan dengan jelas mengomunikasikan maksud saya kepada kolega.

Program imperatif secara inheren stateful sehingga kami tidak selalu melihat ketika kami memperkenalkan negara. Misalnya dalam bahasa C, konstruksi bahasa tertentu seperti operator titik koma menandai "titik urutan", yang merupakan transisi keadaan dan memberlakukan pengurutan antar operasi. Hal-hal berbeda di lingkungan seperti bahasa fungsional murni seperti Haskell atau ketika menggunakan protokol stateless seperti HTTP. Tiba-tiba, keadaan apa pun harus menjadi eksplisit, dan secara eksplisit menjadikan desain kami sebagai mesin keadaan dapat membuatnya lebih mudah dikelola.

Mesin negara yang terbatas memainkan peran penting dalam penguraian, karena mereka sesuai dengan ekspresi reguler. Mengimplementasikan beberapa ekspresi reguler secara manual dapat menghasilkan kode yang sangat berbulu, yang paling buruk bahkan tidak benar. Ketika kami menyadari bahwa kami menerapkan mesin negara, kami dapat menggunakan berbagai teknik implementasi yang dikenal untuk membantu kami. Misalnya, kita bisa membuat status eksplisit dan menyimpan status saat ini dalam sebuah variabel. Atau, kita dapat membuat negara tersirat melalui aliran kontrol pada bahasa kita. Saya telah melakukan keduanya dalam keadaan yang berbeda, tetapi menyatakan bahwa kami menerapkan mesin negara (yang menampilkan transisi keadaan terbatas, keadaan awal, kondisi akhir yang diketahui, tidak ada rekursi, dan tidak ada keadaan tersirat melalui alokasi data yang persisten) daripada membuat program yang tidak dibatasi lebih mudah untuk diimplementasikan dan dipahami.

Saya jarang menggunakan perpustakaan mesin negara, karena semua bahasa pemrograman yang saya tahu membuatnya mudah untuk mengekspresikan mesin negara dalam bahasa itu dengan mudah dan efisien. Tetapi ada pengecualian: sementara automata deterministik mudah diimplementasikan, automata nondeterministic cukup non-trivial, karena mesin keadaan mungkin di beberapa negara pada saat yang sama. Menggunakan perpustakaan yang mengimplementasikan NFA atau menulis ulangnya membuat saya mengabaikan kesulitan ini dan fokus pada hal-hal yang sebenarnya penting.

Di luar penggunaan mesin negara sebagai desain dan mesin negara dalam ilmu komputer dan teori bahasa, sebenarnya tidak ada banyak kegunaan. Sirkuit logika stateful muncul di pikiran. Penggunaan utama mesin negara untuk programmer adalah belajar untuk berpikir dalam hal status dan transisi negara. Di mana program saya memiliki status implisit? Apakah saya benar menerapkan semua transisi negara? Apakah saya melewatkan sesuatu dan membuka status yang tidak valid? Pemikiran seperti itu menjadi sangat relevan lagi dalam pemrograman berorientasi objek, karena bidang anggota suatu objek berhubungan dengan state, dan metode dapat mempengaruhi transisi state. Saya akan ragu untuk secara eksplisit mengimplementasikan mesin negara dalam suatu objek, tetapi mesin negara dapat menjadi model mental yang cocok untuk perilaku tersebut.

Alasan utama untuk menulis perpustakaan mesin negara adalah untuk memastikan Anda telah memahami topik tersebut, tetapi dalam sebagian besar aplikasi Anda tidak akan membutuhkannya atau lebih baik memutar tangan mereka.