Avtomatlarǵa tiykarlanǵan programmalastırıw
Avtomatlarǵa tiykarlanǵan programmalastırıw — bul programma yamasa onıń bir bólimi shekli-jaǵday mashinasınıń (FSM) yamasa basqa (kóbinese quramalıraq) formal avtomattıń modeli retinde qaralatuǵın programmalastırıw paradigması (avtomatlar teoriyasın qarań). Geyde múmkin bolǵan jaǵdaylardıń potencial sheksiz toplamı kirgiziledi hám bunday toplam tek sanaw emes, al quramalı strukturaǵa iye bolıwı múmkin.
Shekli-jaǵday mashinasına tiykarlanǵan programmalastırıw ulıwma alǵanda birdey, biraq, formal túrde aytqanda, barlıq múmkin bolǵan variantlardı qamtımaydı, sebebi FSM shekli-jaǵday mashinasın bildiredi, al avtomatlarǵa tiykarlanǵan programmalastırıw qatań mániste FSMlerdi paydalanıwdı minnetlemeydi.
Tómendegi qásiyetler avtomatlarǵa tiykarlanǵan programmalastırıwdıń tiykarǵı kórsetkishleri bolıp tabıladı:
- Programmanıń orınlanıw waqıt dáwiri avtomat qádemlerine shekem anıq bólingen. Hárbir qádem, negizinde, bir kirisiw noqatı bar kod bóliminiń (barlıq qádemler ushın birdey) orınlanıwı bolıp tabıladı. Bul bólim hár túrli jaǵdaylarǵa baylanıslı orınlanıwı ushın kishi bólimlerge bóliniwi múmkin, degen menen bul minnetli emes.
- Avtomat qádemleri arasındaǵı hár qanday baylanıs tek avtomat jaǵdayı dep atalǵan anıq belgilengen ózgeriwshiler toplamı arqalı ǵana múmkin. Hár qanday eki qádem arasında programmanıń lokal ózgeriwshilerdiń mánisleri, qaytıw adresleri, aǵımdaǵı kórsetpe kórsetkishi hám t.b. sıyaqlı óziniń jaǵdayınıń jasırın komponentleri bola almaydı. Yaǵnıy, pútkil programmanıń jaǵdayı, avtomat qádemine kiriwdiń hár qanday eki momentinde alınǵanda, tek avtomat jaǵdayı dep esaplanatuǵın ózgeriwshilerdiń mánislerinde ǵana ayırmashılıq etiwi múmkin.
Avtomatlarǵa tiykarlanǵan kodtıń pútkil orınlanıwı — bul avtomat qádemleriniń cikli.
Avtomatlarǵa tiykarlanǵan programmalastırıw túsinigin paydalanıwdıń jáne bir sebebi — bul usılda baǵdarlamashınıń programma haqqında oylaw stili Tyuring mashinaları, Markov algoritmleri hám t.b. paydalanıp matematikalıq wazıypalardı sheshiw ushın paydalanılatuǵın oylaw stiline júdá uqsas.
Qollanılıwı
Avtomatlarǵa tiykarlanǵan programmalastırıw leksikalıq hám sintaksislik analizlerde keń qollanıladı[1].
Bunnan tısqarı, avtomatlar túsiniginde oylaw (yaǵnıy, orınlanıw processin avtomat qádemlerine bóliw hám informaciyanı qádemnen qádemge anıq avtomat jaǵdayı arqalı ótkiziw) waqıyaǵa baǵdarlanǵan programmalastırıw ushın parallel processlerdi yamasa aǵımlardı paydalanıwǵa jalǵız alternativa retinde zárúr.
Jaǵdaylar hám jaǵday mashinaları túsinikleri kóbinese formal specifikaciya tarawında paydalanıladı. Mısalı, UML-ge tiykarlanǵan programmalıq támiynat arxitekturasın islep shıǵıw programmanıń háreketin anıqlaw ushın jaǵday diagrammaların paydalanadı. Sonday-aq hár túrli baylanıs protokolları kóbinese jaǵdaydıń anıq túsinigi paydalanılıp anıqlanadı.
Avtomatlar (qádemler hám jaǵdaylar) túsiniginde oylaw geypara programmalastırıw tilleriniń semantikasın táriyiplew ushın da paydalanılıwı múmkin. Mısalı, Refal tilinde jazılǵan programmanıń orınlanıwı abstrakt Refal mashinası dep atalatuǵın qádemler izbe-izligi retinde táriyiplenedi; mashinanıń jaǵdayı — bul kórinis (ózgeriwshilersiz qálegen Refal ańlatpası).
Scheme tilindegi dawam etiwler qádemler hám jaǵdaylar túsiniginde oylawdı talap etedi, degen menen Scheme ózi hesh qanday avtomatlarǵa baylanıslı emes (ol rekursiv). call/cc ózgesheliginiń islewi ushın, implementaciya orınlanıp atırǵan programmanıń pútkil jaǵdayın uslap alıwı kerek, bul tek jaǵdayda jasırın bólim bolmaǵanda ǵana múmkin. Bunday uslap alınǵan jaǵday dawam etiw dep ataladı hám onı (salıstırmalı túrde quramalı) avtomattıń jaǵdayı retinde qarawǵa boladı. Avtomat qádemi — bul aldınǵısınan keyingi dawam etiwdi shıǵarıw, al orınlanıw procesi — bunday qádemlerdiń cikli.
Aleksandr Ollongren óziniń kitabında[2] programmalastırıw tilleriniń semantikasın táriyiplewdiń tolıǵı menen formal avtomatlarǵa tiykarlanǵan Vena usılın túsindiredi.
STAT sisteması avtomatlarǵa tiykarlanǵan usıldı paydalanıwdıń jaqsı mısalı bolıp tabıladı; bul sistema, basqa ózgeshelikler menen birge, tolıǵı menen avtomatlarǵa baǵdarlanǵan STATL dep atalatuǵın ornatılǵan tildi óz ishine aladı.
Tariyxı
Avtomatlarǵa tiykarlanǵan usıllar formal til analizleri sıyaqlı avtomatlar teoriyasına tiykarlanǵan algoritmler bar bolǵan tarawlarda keń qollanılǵan.
Bul haqqındaǵı dáslepki maqalalardıń biri Djonson hám basqaları tárepinen 1968-jılı jazılǵan[3].
Avtomatlarǵa tiykarlanǵan programmalastırıwdıń ulıwma usıl retinde eń dáslepki atap ótiwleriniń biri Piter Naurdıń 1963-jılǵı maqalası[4]. Avtor bul usıldı Tyuring mashinası usılı dep ataydı, degen menen maqalada haqıyqıy Tyuring mashinası berilmegen; onıń ornına, qádemler hám jaǵdaylarǵa tiykarlanǵan usıl táriyiplengen.
Imperativ hám proceduralıq programmalastırıw menen salıstırıw
Jaǵday túsinigi tek avtomatlarǵa tiykarlanǵan programmalastırıwǵa tán emes[5]. Ulıwma alǵanda, jaǵday (yamasa programma jaǵdayı) hár qanday kompyuter programmasınıń orınlanıwı waqtında, orınlanıw dawamında ózgeriwi múmkin bolǵan barlıq informaciyanıń birikpesi retinde payda boladı. Mısalı, dástúrli imperativ programmanıń jaǵdayı tómendegilerden ibarat:
- barlıq ózgeriwshilerdiń mánisleri hám dinamikalıq yadta saqlanǵan informaciya;
- registrlerde saqlanǵan mánisler;
- stek mazmunı (sonıń ishinde lokal ózgeriwshilerdiń mánisleri hám qaytıw adresleri);
- kórsetpe kórsetkishiniń aǵımdaǵı mánisi.
Bular anıq bólimge (mısalı, ózgeriwshilerde saqlanǵan mánisler) hám jasırın bólimge (qaytıw adresleri hám kórsetpe kórsetkishi) bóliniwi múmkin.
Usını aytıp ótkennen soń, avtomatlarǵa tiykarlanǵan programma jaǵdaydıń jasırın bólimi minimallastırılǵan imperativ programmanıń arnawlı bir jaǵdayı retinde qaralıwı múmkin. Qádem kodı bólimine kiriwdiń eki hár túrli momentinde alınǵan pútkil programmanıń jaǵdayı tek avtomat jaǵdayında ǵana ayırmashılıq etiwi múmkin. Bul programmanıń analizin ápiwayılastıradı.
Obyektke baǵdarlanǵan programmalastırıw menen baylanısı
Obyektke baǵdarlanǵan programmalastırıw teoriyasında, obyekt ishki jaǵdayǵa iye dep aytıladı hám xabarlardı qabıllawǵa, olarǵa juwap beriwge, basqa obyektlerge xabarlar jiberiwge hám xabar menen islesiw waqtında óziniń ishki jaǵdayın ózgertiwge uqıplı. Anaǵurlım ámeliy terminologiyada, obyekttiń metodın shaqırıw obyektke xabar jiberiw menen birdey esaplanadı.
Solay etip, bir tárepten, obyektke baǵdarlanǵan programmalastırıwdan alınǵan obyektlerdi jaǵdayı jeke maydanlardıń kombinaciyası bolǵan avtomatlar (yamasa avtomatlardıń modelleri) retinde qarawǵa boladı hám bir yamasa bir neshe metodlar qádem retinde esaplanadı. Bunday metodlar bir-birin yamasa ózlerin tikkeley yamasa janapay túrde shaqıra almaydı, basqa jaǵdayda obyekt avtomatlarǵa tiykarlanǵan usılda ámelge asırılǵan dep esaplanıwı múmkin emes.
Ekinshi tárepten, obyekt avtomattıń modelin ámelge asırıw ushın jaqsı. Avtomatlarǵa tiykarlanǵan usıl obyektke baǵdarlanǵan til ishinde qollanılǵanda, avtomat modeli ádette bir klass tárepinen ámelge asırıladı, jaǵday klasstıń jeke maydanları menen kórsetiledi, al qádem bir metod retinde ámelge asırıladı; bunday metod ádette klasstıń jalǵız turaqlı emes publikalıq metodı bolıp tabıladı (konstruktorlar hám destruktorlardan basqa). Basqa publikalıq metodlar jaǵdaydı soray aladı, biraq onı ózgertpeydi. Barlıq ekinshi dárejeli metodlar (mısalı, belgili bir jaǵday qayta islewshileri) ádette klasstıń jeke bólimi ishinde jasırın boladı.
Derekler
- ↑ Aho, Alfred V.; Ullman, Jeffrey D.. The theory of parsing, translation and compiling. Englewood Cliffs, N. J.: Prentice-Hall, 1973. ISBN 0-13-914564-8.
- ↑ Definition of programming languages by interpreting automata.
- ↑ Johnson, W. L.; Porter (1968). Automatic generation of efficient lexical processors using finite state techniques. 11.
- ↑ Naur, Peter (September 1963). "The design of the GIER ALGOL compiler Part II". BIT Numerical Mathematics 3 (3): 145–166. doi:10.1007/BF01939983.
- ↑ "Automata-based programming". Scientific and Technical Journal of Information Technologies, Mechanics and Optics (53).