Bonjour chers lecteurs. Cet article se concentrera sur une approche de la génération automatique de programmes selon le modèle de bloc du problème, pour résoudre le problème inverse (restaurer le modèle du problème d'origine à partir du programme déjà généré), et aussi pour résoudre le problème de vérification des programmes générés. Le sujet lui-même est très sérieux, mais je vais essayer de rendre l'article aussi populaire que possible (sans une revue approfondie des analogues, une partie théorique strictement formulée et d'autres difficultés), avec des exemples et des descriptions de diverses applications.
1. Génération automatique de programmes
Pour générer un programme, il faut tout d'abord savoir quel problème nous résolvons. Ayant un énoncé clair et formalisé du problème, il est déjà possible de construire quelques règles pour étendre cet énoncé dans un plan pour résoudre le problème et les règles pour convertir un plan de solution en code final dans un langage algorithmique généralisé ou spécifique. Dans ce cas, une approche est généralement utilisée pour construire le programme final à partir de blocs prêts à l'emploi créés à l'avance - des algorithmes typiques qui sont liés par du code appelant / servant.
Que la formulation initiale du problème à résoudre soit présentée sous la forme d'un diagramme (les blocs peuvent être élémentaires ou, à son tour, être des sous-circuits), par exemple, un réseau d'objets, chacun appartenant à une certaine classe de la hiérarchie des concepts de classe du domaine. Une telle déclaration sera assez claire et compréhensible à la fois pour la personne et le système générant le programme. Le système devrait transformer une telle déclaration en un plan pour résoudre le problème selon certaines règles logiques. Donc, il serait approprié d'écrire les règles d'une telle conversion dans un langage de programmation logique, j'ai choisi GNU Prolog. En pratique, je note, vous pouvez souvent «sauter» cette première phase (une description de haut niveau du problème) en construisant immédiatement une description du plan de solution, également sous la forme d'un schéma de réseau.
Le plan de solution résultant devrait être converti en programme, comme je l'ai déjà écrit, qui est un code qui connecte des algorithmes typiques pour résoudre les "briques" du problème, mis en œuvre, par exemple, sous la forme d'une bibliothèque de fonctions. Ici, différentes manières sont possibles, je décrirai en quelques mots l'approche que j'ai utilisée. Le processus de génération est représenté sous la forme d'une séquence d'événements (par exemple, la génération de déclarations, la génération de la partie d'initialisation, les étapes de la partie principale, la désinitialisation), pour chacune desquelles le réseau d'objets doit être mis en cascade (en se référant aux cascades du réseau, ce schéma élimine le modèle en boucle lors du traitement des événements) pour répondre par génération fragments de code correspondants. Dans ce cas, les objets s'appuient sur l'identifiant de l'événement, les valeurs de leurs paramètres (définies par l'utilisateur lors de la construction de l'énoncé de bloc du problème), ainsi que sur les données qu'ils peuvent se transmettre entre eux par les relations entre eux. Par conséquent, chaque objet du plan de solution possède des méthodes pour répondre à de tels événements qui génèrent du code (et, dans le cas général, du texte arbitraire). Pour résoudre ce problème, j'ai choisi le langage PHP - il peut parfaitement générer des fragments de texte arbitraires.
Le réglage du système sur le domaine est effectué en développant une hiérarchie appropriée de classes de génération.
Un exemple de script générateur qui génère du code pour la classe "Traitement vectoriel (minimum, maximum, moyenne arithmétique)":<? 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"; } } ?>
Il s'agit d'un schéma relativement simple qui fonctionne. Un système qui implémente un tel schéma de génération (PGEN ++) permet, par exemple, la génération de programmes décisifs dans les domaines suivants:
a) modélisation des processus de propagation de la pollution;
b) la solution de certains problèmes cinématiques de simples robots manipulateurs;
c) des programmes de formation simples pour travailler avec des données vectorielles (recherche de minimum, maximum, moyenne arithmétique);
d) développement de tests pour le système de tests psychologiques PROFTEST.
Voici
un exemple de l' énoncé initial du problème (un simple programme de traitement de données vectorielles) sous la forme d'un diagramme:
Et c'est le
résultat de la génération du programme :
2. Problème inverse: reconstruction de l'énoncé du problème (modèle initial) en fonction du programme généré. Vérification des programmes générés
Tout d'abord, pourquoi est-il nécessaire de résoudre un tel problème. Son application directe et, je pense, la plus évidente est la vérification des programmes générés automatiquement. Si nous avions le modèle A, construit le programme P dessus, à partir duquel le modèle B a été reconstruit, alors le programme est probablement correct si les modèles A et B coïncident.
La solution simple suivante est proposée. Dans la génération automatique du programme apparaissant la génération d'objets appartenant à une certaine hiérarchie de classes du domaine. Ils n'avaient que des méthodes génératives. Ajoutez-leur des méthodes de reconnaissance. Ensuite, le programme source (ou, dans le cas général, tout texte) est analysé séquentiellement par les méthodes de reconnaissance de chaque classe, qui, une fois la reconnaissance réussie, génère un ou des objets de cette classe. Nous obtenons un ensemble ordonné (dans l'ordre de "lecture" du texte) d'éléments de modèle paramétrés. Reste à déterminer la relation entre eux en fonction de la séquence des objets et la relation entre leurs paramètres. Pour cela, des règles de décision spéciales peuvent être appliquées.
La méthode de reconnaissance, dans mon implémentation, comprend la partie reconnaissance (c'est un groupe d'expressions régulières modifiées) et la partie décisive (écrite en GNU Prolog). Les expressions régulières sont modifiées de manière à effectuer un prétraitement (vérification du dictionnaire, vérification floue de la similitude selon Levenshtein, vérification de l'équilibre des expressions entre parenthèses) au stade de l'analyse, pour cela, elles ont ajouté la possibilité d'inclure diverses chaînes (vérification, ajout, suppression, formation d'un réseau neuronal) de prédicats «rapides».
Ce circuit fonctionne également. En tant qu'application directe, il a été utilisé pour reconstruire des programmes simples pour travailler avec des données vectorielles (recherche de minimum, maximum, moyenne arithmétique), auquel cas il a démontré avec succès la vérification possible des programmes générés en comparant les modèles originaux et reconstruits. Mais il existe d'autres applications, à leur sujet plus loin.
3. Interface en langage naturel pour le système de génération de programmes
Lors de la résolution du problème inverse (décrit ci-dessus), il n'y a pas de restrictions sur le type de matériaux source pour reconstruire le modèle du problème résolu. Il pourrait bien s'agir d'un texte en langage naturel. Écrivez simplement les méthodes de reconnaissance appropriées. Par conséquent, une application inattendue du problème inverse peut être la mise en œuvre d'une interface en langage naturel au système de génération:
a) l'énoncé du problème est rédigé dans un langage naturel simplifié;
b) le problème inverse est résolu - une déclaration formelle est extraite de la déclaration en langage naturel (un réseau d'objets-éléments du domaine);
c) le système est lancé pour générer un programme selon la déclaration officielle obtenue.
Et ce circuit fonctionne également. Un exemple est développé pour le même cas de programmes de formation simples pour travailler avec des données vectorielles.
Voici
un exemple de méthode de reconnaissance (de la classe de clavier «Saisir un vecteur ou un scalaire»), qui est divisée en deux versions (reconnaissance d'un texte de programme (mode programmatique) ou reconnaissance d'un fragment d'une déclaration de problème en russe (mode russe)). En haut se trouve la partie reconnaissance, puis les prédicats sur le 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 exemple d'une déclaration de problème en russe: . max. min. V 10 . V . V min. V max. min . max . V . .
Et le
modèle du problème obtenu par le système à partir de la description en langage naturel ci-dessus :
4. Autres applications du problème inverse
Lors de la résolution du problème inverse, rien ne nous empêche de considérer non seulement le fait de reconnaître un certain programme, mais de le reconnaître «avec amélioration» ou un autre traitement (caractère arbitraire). En particulier, il a été possible de développer un «paralléliseur automatique» d'un programme reconnaissable écrit en C. Il effectue une analyse statique et partiellement dynamique du code reconnu et y insère des directives de parallélisation de l'extension Cilk / Cilk ++. Cette tâche d'amélioration est implémentée par la reconnaissance de méthodes (sur le GNU Prolog).
Un exemple de programme informatique C traité par un paralléliseur (il a inséré les directives cilk_spawn et 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 peu de fiction. Vérification et identification de programmes arbitraires avec code source fermé
Il s'agit ici de programmes arbitraires écrits par un programmeur et / ou un système générant des programmes pour lesquels il n'y a tout simplement pas de code source. Qu'il soit nécessaire de vérifier le bon fonctionnement d'un tel programme, voire de comprendre ce qu'il fait. Dans ce cas, l'une ou l'autre version de la soi-disant «méta-couche» peut être utilisée - un composant hypothétique du système d'exploitation qui suit la séquence entière du programme (fonctions d'appel, modification des données en mémoire, etc.) et construit un modèle approximatif de sa logique une forme équivalente au fonctionnement d'un programme dans n'importe quel langage de programmation. Reste alors à résoudre le problème inverse d'un tel programme - à restaurer un ou plusieurs modèles initiaux qui permettraient au moins d'évaluer la justesse ou de comprendre la finalité du programme. Le prototype d'un tel «métaslayer» a été une fois développé par l'auteur pour le cas des programmes C / C ++, ce n'était pas tellement possible, mais quelque chose fonctionnait. Peut-être qu'un jour, quelqu'un voudra effectuer un tel travail dans son intégralité.
6. Conclusion
J'espère avoir pu démontrer que la génération automatique de programmes et la solution du problème inverse ne sont pas des problèmes purement académiques, mais quelque chose d'utile et ayant des conséquences pratiques directes. Dans le même temps, les décisions présentées ici ne prétendent pas être complètes et évidentes, mais elles sont mises en œuvre et prétendent à une certaine nouveauté.