Hallo liebe Leser. Dieser Artikel konzentriert sich auf einen Ansatz zur automatischen Generierung von Programmen gemäß dem Blockmodell des Problems, zur Lösung des inversen Problems (Wiederherstellung des Modells des ursprünglichen Problems aus dem bereits generierten Programm) und zur Lösung des Problems der Überprüfung generierter Programme. Das Thema selbst ist sehr ernst, aber ich werde versuchen, den Artikel so populär wie möglich zu machen (ohne eine gründliche Überprüfung der Analoga, einen streng formulierten theoretischen Teil und andere Schwierigkeiten), mit Beispielen und Beschreibungen verschiedener Anwendungen.

1. Automatische Generierung von Programmen

Um ein Programm zu generieren, muss man zunächst wissen, welches Problem wir lösen. Mit einer klar formalisierten Erklärung des Problems ist es bereits möglich, einige Regeln für die Erweiterung dieser Aussage in einen Plan zur Lösung des Problems und die Regeln für die Konvertierung eines Lösungsplans in endgültigen Code in einer verallgemeinerten oder spezifischen algorithmischen Sprache zu erstellen. In diesem Fall wird normalerweise ein Ansatz verwendet, um das endgültige Programm aus vorgefertigten Blöcken zu erstellen, die im Voraus erstellt wurden - typische Algorithmen, die durch einen aufrufenden / bedienenden Code verknüpft sind.

Die anfängliche Formulierung des zu lösenden Problems sei in Form eines Blockdiagramms (Blöcke können elementar oder wiederum Teilschaltungen sein) dargestellt, beispielsweise eines Netzwerks von Objekten, von denen jedes zu einer bestimmten Klasse aus der Hierarchie der Klassenkonzepte des Themenbereichs gehört. Eine solche Aussage ist sowohl für die Person als auch für das System, das das Programm erstellt, ziemlich klar und verständlich. Das System sollte eine solche Aussage in einen Plan zur Lösung des Problems nach einigen logischen Regeln umwandeln. Daher wäre es angebracht, die Regeln einer solchen Konvertierung in einer logischen Programmiersprache zu schreiben. Ich habe mich für GNU Prolog entschieden. In der Praxis können Sie diese erste Phase (eine allgemeine Beschreibung des Problems) häufig „überspringen“, indem Sie sofort eine Beschreibung des Lösungsplans erstellen, auch in Form eines Blocknetzwerkdiagramms.

Der resultierende Lösungsplan sollte, wie ich bereits geschrieben habe, in ein Programm konvertiert werden, bei dem es sich um einen Code handelt, der typische Algorithmen zur Lösung der "Bausteine" des Problems verbindet, die beispielsweise in Form einer Funktionsbibliothek implementiert sind. Hier sind verschiedene Möglichkeiten möglich, ich werde in wenigen Worten den Ansatz beschreiben, den ich verwendet habe. Der Generierungsprozess wird in Form einer Folge von Ereignissen dargestellt (z. B. die Generierung von Deklarationen, die Generierung des Initialisierungsteils, die Stufen des Hauptteils, die De-Initialisierung), für die jeweils das Netzwerk von Objekten kaskadiert werden sollte (in Bezug auf die Kaskaden des Netzwerks eliminiert dieses Schema die Modellschleife während der Ereignisverarbeitung), um nach Generierung zu reagieren entsprechende Codefragmente. In diesem Fall stützen sich die Objekte auf die Kennung des Ereignisses, die Werte ihrer Parameter (die vom Benutzer beim Erstellen der Blockanweisung des Problems festgelegt wurden) sowie auf die Daten, die sie über die Beziehungen zwischen ihnen untereinander übertragen können. Daher verfügt jedes Objekt aus dem Lösungsplan über Methoden zum Reagieren auf solche Ereignisse, die Code (und im allgemeinen Fall beliebigen Text) generieren. Um dieses Problem zu lösen, habe ich die PHP-Sprache gewählt - sie kann einfach perfekt beliebige Textfragmente erzeugen.

Die Systemabstimmung auf den Themenbereich erfolgt durch Entwicklung einer geeigneten Hierarchie der generierenden Klassen.

Ein Beispiel für ein generierendes Skript, das Code für die Klasse "Vektorverarbeitung (Minimum, Maximum, arithmetisches Mittel)" generiert:

<? 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"; } } ?> 

Dies ist ein relativ unkompliziertes Schema, das funktioniert. Ein System, das ein solches Generierungsschema implementiert (PGEN ++), ermöglicht beispielsweise die Generierung entscheidender Programme in folgenden Bereichen:

a) Modellierung von Ausbreitungsprozessen der Verschmutzung;
b) die Lösung einiger kinematischer Probleme einfacher Robotermanipulatoren;
c) einfache Trainingsprogramme zum Arbeiten mit Vektordaten (Suche nach minimalem, maximalem, arithmetischem Mittel);
d) Entwicklung von Tests für das psychologische Testsystem PROFTEST.

Hier ist ein Beispiel für die anfängliche Erklärung des Problems (ein einfaches Vektordatenverarbeitungsprogramm) in Form eines Blockdiagramms:



Und das ist das Ergebnis der Generierung des Programms :

2. Inverses Problem: Rekonstruktion der Problemstellung (Ausgangsmodell) nach dem generierten Programm. Überprüfung der generierten Programme

Warum ist es zunächst notwendig, ein solches Problem zu lösen? Die direkte und meiner Meinung nach offensichtlichste Anwendung ist die Überprüfung automatisch generierter Programme. Wenn wir Modell A hatten, auf dem Programm P aufgebaut war, aus dem Modell B rekonstruiert wurde, dann ist das Programm höchstwahrscheinlich korrekt, wenn die Modelle A und B übereinstimmen.

Die folgende einfache Lösung wird vorgeschlagen. Bei der automatischen Generierung des Programms erscheinen Objekte, die zu einer bestimmten Hierarchie von Klassen des Themenbereichs gehören. Sie hatten nur generative Methoden. Fügen Sie ihnen Erkennungsmethoden hinzu. Dann wird das Quellprogramm (oder im allgemeinen Fall ein beliebiger Text) nacheinander von den Erkennungsmethoden jeder Klasse gescannt, die nach erfolgreicher Erkennung ein Objekt / Objekte dieser Klasse erzeugen. Wir erhalten einen geordneten Satz (in der Reihenfolge des "Lesens" des Textes) parametrisierter Modellelemente. Es bleibt die Beziehung zwischen ihnen basierend auf der Reihenfolge der Objekte und der Beziehung zwischen ihren Parametern zu bestimmen. Hierzu können spezielle Entscheidungsregeln angewendet werden.

Die Erkennungsmethode besteht in meiner Implementierung aus dem Erkennungsteil (dies ist eine Gruppe modifizierter regulärer Ausdrücke) und dem entscheidenden Teil (geschrieben in GNU Prolog). Reguläre Ausdrücke werden so modifiziert, dass sie in der Analysephase eine Vorverarbeitung durchführen (Wörterbuchprüfung, Fuzzy-Prüfung auf Ähnlichkeit nach Levenshtein, Prüfung der Ausgewogenheit von Ausdrücken in Klammern). Dazu wurde die Möglichkeit hinzugefügt, verschiedene Ketten einzuschließen (Prüfen, Hinzufügen, Löschen, Training eines neuronalen Netzwerks) von „schnellen“ Prädikaten.

Diese Schaltung funktioniert auch. Als direkte Anwendung wurde es verwendet, um einfache Lehrpläne für die Arbeit mit Vektordaten (Suche nach minimalem, maximalem, arithmetischem Mittelwert) zu rekonstruieren. In diesem Fall wurde die mögliche Verifizierung der generierten Programme durch Vergleich der ursprünglichen und rekonstruierten Modelle recht erfolgreich demonstriert. Aber es gibt noch andere Anwendungen, über sie weiter.

3. Schnittstelle in natürlicher Sprache für das Programmerzeugungssystem

Bei der Lösung des inversen Problems (oben beschrieben) gibt es keine Einschränkungen hinsichtlich der Art der Ausgangsmaterialien für die Rekonstruktion des Modells des zu lösenden Problems. Es kann durchaus ein Text in natürlicher Sprache sein. Schreiben Sie einfach geeignete Erkennungsmethoden. Daher kann eine unerwartete Anwendung des inversen Problems die Implementierung einer Schnittstelle in natürlicher Sprache zum Generierungssystem sein:

a) die Problemstellung ist in einer vereinfachten natürlichen Sprache verfasst;
b) das umgekehrte Problem ist gelöst - eine formale Aussage wird aus der Aussage in natürlicher Sprache (einem Netzwerk von Objektelementen des Themenbereichs) extrahiert;
c) Das System wird gestartet, um ein Programm gemäß der erhaltenen formalen Erklärung zu generieren.

Und diese Schaltung funktioniert auch. Für den gleichen Fall von einfachen Trainingsprogrammen zum Arbeiten mit Vektordaten wird ein Beispiel entwickelt.

Hier ist ein Beispiel für eine Erkennungsmethode (der Tastaturklasse „Geben Sie einen Vektor oder einen Skalar ein“), die in zwei Versionen unterteilt ist (Erkennung eines Programmtextes (programmatischer Modus) oder Erkennung eines Fragments einer Problemstellung in russischer Sprache (russischer Modus)). Oben befindet sich der Erkennungsteil, dann die Prädikate auf dem 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. 

Ein Beispiel für eine Problemstellung auf Russisch:

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

Und das Modell des Problems, das das System aus der obigen Beschreibung in natürlicher Sprache erhält :

4. Andere Anwendungen des inversen Problems

Bei der Lösung des inversen Problems hindert uns nichts daran, den Fall zu betrachten, ein bestimmtes Programm nicht nur zu erkennen, sondern es „mit Verbesserung“ oder einer anderen (willkürlichen) Verarbeitung zu erkennen. Insbesondere konnte ein „automatischer Parallelisierer“ eines in C geschriebenen erkennbaren Programms entwickelt werden. Er führt eine statische und teilweise dynamische Analyse des erkannten Codes durch und fügt Parallelisierungsanweisungen aus der Cilk / Cilk ++ - Erweiterung ein. Diese Verbesserungsaufgabe wird durch Erkennen von Methoden (auf dem GNU Prolog) implementiert.

Ein Beispiel für ein Computer-C-Programm, das von einem Parallelisierer verarbeitet wird (er hat die Anweisungen cilk_spawn und cilk_sync eingefügt):

 #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. Ein bisschen Fiktion. Überprüfung und Identifizierung beliebiger Programme mit geschlossenem Quellcode

Hier geht es um beliebige Programme, die von einem Programmierer und / oder einem System geschrieben wurden, das Programme generiert, für die es einfach keinen Quellcode gibt. Lassen Sie es erforderlich sein, die korrekte Funktion eines solchen Programms zu überprüfen oder sogar zu verstehen, was es tut. In diesem Fall kann die eine oder andere Version der sogenannten „Meta-Schicht“ verwendet werden - eine hypothetische Komponente des Betriebssystems, die den gesamten Ablauf des Programms verfolgt (Funktionen aufrufen, Daten im Speicher ändern usw.) und ein ungefähres Modell seiner Logik darin erstellt. eine Form, die der Funktionsweise eines Programms in einer beliebigen Programmiersprache entspricht. Dann bleibt das umgekehrte Problem für ein solches Programm zu lösen - ein mögliches Anfangsmodell (oder mögliche Modelle) wiederherzustellen, das es zumindest ermöglicht, die Richtigkeit zu bewerten oder den Zweck des Programms zu verstehen. Der Prototyp eines solchen „Metaslayers“ wurde einst vom Autor für den Fall von C / C ++ - Programmen entwickelt, nicht so viel war möglich, aber etwas funktionierte. Vielleicht wird irgendwann jemand solche Arbeiten in vollem Umfang ausführen wollen.

6. Fazit

Ich hoffe, ich konnte zeigen, dass die automatische Generierung von Programmen und die Lösung des inversen Problems keine rein akademischen Probleme sind, sondern etwas Nützliches und direkte praktische Konsequenzen haben. Gleichzeitig geben die hier vorgestellten Entscheidungen nicht vor, vollständig und offensichtlich zu sein, sondern sie werden umgesetzt und geben eine bestimmte Neuheit vor.