Apakah otomat merupakan suatu peristiwa?

1. Pendahuluan

Setelah mendengar dari bibir otoritatif bahwa "automata adalah suatu peristiwa" [3], saya menyadari bahwa automata terbatas bermerek sepenuhnya. Nilai sendiri: di perpustakaan Qt, model acara automata [1] diimplementasikan, di UML mereka juga [2], kita melihat automata dari paket ekstensi Simulink-Stateflow dari sistem MATLAB [4] (selanjutnya disebut hanya sebagai Stateflow) dan ada tentang peristiwa, dll. dll. Dalam konteks ini, pernyataan Ph.D. A.A. Itu nakal untuk menafsirkan dengan cara yang berbeda, karena tidak ada yang lain, karena tidak mungkin.

Tetapi, jika Anda mengingat teori finite automata (TCA), maka tidak ada satu kata pun tentang automata acara di dalamnya! Tetapi untuk membantah teorinya, diperlukan argumen yang berbobot. Apakah ada alasan untuk meragukan profesionalisme D. Harell, sebagai pencipta notasi di mana bahasa UML, paket Stateflow, mendasarkan ide-idenya, yang, pada gilirannya, tidak asing dengan A.A. Nakal? Memang, UML, Stateflow, pemrograman SWITCH, dan opsi pemrograman otomatis lainnya ada dan, sampai taraf tertentu, berhasil.

Jadi mungkinkah untuk menghapus "stigma peristiwa" dari model mesin keadaan terbatas dengan memisahkan "irisan daging dari lalat"? Yaitu pisahkan teori automata dan model komputasi yang mirip dengan model D. Harel. Dan untuk mempertimbangkan bahwa yang terakhir, meskipun menggunakan terminologi teori automata, mewakili, menilai dari implementasinya, pengembangan model diagram blok program.

Catatan 1. Dalam hal ini, kita berbicara tentang model manajemen program, dan bukan tentang model program itu sendiri (untuk detail lebih lanjut tentang model, lihat [5]).

Jadi, ingat, perpustakaan Qt mengimplementasikan model acara dari mesin negara terbatas, yang dipinjam dari UML. Model yang sama diimplementasikan oleh Stateflow. Yaitu sumber acara adalah UML, di mana automata didasarkan pada notasi yang diusulkan oleh D. Harel. Tetapi menyalahkan yang terakhir untuk membuat pemrograman otomatis seperti itu juga tidak akan benar, karena "Kejadian" adalah kecenderungan pendekatan modern untuk implementasi model perangkat lunak. Ini didasarkan pada pendapat otoritatif seperti yang disebutkan "mesin adalah suatu peristiwa", dan popularitas tinggi bahasa dan teknologi seperti UML. Tanpa ragu, ini adalah hasil dari peniruan mesin di bawah prinsip operasi sistem operasi yang ada.

Tapi, kami ulangi, karena sepertinya tidak aneh, tetapi bagi sebagian orang itu bahkan mungkin menjadi berita, dalam teori automata tidak ada model kejadian dari robot terbatas. Setidaknya di bagian itu yang dianggap klasik (lihat untuk detail lebih lanjut, misalnya, [6] atau [7]). Ada kontradiksi yang jelas antara teori dan praktik. Dalam situasi seperti itu, Anda perlu melakukan sesuatu dengan teori atau memengaruhi praktik. Tapi, mungkin, programmer benar dalam keinginan mereka untuk menyelesaikan model mesin negara yang terbatas dengan memasukkan konsep "acara" di dalamnya [8, 9]?

Tetapi bagaimana menghubungkan keinginan pemrogram dengan fakta bahwa "kesulitan terbesar dalam menggunakan pendekatan automaton terhubung dengan memahami fitur fungsi automata dalam sistem acara" (lihat [8]). Saya ingin memahami penyebab masalah seperti itu dan, dalam konteks ini, menerapkan mesin acara dan / atau analog mereka. Untuk tujuan ini, untuk spesifik, kami mengambil implementasi automata di Qt dan mengulanginya menggunakan model otomat terbatas klasik.

Implementasi seperti automata acara diperlukan untuk mengevaluasi dan / atau mengatasi "fitur" yang disebutkan. Menggunakan model klasik akan memperluas teori automata ke praktik "pemrograman acara" juga. Dan, pada akhirnya, analog yang didasarkan pada model lain hanya akan memperluas area penerapan model mesin keadaan terbatas.

2. Peristiwa, sinyal, dan identitas gender automata

Dalam UML, suatu peristiwa adalah "sebuah fenomena signifikan yang memiliki posisi tertentu dalam ruang dan waktu ... dan membawa konsekuensi tertentu" [10]. Suatu peristiwa dalam teori automata adalah subset dari karakter input yang diwakili oleh karakter alfabet keluaran (bahkan ada konsep aljabar peristiwa dalam TCA) [6]. Hal yang sama yang menyebabkan transisi otomat disebut sinyal input dalam teori automata. Mereka adalah konsekuensi dan “alasannya, transisi otomat dari satu kondisi ke kondisi lainnya. Dalam hal ini, sinyal output adalah "respons otomat terhadap sinyal input." Keduanya mengacu pada waktu yang ditentukan oleh transisi automaton yang sesuai. [6]. Dalam UML, sinyal (sinyal) adalah "entitas bernama yang berfungsi sebagai alat komunikasi." antar benda ”[10].

Dengan demikian, nama-nama istilahnya sama, tetapi makna yang diinvestasikan di dalamnya berbeda. Meskipun, jika Anda mengatur ulang, Anda dapat menemukan kesamaan: menjadi jelas bahwa peristiwa di UML sesuai dengan sinyal mesin keadaan terbatas di TCA. Tapi, mungkin, entitas yang berbeda juga tersembunyi di bawah istilah "mesin negara terbatas"? Mari kita coba mencari tahu, dimulai dengan acara ...

Acara automaton adalah robot pasif, karena hanya berfungsi pada saat kedatangan acara. Sebaliknya, robot klasik mewakili model aktif. Ini berfungsi tanpa merujuk pada apa pun (untuk detail lebih lanjut tentang automata pasif dan aktif, lihat [9]). Di sini hubungan dengan dua pelari memohon, di mana yang pertama didorong oleh tendangan (peristiwa), dan yang kedua berjalan dengan sendirinya.

Berbeda dengan [8], pada awalnya kami tidak akan mengaitkan momen-momen kejadian peristiwa dengan permulaan otomat. Jadi kita akan tetap dalam kerangka teori automata, yang menentukan sifat asinkron dari fungsi automata sehubungan dengan lingkungan eksternal. Ini hanya berbicara tentang waktu diskrit, di mana perubahan negara dilakukan untuk periode waktu-kecil yang sewenang-wenang, tetapi tidak sama dengan nol. Dan alasan untuk transisi adalah keadaan saat ini dan sinyal input dari mesin, di mana konsekuensinya adalah pemasangan status baru dan nilai-nilai sinyal output dari mesin (untuk rincian lebih lanjut tentang definisi mesin lihat [6]).

Teori Automata fleksibel dalam menentukan waktu diskrit, yang merupakan model waktu nyata. Jadi, siklus waktu diskrit dapat memiliki nilai tetap atau mengambang dari interval waktu-nyata, dan sesuai dengan ini, mesin disebut sinkron atau asinkron. Pada saat yang sama, interval waktu yang terkait dengan jam dapat memiliki nilai apa pun, termasuk nilai yang sangat kecil, tetapi tidak sama dengan nol.

Catatan 2. Model mesin keadaan terbatas adalah salah satu dari beberapa model formal yang termasuk dalam definisi model real-time dalam bentuk eksplisit.

Akibatnya, kecepatan "tak terbatas" resmi dari otomat aktif memungkinkan setiap peristiwa diperlakukan sebagai sinyal input potensial (dalam hal UML, kondisi [11] sesuai dengan itu). Mesin hanya perlu "menangkap" peristiwa / sinyal tersebut dan berhenti di antara keduanya. Semua ini sebenarnya mendefinisikan protokol untuk kerja bersama medium dan mesin. Protokol juga harus menyelesaikan masalah mengenali kejadian identik yang diterima secara berturut-turut. Tanpa ini, misalnya, dua simbol yang identik, yang diterima satu demi satu, dapat dianggap sebagai satu.

Secara formal, nuansa pemrosesan peristiwa tidak signifikan (lihat automata abstrak yang sama), tetapi dalam implementasi praktis dari algoritma yang dibangun oleh jenis model peristiwa, mereka harus diperhitungkan. Dalam kasus perpustakaan Qt, akuntansi mereka disembunyikan di kelas implementasi otomat. Lebih lanjut, kami akan memperhitungkan perbedaan antara event dan automata klasik menggunakan contoh implementasi kalkulator paling sederhana dari [1], di mana “implementasi event” diberikan. Berbeda dengan solusi ini, model yang setara akan dibuat berdasarkan pada mesin state hingga klasik.

3. Model Kalkulator

Jadi, mari kita mulai ... Kita menyebut sinyal peristiwa, peristiwa automata biasa ... atau dalam urutan terbalik dan / atau sebaliknya? Ugh! Bingung. Singkatnya, "cuzdra shteko budlanula" yang lengkap dan sesuatu yang "ikal". Untuk mengetahui siapa itu siapa, apa dan apa yang harus dihubungi, cara paling pasti adalah memilih "bokra" tertentu dan "menabraknya" ... Program "kalkulator otomatis" akan terus menjadi "sisi" seperti itu.

3.1. Model kalkulator aktif

Dalam gbr. 1 menunjukkan model asli dari Kalkulator kelas dari [1]. Secara tampilan, ini terlihat seperti mesin abstrak klasik tanpa jalan keluar. Perbedaannya adalah bahwa Qt menghubungkan tindakan ketika masuk dan keluar dari keadaan. Pada output, mereka dipicu oleh sinyal yang keluar (), dan saat memasuki keadaan, oleh sinyal yang dimasukkan (). Namun, kami perhatikan, tindakan ini tidak terwakili dalam grafik dengan cara apa pun.

Jika kita membandingkan model pada Gambar. 1 dengan otomat dengan keadaan abstrak (nama lainnya adalah struktural, automaton logis), orang dapat dengan mudah melihat bahwa tindakan di pintu keluar dari negara sesuai dengan sinyal dari otomat Mealy, dan tindakan di pintu masuk sesuai dengan sinyal dari otomat Moore.
Catatan 3. Selanjutnya, dengan mempertimbangkan implementasi perangkat lunak model, kami tidak akan berbicara tentang sinyal, peristiwa, kondisi, dll., Tetapi tentang tindakan automata, dengan asumsi bahwa pada tingkat program mereka terkait dengan tindakan program tertentu, yang dalam kasus umum diwakili oleh fungsi perangkat lunak.

Apa yang disebut automaton Mili-Moore gabungan (atau automaton campuran berbeda [12]), setara dengan automaton pada Gambar. 1, ditunjukkan pada Gambar. 2, di mana fungsi yang sesuai dengan sinyal input dan output dari otomat juga ditampilkan di sebelah kanan grafik.


Fig. 1. Diagram mesin acara kalkulator


Fig. 2. Hitung Miley-Moore Kalkulator kelas automaton

Untuk model yang mirip dengan otomat pada Gambar. 2, dengan tindakan input / output yang kami maksudkan adalah predikat dan tindakan yang merupakan metode-metode fungsi program dari kelas [automaton]. Predikat menganalisis keadaan elemen memori saat ini (variabel, properti kelas) dengan cara apa pun (ini penting!) Tanpa memengaruhi mereka, tetapi tergantung pada nilainya, kembalikan nilai Boolean. Tindakan nilai tidak kembali, tetapi mengubah elemen memori.
Dari ara. 2 itu mengikuti bahwa model kalkulator, seperti "kotak hitam", memiliki empat saluran input dan tujuh saluran output dalam hal jumlah predikat dan tindakan. Sangat mudah untuk melihat bahwa dibandingkan dengan otomat abstrak, yang menurut definisi tidak memiliki lebih dari satu input dan satu saluran keluaran, otomat struktural yang memiliki banyak saluran lebih universal, fleksibel dan nyaman.

Model dalam gbr. 2 dapat disederhanakan dengan "menempelkan" status 1 dan 2. Untuk melakukan ini, pertama-tama Anda harus mengubah automaton asli menjadi otomat Mealy. Kami mendapatkannya dengan memuat busur memasuki keadaan sinyal dengan sinyal yang diwakili oleh sinyal dari simpul otomat Moore. Setelah ini, operasi perekatan menjadi jelas. Hasil pengeleman status ke status 2, yang sekarang menjadi awal, ditunjukkan pada Gambar. 3.


Fig. 3. Hasil transformasi dan perekatan keadaan otomat pada Gambar. 2

Jelaskan tindakan y1 dan variabel nTypeButtons. Secara total, mereka menerapkan protokol yang mensimulasikan peristiwa. Variabel nTypeButtons menentukan jenis simbol input automaton dengan membaginya menjadi simbol digital, simbol operasi, simbol "reset" dan simbol "sama". Nilainya sama dengan nol berarti tidak adanya karakter input (tidak ada tombol kalkulator yang ditekan). Setelah memproses simbol, ini juga berarti bahwa simbol input dirasakan secara otomatis. Ini memblokir respons terhadap karakter input.

Kode untuk kelas kalkulator yang dibuat dalam kerangka lingkungan pemrograman komponen visual otomatis (VKPa) [5] ditunjukkan dalam daftar 1, 2.


Mari kita jelaskan. Dalam VKPa, setiap kelas otomat mewarisi sifat-sifat dari kelas otomat dasar LFsaAppl. Metode Create () membuat salinan kelas yang termasuk dalam pustaka dinamis proses otomatis. Metode MooreAction () virtual tumpang tindih ketika model otomat Moore dipilih, mendefinisikan tindakan yang terkait dengan keadaan otomat. Metode x [n] dan y [n] adalah predikat dan tindakan yang terkait dengan saluran input / output otomat. Algoritme perilaku kelas [otomat] diwakili oleh tabel transisi (lihat Listing 2), yang terdiri dari array string tipe LArc. Sisa kode mengulangi kode dari Kalkulator kelas sumber.


Pemberitahuan Listing 2 berisi tiga tabel lompatan (dua dikomentari). Ini adalah bagaimana kemampuan kontrol khusus direalisasikan ketika, setelah menghapus komentar, perilaku kelas dapat diubah "dengan klik" tanpa memengaruhi metode dan propertinya. Metode y10 dan garis yang sesuai dalam tabel transisi (lihat baris yang ditandai dengan komentar SWICH) diperkenalkan untuk memodelkan teknologi SWITCH (untuk lebih jelasnya lihat [9]) dalam kerangka teknologi VKPA. Dalam hal ini, perilaku robot apa pun dimodelkan dengan panggilan siklik ke operator SWITCH, yang meniru perilaku robot tersebut (di sini robot VKPa bertindak sebagai lingkungan eksternal).

3.2. Model kalkulator pasif

Model kalkulator aktif secara konstan memindai saluran input. Segera setelah nilai variabel nTypeButtons menjadi nol, ini berfungsi sebagai tanda kedatangan simbol berikutnya ke input otomat. Akibatnya, transisi dan tindakan y1 dipicu, mengatur ulang variabel nTypeButtons, memblokir mesin otomatis yang dipicu oleh karakter yang sama.
Berbeda dengan model "kalkulator aktif", robot peristiwa tidak dapat, menurut definisi, memproses ulang simbol input. Sekarang jelas bahwa "kesulitan terbesar dalam menggunakan pendekatan otomat ... dalam sistem acara" tampaknya muncul untuk menekan aktivitas automaton aktif dan menghubungkan fungsinya dengan peristiwa. Kami menunjukkan prosedur untuk beralih ke robot pasif menggunakan contoh "kalkulator aktif" yang baru dibuat.
Lingkungan VKPa berisi mode operasi selangkah demi selangkah yang diperkenalkan untuk proses debugging otomatis. Tetapi dapat digunakan untuk mensimulasikan mesin acara. Untuk melakukan ini, 1) mengatur ruang otomat di mana otomat ditempatkan mode operasi langkah-demi-langkah (perhatikan, bukan otomat terpisah, tetapi seluruh ruang otomat yang berisi automata), dan 2) mengaitkan momen-momen kejadian peristiwa dengan eksekusi satu langkah terpisah dari operasi ruang. Listing 3 menunjukkan bagaimana melakukan ini, hanya mencerminkan perubahan yang dilakukan pada model (header kelas tetap tidak berubah).


Di sini, pertama, status [awal] tambahan diperkenalkan, di mana referensi ke ruang di mana mesin berada, dan tautan ke objek yang menentukan sifat-sifat ruang (termasuk mode operasinya) diperiksa. Eh membentuk aksi y12. Ketika tautan diatur, ada transisi ke keadaan awal [sebelumnya] dari model kalkulator dengan pemasangan mode operasi langkah-demi-langkah dari ruang otomat.

Lebih lanjut, model ini beroperasi dalam mode operasi ruang angkasa selangkah demi selangkah. Peluncuran satu langkah mengimplementasikan kode yang dimasukkan ke event handler yang terkait dengan input karakter berikutnya (lihat Listing 3 untuk perubahan yang dilakukan pada digitTombol Ditekan dan metode operasiTombol Ditekan).

4. Mengapa?

Mengapa menemukan sesuatu, jika ada, seperti yang dapat diasumsikan, model acara D. Harel yang lebih maju. Dan bagaimana cara berpikir yang berbeda jika dijalankan di UML, Stateflow, di perpustakaan Qt, dll. dll. dan tidak ada banyak panik tentang kekurangannya. Nah, mereka menyebut peristiwa sinyal, dan mengubah mesin aktif menjadi pasif ... Dan jika model, seperti yang mereka katakan, juga secara formal setara dengan mesin Mili / Moore klasik, lalu bagaimana tidak percaya? Dan begitulah, jika semua pernyataan ini diambil hanya dengan iman ...

Ikuti awal acara (ini persis seperti yang kami lakukan di atas). Otomat struktural klasik memiliki, misalnya, banyak saluran input, yang masing-masing terkait dengan sinyal, dan mereka dapat diproses secara bersamaan / secara paralel. Tetapi UML mengatakan bahwa “setiap objek hanya dapat memproses satu peristiwa pada satu waktu” dan bahkan “jika dua peristiwa terjadi secara bersamaan, objek tersebut masih akan memprosesnya satu per satu” [10]. Dengan demikian, pada tingkat definisi, sinyal dan peristiwa adalah setara, tetapi idyll runtuh dalam proses implementasi transisi model.

Pertimbangkan contoh yang dengannya saya mulai menguji / mempelajari bahasa atau teknologi apa pun. Ini tentang implementasi perangkat lunak dari model elemen AND-NOT. Pada tingkat struktural, itu sesuai dengan "kotak hitam", yang memiliki dua saluran input dan satu output, dan pada yang algoritmik, otomat ditunjukkan pada Gambar. 4.


Fig. 4. Model otomat elemen DAN TIDAK

Bagaimana cara membuat model prosedural reguler (lihat Listing 4) atau bagaimana mengimplementasikan otomaton dalam VKPa (lihat Listing 5) dapat dimengerti, tetapi bagaimana mengulang ini berdasarkan automaton event dari perpustakaan Qt tidak begitu jelas karena masalah implementasi transisi dari negara “1” untuk menyatakan "0", yang memerlukan analisis simultan dari beberapa peristiwa.

Listing 4. Obyek implementasi model prosedural AND-NOT



Dengan demikian, biarkan implementasi model acara elemen NAND dalam kerangka kerja kelas otomat Qt menjadi "pekerjaan rumah" bagi warga Habrovans. Saya hanya bisa mengutip keputusannya di Stateflow sebagai "cherry on the cake". Itu ditunjukkan dalam gambar. 5. Bantuan Stateflow digunakan di sini, yang memungkinkan tidak menandai transisi dengan suatu peristiwa: jika nama acara tidak ditentukan, maka transisi akan terjadi ketika peristiwa apa pun terjadi (lihat label transisi pada [13] untuk contoh).


Fig. 5. Model otomat elemen AND-NOT di Stateflow

Dengan demikian, mesin negara adalah model mesin hybrid (aktif-pasif). Benar, tidak jelas bagaimana mesin akan berperilaku tanpa adanya peristiwa sama sekali. Dapat diasumsikan bahwa itu akan "membeku" untuk mengantisipasi peristiwa. Dan jika tidak? Yaitu pada akhirnya, itu masih lebih cenderung pasif daripada model mesin yang aktif. Meskipun hanya dalam penampilan, sulit untuk membedakan dari yang terakhir.

5. Kesimpulan

Sehubungan dengan peristiwa, kita dapat mengatakan bahwa, karena aktivitas, implementasi model klasik automata terlihat lebih disukai daripada model automata sinkron. Jika kita berbicara tentang pemrograman otomatis secara umum, paket ekstensi Stateflow menunjukkan jenis pemrograman yang benar-benar berbeda. Tapi, sayangnya, sejauh ini hanya dalam perspektif, karena masalah tetap karena model komputasi Stateflow, yang pada dasarnya tetap diagram blok. Tampaknya tepat karena alasan ini, bersama dengan automata, pemrograman visual di Statefow diwakili oleh notasi diagram alur.

Untuk mengetahui di mana pemrograman otomatis sebenarnya, dan di mana tiruannya, adalah salah satu tujuan utama kami. Dalam artikel sebelumnya [5], kami memecahkan salah satu tugas dasar yang diajukan - kami merumuskan konsep program otomat. Selanjutnya, Anda perlu berurusan dengan definisi model manajemen program, yang seharusnya menjadi otomat-terbatas dan menjadi efektif dan nyaman untuk programmer.

Setelah menangani berbagai peristiwa, kami meletakkan dasar untuk pekerjaan semacam itu. Dalam artikel selanjutnya, kita akan sudah memahami detail model yang diusulkan oleh D. Harel. Berjalan sedikit di depan, kami katakan bahwa, terus terang saja, dia mendistorsi pemahaman automata. Tetapi, di sisi lain, di sini kita harus memberikan haknya, dia mengungkapkan masalah yang tidak akan memungkinkan, tanpa dia, untuk membentuk pemrograman otomatis yang efektif dalam kerangka model klasik yang akan menarik para programmer.

Kami menemukan di atas bahwa, setidaknya, pada tingkat acara, automata klasik tidak memiliki masalah. Kami akan mengerti lebih jauh ... Sementara itu, ini hanya permulaan. Kami sedang menunggu banyak hal menarik, dan, perhatikan, tidak melampaui teori klasik automata. Ini sangat penting jika kita ingin pemrograman yang benar-benar otomatis. Semoga sukses! :)

Referensi

1. Borovsky A.N. Qt4.7. Praktis pemrograman C ++. - SPb.: BHV-Petersburg, 2012 .-- 496 hal.
2. BUCH G., RAMBO J., JACOBSON I. UML. Panduan pengguna. Edisi kedua. Akademiya IT: Moscow, 2007 .-- 493 hal.
3. Shalyto A. A. Kuliah baru tentang pemrograman otomatis. 2019, [Sumber daya elektronik], Mode akses: www.youtube.com/watch?v=PPWTxceMutk&feature=youtu.be , gratis. Yaz. Rusia (tanggal perawatan 5 Desember 2019).
4. Stateflow. www.mathworks.com/products/stateflow.html , gratis. Yaz. Bahasa inggris (tanggal sirkulasi 7.01.2020).
5. Mesin Turing, sebagai model program otomat. habr.com/en/post/481998 , gratis. Yaz. Rusia (tanggal sirkulasi 7.01.2020).
6. Melikhov A.N. Grafik berorientasi dan mesin negara hingga. - M.: Nauka, 1971. - 416 hal.
7. KUDRYAVTSEV VB, Aleshin S.V., PODKOLZIN A.S. Pengantar teori automata - M.: Ilmu. Ch. ed. Fisika-Matematika. lit., 1985.-- 320 hal.
8. Tukkel N.I., Shalyto A.A. Implementasi automata saat pemrograman sistem acara. "Programmer", 2002. No. 4. C.74-80.
9. Polikarpova N., A. Shalyto A. pemrograman Automaton. 2nd ed., St. Petersburg.: Peter, 2011 .-- 176 hal.
10. Rambo J., Jacobson A., Butch G. UML: referensi khusus. - St. Petersburg: Peter, 2002 .-- 656 hal.
11. Goma H. ​​UML. Desain sistem waktu-nyata, aplikasi paralel dan terdistribusi: Per. dari bahasa inggris - M.: DMK Press, 2002. - 2002. - 704 p.
12. SHALYTO A.A. Teknologi BERALIH. Algoritma dan pemrograman tugas kontrol logika. St. Petersburg: Nauka, 1998.628 s.
13. Rogachev G.N. Stateflow notations. bourabai.kz/cm/stateflow13.htm , gratis. Yaz. Rusia (tanggal banding 01.10.2020).