scp-notes-ru

Проблемно-ориентированные языки и суперкомпиляция

Сергей Романенко

29 июня 2009 г.

Наконец, наступил подходящий момент, чтобы обсудить связь между языком Рефал, суперкомпиляцией и “проблемно-ориентированными языками” (которые на великом и могучем англосаксонском наречии часто именуют как “domain-specific languages”).

Тема, конечно, необъятная, поэтому я ограничусь рассмотрением только двух подходов к использованию суперкомпиляции для разработки, реализации и использования проблемно-ориентированных языков.

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

А второй подход я, также чисто условно, буду называть подходом “высшего порядка”. А в чём он состоит - увидим по ходу дела.

Итак, начнём с языка Рефал. Было время, когда он весьма продуктивно использовался в СССР для “решения задач, имеющих важное народнохозяйственное значение”. Прагматично настроенные люди (среди которых был и я) рассматривали Рефал примерно как ишака, на котором можно было ездить и возить воду. Т.е., попросту говоря, использовали Рефал в качестве “обычного” языка программирования.

Однако, в момент своего возникновения, Рефал задумывался не в качестве ишака, а в качестве то ли лебедя, то ли орла, предназначенного для воспарения в высшие сферы. И назывался он более возвышенно и поэтично: “метаалгоритмический язык” (в пику всяким жалким фортранам и алголам, претендовавшим в том время всего-навсего на звание “алгоритмических языков”)! Если кто мне не верит, может раскрыть статью 1968 года и посмотреть, что там написано:

Рефал был предназначен не для того, чтобы писать на нём программы напрямую, а для того, чтобы с его помощью реализовывать языки, ориентированные на конкретные классы задач (проблемно-ориентированные языки, domain-specific languages).

Задумано было хорошо и правильно! Но, увы, в должной мере “процесс” тогда “не пошёл”…

Скорее всего из-за того, что замысел требовал слишком много от тогдашнего “железа”. На дворе был 1968 год. В Институт Прикладной Математики привезли новый могучий компьютер БЭСМ-6, который выполнял аж 1 миллион операций в секунду. Памяти у БЭСМ-6 было аж 192 килобайта! И даже кеш памяти был размером в 16 48-битных слов: 4 чтения данных, 4 чтения команд, 8 — буфер записи.

(В скобках замечу, что в моём настольном компьютере, на котором я и сочиняю это послание, в данный момент имеется 4 гигабайта памяти. 4 000 000 / 192 = 20833.)

Вот, именно поэтому, в момент рождения Рефала воспарять было труднее, чем сейчас. Произошло примерно то же, что с самолётом Можайского: концептуально у Можайского всё было правильно. Но пропеллер крутила паровая машина…

Но с тех пор много воды утекло. Когда Рефал только появился, он вызвал у многих откровенный скепсис, переходящий в отвращение и возмущение. Главным образом из-за того, что был слишком не похож на “нормальный” язык. Люди пробовали на нём писать и начинали спрашивать: “а где в Рефале оператор цикла?”, “а где в Рефале оператор присваивания?”… А в Рефале ничего этого не было: были только данные в виде деревьев, сопоставление с образцом и рекурсивные функции. Это было чудовищно даже по сравнению с Лиспом. В Лиспе всё же были и предикаты, и условные выражения, и присваивания, и даже goto! Словом, “настоящему” программисту было на что опереться, было где “голову преклонить”. А в Рефале у человека последнее отнимали… И приговор у многих был однозначный: “Рефал - плохой язык. Потому что программировать на нём - неудобно!”

А самый убийственный аргумент состоял в том, что “Рефал невозможно эффективно реализовать”… Действительно, если нет “эффективной” реализации (“эффективной” по отношению к “железу”, которое было тогда, а не к тому, которое есть “сейчас”), то какое уж тут “воспарение”? О какой реализации проблемно-ориентированных языков с помощью Рефала можно говорить?

И действительно, на изготовления реализации, пригодной для использования “в народном хозяйстве”, ушло несколько лет: История Pефал-компилятора.

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

Впрочем, на первый взгляд, связь между Рефалом, проблемно-ориентированными языками и суперкомпиляцией не очевидна. Но она существует и заключается в следующем.

Рефал - язык первого порядка. И “классический” подход Турчина состоял в том, что на “метаалгоритмическом языке” нужно писать интерпретаторы, реализующие проблемно-ориентированные языки.

Допустим, есть язык L, который мы хотим реализовать. Пишем на Рефале интерпретатор intL, который берёт на входе программу prog и исходные данные этой программы input и выдаёт результат работы prog для входных данных input. Или, выражаясь более кратко, вычисляем intL(prog,input) и получаем результат применения prog к input.

При этом, теоретически, intL можно написать на любом “алгоритмическом языке”: можно на языке ассемблера, можно и на языке машины Тьюринга, а можно и на Рефале. В этом смысле, конечно, Рефал - это просто (ещё один) “алгоритмический язык”. Однако, был всё же некоторый резон, что при рождении Рефала он был объявлен “метаалгоритмическим языком”! Когда Рефал появился на свет, приятных и удобных языков для быстрого написания интерпретаторов просто не существовало! Ну, во всяком случае, на Рефале интерпретатор писался и отлаживался в 10 (а то и в 100) раз быстрее, чем на чём-либо другом.

Но сейчас, конечно, ситуация уже не та. Сегодня Рефал уже не воспринимается как что-то диковинное. Все новаторские идеи, которые когда-то были в него заложены, сегодня растащены по нескольким другим хорошо известным языкам. Например, рефальские структуры данных (не бинарные, как в Лиспе, а произвольные деревья) - это xml (который можно обрабатывать с помощью xslt). Сопоставление с образцом и рекурсивные функции - это Standard ML (SML) и Haskell. Так что, можно с полным основанием утверждать, что идеи, на которых был основан Рефал были правильными и здравыми, поскольку они выжили, победили, и превратились нечто “очевидное” и “тривиальное”. :-)

Вот и HLL, входной язык суперкомпилятора HOSC, по сути, включает Рефал в качестве подмножества: есть в нём и деревья, в качестве данных, и сопоставление с образцом, и рекурсивные функции. Правда, как объясняется в послании Суперкомпиляция функций высших порядков, есть и кое-что ещё, поэтому этот язык можно считать (если нравится) и подмножеством Хаскеля.

Попробуем-ка реализовать на HLL интерпретатор какого-нибудь проблемно-ориентированного языка!

В этом месте я призадумался… Извечная проблема всех программистов состоит в том, что трудно излагать какие-то абстрактные идеи, не приводя конкретных примеров их применения. А когда программист пытается придумать пример, он “попадает в клещи”: если придумать “реалистичный” пример, то он получается таких размеров, что не влезает ни в статью, ни в слайды. А если пример маленький, дегенеративный, то в нём и смысла никакого нет: он получается слишком “тривиальным” и “нереалистичным”.

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

Допустим, нам хочется реализовать проблемно-ориентированный язык, предназначенный для распознавания регулярных выражений. Будем, для краткости, называть его языком R. И реализуем в виде интерпретатора intR, который будет принимать на входе программу на языке R и входную цепочку, которую нужно проанализировать. Другими словами, вызов интерпретатора будет выглядеть так:

intR r i

где r - программа на языке R, а i - входная цепочка. Задача интерпретатора - “откусить” от i начало, удовлетворяющее программе r. В случае успеха, intR будет выдавать Some j, где j - остаток входной цепочки, а в случае неуспеха intR будет выдавать None.

Теперь нам нужно конкретизировать, что должны из себя представлять r и i? Будем считать, что на вход подаётся цепочка из букв A, B и С, завершающаяся “признаком конца файла” Eof. На языке HLL совокупность таких цепочек описывается с помощью объявления типа данных Input:

data Input = Eof | A Input | B Input | C Input;

А множество допустимых программ на языке R опишем с помощью такого типа данных:

data R = Seq R R | Alt R R | Opt R | Rep R | IsA | IsB | IsC;

Смысл конструкций языка R следующий:

Для выдачи результатов из интерпретатора нам также понадобится тип данных Option:

data Option a = None | Some a;

Теперь мы можем записать на языке R, например, такую программу:

Seq IsA (Rep (Alt IsA IsB))

соответствующую, в более привычных обозначениях, регулярному выражению A (A | B)*. Т.е. входная цепочка должна начинаться с A, а потом должна следовать цепочка, состоящая только из A и В.

Теперь можно написать функцию, реализующую интерпретатор intR. Вызов этой функции, как уже говорилось, должен иметь вид intR r i. Понятно, что intR должен анализировать r, и для каждой разновидности r должна быть предусмотрена соответствующая обработка. Поэтому, intR имеет следующую структуру:

intR = \r i -> case r of {
  Seq r1 r2 -> ...;
  Alt r1 r2 -> ...;
  Opt r1 -> ...;
  Rep r1 -> ...;
  IsA -> ...;
  IsB -> ...;
  IsC -> ...;
};

где внутри многоточий интерпретатор что-то делает и, если надо, рекурсивно вызывает сам себя.

Дописав недостающие части интерпретатора и собрав все куски вместе, получаем такую программу на языке HLL:

data Input = Eof | A Input | B Input | C Input;
data R = Seq R R | Alt R R | Opt R | Rep R | IsA | IsB | IsC;

data Option a = None | Some a;

intR (Seq IsA (Rep (Alt IsA IsB))) i

where

intR = \r i -> case r of {

  Seq r1 r2 -> case intR r1 i of {
    None -> None;
    Some j -> intR r2 j;
  };

  Alt r1 r2 -> case intR r1 i of {
    None -> intR r2 i;
    Some j -> Some j;
  };

  Opt r1 -> case intR r1 i of {
    None -> Some i;
    Some j -> Some j;
  };

  Rep r1 -> case intR r1 i of {
    None -> Some i;
    Some j -> intR (Rep r1) j;
  };

  IsA -> case i of {
    Eof -> None; A j -> Some j; B j -> None; C j -> None;
  };

  IsB -> case i of {
    Eof -> None; A j -> None; B j -> Some j; C j -> None;
  };

  IsC -> case i of {
    Eof -> None; A j -> None; B j -> None; C j -> Some j;
  };
};

В этой программе перед ключевым словом where находится “целевое” выражение

intR (Seq IsA (Rep (Alt IsA IsB))) i

содержащее одну свободную переменную i, через которую и передаются исходные данные в HLL-программу. А исполнение программы сводится к вычислению “целевого” выражения.

Теперь засовываем всю программу в суперкомпилятор HOSC и получаем такую остаточную программу:

data Input  = Eof  | A Input | B Input | C Input;
data R  = Seq R R | Alt R R | Opt R | Rep R | IsA  | IsB  | IsC ;
data Option a = None  | Some a;

case  i  of {
 Eof  -> None;
 A y2 ->
   (letrec
     f=(\s16->
       case  s16  of {
         Eof  -> (Some Eof);
         A u12 -> (f u12);
         B x16 -> (f x16);
         C x15 -> (Some (C x15)); })
   in
     (f y2));
 B x2 -> None;
 C v1 -> None;
}

Всё без обмана! Кто не верит, может посмотреть этот пример “вживую”: Parsing (first order)

Хорошо видно, что, в результате суперкомпиляции, и исходная программа на языке R, и интерпретатор intR как бы “растворились” в остаточной программе. Из программы на языке R получилась программа на языке HLL, которая напрямую делает “то, что надо”.

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

А применительно к проблемно-ориентированным языкам вывод такой: суперкомпиляция даёт возможность реализовывать предметно-ориентированные языки с помощью интерпретаторов, а потом удалять “слой интерпретации” с помощью суперкомпиляции.

Зафиксировав это приятный факт, переходим к “следующему пункту цирковой программы”: использованию функций высших порядков для реализации предметно-ориентированных языков.

Этот подход основан на использовании “комбинаторов”: функций, которые берут одну или несколько функций в качестве аргументов и вырабатывают новую функцию в качестве результата.

Попробуем применить комбинаторы для анализа регулярных выражений. Для этого введём понятие “парсера”. А именно, будем называть “парсером” любую функцию p, берущую на входе цепочку i типа Input

data Input = Eof | A Input | B Input | C Input;

и возвращающую либо None (что означает, что парсер “отвергает” цепочку), либо Some j, где j - “хвост” цепочки i (что означает, что парсер “откусил” от i начальный участок).

Кстати, интерпретатор IntR, с формальной точки зрения, можно было бы рассматривать как “преобразователь программ на языке R в парсеры”, считая, что intR принимает два аргумента r и i не сразу, а по-очереди. Т.е., сначала вычисляем intR r и получается парсер, который потом и применяем к i. Формально-то это, конечно, так, на на самом-то деле intR устроен так, что он ничего даже и не начинает вычислять до тех пор, пока не получит оба аргумента!

А в случае “комбинаторного” подхода идея заключается в том, что можно работать с парсерами напрямую: реализовать несколько простейших парсеров, а потом собирать более сложные парсеры из более простых с помощью “комбинаторов”.

Другими словами, в случае подхода “первого порядка” у нас был язык, в котором было несколько синтаксических конструкций, и эти конструкции позволяли собирать новые программы, исходя из более простых. Например, в языке R была конструкция Alt, которая из двух программ r1 и r2 делала новую программу Alt r1 r2. Т.е. одни сущности первого порядка преобразовывались в другие сущности первого порядка.

А в случае “комбинаторного” подхода идея заключается в том, что синтаксические конструкции можно заменить на комбинаторы, преобразующие одни функции в другие. В частности, языку R соответствует такой набор комбинаторов:

Например, seq реализуется следующим образом:

seq = \p1 p2 i -> case p1 i of { None -> None; Some j -> p2 j; };

При этом, вызов интерпретатора intR

intR (Seq IsA (Rep (Alt IsA IsB))) i

превращается в

seq isA (rep (alt isA isB)) i

Теперь мы можем переписать всю программу в духе “высшего порядка”, рассыпав интерпретатор intR на отдельные комбинаторы. Получается

data Input = Eof | A Input | B Input | C Input;
data Option a = None | Some a;

seq isA (rep (alt isA isB)) i

where

seq = \p1 p2 i -> case p1 i of {
  None -> None;
  Some j -> p2 j;
};

alt = \p1 p2 i -> case p1 i of {
  None -> p2 i;
  Some j -> Some j;
};

opt = \p i -> case p i of {
  None -> Some i;
  Some j -> Some j;
};

rep = \p i -> case p i of {
  None -> Some i;
  Some j -> rep p j;
};

isA = \i -> case i of {
  Eof -> None; A j -> Some j; B j -> None; C j -> None;
};

isB = \i -> case i of {
  Eof -> None; A j -> None; B j -> Some j; C j -> None;
};

Засовываем эту программу в суперкомпилятор HOSC и получаем остаточную программу

data Input = Eof | A Input | B Input | C Input; data Option a = None |
Some a;

case  i  of {
  Eof  -> None;
  A v1 ->
    (letrec
      f=(\y3->
        case  y3  of {
          Eof  -> (Some Eof);
          A s2 -> (f s2);
          B u -> (f u);
          C t -> (Some (C t)); })
    in
      (f v1));
  B r -> None;
  C x1 -> None;
}

И эта программа (с точностью до имён переменных) совпадает с остаточной программой, которая получилась в результате специализации интерпретатора intR по отношению к R-программе! “Вживую” этот пример можно посмотреть здесь: Parsing (higher order = combinators).

Итак, суперкомпиляция позволяет избавиться от накладных расходов, связанных с интерпретацией, при реализации проблемно-ориентированных языков.

Причём, при наличии суперкомпилятора, способного работать с функциями высших порядков, можно использовать два подхода:

Какой же из двух подходов “лучше”? А кто-ж его знает… Как говорится, “на вкус и цвет - товарищей нет”.

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

В случае интерпретатора первого порядка, приходится иметь дело как с синтаксисом, так и с семантикой интерпретируемого языка. Во-первых, только в случае совсем простых проблемно-ориентированных языков (ПО-языков) можно работать с исходной программой напрямую. Если ПО-язык не совсем тривиален, программу надо сначала подвергнуть лексическому и синтаксическому анализу и преобразовать её в дерево абстрактного синтаксиса, с которым уже и имеет дело интерпретатор.

Поэтому, в нетривиальных случаях, на вход интерпретатора первого порядка подаётся ПО-программа в виде синтаксического дерева и исходные данные для этой программы. Если изучить такой интерпретатор, то обнаруживается, что он выполняет следующие действия:

С помощью проекций Футамуры можно убрать слой интерпретации, так, чтобы остались только “полезные” операции над данными.

В случае ПО-программы, реализованной через комбинаторы, получается другая картина.

Отсюда и преимущества “комбинаторного” подхода:

А с точки зрения суперкомпиляции, комбинаторный подход выглядит более привлекательным просто потому, что он “облегчает жизнь” суперкомпилятору. Да просто потому, что интерпретатор первого порядка, помимо “полезных” действий, содержит и массу “административных”, которые суперкомпилятору приходится удалять. Получается абсурдная картина: человек старался-старался, писал интерпретатор, реализовывал анализ синтаксиса, работу с переменными, циклами и вызовами функций. И для чего? Только для того, чтобы частичный вычислитель или суперкомпилятор всё это удалил!

Получается, что сначала трудности героически создаются (человеком), а потом - героически преодолеваются (суперкомпилятором). А зачем? Вот основная идея комбинаторного подхода и состоит в том, что “умный в гору не пойдёт, умный гору обойдёт”. И от этого становится лучше и программисту, и суперкомпилятору. Но при одном условии: если у суперкомпилятора “хватает мозгов” для работы с функциями высших порядков.

Оригинал послания и комментарии