Um autômato é uma coisa do evento?

1. Introdução

Tendo ouvido dos lábios autoritários que “autômatos são uma coisa de evento” [3], percebi que autômatos finitos são marcados completamente. Julgue por si mesmo: na biblioteca Qt, um modelo de evento de autômatos [1] é implementado, na UML eles também são [2], analisamos os autômatos do pacote de extensão Simulink-Stateflow do sistema MATLAB [4] (daqui em diante simplesmente Stateflow) e sobre eventos, etc. etc. Nesse contexto, a afirmação do Ph.D. A.A. É impertinente interpretar de uma maneira diferente, porque nada mais pode ser, porque não pode ser.

Mas, se você se lembra da teoria dos autômatos finitos (TCA), não há uma palavra sobre autômatos de eventos nela! Mas, para contradizer a teoria, são necessários argumentos pesados. Existe alguma razão para duvidar do profissionalismo de D. Harell, como criador da notação na qual a linguagem UML, o pacote Stateflow, baseia suas idéias, que, por sua vez, não são desconhecidas por A.A. Impertinente? De fato, existem UML, Stateflow, programação SWITCH e outras opções de programação automática e, em um grau ou outro, funcionam com êxito.

Então, é possível remover o “estigma dos eventos” do modelo de máquina de estados finitos, separando os “costeletas das moscas”? I.e. separar a teoria dos autômatos e dos modelos computacionais semelhantes aos modelos de D. Harel. E considerar que estes últimos, embora utilizem a terminologia da teoria dos autômatos, representam, a julgar pela sua implementação, o desenvolvimento de um modelo de diagramas de blocos de programas.

Observação 1. Nesse caso, estamos falando sobre o modelo de gerenciamento de programa, e não sobre o próprio modelo de programa (para obter mais detalhes sobre os modelos, consulte [5]).

Portanto, lembre-se, a biblioteca Qt implementa um modelo de evento de uma máquina de estados finitos, que foi emprestada da UML. O mesmo modelo é implementado pelo Stateflow. I.e. a fonte dos eventos é a UML, onde os autômatos são baseados na notação proposta por D. Harel. Mas culpar o último por criar essa programação automática também não seria verdade, porque "Eventfulness" é uma tendência das abordagens modernas para a implementação de modelos de software. Ele é baseado em opiniões oficiais, como as mencionadas “máquinas são uma coisa do evento” e a alta popularidade de linguagens e tecnologias como a UML. Sem dúvida, este é o resultado da imitação de máquinas sob os princípios existentes de operação de sistemas operacionais.

Mas, repetimos, como não parece estranho, mas para alguns pode até se tornar notícia, na teoria dos autômatos não há modelo de evento de um autômato finito. Pelo menos na parte considerada clássica (veja para mais detalhes, por exemplo, [6] ou [7]). Existe uma clara contradição entre teoria e prática. Em tal situação, você precisa fazer algo com a teoria ou de alguma forma influenciar a prática. Mas, talvez, os programadores estejam certos em seu desejo de finalizar o modelo de uma máquina de estados finitos, incluindo o conceito de "evento" nela [8, 9]?

Mas como conectar os desejos dos programadores ao fato de que “as maiores dificuldades no uso da abordagem de autômatos estão relacionadas à compreensão dos recursos do funcionamento dos autômatos nos sistemas de eventos” (ver [8]). Gostaria de entender as causas de tais problemas e, nesse contexto, implementar máquinas de eventos e / ou seus análogos. Para esse propósito, para detalhes, tomamos a implementação de autômatos no Qt e os repetimos usando o modelo de um autômato finito clássico.

Essa implementação de autômatos de eventos é necessária para avaliar e / ou superar os "recursos" mencionados. O uso do modelo clássico também estenderá a teoria dos autômatos à prática da “programação de eventos”. E, no final, um analógico baseado em outro modelo expandirá apenas a área de aplicação de modelos de máquinas de estados finitos.

2. Eventos, sinais e identidade de gênero de autômatos

Na UML, um evento é "um fenômeno significativo que tem uma certa posição no tempo e no espaço ... e acarreta certas consequências" [10]. Um evento na teoria dos autômatos é um subconjunto dos caracteres de entrada representados pelos caracteres do alfabeto de saída (existe até o conceito de álgebra de eventos no TCA) [6]. A mesma coisa que causa a transição de um autômato é chamada de sinais de entrada na teoria dos autômatos. São as conseqüências e “a razão, a transição do autômato de um estado para outro. Nesse caso, os sinais de saída são "a resposta do autômato aos sinais de entrada". Ambos se referem a instantes de tempo determinados pelas transições correspondentes do autômato "[6]. Na UML, o sinal (sinal) é" uma entidade nomeada que serve como um meio de comunicação entre objetos ”[10].

Assim, os nomes dos termos são os mesmos, mas o significado investido neles é diferente. Embora, se você os reorganizar, poderá encontrar uma semelhança: fica claro que os eventos na UML correspondem aos sinais das máquinas de estados finitos no TCA. Mas, talvez, diferentes entidades também estejam ocultas sob o termo "máquina de estados finitos"? Vamos tentar descobrir, começando pelos eventos ...

O autômato de evento é um autômato passivo, porque funciona apenas no momento da chegada dos eventos. Por outro lado, o autômato clássico representa o modelo ativo. Ele funciona sem referência a nada (para mais detalhes sobre autômatos passivos e ativos, consulte [9]). Aqui a associação com dois corredores implora, onde o primeiro é impulsionado por chutes (eventos) e o segundo é executado por si só.

Ao contrário de [8], não associaremos inicialmente os momentos de ocorrência de eventos com o início do autômato. Portanto, permaneceremos na estrutura da teoria dos autômatos, que determina a natureza assíncrona do funcionamento dos autômatos em relação ao ambiente externo. Ele fala apenas de tempo discreto, no qual a mudança de estados é realizada por um período arbitrariamente pequeno, mas não igual a zero, em tempo real. E a razão para as transições é o estado atual e os sinais de entrada da máquina, onde as consequências são a instalação de um novo estado e os valores dos sinais de saída da máquina (para obter mais detalhes sobre a definição de máquinas, consulte [6]).

A teoria dos autômatos é flexível na determinação do tempo discreto, que é um modelo em tempo real. Portanto, um ciclo de tempo discreto pode ter um valor fixo ou flutuante de um intervalo em tempo real e, de acordo com isso, as máquinas são chamadas síncronas ou assíncronas. Ao mesmo tempo, o intervalo de tempo associado ao relógio pode ter qualquer valor, incluindo um valor infinitamente pequeno, mas não igual a zero.

Observação 2. Um modelo de máquina de estados finitos é um dos poucos modelos formais que inclui em sua definição um modelo em tempo real de forma explícita.

Como resultado, a velocidade formalmente "infinita" do autômato ativo permite que qualquer evento seja tratado como um sinal de entrada potencial (em termos de UML, a condição [11] corresponde a ele). A máquina precisará apenas "capturar" esses eventos / sinais e fazer uma pausa entre eles. Tudo isso realmente define o protocolo para o trabalho conjunto do meio e do autômato. O protocolo também deve resolver o problema de reconhecer eventos idênticos recebidos sucessivamente. Sem isso, por exemplo, dois símbolos idênticos, recebidos um após o outro, podem ser percebidos como um.

Formalmente, as nuances do processamento de eventos não são significativas (consulte o mesmo autômato abstrato), mas na implementação prática de algoritmos construídos pelo tipo de modelo de evento, elas devem ser levadas em consideração. No caso da biblioteca Qt, sua contabilidade está oculta nas classes de implementação do autômato. Além disso, levaremos em conta as diferenças entre autômatos clássicos e de eventos, usando o exemplo da implementação da calculadora mais simples de [1], onde é dada sua "implementação de evento". Em contraste com essa solução, modelos equivalentes serão criados com base na máquina clássica de estados finitos.

3. Modelos de calculadora

Então, vamos começar ... Chamamos sinais de eventos, evento de autômatos comuns ... ou na ordem inversa e / ou vice-versa? Ugh! Confuso. Em suma, o "glocky cuzdra shteko budlanula" completo e algo "cachos". Para descobrir quem é quem, o que e o que chamar, a maneira mais segura é escolher um "bokra" específico e "bater nele" ... O programa de "calculadora automática" continuará sendo esse "lado".

3.1 Modelo de calculadora ativo

Na fig. 1 mostra o modelo original da classe Calculator de [1]. Na aparência, parece uma máquina abstrata clássica sem saída. A diferença é que o Qt conecta ações quando entra e sai de um estado. Na saída, eles são acionados pelo sinal de saída () e, ao entrar no estado, pelo sinal de entrada (). Mas, observamos, essas ações não são representadas no gráfico de forma alguma.

Se compararmos o modelo na Fig. 1 com um autômato com um estado abstrato (seus outros nomes são estruturais, autômato lógico), pode-se ver facilmente que as ações na saída do estado correspondem aos sinais do autômato de Mealy e as ações na entrada correspondem aos sinais do autômato de Moore.
Observação 3. Além disso, considerando a implementação de software do modelo, não falaremos sobre sinais, eventos, condições, etc., mas sobre as ações dos autômatos, assumindo que no nível do programa eles estejam associados a determinadas ações do programa, que no caso geral representado por funções de software.

O chamado autômato Mili-Moore combinado (ou um autômato diferentemente misto [12]), equivalente ao autômato na Fig. 1, é mostrado na Fig. 2, onde as funções correspondentes aos sinais de entrada e saída do autômato também são mostradas à direita do gráfico.


Fig. 1. Diagrama da máquina de eventos da calculadora


Fig. 2. Calculadora da classe de autômatos Count Miley-Moore

Para um modelo semelhante a um autômato na Fig. 2, por ações de entrada / saída, queremos dizer predicados e ações que são funções-métodos de programa de classes [autômatos]. Os predicados analisam o estado atual dos elementos de memória (variáveis, propriedades de classe) de forma alguma (isso é importante!) Sem afetá-los, mas dependendo de seu valor, retorne um valor booleano. Ações de um valor não retornam, mas alteram os elementos de memória.
A partir da fig. 2 segue-se que o modelo da calculadora, como a “caixa preta”, possui quatro canais de entrada e sete canais de saída em termos do número de predicados e ações. É fácil ver que, em comparação com um autômato abstrato, que por definição não possui mais de um canal de entrada e de saída, um autômato estrutural com muitos canais é mais universal, flexível e conveniente.

O modelo na fig. 2 pode ser simplificado “colando” os estados 1 e 2. Para fazer isso, primeiro você precisa transformar o autômato original em um autômato Mealy. Nós o obtemos carregando os arcos que entram no estado dos sinais com os sinais representados pelos sinais dos vértices do autômato de Moore. Depois disso, a operação de colagem se torna aparente. O resultado da colagem dos estados no estado 2, que agora se torna inicial, é mostrado na Fig. 3)


Fig. 3. O resultado da transformação e colagem dos estados do autômato na Fig. 2

Explique a ação y1 e a variável nTypeButtons. No total, eles implementam um protocolo que simula eventos. A variável nTypeButtons determina o tipo de símbolos de entrada do autômato dividindo-os em símbolos digitais, símbolos de operação, o símbolo "reset" e o símbolo "igual". Seu valor igual a zero significa a ausência de caracteres de entrada (nenhuma das teclas da calculadora é pressionada). Após o processamento do símbolo, isso também significa que o símbolo de entrada é percebido automaticamente. Isso bloqueia a resposta ao caractere de entrada.

O código para a classe da calculadora criada no âmbito do ambiente de programação automática de componentes visuais (VKPa) [5] é mostrado nas listagens 1, 2.


Vamos explicar No VKPa, qualquer classe de autômato herda as propriedades da classe de autômato base LFsaAppl. O método Create () cria cópias das classes incluídas nas bibliotecas dinâmicas dos processos automáticos. O método virtual MooreAction () se sobrepõe quando um modelo de autômato Moore é selecionado, definindo ações associadas aos estados do autômato. Os métodos x [n] e y [n] são os predicados e ações associados aos canais de entrada / saída do autômato. O algoritmo de comportamento da classe [autômato] é representado pela tabela de transição (consulte a Listagem 2), que consiste em uma matriz de cadeias de caracteres do tipo LArc. O restante do código repete o código da classe de origem Calculator.


A Lista 2 de aviso contém três tabelas de salto (duas são comentadas). É assim que os recursos do controle dedicado são realizados quando, após a remoção do comentário, o comportamento da classe pode ser alterado "por clique" sem afetar seus métodos e propriedades. O método y10 e a linha correspondente na tabela de transição (consulte a linha marcada com o comentário SWICH) foram introduzidos para simular a tecnologia SWITCH (para obter mais detalhes, consulte [9]) dentro da estrutura da tecnologia VKPA. Nesse caso, o comportamento de qualquer autômato é modelado por uma chamada cíclica ao operador SWITCH, que imita o comportamento do autômato (aqui o autômato VKPa atua como um ambiente externo).

3.2 Modelo de calculadora passiva

O modelo ativo da calculadora varre constantemente os canais de entrada. Assim que o valor da variável nTypeButtons se torna diferente de zero, isso serve como um sinal da chegada do próximo símbolo à entrada do autômato. Como resultado, a transição e a ação y1 são acionadas, redefinindo a variável nTypeButtons, bloqueando o reativamento automático da máquina pelo mesmo caractere.
Diferentemente do modelo da “calculadora ativa”, um autômato de evento não pode, por definição, reprocessar um símbolo de entrada. Agora está claro que "as maiores dificuldades em usar a abordagem de autômatos ... em sistemas de eventos" parecem se resumir a suprimir a atividade de um autômato ativo e vincular seu funcionamento a eventos. Mostramos o procedimento para mudar para um autômato passivo usando o exemplo da “calculadora ativa” recém-criada.
O ambiente VKPa contém um modo de operação passo a passo, introduzido para depurar processos automáticos. Mas pode ser usado para simular máquinas de eventos. Para fazer isso, 1) defina o espaço do autômato no qual o autômato é colocado um modo de operação passo a passo (observe, não um autômato separado, mas todo o espaço do autômato que contém autômatos) e 2) relacione os momentos de ocorrência de eventos com a execução de uma etapa discreta da operação do espaço. A Listagem 3 demonstra como fazer isso, refletindo apenas as alterações feitas no modelo (o cabeçalho da classe permanece inalterado).


Aqui, primeiramente, é introduzido um estado [inicial] adicional, no qual a referência ao espaço em que a máquina está localizada e o link para o objeto que determina as propriedades do espaço (incluindo seu modo de operação) são verificados. Eh forma a ação de y12. Quando os links são configurados, ocorre uma transição para o [antigo] estado inicial do modelo da calculadora com a instalação de um modo de operação passo a passo do espaço do autômato.

Além disso, o modelo opera em um modo passo a passo da operação espacial. O lançamento de uma etapa implementa o código inserido nos manipuladores de eventos associados à entrada do próximo caractere (consulte a Listagem 3 para as alterações feitas nos métodos digitButtonPressed e operationButtonPressed).

4. porque

Por que inventar algo, se existe, como se pode supor, um modelo de evento mais avançado de D. Harel. E como pensar de maneira diferente se foi executada em UML, Stateflow, na biblioteca Qt, etc. etc. e não há muito pânico sobre suas falhas. Bem, eles chamaram os eventos de sinais e transformaram a máquina ativa em passiva ... E se o modelo, como eles dizem, também é formalmente equivalente às máquinas clássicas de Mili / Moore, então como não acreditar nele? E assim é, se todas essas declarações forem tomadas apenas com fé ...

Veja o início do evento (foi exatamente o que fizemos acima). Um autômato estrutural clássico possui, por exemplo, muitos canais de entrada, cada um dos quais associado a um sinal, e eles podem ser processados ​​simultaneamente / em paralelo. Mas a UML diz que “cada objeto pode processar apenas um evento de cada vez” e mesmo “se dois eventos ocorrerem simultaneamente, o objeto ainda os processará um de cada vez” [10]. Assim, no nível de definição, sinais e eventos são equivalentes, mas o idílio entra em colapso no processo de implementação de transições de modelo.

Considere o exemplo com o qual começo a testar / aprender qualquer idioma ou tecnologia. É sobre a implementação de software do modelo de elemento AND-NOT. No nível estrutural, corresponde à “caixa preta”, que possui dois canais de entrada e uma saída, e no algorítmico, o autômato mostrado na Fig. 4)


Fig. 4. O modelo de autômato do elemento AND NOT

Como criar um modelo de procedimento regular (consulte a Listagem 4) ou como implementar um autômato no VKPa (consulte a Listagem 5) é compreensível, mas como repetir isso com base no autômato de evento da biblioteca Qt não é muito claro devido ao problema de implementar a transição do estado “1” para indicar "0", o que requer a análise simultânea de vários eventos.

Listagem 4. Implementação de objeto do modelo de procedimento AND-NOT



Assim, permita que a implementação do modelo de evento do elemento NAND no âmbito das classes de autômatos Qt seja "lição de casa" para os Habrovanos. Só posso citar sua decisão no Stateflow como uma “cereja no bolo”. É mostrado na fig. 5. O relevo do Stateflow é usado aqui, o que permite não marcar a transição com um evento: se o nome do evento não for especificado, a transição ocorrerá quando ocorrer um evento (consulte o rótulo da transição em [13], por exemplo).


Fig. 5. Um modelo de autômato de um elemento AND-NOT no Stateflow

Assim, máquinas de estado são um modelo híbrido (ativo-passivo) de uma máquina. É verdade que não está claro como a máquina se comportará na ausência de nenhum evento. Pode-se supor que “congelará” em antecipação a eventos. E se não forem? I.e. no final, ainda é mais provável que seja um modelo de máquina passiva do que ativa. Embora apenas na aparência seja difícil distinguir deste último.

5. Conclusão

Em relação aos eventos, podemos dizer que, devido à atividade, a implementação do modelo clássico de autômatos parece preferível ao modelo de autômatos síncronos. Se falamos sobre programação automática em geral, o pacote de extensão Stateflow demonstra como pode ser um tipo de programação completamente diferente. Mas, infelizmente, até agora apenas em perspectiva, porque os problemas permanecem devido ao modelo computacional Stateflow, que permanece essencialmente um diagrama de blocos. Parece que, exatamente por essas razões, juntamente com os autômatos, a programação visual no Statefow é representada pela notação de fluxogramas.

Descobrir onde está a programação automática real e onde está a sua imitação é um dos nossos principais objetivos. No artigo anterior [5], resolvemos uma das tarefas básicas propostas - formulamos o conceito de programas de autômatos. Em seguida, você precisa lidar com a definição de um modelo de gerenciamento de programa, que deve ser autômato finito e ser eficaz e conveniente para os programadores.

Tendo lidado com os eventos, lançamos as bases para esse trabalho. Em outros artigos, já entenderemos os detalhes do modelo proposto por D. Harel. Seguindo um pouco à frente, dizemos que, para ser franco, ela distorceu o entendimento dos autômatos. Mas, por outro lado, devemos dar o devido devido, revelou problemas que não permitiriam, sem tê-lo, formar uma programação automática eficaz dentro da estrutura do modelo clássico que atrairia programadores.

Descobrimos acima que, pelo menos no nível do evento, os autômatos clássicos não têm problemas. Vamos entender mais ... Enquanto isso, isso é apenas o começo. Estamos esperando muitas coisas interessantes e, note, não indo além da teoria clássica dos autômatos. Isso é crucial se queremos uma programação verdadeiramente automatizada. Desejamos-lhe sucesso! :)

Referências

1. Borovsky A.N. Qt4.7. Programação prática em C ++. - SPb.: BHV-Petersburg, 2012 .-- 496 p.
2. BUCH G., RAMBO J., JACOBSON I. UML. Manual do usuário. Segunda edição. Akademiya IT: Moscou, 2007 - 493 p.
3. Shalyto A. A. Uma nova palestra sobre programação automática. 2019, [Recurso eletrônico], Modo de acesso: www.youtube.com/watch?v=PPWTxceMutk&feature=youtu.be , gratuito. Yaz. Russo (data do tratamento em 5 de dezembro de 2019).
4. Fluxo de estado. www.mathworks.com/products/stateflow.html , gratuito. Yaz. Inglês (data de circulação 7.01.2020).
5. Máquina de Turing, como modelo de programas de autômatos. habr.com/en/post/481998 , grátis. Yaz. Russo (data de circulação 7.01.2020).
6. Melikhov A.N. Gráficos orientados e máquinas de estados finitos. M.: Nauka, 1971. 416 p.
7. KUDRYAVTSEV VB, Aleshin S.V., PODKOLZIN A.S. Introdução à teoria dos autômatos - M .: Science. Cap. ed. Física-Matemática. lit., 1985 - 320 p.
8. Tukkel N.I., Shalyto A.A. Implementação de autômatos na programação de sistemas de eventos. "Programador", 2002. No. 4. C.74-80.
9. Polikarpova N., A. Shalyto A. Programação de autômatos. 2nd ed., St. Petersburg.: Peter, 2011 - 176 p.
10. Rambo J., Jacobson A., Butch G. UML: referência especial. - São Petersburgo: Peter, 2002 - 656 p.
11. Goma H. ​​UML. Projeto de sistemas em tempo real, aplicativos paralelos e distribuídos: por. do inglês - M.: DMK Press, 2002. - 2002. - 704 p.
12. SHALYTO A.A. Tecnologia SWITCH. Algoritmização e programação de tarefas de controle lógico. São Petersburgo: Nauka, 1998, 628 s.
13. Rogachev G.N. Notações de fluxo de estado. bourabai.kz/cm/stateflow13.htm , gratuito. Yaz. Russo (data do recurso 01.10.2020).