Modelo de gerenciamento automatizado de programas

1. Introdução

Em [1], foi dada uma resposta à questão do que é considerado programação automática (AP), mas o modelo de uma máquina de estados finitos (SC) não foi descrito em detalhes como um modelo de controle de programas automáticos. É claro que um autômato abstrato puro não é adequado para esse papel, porque limitado pelo número de canais. Mas o modelo estrutural do autômato, bem como a teoria do autômato estrutural correspondente a ele, ainda não permite dar uma resposta sobre a escolha do modelo do autômato.

O problema começa com o fato de que, dentre os muitos trabalhos sobre a teoria dos autômatos finitos (ACT), poucos são os que definem o modelo de um autômato finito estrutural (ACS). É verdade que se pode entender que um autômato estrutural é um diagrama [estrutural] de autômatos elementares (elementos funcionais) que implementa um modelo de um autômato abstrato [2]. Lembre-se de que, de acordo com a teoria, tudo começa com a criação de um modelo de dispositivo na forma de um autômato abstrato e, em seguida, a tarefa é sintetizar um circuito digital que o implementa [3].

A programação à primeira vista parece um pouco com uma síntese de circuitos digitais. Mas só a princípio. Em primeiro lugar, lá e ali tudo começa com um algoritmo. Em segundo lugar, as questões estruturais da organização e implementação de circuitos digitais e programação têm muito em comum, especialmente no contexto da programação paralela. Mas discutiremos o tópico do paralelismo separadamente. Enquanto isso, nossa tarefa é escolher e / ou modificar o modelo de uma máquina de estados finitos, o que seria compreensível, conveniente e agradável para programadores estragados por várias ferramentas de software.

É verdade que a pergunta é imediatamente lógica - por que mais um “kit de ferramentas automático” incomum? Vamos tentar responder a essa pergunta definindo um modelo de controle automático [aninhado], considerando também suas vantagens em comparação com o modelo de programação usual.

2. Definição do modelo de controle de programas automáticos

No processo de evolução, a prática da programação formou certos requisitos para o modelo de gerenciamento do programa. Deve-se reconhecer que o modelo de uma máquina clássica de estados finitos corresponde pouco a eles. E se a tarefa é usar autômatos na programação, ela precisa ser adaptada. É desejável fazer isso no quadro da teoria dos autômatos. As principais reivindicações para o AP existente são reduzidas ao fato de que essa condição é violada.

Definição 1. Chamamos de forma normal disjuntiva de autômatos finitos (DNKA) autômatos finitos totalmente definidos cujas transições são rotuladas por conjunções elementares de variáveis ​​lógicas.

O modelo de DNA é baseado em modelos formais de autômatos totalmente (totalmente) definidos com um estado abstrato [4] e autômatos lógicos [5].

Definição 2. Chamamos a forma disjuntiva de um autômato finito (DFA), um autômato na forma de um DFA contendo apenas transições resultantes .

As transições marcadas com sinais de saída e as transições com um traço no lugar dos sinais de saída que alteram o estado atual do autômato são classificadas como transições efetivas. As transições que não estão incluídas na descrição do autômato disjuntivo constituem uma adição da DKA (DDA) ao autômato do DFA totalmente definido. Tal adição é um autômato que consiste em estados isolados com transições na forma de loops e traços no lugar dos sinais de saída.

3. O modelo de memória para o modelo de cálculo AP

A presença de muitas entradas e saídas do DFA define o paralelismo dos operadores / funções de software associados a ele. Para sua correta implementação, é necessário um modelo de memória do tipo CREW (leitura simultânea exclusiva - gravação) [6]. Dentro de sua estrutura, a leitura dos valores atuais dos dados é permitida por parte do conjunto de todas as funções (predicados e ações), e apenas uma delas pode alterar dados gerais para ações executáveis ​​paralelas.

O modelo de controle automático, em contraste com o modelo de computação multithread, limita claramente a execução dos operadores / funções do programa automático aos limites de um ciclo de tempo discreto. Em tal situação, quaisquer alterações na memória por ações executadas no ciclo de clock atual podem ser gravadas na “memória de sombra” , para que, depois de concluídas e antes do início do próximo ciclo de clock discreto, elas se tornem seus novos valores.

A interação dos operadores do programa de autômatos com a memória será chamada de modelo de memória de sombra . Este modelo é uma parte essencial do modelo geral de programação automática. Garante a correção da operação paralela dos operadores de ponto de acesso e simplifica a programação de processos paralelos.

Dentro da estrutura do modelo de memória, mecanismos complexos e pouco confiáveis ​​para a sincronização multi-threaded dos processos não são realmente necessários (para obter mais detalhes, consulte [7]). Porém, se necessário, devido à equivalência de autômatos e esquemas gráficos de algoritmos (GAW) [8], o modelo de programação automática não limita sua aplicação.

4. Modelos aninhados e inerciais de autômatos

A tarefa de criar um modelo do elemento lógico do atraso, escolhido como exemplo, por um lado, demonstra os problemas do modelo clássico do autômato e, por outro lado, reflete as qualidades do modelo DFA que resolve problemas algorítmicos com meios mais visuais e convenientes. O modelo introduzido de autômatos aninhados gera uma subclasse de modelos de autômatos, a seguir denominados autômatos inerciais , e uma subclasse correspondente de algoritmos inerciais .

Portanto, seja a tarefa de criar um modelo discreto de um elemento lógico de atraso que implemente a transmissão de um sinal de entrada binário. Além disso, os tempos de seus atrasos t01 e t10, respectivamente, para os estados de unidade e zero no caso geral não coincidem.

O modelo mais simples de um único atraso na forma de um autômato Mealy é mostrado na Fig. 1 (veja, para comparação, o modelo de atraso em [2]). Seus atrasos são determinados por um único ciclo de relógio discreto. Modelos mais complexos de atrasos de transporte (para obter mais detalhes sobre os tipos de atrasos, veja [9]) na forma de um autômato Miley e um modelo combinado de Miley-Moore são apresentados, respectivamente, na Fig. 2a e fig. 2b.


Fig. 1. Modelo de atraso da unidade na forma de um autômato de milhas


Fig. 2. O modelo de atraso de transporte de Miles (a) e Miles-Moore (b)

O sinal de entrada x3 (lembramos que no programa automático corresponde ao predicado [1]) assume um valor verdadeiro se o valor do contador do relógio for igual ao valor da variável t igual ao atraso t01 ou t10. O valor da variável t é atribuído aos sinais y3 e y4 (no programa, a ação funciona com o mesmo nome que os sinais de saída). Os sinais y1, y2 definem o valor da variável que representa a saída do modelo. O sinal y5 incrementa o contador do relógio, que é redefinido pelo sinal y6.

Observação 2. Os estados internos do modelo na Fig. 1, é conveniente associar a um estado de saída de um elemento. Isso nos permite excluir não apenas os operadores y1 e y2, mas também a própria variável de saída.

A implementação da incorporação de autômatos semelhante à chamada de sub-rotinas forma a tecnologia da programação modular de autômatos. Ao mesmo tempo, no nível do software, em contraste com tentativas semelhantes no nível do hardware (veja [10] para comparação), isso é muito mais simples. Para fazer isso, é necessário inserir a chamada de programa do autômato aninhado e, em seguida, o kernel da implementação de autômatos, como um processador normal, organiza o retorno do controle ao nível atual de aninhamento.

Definição 3. Os autômatos aninhados serão chamados de autômatos com um estado final, cuja transição inicia o procedimento de retorno ao nível anterior (classificação) de aninhamento.

A implementação correta do aninhamento de autômatos impõe restrições ao procedimento para sua criação. Em primeiro lugar, um autômato aninhado só pode ser subordinado. Além disso, um autômato de nível superior, excluindo a classificação zero, também pode ser um autômato aninhado. Em segundo lugar, em qualquer transição, apenas um autômato aninhado pode ser criado. O mecanismo de autômatos aninhados também cria a base para a implementação de algoritmos recursivos baseados no controle automático.


Fig. 3. Modelo de atraso na forma de autômatos aninhados

A Fig. 3 mostra o modelo de atraso, onde a Fig. 3a representa o modelo de nível superior, e a Fig. 3b e a Fig. 3c - variantes de autômatos aninhados para atrasos de transporte e inerciais (para obter mais detalhes sobre os tipos de atrasos, consulte [8]). Ao mesmo tempo, estes são exemplos de dois tipos de autômatos aninhados - ordinário e inercial . O tipo de autômato aninhado é definido pelo nome de seus estados finais: um estado com o nome "00" determina a saída usual do autômato aninhado e um estado com o nome "XX" não altera o estado atual do autômato de nível superior.

Uma explicação importante para a compreensão do algoritmo de atraso inercial. Para isso (veja a Fig. 3c), o valor do predicado x1 depende da transição na qual o autômato incorporado é criado. Em outras palavras, o predicado no estado "0" controla a preservação de "zero" na entrada e no estado "1", pelo contrário, "unidades". Se o valor na entrada for zero no valor zero da saída, será necessário retornar o valor verdadeiro. Além disso, se a estabilidade da entrada for violada (o valor x1 é falso) e o tempo de atraso não expirar (o valor x3 é falso), a saída da máquina incorporada será realizada através do estado inercial (consulte a Fig. 3c).

Definição 4. Os autômatos, incluindo a chamada de autômatos aninhados que têm um estado inercial final, serão chamados autômatos inerciais .

No modelo da Fig. 3a, a ação z1 (o símbolo z é selecionado para os nomes de ações que incluem uma chamada para um autômato aninhado) cria um autômato aninhado se um valor de atraso for definido. Como parte dessa ação, o tipo de atraso especificado é determinado, de acordo com o qual um dos autômatos aninhados é criado, mostrado nas Fig.3b ou Fig. 3c.

No nível superior da hierarquia, a visão do autômato na Figura 3a coincide completamente em estrutura com o modelo na Figura 1, diferindo apenas na presença de ações nas transições. Atrasos com autômatos aninhados têm uma forma mais simples em comparação com o modelo de nível único na Fig. 2. Um autômato aninhado também pode ser considerado como um tipo de "autômato de biblioteca" que pode ser chamado de qualquer outro autômato.

3. Programação de autômatos de objetos

O modelo de controle automático, além da forma gráfica, também possui uma forma tabular simples - uma tabela de transição (TP), que pode ser efetivamente interpretada em C ++. Dentro de sua estrutura, um programa de autômato separado (ou parte dele) e, consequentemente, sua definição na forma de um circuito de programa S podem ser representados por uma classe. Nesse caso, os modelos de memória corresponderão às propriedades da classe, o conjunto de operações corresponderá aos métodos da classe e o controle automático na forma de um TP descreverá o comportamento da classe. A introdução do controle na classe nos permite falar sobre objetos ativos, também chamados de agentes, etc.

Muitos objetos com comportamento na forma de controle de autômato formalizam o conceito de um programa paralelo de autômato de objetos . Nesse caso, o modelo de qualquer programa paralelo pode ser representado por um diagrama de programa no qual o controle C será apresentado na forma de uma rede de autômatos, onde autômatos de componentes descrevem o comportamento de objetos ativos, a memória M é representada por uma combinação de propriedades de objetos e muitos operadores A são representados por uma combinação de métodos de objetos de programa.

No ambiente VKPA, a função da linguagem de programação automatizada é atribuída à linguagem C ++. No “C ++ automático”, os objetos são dotados de atividade / comportamento e têm os meios de descrever e implementar paralelismo, tanto no nível de métodos de objetos individuais quanto no nível de descrição da operação paralela de muitos objetos.

As implementações de objetos existentes do AP são bastante complicadas. No VKPa, sua implementação de objeto é baseada na interpretação de autômatos e controle dedicado do programa. Diferentemente da implementação direta de autômatos, usada, por exemplo, na tecnologia SWITH, isso elimina o procedimento para converter um modelo de autômato em um modelo de fluxograma. O algoritmo de interpretação usado no VKPa é semelhante ao método de interpretação de tabelas de decisão de E. Hamby [12].

A menos que especificado de outra forma, associaremos ainda mais o conceito de um programa de autômato ao conceito de um objeto de autômato (AO) no sentido de POO, mas levando em consideração o conceito de um programa paralelo de autômato de objeto apresentado acima. Por esse motivo, os operadores e a memória do ponto de acesso serão determinados através dos métodos e propriedades dos objetos ativos. Os objetos autômatos são diferenciados dos objetos comuns pela presença de comportamento determinado pelo modelo da máquina de estados.

4. Conclusões

Criar um modelo de autômatos aninhados é um passo em direção a uma mudança qualitativa na tecnologia de programação. O modelo inercial descrito do autômato é semelhante ao conceito de estados históricos na UML. A incorporação usual de autômatos tem um analógico na programação, a “incorporação inercial” não a possui, porque Em um programa, você não pode retornar a um comando que precede uma chamada de sub-rotina. E esses são elementos de uma diferença qualitativa entre programação automática e programação comum.

Você pode, é claro, introduzir memória de sombra na programação comum e denotar o paralelismo de funções. Mas, na estrutura do modelo de autômatos, tudo isso tem uma forma orgânica, tanto em termos de descrição quanto em termos de desempenho. Tudo é determinado pelo paralelismo natural do modelo. O modelo do diagrama de blocos não possui esses recursos.

Objetos ativos também expandem os recursos de programação. Mas o “wrapper de objeto”, por sua vez, afeta qualitativamente a programação automática, simplificando os procedimentos para chamar e implementar autômatos aninhados. Portanto, o uso das propriedades da classe [local] permite implementar não apenas a incorporação, mas também algoritmos recursivos.