Bisakah program berorientasi objek dilihat sebagai Mesin Hingga Negara?

Ini mungkin pertanyaan filosofis / mendasar, tetapi saya hanya ingin menjelaskannya.

Dalam pemahaman saya, Finite State Machine adalah cara pemodelan sistem di mana output sistem tidak hanya akan bergantung pada input saat ini, tetapi juga keadaan sistem saat ini. Selain itu, seperti namanya, mesin negara terbatas dapat tersegmentasi dalam sejumlah negara terbatas N dengan keadaan dan perilaku masing-masing.

Jika ini benar, bukankah seharusnya setiap objek dengan data dan fungsi anggota menjadi keadaan dalam model berorientasi objek kami, menjadikan desain berorientasi objek sebagai mesin keadaan terbatas?

Jika itu bukan interpretasi FSM dalam desain objek, apa sebenarnya yang dimaksud orang ketika mereka menerapkan FSM dalam perangkat lunak? apakah saya melewatkan sesuatu?

Terima kasih

Setiap program berulir tunggal yang dijalankan pada mesin dengan jumlah penyimpanan terbatas dapat dimodelkan sebagai mesin keadaan terbatas. Keadaan tertentu dalam mesin keadaan terbatas akan mewakili nilai spesifik dari semua penyimpanan yang relevan — variabel lokal, variabel global, penyimpanan tumpukan, data yang saat ini ditukar dalam memori virtual, bahkan konten file yang relevan. Dengan kata lain, akan ada banyak negara dalam model negara yang terbatas, bahkan untuk program yang sangat sepele.

Bahkan jika satu-satunya status program Anda adalah variabel global tunggal dari tipe integer 32-bit, yang menyiratkan setidaknya 2 ^ 32 (lebih dari 4 miliar) negara. Dan itu bahkan tidak memperhitungkan penghitung program dan panggilan stack.

Model otomat push-down lebih realistis untuk hal semacam ini. Ini seperti otomat terbatas, tetapi memiliki konsep stack. Ini sebenarnya bukan tumpukan panggilan seperti pada kebanyakan bahasa pemrograman.

Ada penjelasan Wikipedia , tetapi jangan macet di bagian definisi formal.

Automata push-down digunakan untuk memodelkan perhitungan umum. Mesin Turing serupa , tetapi IIRC tidak identik - meskipun kemampuan komputasinya setara .

Terima kasih kepada kevin cline karena telah menunjukkan kesalahan di atas - seperti yang juga ditunjukkan oleh Wikipedia , push-down automata lebih kuat daripada mesin keadaan terbatas, tetapi kurang kuat daripada mesin Turing.

Sejujurnya aku tidak tahu di mana kentut otak ini berasal dari - saya lakukan tahu bahwa konteks tata bahasa sensitif lebih kuat daripada konteks bebas, dan bahwa konteks tata bahasa sensitif tidak dapat diurai menggunakan robot push-down sederhana. Saya bahkan tahu bahwa walaupun dimungkinkan untuk mengurai tata bahasa bebas konteks yang ambigu dalam waktu linier, umumnya diperlukan lebih dari otomat push-down (deterministik) untuk melakukan itu. Jadi bagaimana saya bisa sampai akhirnya percaya bahwa automaton push-down sama dengan mesin Turing adalah aneh.

Mungkin saya sedang memikirkan otomat push-down dengan beberapa mesin tambahan ditambahkan, tapi itu akan seperti menghitung otomat terbatas hingga setara dengan otomat push-down (hanya menambah dan mengeksploitasi tumpukan).

Automata push-down penting dalam penguraian. Saya cukup akrab dengan mereka dalam konteks itu, tetapi saya tidak pernah benar-benar mempelajarinya sebagai model komputasi sains-komputer, jadi saya tidak bisa memberikan lebih banyak detail daripada yang sudah saya miliki.

Dimungkinkan untuk memodelkan objek OOP tunggal sebagai mesin keadaan terbatas. Status mesin akan ditentukan oleh status semua variabel anggota. Biasanya, Anda hanya akan menghitung status yang valid antara panggilan metode (tidak selama). Sekali lagi, Anda pada umumnya akan memiliki banyak negara yang perlu dikhawatirkan — ini adalah sesuatu yang mungkin Anda gunakan sebagai model teoretis, tetapi Anda tidak ingin menyebutkan semua negara bagian itu, kecuali mungkin dalam kasus sepele.

Namun, cukup umum untuk memodelkan beberapa aspek dari keadaan suatu objek menggunakan mesin keadaan terbatas. Kasus umum adalah AI untuk objek game.

Ini juga apa yang biasanya dilakukan ketika mendefinisikan parser menggunakan model otomat push-down. Meskipun ada serangkaian negara terbatas dalam model negara, ini hanya memodelkan bagian dari negara pengurai - informasi tambahan disimpan dalam variabel tambahan di samping negara itu. Ini menyelesaikan misalnya masalah 4-miliar-negara-untuk-satu-bilangan bulat — jangan sebutkan semua negara bagian itu, cukup sertakan variabel bilangan bulat. Dalam beberapa hal ini masih merupakan bagian dari keadaan otomat push-down, tetapi ini merupakan pendekatan yang jauh lebih mudah dikelola daripada efeknya menggambar 4 miliar gelembung negara pada diagram.

Masalahnya bukanlah apakah sesuatu "adalah" atau "bukan" mesin negara yang terbatas. Mesin keadaan terbatas adalah model mental yang mungkin berguna untuk memahami sesuatu jika benda itu dapat dianggap sebagai satu.

Biasanya model mesin keadaan terbatas berlaku untuk hal-hal dengan sejumlah kecil negara, seperti tata bahasa biasa, atau sequencer instruksi komputer.

Untuk menjawab pertanyaan Anda secara langsung: hampir pasti tidak. Tampaknya tidak ada teori matematika formal untuk OOP dengan cara yang lambda kalkulus dan / atau Combinatory Logic di bawah pemrograman fungsional, atau Turing Machines di bawah pemrograman imperatif biasa.

Lihat pertanyaan stackoverflow ini untuk lebih lanjut.

Dugaan saya adalah bahwa kurangnya teori matematika yang mendasari adalah mengapa semua orang tahu apa "objek" ketika mereka melihatnya, tetapi tidak ada yang melihat "objek" sama seperti orang lain.

Tidak, tidak praktis juga. Mesin keadaan terbatas biasanya hanya mengingat satu bagian data: keadaan saat ini.

Aplikasi khas FSM adalah lexing atau parsing. Sebagai contoh, ketika kita melakukan lexing, itu (biasanya) cukup mudah untuk menyandikan tindakan untuk setiap input yang mungkin dalam hal kondisi saat ini, dan nilai input.

Sebagai contoh, kita mungkin memiliki NUMBER keadaan di mana kita membaca angka-angka angka. Jika karakter berikutnya yang kita baca adalah angka, kita tetap dalam status NUMBER. Jika ini spasi atau tab, kami akan mengembalikan digit dan kemudian maju ke kondisi WHITE_SPACE, atau sesuatu dengan urutan itu.

Sekarang, memang benar bahwa dalam FSM tipikal (terutama yang diterapkan dalam perangkat lunak) kita berakhir dengan potongan-potongan yang secara teknis tidak cukup cocok dengan FSM dicampur dengan FSM itu sendiri. Misalnya, ketika kita membaca angka angka, Anda sering akan menyimpan posisi angka pertama, jadi ketika Anda sampai di ujung Anda dapat dengan mudah menghitung nilai angka.

FSM sendiri, memiliki beberapa keterbatasan - tidak memiliki mekanisme penghitungan. Pertimbangkan, misalnya, bahasa yang menggunakan "/ " untuk memulai komentar dan " /" untuk mengakhiri komentar. Lexernya mungkin memiliki status KOMENTAR yang dimasukkan ketika melihat token ' / '. Tidak ada cara pada saat ini (singkat menambahkan negara lain seperti COMMENT2) untuk mendeteksi "/ " lain dan menyadari bahwa itu berurusan dengan komentar bersarang. Sebaliknya, di negara komentar, itu akan diakui */sebagai menyuruhnya meninggalkan negara komentar, dan apa pun meninggalkannya di negara komentar.

Seperti yang disebutkan, Anda tentu saja dapat menyertakan status COMMENT2 untuk komentar bersarang - dan dalam kondisi tersebut, COMMENT3, dan sebagainya. Namun, pada titik tertentu, Anda akan bosan menambahkan lebih banyak status, dan itu akan menentukan kedalaman bersarang maksimum yang Anda izinkan untuk komentar. Dengan beberapa bentuk parser lain (yaitu, bukan mesin keadaan murni, tetapi sesuatu yang memiliki memori untuk menghitungnya) Anda bisa langsung melacak kedalaman bersarang Anda, sehingga Anda tetap dalam keadaan KOMENTAR sampai Anda mencapai tanda komentar dekat yang menyeimbangkan yang pertama, sehingga penghitung Anda kembali ke 0 dan Anda meninggalkan status KOMENTAR.

Seperti yang saya katakan, ketika Anda menambahkan penghitung seperti itu, apa yang Anda miliki tidak lagi benar-benar FSM. Pada saat yang sama, itu adalah benar-benar cukup dekat - khususnya, cukup dekat bahwa Anda dapat mensimulasikan meja dengan hanya menambahkan lebih banyak negara.

Dalam kasus yang khas, namun, ketika berbicara seseorang tentang menerapkan FSM dalam perangkat lunak, mereka akan tetap cukup "murni". Secara khusus, perangkat lunak akan bereaksi terhadap input saat ini hanya berdasarkan pada kondisi saat ini, dan nilai input itu sendiri. Jika reaksinya tergantung pada banyak hal lain, mereka biasanya tidak akan menyebutnya mesin negara (setidaknya jika mereka tahu apa yang mereka bicarakan).

Saya tidak percaya jawaban yang diterima sepenuhnya benar.

Anda tidak dapat membuat model program arbitrer yang ditulis dalam bahasa Turing Lengkap, apakah itu berorientasi objek atau tidak, sebagai Mesin Hingga Negara. Hampir semua bahasa komputer modern, seperti Java, C ++, atau Smalltalk, Turing Lengkap.

Misalnya, Anda tidak dapat membuat Mesin Status Hingga untuk mengenali urutan objek di mana Anda memiliki n instance dari satu objek diikuti oleh n instance dari objek lain karena Mesin Finite State tidak mampu menulis n ke variabel. Mereka hanya dapat membaca input dan beralih ke status.