Здравствуйте, уважаемые читатели. В этой статье речь пойдет об одном подходе к автоматическому порождению программ по блочной модели задачи, к решению обратной задачи (восстановления модели исходной проблемы по уже порожденной программе), а также к решению проблемы верификации порожденных программ. Сама по себе тема очень серьезная, но статью я, по возможности, постараюсь сделать популярной (без тяжеловесного обзора аналогов, строго оформленной теоретической части и прочих сложностей), с примерами и описанием различных применений.

1. Автоматическое порождение программ


Для генерации любой программы требуется, прежде всего, знать, какую задачу мы решаем. Имея четкую формализованную постановку задачи, уже можно строить некие правила разворачивания этой постановки в план решения задачи и правила преобразования плана решения в конечный код на обобщенном или конкретном алгоритмическом языке. При этом обычно используется подход к построению конечной программы из готовых, созданных заранее, блоков – типовых алгоритмов, которые связываются неким вызывающим/обслуживающим кодом.

Пусть исходная постановка решаемой задачи представляется в виде блочной схемы (блоки могут быть элементарными или, в свою очередь являться подсхемами), например, сети объектов, каждый из которых относится к некоторому классу из иерархии классов-понятий предметной области. Такая постановка будет вполне наглядна и понятна как человеку, так и системе порождения программы. Такую постановку система должна преобразовать в план решения задачи по некоторым логическим правилам. Значит, правила такого преобразования было бы уместно писать на каком-нибудь языке логического программирования, я выбрал GNU Prolog. На практике, замечу, часто можно «пропустить» эту первую фазу (высокоуровневое описание задачи), сразу построив описание плана решения, также в виде блочной сетевой схемы.

Полученный план решения следует преобразовать в программу, как я уже писал, представляющую собой код, связывающий типовые алгоритмы решения «кирпичиков» задачи, реализованные, например, в виде библиотеки функций. Здесь возможны самые различные пути, опишу в нескольких словах использованный мной подход. Процесс порождения представляется в виде последовательности событий (например, генерация деклараций, генерация инициализационной части, этапы основной части, деинициализация), на каждое из которых сеть объектов должна покаскадно (имеются в виду каскады сети, такая схема исключает зацикливание модели при обработке события) реагировать генерацией соответствующих фрагментов кода. При этом объекты опираются на идентификатор события, значения своих параметров (задаются пользователем при построении блочной постановки задачи), а также на данные, которые они могут передавать друг другу по связям между ними. Поэтому каждый объект из плана решения имеет методы реакции на такие события, генерирующие код (а в общем случае – произвольный текст). Для решения такой задачи я выбрал язык PHP – он как раз прекрасно может генерировать произвольные текстовые фрагменты.

Настройка системы на предметную область выполняется путем разработки соответствующей иерархии порождающих классов.

Пример порождающего скрипта, генерирующего код для класса «Обработка вектора (минимум, максимум, среднее арифметическое)»:

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

Это сравнительно несложная схема, которая работает. Система, реализующая такую схему порождения (PGEN++) позволяет, например, генерировать решающие программы в следующих областях:

а) моделирование процессов распространения загрязнений;
б) решение некоторых задач кинематики простых манипуляторов роботов;
в) простые учебные программы для работы с векторными данными (поиск минимума, максимума, среднего арифметического);
г) разработка тестов для системы психологического тестирования ПРОФТЕСТ.

Вот пример исходной постановки задачи (простая программа обработки векторных данных) в виде блочной схемы:



А это результат порождения программы:



2. Обратная задача: реконструкция постановки задачи (исходной модели) по порожденной программе. Верификация порожденных программ


Прежде всего, для чего необходимо решение такой задачи. Ее прямое, и, думаю, самое очевидное применение – верификация автоматически порожденных программ. Если мы имели модель А, построили по ней программу П, из которой реконструировали модель Б, то программа, скорее всего, корректна при совпадении моделей А и Б.

Предлагается следующее простое решение. В автоматическом порождении программы фигурировали порождающие объекты, относящиеся к некоторой иерархии классов предметной области. Они имели только порождающие методы. Добавим к ним распознающие методы. Тогда исходная программа (или, в общем случае, любой текст) последовательно сканируется распознающими методами каждого класса, который, при успешном распознавании, генерирует объект/объекты этого класса. Получаем упорядоченный (в порядке «чтения» текста) набор параметризованных элементов модели. Остается определить связи между ними на основании порядка следования объектов и соотношения между их параметрами. Для этого можно применить специальные решающие правила.

Распознающий метод, в моей реализации, состоит из распознающей части (это группа модифицированных регулярных выражений) и решающей части (написанной на GNU Prolog). Регулярные выражения модифицированы таким образом, чтобы осуществлять некоторую предобработку (проверка по словарю, нечеткая проверка по похожести по Левенштейну, проверки на сбалансированность выражений по скобкам) еще на стадии разбора, для этого в них добавлена возможность включать разнообразные цепочки (проверяющие, добавляющие, удаляющие, обучающие нейронную сеть) «быстрых» предикатов.

Эта схема также работает. В качестве прямого применения она использовалась для реконструкции простых учебных программ для работы с векторными данными (поиск минимума, максимума, среднего арифметического), в таком случае она вполне успешно продемонстрировала возможную верификацию порожденных программ путем сравнения исходной и реконструированной моделей. Но есть и иные применения, о них дальше.

3. Естественно-языковой интерфейс для системы порождения программ


При решении обратной задачи (описана выше) нет каких-либо ограничений на вид исходных материалов для восстановления модели решаемой задачи. Это вполне может быть текст на естественном языке. Просто надо написать соответствующие распознающие методы. Поэтому, неожиданным применением обратной задачи может быть реализация естественно-языкового интерфейса к системе порождения:

а) пишется постановка задачи на упрощенном естественном языке;
б) решается обратная задача – из естественно-языковой постановки извлекается формальная постановка (сеть объектов-элементов предметной области);
в) система запускается на порождение программы по полученной формальной постановке.

И эта схема тоже работает. Пример разработан для того же случая простых учебных программ для работы с векторными данными.

Вот пример распознающего метода (класса «Ввод с клавиатуры вектора или скаляра»), который разбит на две версии (распознавание текта программы (режим Programmatical) или распознавание фрагмента постановки задачи на русском языке (режим Russian)). Сверху идет распознающая часть, далее решающие предикаты на 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.

Пример постановки задачи на русском языке:
Составить программу. Ввести скаляр max. Ввести скаляр min.

Введем вектор V из 10 элементов. Зададим вектор V с клавиатуры. Найдем минимум вектора V и поместим результат в скаляр min.

Найдем также максимум вектора V и поместим результат в скаляр max. Вывести скаляр min на экран. Вывести скаляр max на экран.

Вывести вектор V на экран.

А среднее арифметическое считать не будем.

И модель задачи, полученная системой из приведенного выше естественно-языкового описания:


4. Иные применения обратной задачи


Ничто не мешает при решении обратной задачи рассмотреть случай не просто распознавания некоторой программы, а ее распознавание «с улучшением» или иной (произвольного характера) переработкой. В частности, удалось разработать «автоматический параллелизатор» распознаваемой программы, написанной на языке C. Она проводит статический и, отчасти, динамический анализ распознаваемого кода и вставляет в него директивы распараллеливания из расширения Cilk/Cilk++. Такая задача улучшения реализуется распознающими методами (на GNU Prolog).

Пример вычислительной C-программы, обработанной параллелизатором (он вставил директивы cilk_spawn и 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. Немного фантастики. Верификация и идентификация произвольных программ с закрытым исходным кодом


Здесь речь уже идет о произвольных программах, написанных программистом и/или системой порождении программ, для которых просто нет исходного кода. Пусть требуется проверить корректность функционирования такой программы, или хотя бы даже понять, чем она занимается. В таком случае может быть использован тот или иной вариант так называемого «метаслоя» — гипотетического компонента операционной системы, который отслеживает всю последовательность работы программы (вызов функций, модификация данных в памяти и т.п.) и строит по ней приблизительную модель ее логики в виде эквивалентной по функционированию программы на каком-либо языке программирования. После чего остается решить для такой программы обратную задачу – восстановить возможную исходную модель (или модели), которые позволили бы хотя бы оценить правильность или понять предназначение программы. Прототип такого «метаслоя» когда-то разрабатывался автором для случая C/C++-программ, удалось не так уж много, но кое-что работало. Возможно, когда-нибудь кто-нибудь захочет такую работу выполнить в полноценном объеме.

6. Заключение


Надеюсь, что сумел продемонстрировать, что и автоматическое порождение программ и решение обратной задачи – не чисто академические проблемы, а нечто полезное и имеющее прямые практические следствия. При этом изложенные здесь решения не претендуют на полноту и очевидность, но они реализованы и претендуют на определенную новизну.

Комментарии (9)


  1. begemot_sun
    20.08.2018 11:23

    > Составить программу. Ввести скаляр max. Ввести скаляр min.
    по сути сложность не уменьшилась, а вот лаконичность пострадала.
    Мне кажется проще тоже самое написать на обычном языке программирования.


    1. pekunov Автор
      20.08.2018 14:06

      Да, это учебный пример (можно использовать при обучении программированию, показывая, какие программы можно получать для решения различных простых задач). Профессиональному программисту такую программу, конечно, написать несложно. Порождение же программ оправданно для решения сложных задач, когда однократно затраченное на создание порождающих классов время намного меньше суммарного времени на написание требуемых программ специалистом.


      1. begemot_sun
        20.08.2018 14:44

        В данном случае следует просто говорить про DSL и компиляцию из одного языка программирования в другой.


        1. pekunov Автор
          20.08.2018 15:39

          DSL — действительно, одно из направлений прикладного автоматического порождения программ. Но ни решение задачи, обратной порождению, ни строгая верификация порождённой программы, для DSL-направления не характерны, насколько я знаю.


  1. hardmodebitch
    20.08.2018 16:57

    Совершенно не понял, о чём статья. Вот от слова совсем. Гугление по встречающимся в статье терминам («порождение кода», «автоматическое порождение программ») не дало никаких адекватных результатов. Поясните, пожалуйста, в двух словах, зачем всё это нужно и где можно прочесть более подробно об описанных в статье процессах? Очень не люблю, когда мне что-то не понятно даже приблизительно.


    1. pekunov Автор
      20.08.2018 17:16

      Если в нескольких словах: речь идет о создании такой системы, которая во-многом заменяет программиста, поскольку позволяет:
      а) описывать решаемую задачу в виде некоторой схемы;
      б) автоматически генерировать по такой схеме программу, решающую данную задачу;
      в) решать обратную проблему: брать некоторую программу и, хотя бы частично, распознавать, какую задачу эта программа решает.
      Кроме того, речь идет о некоторых побочных применениях такой системы: о том, что можно генерировать программу не только по некоторой визуальной блочной схеме, но и по текстовому описанию этой задачи, например на русском языке (с упрощениями и ограниченими).
      Можно почитать про DSL (Domain Specific Language). Похожими вещами также занимается, например, программа Rational Rose. Кроме того, на схожие темы существуют бумажные книги (например, немного, но есть в книге К.Чарнецки, У.Айзенекера «Порождающее программирование: Методы, инструменты, применение»). Есть много научных книг и статей, например, про SWITCH-технологии, можете поискать в Интернете.


  1. true-grue
    20.08.2018 20:09

    К сожалению, «определенной новизны» я в тексте не увидел. Метапрограммирование, генераторы программ, графическое программирование, DSL...— все это известно давно, согласитесь.

    В этом смысле обзор аналогов, от которого Вы отказались, был бы весьма кстати. Комментаторы справедливо указывают, что четких терминов, которые можно легко нагуглить, у Вас практически нет. Вашу «прямую задачу» в настоящее время связывают с направлением program synthesis (superoptimization и другие подходы «на примерах»). К «обратной задаче» относится направление automatic algorithm recognition (в этом контексте постановка задачи автораспараллеливания как раз весьма и весьма уместна). Оба этих направления чрезвычайно перспективны и по ним уже накоплен определённый объём серьезных результатов.


    1. pekunov Автор
      20.08.2018 20:25

      Все изложенное основано на идее применения особого вида моделей, которые я называю объектно-событийными (ОСМ). В этом и состоит новизна, если в паре слов.


  1. berez
    20.08.2018 20:09

    Пусть исходная постановка решаемой задачи представляется в виде блочной схемы ...

    Напомнило язык ДРАКОН.