Olá queridos leitores. Este artigo se concentrará em uma abordagem para a geração automática de programas de acordo com o modelo de blocos do problema, para resolver o problema inverso (restaurar o modelo do problema original do programa já gerado) e também para resolver o problema de verificação de programas gerados. O tópico em si é muito sério, mas tentarei tornar o artigo o mais popular possível (sem uma revisão pesada de análogos, uma parte teórica estritamente formulada e outras dificuldades), com exemplos e descrições de várias aplicações.

1. Geração automática de programas

Para gerar qualquer programa, é necessário, antes de tudo, saber que problema estamos resolvendo. Tendo uma declaração formalizada clara do problema, já é possível criar certas regras para expandir essa declaração em um plano para resolvê-lo e as regras para converter um plano de solução em código final em uma linguagem algorítmica generalizada ou específica. Nesse caso, uma abordagem geralmente é usada para criar o programa final a partir de blocos prontos criados previamente - algoritmos típicos que são vinculados por algum código de chamada / veiculação.

Que a formulação inicial do problema a ser resolvido seja apresentada na forma de um diagrama de blocos (os blocos podem ser elementares ou, por sua vez, subcircuitos), por exemplo, uma rede de objetos, cada um dos quais pertence a uma determinada classe da hierarquia de conceitos de classe da área de assunto. Essa declaração será bastante clara e compreensível para a pessoa e o sistema que está gerando o programa. O sistema deve transformar essa declaração em um plano para resolver o problema de acordo com algumas regras lógicas. Portanto, seria apropriado escrever as regras dessa conversão em alguma linguagem de programação lógica, escolhi o GNU Prolog. Na prática, observo que muitas vezes você pode "pular" essa primeira fase (uma descrição de alto nível do problema) criando imediatamente uma descrição do plano de solução, também na forma de um diagrama de rede em bloco.

O plano de solução resultante deve ser convertido em um programa, como já escrevi, que é um código que conecta algoritmos típicos para resolver os "tijolos" do problema, implementados, por exemplo, na forma de uma biblioteca de funções. Aqui, várias maneiras são possíveis, descreverei em poucas palavras a abordagem que usei. O processo de geração é representado na forma de uma sequência de eventos (por exemplo, a geração de declarações, a geração da parte de inicialização, os estágios da parte principal, a reinicialização), para cada um dos quais a rede de objetos deve ser conectada em cascata (referindo-se às cascatas da rede, esse esquema elimina o loop do modelo ao processar o evento) para responder pela geração fragmentos de código correspondentes. Nesse caso, os objetos dependem do identificador do evento, dos valores de seus parâmetros (definidos pelo usuário ao construir a declaração de bloco do problema), bem como dos dados que eles podem transmitir entre si através dos relacionamentos entre eles. Portanto, cada objeto do plano de solução possui métodos para responder a esses eventos que geram código (e, no caso geral, texto arbitrário). Para resolver esse problema, escolhi a linguagem PHP - ela pode perfeitamente gerar fragmentos de texto arbitrários.

O ajuste do sistema para a área de assunto é realizado através do desenvolvimento de uma hierarquia apropriada de classes geradoras.

Um exemplo de um script de geração que gera código para a classe "Processamento vetorial (mínimo, máximo, média aritmética)":

<? if ($Stage == stInit) { $argumentID = $Arg["ID"][0]; $argumentSize = $Arg["Size"][0]; $resultID = GetNextMail("result" . $this->ID); if ($this->Op == "Min") { echo " " . $resultID . " = 1E300;\n"; } else if ($this->Op == "Max") { echo " " . $resultID . " = -1E300;\n"; } elseif ($this->Op == "Avr") { echo " " . $resultID . " = 0.0;\n"; } ?> for (i = 0; i < <? echo $argumentSize; ?>; i++) <? if ($this->Op == "Min") { ?> if (<? echo $argumentID . "[i] < " . $resultID; ?>) <? echo $resultID . " = " . $argumentID . "[i];\n"; } else if ($this->Op == "Max") { ?> if (<? echo $argumentID . "[i] > " . $resultID; ?>) <? echo $resultID . " = " . $argumentID . "[i];\n"; } elseif ($this->Op == "Avr") { echo " " . $resultID . " += " . $argumentID . "[i];\n"; } if ($this->Op == "Avr") { echo " " . $resultID . " /= " . $argumentSize . ";\n"; } } ?> 

Este é um esquema relativamente simples que funciona. Um sistema que implementa esse esquema de geração (PGEN ++) permite, por exemplo, a geração de programas decisivos nas seguintes áreas:

a) processos de modelagem da propagação da poluição;
b) a solução de alguns problemas cinemáticos de manipuladores simples de robôs;
c) programas simples de treinamento para trabalhar com dados vetoriais (busca de média mínima, máxima e aritmética);
d) desenvolvimento de testes para o sistema de testes psicológicos PROFTEST.

Aqui está um exemplo da declaração inicial do problema (um programa simples de processamento de dados vetoriais) na forma de um diagrama de blocos:



E este é o resultado da geração do programa :

2. Problema inverso: reconstrução do enunciado do problema (modelo inicial) de acordo com o programa gerado. Verificação de programas gerados

Primeiro de tudo, por que é necessário resolver esse problema. Sua aplicação direta e, acho, a mais óbvia, é a verificação de programas gerados automaticamente. Se tivéssemos o modelo A, construímos o programa P, a partir do qual o modelo B foi reconstruído, o programa provavelmente estará correto se os modelos A e B coincidirem.

A seguinte solução simples é proposta. Na geração automática do programa aparecendo gerando objetos pertencentes a uma certa hierarquia de classes da área de assunto. Eles tinham apenas métodos generativos. Adicione métodos de reconhecimento a eles. Em seguida, o programa de origem (ou, no caso geral, qualquer texto) é varrido sequencialmente pelos métodos de reconhecimento de cada classe, que, após o reconhecimento bem-sucedido, geram um objeto / objetos dessa classe. Nós obtemos um conjunto ordenado (na ordem de "ler" o texto) de elementos de modelo parametrizados. Resta determinar a relação entre eles com base na sequência de objetos e a relação entre seus parâmetros. Para isso, regras especiais de decisão podem ser aplicadas.

O método de reconhecimento, na minha implementação, consiste na parte de reconhecimento (este é um grupo de expressões regulares modificadas) e a parte decisiva (escrita no GNU Prolog). As expressões regulares são modificadas de forma a realizar algum pré-processamento (verificação de dicionário, verificação difusa de similaridade de acordo com Levenshtein, verificação do equilíbrio de expressões entre parênteses) no estágio de análise, para isso eles adicionaram a capacidade de incluir várias cadeias (verificação, adição, exclusão, treinamento de uma rede neural) de predicados "rápidos".

Este circuito também funciona. Como aplicação direta, foi utilizado para reconstruir currículos simples para trabalhar com dados vetoriais (busca de média mínima, máxima e aritmética), caso em que demonstrou com êxito a possível verificação dos programas gerados, comparando os modelos originais e reconstruídos. Mas existem outras aplicações, sobre elas ainda mais.

3. Interface em linguagem natural para o sistema de geração de programas

Ao resolver o problema inverso (descrito acima), não há restrições quanto ao tipo de material de origem para reconstruir o modelo do problema que está sendo resolvido. Pode muito bem ser um texto em linguagem natural. Basta escrever métodos de reconhecimento apropriados. Portanto, uma aplicação inesperada do problema inverso pode ser a implementação de uma interface de linguagem natural para o sistema de geração:

a) a declaração do problema está escrita em linguagem natural simplificada;
b) o problema inverso é resolvido - uma declaração formal é extraída da declaração em linguagem natural (uma rede de objetos-elementos da área de assunto);
c) o sistema é lançado para gerar um programa de acordo com a declaração formal obtida.

E esse circuito também funciona. Um exemplo é desenvolvido para o mesmo caso de programas de treinamento simples para trabalhar com dados vetoriais.

Aqui está um exemplo de um método de reconhecimento (da classe de teclado "Digite um vetor ou uma escalar"), dividido em duas versões (reconhecimento de um texto de programa (modo programático) ou reconhecimento de um fragmento de uma declaração de problema em russo (modo russo)). No topo está a parte de reconhecimento, depois os predicados no GNU Prolog.

 @versions(Programmatical) @global_unique(PROCESS,infinity):- (\s*for\s*\(i\s*\=\s*0\;\s*i\s*\<\s*(\d+)->{N}\;\s*i\+\+\)\s*\{\\n\s*printf\(\"(\w+)->{VECTOR} \[\%i\]\s*\=\s*\"\,\s*i\)\;\\n\s*scanf\(\"\%lf\"\,\s*\&(\w+)==>{VECTOR}\[i\]\)\;\\n\s*\}\\n)| (\s*printf\(\"(\w+)->{SCALAR}\s*\=\s*\"\)\;\\n\s*scanf\(\"\%lf\"\,\s*\&(\w+)==>{SCALAR}\)\;\\n). @versions(Russian) @nearest(db_vvedem,2,"db_vvedem.csv"). @fast(db_var,"db_var.csv"). @global_unique(PROCESS,infinity):- (()->{VAR}([--]+)?=>{db_vvedem($)}\s+((\s+\s+)?)->{KEYB} ([--]+)?=>{db_var($,$VAR)}\s+(\w+)->{ID}((\s+\s+)?)!=>{KEYB}\s*\.). @versions(Russian) handle:-xpath('PROCESS','//ID/text()',[VText]), xpath('PROCESS','//VAR/text()',['0']), simple_vector(_,VText,_), global_id(GID),assertz(simple_act(GID,in,VText,'')),!. handle:-xpath('PROCESS','//ID/text()',[SText]), xpath('PROCESS','//VAR/text()',['1']), global_id(GID),assertz(simple_act(GID,in,SText,'')),!. @versions(Programmatical) handle:-xpath('PROCESS','//VECTOR/text()',[VText]), xpath('PROCESS','//N/text()',[NText]), simple_vector(_,VText,NText), global_id(GID),assertz(simple_act(GID,in,VText,'')),!. handle:-xpath('PROCESS','//SCALAR/text()',[SText]), simple_scalar(_,SText), global_id(GID),assertz(simple_act(GID,in,SText,'')),!. @versions(Programmatical,Russian) @goal:- handle,!. @done:- clear_db. 

Um exemplo de uma declaração de problema em russo:

  .   max.   min.   V  10 .   V  .    V      min.     V      max.   min  .   max  .   V  .      . 

E o modelo do problema obtido pelo sistema a partir da descrição em linguagem natural acima :

4. Outras aplicações do problema inverso

Ao resolver o problema inverso, nada nos impede de considerar o caso de não apenas reconhecer um determinado programa, mas reconhecê-lo “com aprimoramento” ou outro processamento (caractere arbitrário). Em particular, foi possível desenvolver um “paralelizador automático” de um programa reconhecível escrito em C. Ele realiza uma análise estática e parcialmente dinâmica do código reconhecido e insere nele diretivas de paralelização da extensão Cilk / Cilk ++. Essa tarefa de melhoria é implementada pelo reconhecimento de métodos (no GNU Prolog).

Um exemplo de um programa C de computação processado por um paralelizador (ele inseriu as diretivas cilk_spawn e cilk_sync):

 #include <stdio.h> #include <math.h> #include <omp.h> #define PI 3.14159265358 #define NX 100 #define NY 100 #define MaxT 0.001 #define h 0.01 #define tau 0.00001 #define cilk_spawn _Cilk_spawn #define cilk_sync _Cilk_sync void F( double x, double y, double t, double * val ){ double r = sqrt(x*x + y*y); double result = 0.0; int i; for ( i = 0; i < 300; i++ ) result += exp(-r*t)*sin(0.1*i*r + 0.5*PI); *val = result; } int main( ){ double f[NY][NX] = {0.0}; double v[NY][NX] = {0.0}; double v1[NY][NX] = {0.0}; double t; int x, y; double start = omp_get_wtime(); for ( t = 0.0; t < MaxT; t += tau ) { for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) cilk_spawn F(x*h, y*h, t, &f[y][x]); for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) { cilk_sync; v1[y][x] = v[y][x] + tau*((v[y-1][x]+v[y+1][x]+v[y][x-1]+v[y][x+1]-4.0*v[y][x])/h/h - f[y][x]); } for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) v[y][x] = v1[y][x]; } for ( y = 0; y < NY; y++ ) { for ( x = 0; x < NX; x++ ) printf("%lf ", v[y][x]); printf("\n"); } printf("Total time = %lf\n", omp_get_wtime() - start); return 0; } 

5. Um pouco de ficção. Verificação e identificação de programas arbitrários com código fonte fechado

Aqui estamos falando de programas arbitrários escritos por um programador e / ou um sistema que gera programas para os quais simplesmente não há código-fonte. Seja necessário verificar o funcionamento correto de um programa ou mesmo entender o que está fazendo. Nesse caso, uma ou outra versão da chamada "meta camada" pode ser usada - um componente hipotético do sistema operacional que rastreia toda a sequência do programa (chamando funções, modificando dados na memória etc.) e constrói nele um modelo aproximado de sua lógica. uma forma equivalente ao funcionamento de um programa em qualquer linguagem de programação. Resta então resolver o problema inverso de um programa desse tipo - restaurar um possível modelo (ou modelos) inicial que permita pelo menos avaliar a correção ou entender o objetivo do programa. O protótipo de tal “metasslayer” já foi desenvolvido pelo autor para o caso de programas C / C ++; não era possível tanto, mas algo funcionava. Talvez um dia alguém queira realizar esse trabalho por completo.

6. Conclusão

Espero ter conseguido demonstrar que a geração automática de programas e a solução do problema inverso não são problemas puramente acadêmicos, mas algo útil e com conseqüências práticas diretas. Ao mesmo tempo, as decisões apresentadas aqui não pretendem ser completas e óbvias, mas são implementadas e pretendem uma certa novidade.