Hola queridos lectores. Este artículo se centrará en un enfoque para la generación automática de programas de acuerdo con el modelo de bloques del problema, para resolver el problema inverso (restaurar el modelo del problema original desde el programa ya generado) y también para resolver el problema de verificación de los programas generados. El tema en sí es muy serio, pero trataré de hacer que el artículo sea lo más popular posible (sin una gran revisión de análogos, una parte teórica estrictamente formulada y otras dificultades), con ejemplos y descripciones de diversas aplicaciones.

1. Generación automática de programas.

Para generar cualquier programa, es necesario, en primer lugar, saber qué problema estamos resolviendo. Al tener una declaración formal clara del problema, ya es posible construir algunas reglas para expandir esta declaración en un plan para resolver el problema y las reglas para convertir un plan de solución en código final en un lenguaje algorítmico generalizado o específico. En este caso, generalmente se usa un enfoque para construir el programa final a partir de bloques prefabricados creados de antemano, algoritmos típicos que están vinculados por algún código de llamada / servicio.

Deje que la formulación inicial del problema a resolver se presente en forma de diagrama de bloques (los bloques pueden ser elementales o, a su vez, subcircuitos), por ejemplo, una red de objetos, cada uno de los cuales pertenece a una determinada clase de la jerarquía de conceptos de clase del área temática. Dicha declaración será bastante clara y comprensible tanto para la persona como para el sistema que genera el programa. El sistema debe transformar dicha declaración en un plan para resolver el problema de acuerdo con algunas reglas lógicas. Entonces, sería apropiado escribir las reglas de tal conversión en algún lenguaje de programación lógico, elegí GNU Prolog. En la práctica, observo que a menudo puede "saltear" esta primera fase (una descripción de alto nivel del problema) construyendo inmediatamente una descripción del plan de solución, también en forma de diagrama de red de bloques.

El plan de solución resultante debería convertirse en un programa, como ya escribí, que es un código que conecta algoritmos típicos para resolver los "ladrillos" del problema, implementado, por ejemplo, en forma de una biblioteca de funciones. Aquí es posible una variedad de formas, describiré en pocas palabras el enfoque que utilicé. El proceso de generación se representa en forma de una secuencia de eventos (por ejemplo, la generación de declaraciones, la generación de la parte de inicialización, las etapas de la parte principal, la inicialización), para cada una de las cuales la red de objetos debe conectarse en cascada (refiriéndose a las cascadas de la red, este esquema elimina el bucle del modelo durante el procesamiento de eventos) para responder por generación fragmentos de código correspondientes. En este caso, los objetos se basan en el identificador del evento, los valores de sus parámetros (establecidos por el usuario cuando construye la declaración de bloque del problema), así como en los datos que pueden transmitirse entre sí a través de las relaciones entre ellos. Por lo tanto, cada objeto del plan de solución tiene métodos para responder a tales eventos que generan código (y, en el caso general, texto arbitrario). Para resolver este problema, elegí el lenguaje PHP: simplemente puede generar fragmentos de texto arbitrarios.

El ajuste del sistema al área temática se lleva a cabo desarrollando una jerarquía apropiada de generación de clases.

Un ejemplo de un script generador que genera código para la clase "Procesamiento de vectores (mínimo, máximo, media 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 es un esquema relativamente sencillo que funciona. Un sistema que implementa dicho esquema de generación (PGEN ++) permite, por ejemplo, la generación de programas decisivos en las siguientes áreas:

a) modelar procesos de propagación de la contaminación;
b) la solución de algunos problemas cinemáticos de simples manipuladores de robots;
c) programas de capacitación simples para trabajar con datos vectoriales (búsqueda de mínimo, máximo, media aritmética);
d) desarrollo de pruebas para el sistema de pruebas psicológicas PROFTEST.

Aquí hay un ejemplo de la declaración inicial del problema (un simple programa de procesamiento de datos vectoriales) en forma de diagrama de bloques:



Y este es el resultado de generar el programa :

2. Problema inverso: reconstrucción del enunciado del problema (modelo inicial) según el programa generado. Verificación de programas generados

En primer lugar, ¿por qué es necesario resolver este problema? Es directo, y creo que la aplicación más obvia es la verificación de programas generados automáticamente. Si teníamos el modelo A, construimos el programa P sobre él, a partir del cual se reconstruyó el modelo B, entonces el programa probablemente sea correcto si coinciden los modelos A y B.

Se propone la siguiente solución simple. En la generación automática del programa aparece generando objetos pertenecientes a una determinada jerarquía de clases del área temática. Solo tenían métodos generativos. Agregue métodos de reconocimiento a ellos. Luego, el programa fuente (o, en el caso general, cualquier texto) es escaneado secuencialmente por los métodos de reconocimiento de cada clase, que, con el reconocimiento exitoso, genera un objeto / objetos de esta clase. Obtenemos un conjunto ordenado (en el orden de "lectura" del texto) de elementos de modelo parametrizados. Queda por determinar la relación entre ellos en función de la secuencia de objetos y la relación entre sus parámetros. Para esto, se pueden aplicar reglas especiales de decisión.

El método de reconocimiento, en mi implementación, consiste en la parte de reconocimiento (este es un grupo de expresiones regulares modificadas) y la parte decisiva (escrita en GNU Prolog). Las expresiones regulares se modifican de tal manera que se realice un preprocesamiento (verificación de diccionario, verificación difusa de similitud según Levenshtein, verificación del equilibrio de expresiones entre paréntesis) en la etapa de análisis, para esto agregaron la capacidad de incluir varias cadenas (verificación, adición, eliminación, entrenamiento de una red neuronal) de predicados "rápidos".

Este circuito también funciona. Como aplicación directa, se utilizó para reconstruir planes de estudio simples para trabajar con datos vectoriales (búsqueda de la media aritmética mínima, máxima), en cuyo caso demostró con bastante éxito la posible verificación de los programas generados mediante la comparación de los modelos originales y reconstruidos. Pero hay otras aplicaciones, sobre ellas más.

3. Interfaz de lenguaje natural para el sistema de generación de programas.

Al resolver el problema inverso (descrito anteriormente), no hay restricciones sobre el tipo de materiales fuente para reconstruir el modelo del problema que se está resolviendo. Bien puede ser un texto en lenguaje natural. Simplemente escriba los métodos de reconocimiento apropiados. Por lo tanto, una aplicación inesperada del problema inverso puede ser la implementación de una interfaz de lenguaje natural para el sistema de generación:

a) la declaración del problema está escrita en un lenguaje natural simplificado;
b) se resuelve el problema inverso: se extrae una declaración formal de la declaración del lenguaje natural (una red de objetos-elementos del área temática);
c) el sistema se inicia para generar un programa de acuerdo con la declaración formal obtenida.

Y este circuito también funciona. Se desarrolla un ejemplo para el mismo caso de programas de capacitación simples para trabajar con datos vectoriales.

Aquí hay un ejemplo de un método de reconocimiento (de la clase de teclado "Introducir un vector o un escalar"), que se divide en dos versiones (reconocimiento de un texto de programa (modo programático) o reconocimiento de un fragmento de una declaración de problema en ruso (modo ruso)). En la parte superior está la parte de reconocimiento, luego los predicados en el 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. 

Un ejemplo de una declaración de problema en ruso:

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

Y el modelo del problema obtenido por el sistema a partir de la descripción del lenguaje natural anterior :

4. Otras aplicaciones del problema inverso.

Al resolver el problema inverso, nada nos impide considerar el caso de no solo reconocer cierto programa, sino reconocerlo "con mejora" u otro procesamiento (de carácter arbitrario). En particular, fue posible desarrollar un "paralelizador automático" de un programa reconocible escrito en C. Lleva a cabo un análisis estático y, en parte, dinámico del código reconocido e inserta directivas de paralelización desde la extensión Cilk / Cilk ++. Esta tarea de mejora se implementa mediante el reconocimiento de métodos (en el GNU Prolog).

Un ejemplo de un programa informático C procesado por un paralelizador (insertó las directivas cilk_spawn y 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. Un poco de ficción. Verificación e identificación de programas arbitrarios con código fuente cerrado

Aquí estamos hablando de programas arbitrarios escritos por un programador y / o un sistema que genera programas para los cuales simplemente no hay código fuente. Permita que se verifique el funcionamiento correcto de dicho programa, o incluso que comprenda lo que está haciendo. En este caso, se puede usar una u otra versión de la llamada "meta capa", un componente hipotético del sistema operativo que rastrea la secuencia completa del programa (funciones de llamada, modificación de datos en la memoria, etc.) y construye un modelo aproximado de su lógica en él. Una forma equivalente al funcionamiento de un programa en cualquier lenguaje de programación. Luego queda resolver el problema inverso de dicho programa: restaurar un posible modelo (o modelos) inicial que permita al menos evaluar la corrección o comprender el propósito del programa. El autor desarrolló el prototipo de una “metacapa” de este tipo para el caso de los programas C / C ++, no fue posible, pero algo funcionó. Quizás algún día alguien querrá realizar tal trabajo en su totalidad.

6. Conclusión

Espero haber podido demostrar que la generación automática de programas y la solución del problema inverso no son problemas puramente académicos, sino algo útil y que tiene consecuencias prácticas directas. Al mismo tiempo, las decisiones presentadas aquí no pretenden ser completas y obvias, sino que se implementan y pretenden una cierta novedad.