Разные мысли о метавычислениях, суперкомпиляции, специализации программ. И об их применениях. Желающие приглашаются в соавторы блога.

понедельник, 29 июня 2009 г.

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

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

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

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

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

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

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

  • Турчин В.Ф. Метаалгоритмический язык. — Кибернетика № 4, 1968. С. 116−124. DJVU PDF

Рефал был предназначен не для того, чтобы писать на нём программы напрямую, а для того, чтобы с его помощью реализовывать языки, ориентированные на конкретные классы задач (проблемно-ориентированные языки, 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 следующий:

  • Seq r1 r2. Попытаться отщепить от цепочки начальный кусок с помощью r1. Если получится - попытаться отщепить от остатка начальный кусок с помощью r2.
  • Alt r1 r2. Попытаться отщепить от цепочки начальный кусок с помощью r1. Если не получится - попытаться отщепить от той же цепочки начальный кусок с помощью r2.
  • Opt r1. Попытаться отщепить от цепочки начальный кусок с помощью r1. Если не получится, отщепить пустую цепочку.
  • Rep r1. Попытаться отщепить от цепочки начальный кусок с помощью r1 максимально возможное число раз.
  • IsA, IsB, IsC. Попытаться отщепить от цепочки A, B или C соответственно.

Для выдачи результатов из интерпретатора нам также понадобится тип данных 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 r1 r2. Пытается отщепить от цепочки начальный кусок с помощью r1. Если получилось - пытается отщепить от остатка начальный кусок с помощью r2.
  • alt r1 r2. Пытается отщепить от цепочки начальный кусок с помощью r1. Если не получилось - пытается отщепить от той же цепочки начальный кусок с помощью r2.
  • opt r1. Пытается отщепить от цепочки начальный кусок с помощью r1. Если не получилось, отщепляет пустую цепочку.
  • rep r1. Пытается отщепить от цепочки начальный кусок с помощью r1 максимально возможное число раз.
  • isA, isB, isC. Пытается отщепить от цепочки A, B или C соответственно.

Например, 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).

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

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

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

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

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

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

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

  • Хождение по синтаксическому дереву и анализ этого дерева.

  • Работа со средой (поддержание списков переменных и их значений).

  • Деятельность, связанная с организацией управления в интерпретируемой программе (циклы, рекурсия, вызов функций и передача параметров).

  • И, наконец, операции над теми данными (проверки и вычисления), которые должна обрабатывать ПО-программа. Строго говоря, только эти операции и являются "практически полезными". А всё остальное - это "административные накладные расходы".

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

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

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

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

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

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

  • Реализация ПО-языка через комбинаторы более проста для понимания. При чтении интерпретатора происходит "раздвоение сознания" из-за того, что "содержательные" действия перемешаны с "административными", и приходится думать одновременно и о тех, и о других. А в случае комбинаторов, приходится разбираться только с "полезными" действиями.

  • Основная трудность при чтении интерпретатора состоит в том, что все его части завязаны в один "тугой узел". Т.е., невозможно понять ни одну из его частей, не разобравшись с остальными. А в случае набора комбинаторов, каждый комбинатор можно изучать отдельно от других, поскольку они связаны между собой, как правило, только через входные/выходные данные (про которые достаточно знать только их типы).

  • Интерпретатор первого порядка трудно расширять из-за сильной взаимосвязи всех его частей. Сделав локальное изменение, легко обрушить всю конструкцию. Следовательно, и ПО-язык, реализуемый этим интерпретатором, трудно расширять. А в случае набора комбинаторов, добавление новых комбинаторов обычно никак не затрагивает старые. Поэтому, и ПО-язык легче поддаётся расширению.

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

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

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

четверг, 18 июня 2009 г.

Прогонка для функций высших порядков

В заметках

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

Сейчас мы постараемся подробнее разобраться, как выглядит прогонка в случае "ленивого" языка с функциями высших порядков. Суперкомпилятор HOSC обрабатывает программы именно на языке такого рода: Higher Order Lazy Language (HLL).

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

d1 ... dN e0 where f1 = e1; ... fN = eN;

и содержит следующие части:

  • d1 ... dN - объявления типов для данных, обрабатываемых программой. (Сейчас эта часть программы нас не очень интересует.)

  • e0 - "целевое" выражение. Считается, что исполнение программы сводится к вычислению e0. Если e0 содержит свободные переменные, то через них в программу передаются исходные данные.

  • f1 = e1; ... fN = eN; - определения глобальных функций. Эти функции могут использоваться внутри целевого выражения e0 .

Вот пример программы:

data Nat = Z | S Nat;

add a b

where

add = \x y -> case x of { Z -> y; S x1 -> S (add x1 y); };

Целевое выражение содержит три свободные переменные a и b, через которые в программу и передаются исходные данные, а исполнение программы сводится к тому, что в целевое выражение add a b подставляются значения переменных a и b, после чего получившееся выражение и вычисляется.

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

Заметим, что в случае вычислений первого порядка (как в суперкомпиляторе SPSC) было достаточно сказать, что выражение вообще не содержит переменные (или содержит), а в случае высшего порядка приходится ещё различать свободные и связанные переменные.

Как выполняется такого рода программа, сначала рассмотрим на примере. (И, с точки зрения людей, пишущих на Фортране, такой способ исполнения программы выглядит как чистое извращение. :-) )

Допустим, на вход поступили такие данные:

a = S Z;

b = Z;

Подставляем значения a и b в add a b. Получается

add (S Z) Z

И вот тут-то и начинается самое страшное. В случае языка первого порядка (как в SPSC) мы сразу же, за один шаг, преобразовали бы это выражение в выражение

S (add Z Z)

сделав много разных дел:

  1. Нашли бы определение функции add.
  2. Распознали бы, какое правило из определения add применить. А для этого нужно было бы выполнить сопоставление в образцом.
  3. Применили бы правило.

Но то, что было в случае "первого порядка" одним большим действием, в случае HLL разбивается на несколько более элементарных действий. Разбиение на мелкие действия хорошо с точки зрения компьютера, с точки зрения тех, кто пишет статьи о суперкомпиляторе, и даёт некоторые дополнительные возможности в процессе преобразований. Но есть и "оборотная сторона медали"! При попытке "прокрутить" какие-то примеры вручную, на бумаге, сразу же оказывается, что граф конфигураций жутко раздувается. Точнее, раздувается не сам граф, как таковой, а конфигурации, находящиеся внутри узлов графа. Что мы сейчас и увидим.

Итак, смотрим на выражение

(add (S Z) Z)

На верхнем уровне - вызов функции add. Хорошо бы его применить к аргументам. Чтобы сделать это, ищем определение функции add, и подставляем его вместо имени функции! Таков уж язык высшего порядка. В случае первого порядка, программа и данные строго разделены, но если мы объявили, что функции являются "равноправными значениями" (first-class values), различие между "программой" и "данными" рассеивается как утренний туман (или, говоря ещё более поэтично, как нежные лепестки цветка сакуры под весенним ветром). Если число можно подставить, можно и функцию подставить. Что и делаем. Получается вот такая гадость:

(\x -> (\y -> case x of { Z -> y; S x1 -> S (add x1 y); })) (S Z) Z

Концептуально - ясно и понятно. Но выписывать руками - сущее мучение.

Теперь выражение имеет вид (\v -> e0) e1, и понятно, что нужно сделать дальше: применить функцию к аргументу. Т.е. в e0 заменить все вхождения v на e1. Конкретно, (\x -> ...) применяем к S Z и получаем

(\y -> case S Z of { Z -> y; S x1 -> S (add x1 y); }) Z

Теперь (\y -> ...) применяем к Z. Получается

case S Z of { Z -> Z; S x1 -> S (add x1 Z); }

И вот теперь наступает момент, когда нужно выполнить "сопоставление с образцом". Аргумент case-выражения содержит конструктор S на верхнем уровне. Поэтому, S Z сопоставляется с образцом S x1. При этом, переменная x1 принимает значение Z. После чего, мы извлекаем из case-выражения ветвь

S x1 -> S (add x1 Z);

и подставляем в S (add x1 Z) значение переменной x1, т.е. Z. После чего обрабатываемое выражение принимает вид:

S (add Z Z)

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

Но в случае "ленивого" языка, результат вычисления может выдаваться потребителю не весь сразу - а частями. В данном случае, "частичный результат" (в виде конструктора S на верхнем уровне) - налицо. Поэтому, можно считать, что вычисление "частично закончено". Но, предположим, что некий потребитель "съел" верхний конструктор, и захотел использовать значение его аргумента add Z Z. Ну что же, тогда вычисление возобновляется, и получается такая последовательность преобразований:

add Z Z

(\x -> (\y -> case x of { Z -> y; S x1 -> S (add x1 y); })) Z Z

(\y -> case Z of { Z -> y; S x1 -> S (add x1 y); }) Z

case Z of { Z -> Z; S x1 -> S (add x1 Z); }

Z

Т.е., "совсем" окончательный результат - S Z.

А теперь наступил момент, когда нужно перейти от "обычных" вычислений к "метавычислениям". Что будет, если не подавать в программу исходные данные, а оставить в целевом выражении переменные, и попытаться вычислять "прямо так"? Оказывается, что это - не так уж трудно. Начинаем с выражения add a b. И видим, что несколько первых шагов делаются точно так же, как и в случае известных исходных данных:

add a b

(\x -> (\y -> case x of { Z -> y; S x1 -> S (add x1 y); })) a b

(\y -> case a of { Z -> y; S x1 -> S (add x1 y); }) b

case a of { Z -> b; S x1 -> S (add x1 b); }

А вот теперь появляется интересная ситуация: в аргументе case-выражения - переменная a, значение которой неизвестно. Как выбрать нужную ветвь в case-выражении?

Единственный выход - действовать "разбором случаев": рассмотреть отдельно два случая: a = Z и a = S a1, где a1 - новая переменная, которая не встречалась в программе. В этот момент линейная последовательность вычислений превращается в дерево!

Итак, для случая a = Z получается

case Z of { Z -> b; S x1 -> S (add x1 b); }

b

А для случая a = S a1 получается

case S a1 of { Z -> b; S x1 -> S (add x1 b); }

S (add a1 b)

Дальше мы извлекаем из конструктора его аргумент, и начинаем изучать процесс его вычисления отдельно (как и в случае языка первого порядка). И видим, что нам повезло: изучать-то нечего, поскольку add a1 b совпадает (с точностью до имён переменных) с начальной конфигурацией add a b. Значит, можно сделать зацикливание и получить конечный граф конфигураций:

.

Суперкомплятор HOSC именно такой граф и делает: add a b.

Впрочем, этот граф виден, если рассматривать пример через FireFox, ибо для рисования графа используется svg-графика. FireFox рисует эти графы хорошо, а видно ли в других браузерах - не уверен. Кажется, нужно какие-то плагины устанавливать для отрисовки svg-графики...

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

(Но тех, кому интересно, могу порадовать тем, что в работе сейчас находится документ, в котором будут подробно описаны внутренности суперкомпилятора HOSC, в виде формул и всего прочего, что должно быть в "научных" сочинениях.)

Более интересен другой вопрос! Ну хорошо, с прогонкой "высшего порядка" всё, вроде, получается. Но ведь в суперкомпиляторе, кроме прогонки, нужно делать и кое-что ещё: сравнивать конфигурации, строить обобщения конфигураций, проверять, вкладывается ли одна конфигурация в другую или нет?

И здесь возникают кое-какие тонкости, связанные с тем, что в случае "высшего порядка", переменные в конфигурациях могут быть как свободными, так и связанными (в то время, как в случае "первого порядка", связанные переменные в конфигурациях не появлялись).

Но это - тема для отдельного разговора...

воскресенье, 14 июня 2009 г.

Суперкомпиляция функций высших порядков

В послании Что такое суперкомпиляция? было описано, как выглядит суперкомпиляция для случая простого функционального языка "первого порядка".

Теперь пришло время поговорить о суперкомпиляции функций "высших порядков". Что такое "высший порядок", хорошо знает любой поклонник функционального программирования (если, конечно, под "функциональными языками" подразумевать языки вроде Standard ML и Haskell). Однако, как я подозреваю, среди программистов всё ещё встречаются отсталые элементы, ещё не проникшиеся возвышенными принципами "высшей функциональности". :-)

Поэтому, во избежание всякого рода недоразумений, начну рассказ с рассмотрения вопроса, чем, собственно говоря, "высший" порядок отличается от "первого"?

Что такое "язык первого порядка"? Обычно имеют в виду, что имеется некое разделение/сегрегация/дискриминация обрабатываемых данных на данные "первого порядка" (first-order) и "высших порядков" (higher-order). Применительно к функциональным языкам это (как правило) сводится к тому, что проводится различие между "функциями" и "нефункциями". "Нефункции" - это "обычные" данные, вроде чисел, строк, деревьев, а "функции" - ну, это "функции", которые можно применять к данным "первого порядка"...

Как известно, в мире людей всякая дискриминация и сегрегация считается чем-то подозрительным и нехорошим (а на ЮАР за это даже санкции накладывали). Поэтому, и в случае программирования, язык, в котором цветёт пышным цветом дискриминация и сегрегация, выглядит как-то нехорошо. Дело усугубляется ещё и следующей патологией. Поскольку функции являются сущностями "высшего порядка", было бы естественно ожидать, что они должны обладать большими "правами и возможностями" по сравнению с сущностями "первого порядка". В мире людей дело обстоит именно так: дискриминация заключается в том, что вывешиваются таблички "только для...", и те, кого пускают - это "высшие", а кого не пускают - это "низшие". Но в мире программирования всё устроено ровно наоборот! В случае языка "первого порядка", разные ограничения "прав и свобод" имеют место как раз в отношении "высших". Например, строка может выдаваться в качестве результата функции, а функция - не может. Строка может быть элементом списка - а функция не может.

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

Кстати, не следует путать английские термины "first-order" и "first-class"! С виду - похоже, а смысл - разный. "First-class" - означает именно "полноправный", по аналогии с выражением "полноправный гражданин" ("a first-class citizen").

Итак, в чём же заключается "полноправие" функций в языке высшего порядка? А в том, что с функциями можно обращаться так же, как со значениями "первого порядка":

  1. Новые функции могут порождаться динамически в процессе работы программы.

  2. Функции могут передаваться внутрь других функций в качестве параметров.

  3. Функции могут выдаваться в качестве результатов функций.

  4. Функции могут вставляться внутрь данных "первого порядка" (например, в качестве элементов списков или аргументов конструкторов).

Итак, языки "высшего порядка" отличаются от языков "первого порядка" тем, что таблички "только для..." снимаются, и возможности функций возрастают. Но, конечно, на самом-то деле, возможности возрастают не только у функций, но и у программиста, который пишет программу. Можно делать то, что раньше делать было нельзя! Можно применять всякие трюки и приёмчики, которые в терминах языка первого порядка было невозможно даже сформулировать! При этом, однако, оказывается, что новые содержательные возможности требуют и некоторой ревизии на уровне синтаксиса языка программирования.

Рассмотрим, например, такую программу на языке первого порядка:

a1(Nil) = Nil;
a1(Cons(x, xs)) = Cons(S(x), a1(xs));
a2(xs) = a1(a1(xs));

Эта программа работает с натуральными числами, представленными в виде Z, S(Z), S(S(Z)), и списками, представленными в виде Cons(A, Cons(B, Cons(C, Nil))). Функция a1 "проходится" по элементам списка, и к каждому элементу списка прибавляет 1.

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

В языке первого порядка принято записывать применение функции f к аргументу x в виде f(x). До тех пор, пока функции не могут выдавать функции в качестве результата, такая запись удобна. Но, допустим, что результатом вычисления f(x) является функция, которую мы хотим применить к аргументу y. Тогда получается запись вида (f(x))(y). Выглядит уже как-то громоздко (даже если сократить её до f(x)(y)). Поэтому, в языках высшего порядка выражения вида f(x) начали записывать как f x. Преимущество такой записи особенно ясно проявляется именно в случае функций, вырабатывающих функции: вместо f(x)(y) получается f x y. При этом договорились, что "операция" применения функции а аргументу считается ассоциативной влево. Т.е. f x y z означает именно (((f x) y) z).

Извиняюсь, что трачу время и место для объяснения таких "тривиальных" вещей, но они тривиальны для тех, кто привык иметь дело с языками вроде SML или Хаскеля. А для всего остального человечества осознание того, что означает f x y z, требует некоторого "выворачивания мозгов наизнанку".

Конечно, переход к записи f x y z, кроме улучшения внешнего вида выражений, приводит и к некоторым другим последствиям. Например, в случае языков первого порядка, обычно имеются средства для определения функций от "нескольких аргументов". Например, применение функции f "от трёх аргументов" к x, y, z записывается как f(x, y, z). Что такое (x, y, z) - это в разных языках трактуется по-разному. Например, в SML считается, что все функции имеют ровно один аргумент, т.е. x, y, z нужно сначала "слепить" в одно значение (упорядоченную тройку), и подать на вход функции. А в некоторых языках, например, во входном языке специализатора Unmix или суперкомпилятора SPSC, считается, что каждая функция имеет фиксированную "арность" (arity), т.е. фиксированное количество аргументов на входе. В этом случае, запись f(x, y, z) должна восприниматься как единое целое, т.е. (x, y, z) без f отдельного смысла не имеет.

Однако, в случае языка высшего порядка, сразу же возникает "крамольная" мысль: а зачем нужны функции от нескольких аргументов. Вместо того, чтобы писать f(x, y, z) мы можем писать f x y z. При этом, конечно, требуется немного переопределить функцию f и считать, что после получения аргумента x функция f выдаёт не окончательный результат, а новую функцию (f x), которая ожидающую следующий аргумент y. Применяем эту функцию к y - и снова получаем функцию (f x y), ожидающую аргумент z. А вычислив (f x y) z получаем окончательный результат.

Что касается конструкторов для данных первого порядка (вроде конструктора Cons), то их вызовы тоже логично писать не как Cons(x, y), а как Cons x y...

Тут, правда, возникает такой вопрос: а как записать функцию, вырабатывающую функции? Для этого в языках высшего порядка предусмотрены "лямбда-выражения. Например, запись (\x -> S(x)) обозначает функцию, которая берёт x в качестве аргумента и надевает на него конструктор S. Другими словами функцию add1, надевающую S, можно определить двумя эквивалентными способами:

add1 x = S(x);

add1 = \x -> S(x);

Самое приятное свойство лямбда-выражений в том, что они, на самом деле, являются (в общем случае) не "функциональными константами", а "генераторами функций", поскольку при каждом исполнении лямбда-выражения может генерироваться новая функция! Например, если add - сложение чисел, то

addN n = \x -> add n x;

определяет такую функцию addN, что (addN n) вырабатывает функцию, прибавляющую n к аргументу. Например, addN (S(S(Z)) - это функция (\x -> add (S(S(Z))) x), прибавляющая 2 к аргументу. Весь фокус в том, что лямбда-выражение \x -> add n x содержит "свободную" переменную n, и для разных n лямбда-выражение генерирует разные функции.

Теперь у нас есть способ переделать функцию f вызывавшуюся как f(x, y, z), таким образом, чтобы её вызов выглядел как f x y z. А именно, если исходное определение функции f имело вид

f(x, y, z) = E;

его можно переделать так:

f = \x -> (\y -> (\ z -> E));

или даже как

f = \x y z -> E;

если воспользоваться тем, что в функциональных языках "с лямбдами" обычно считается, что "надевание лямбды" ассоциативно вправо. Т.е. \x -> \y -> E эквивалентно \x -> (\y -> E). Также, для краткости, разрешается записывать вложенные "лямбды" в сокращённом виде: \x y -> E эквивалентно \x -> \y -> E.

А ещё более кратко определение f можно записать в виде

f x y z = E;

что является сокращением для f = \x y z -> E;.

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

a1 Nil = Nil;
a1 (Cons x xs) = Cons (S x) (a1 xs);
a2 xs = a1(a1 xs);

Стала ли от этого программа "лучше"? Дело вкуса и привычки... Во всяком случае, скобочек и запятых в программе стало меньше. Тут, правда, есть одна тонкость: в левых частях определения функции a1 появились образцы, которые анализируют структуру аргумента. На самом-то деле, эта запись является сокращением для некоторой комбинации из лямбда-выражений и "case-выражений", но мы пока вникать в это не будем, считая, что смысл функции a1 вполне понятен на неформальном уровне.

Теперь попытаемся просуперкомпилировать выражение a1(a1 us) в духе того, как это делалось в послании Что такое суперкомпиляция? .

Получается такой граф конфигураций:

Если построить по этому графу остаточную программу, получится такое определение функции:

a2 Nil = Nil;
a2(Cons x xs) = Cons (S(S x)) (a2 xs);

Теперь становится видно "невооружённым глазом", что в результате вычисления выражения a1(a1 us)), к каждому элементу списка us прибавляется 2.

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

А теперь наступает самый интересный момент! Изобразительные средства "высшего порядка" дают нам новые возможности по структуризации программ: во многих случаях монолитную программу удаётся представить в виде "композиции" из нескольких независимых частей. Т.е., конечно, это можно делать и в случае языка "первого порядка", но в случае "высшего порядка" таких возможностей больше: практически любой кусок программы из любого определения некоторой функции f можно "вырезать", объявить отдельной функцией g, и "вытащить" g за пределы определения функции f.

Вот, например, посмотрим внимательно на определение функции a1:

a1 Nil = Nil;
a1 (Cons x xs) = Cons (S x) (a1 xs);

В этом определении свалены в одну кучу две совершенно разные вещи:

  1. Применение некоей операции к каждому элементу списка.

  2. Прибавление единицы к числу.

Понятно, что пункт 1 - это некоторая общая идея, которая не зависит от того, что именно совершается над каждым элементом списка. А пункт 2 - это другая идея, которая никак не связана со списками. Поэтому, определение функции a1 мы можем "обобщить", добавив второй параметр, обозначающий произвольную операцию над элементом списка. Получается "классическая" функция map, а программа принимает вид:

map f Nil = Nil;
map f (Cons x xs) = Cons (f x) (map f xs);
a1 xs = map (\x -> S x) xs;

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

map g (map f us)

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

Не возникают ли от этого какие-то ужасные новые трудности в процессе суперкомпиляции? Посмотрим! Попробуем просуперкомпилировать выражение map g (map f us). Получается такой граф конфигураций:

Видно, что граф получается конечным из-за того, что из конфигурации map g (map f us) в конце-концов получается конфигурация map g (map f u1), совпадающая с исходной с точностью до имён переменных. Картина - очень похожая на ту, что наблюдалась в случае суперкомпиляции "первого порядка"...

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

map2 g f Nil = Nil;
map2 g f (Cons x xs) = Cons (g(f x)) (map2 g f xs);

Приятно и поучительно: суперкомпилятор обнаружил такой "закон природы": если ко всем элементам списка применить операцию f, а потом - операцию g, то это - то же самое, что один раз применить ко всем элементам списка композицию операций f и g.

(А в случае "первого порядка" суперкомпилятор делал то же самое, но для частного случая, когда f и g были операцией "прибавления единицы".)

А теперь возникает следующий вопрос: на бумаге-то у нас всё хорошо получилось. Но, как гласит народная мудрость, "гладко было на бумаге, да забыли про овраги"... В качестве ответа, до некоторой степени, может служить суперкомпилятор HOSC. Можно посмотреть на него и убедиться, что с кое-какими заданиями этот суперкомпилятор справляется. В том смысле, что структура остаточной программы не совпадает со структурой исходной программы. :-)

Представляет ли HOSC "практический интерес" (или, другими словами, можно ли его применить для "решения важной народнохозяйственной задачи"), пока сказать трудно. Но штука - забавная.

Осталось сделать несколько замечаний по поводу языка, программы на котором обрабатывает HOSC. Поскольку HOSC - это изделие экспериментальное, его входной язык - "минималистский". По сути он представляет собой некоторое подмножество Хаскеля (Haskell). Этот язык (в его состоянии на данный момент) описан на странице Higher Order Lazy Language (HLL).

HLL - язык со статической типизацией (в смысли Хиндли-Милнера). Писать определения функций в виде

f x y z = E;

пока не разрешается. Нужно писать с "лямбдами" в правой части:

f = \x y z -> E;

Сопоставление с образцом можно делать с помощью case-выражений, в которых каждый образец имеет простейший вид: c x1 x2 ... xN. Поэтому, определение функции map

map f Nil = Nil;
map f (Cons x xs) = Cons (f x) (map f xs);

на самом деле, должно быть записано так:

map = \f us -> case us of {
  Nil -> Nil;
  Cons x xs -> Cons (f x) (map f xs);
};

С другой стороны, в HLL есть конструкция letrec, с помощью которой можно записывать "локальные определения функций". Это позволяет уменьшить количество параметров у функций, когда эти параметры "просто так" перетаскиваются от одного вызова функции к другому. Например, определение

map2 g f Nil = Nil;
map2 g f (Cons x xs) = Cons (g(f x)) (map2 g f xs);

можно переписать так:

map2 = \g f us ->
  letrec loop = \us -> case us of {
    Nil -> Nil;
    Cons x xs -> Cons (g (f x)) (loop xs);
  } in loop us;

HOSC активно использует letrec-и при генерации остаточной программы.

Вот пример полного задания на суперкомпиляцию:

data List a = Nil | Cons a (List a);
data Nat = Z | S Nat;

mapN (S(S(S Z))) f xs

where

map = \f us -> case us of {
  Nil -> Nil;
  Cons x xs -> Cons (f x) (map f xs);
};

mapN = \n f us -> case n of {
  Z -> us;
  S n1 -> map f (mapN n1 f us);
};

Здесь сначала идут объявления типов данных, используемых в программе. Потом - выражение, которое вычисляет программа (и которое становится начальной конфигурацией при суперкомпиляции). Через свободные переменные этого выражения в программу передаются начальные данные при запуске. Затем идёт ключевое слово where, за которым следуют объявления функций. Засовываем эту программу в HOSC (задание mapN n f xs), и получаем такой результат:

data List a = Nil | Cons a (List a);
data Nat = Z | S Nat;
(letrec g=(\x4-> case x4 of {
    Nil -> Nil;
    Cons s2 z1 -> (Cons (f (f (f s2))) (g z1)); })
  in (g xs))

Результат неплохой. Функция mapN применяет функцию f ко всем элементам списка xs, повторяя эту процедуру n раз. В данном случае в начальном выражении задаётся, что n=3. И в остаточной программе получается однопроходный алгоритм, который применяет f к каждому элементу списка xs три раза.

суббота, 6 июня 2009 г.

Что лучше: частичные вычисления или суперкомпиляция?

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

А ближе всего к суперкомпиляции находятся "частичные вычисления" (partial evaluation).

Но, поскольку хочется быть хоть и суровым, но справедливым, я, для начала, частичные вычисления поругаю, и только после этого их похвалю!

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

Пусть целые числа представлены в виде Z, S(Z), S(S(Z)), ... Рассмотрим программу

f(u) = g(u, Z);
g(Z, y) = y;
g(S(x), y) = g(x, S(y));

Функция f является "тождественной" в том смысле, что если на вход подать число u, то f (u) выдаст u.

Если подвергнуть g(u, Z) прогонке, то (на одной из ветвей дерева) получается бесконечная последовательность термов:

g(u, Z) --> g(u1, S(Z)) --> g(u2, S(S(Z))) -->

Если в суперкомпилятор вделан "свисток", основанный на гомеоморфном вложении, то суперкомпилятор замечает, что g(u, Z) гомеоморфно вложено в g(u1, S(Z)). Или, говоря по-простому, если в g(u1, S(Z)) подтереть конструктор S, то получится g(u1, Z), что (с точностью до имён переменных) совпадает с g(u, Z).

Поэтому суперкомпилятор делает обобщение и зацикливание. Можно убедиться в этом на примере суперкомпилятора SPSC: addAcc(a, Z).

А в случае частичного вычисления, получается другая картина. В частичных вычислителях основная идея - вычислять все константные выражения, какие можно. Т.е., "распространять константы", но не локально, а глобально, ради этого раскрывая in-line вызовы функций или генерируя специализированные версии функций для разных значений аргументов. Но, в отличие от суперкомпиляции, конфигурации из вложенных вызовов функций при этом не рассматриваются.

Если частичный вычислитель - типа "offline", то он сначала размечает программу, чтобы узнать, какие подвыражения и параметры функций будут заведомо известны. Для этого символически выполняются операции над данными, а данные делятся на две категории S и D. S - известные данные, а D - неизвестные.

Основная идея "проста как лапоть":

S+S = S
S+D = D
D+S = D
D+D = D

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

В случае нашего примера есть две функции f и g. Для f возможны 2 разметки: f(S) и f(D). А для g - 4 разметки: g(S, S), g(S, D), g(D, S), g(D,D).

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

Когда процесс стабилизируется (достигается "неподвижная точка"), получается корректная разметка. D "испортили" уже всё, что смогли.

Применяем этот принцип к нашему примеру.

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

f(u) = g(u, z);

g(x, y) = if x == 0 then y else g(x-1, y+1);

Для примера будем считать, что нам неизвестно, что будет на входе программы. и задаём начальную разметку: f(D), g(S,S).

  D      D  S
f(u) = g(u, z);
  S  S       S           S        S    S
g(x, y) = if x == 0 then y else g(x-1, y+1);

Видно, что в одном месте g вызывается с первым параметром, имеющим пометку D. Меняем разметку параметров g с g(S,S) на g(D,S). Получается

  D      D  S
f(u) = g(u, z);
  D  S       D           S        D    S
g(x, y) = if x == 0 then y else g(x-1, y+1);


И на этом разметка стабилизируется! Везде S получается только из S. Поэтому, разметка "корректна".

Теперь надо принять решение, раскрывать ли вызовы функции g или генерировать её специализированные версии? Не раскрывать - это более осторожная тактика, применим её. Тогда частичный вычислитель действует так. У f разметка не содержит S: f(D). Поэтому, в остаточной программе генерируется только одна версия функции f. А разметка функции g содержит S: g(D,S). Это означает, что в процессе метавычислений второй аргумент g будет известен, и что для разных констант k будут сгенерированы специализированные версии g, такие, что g_k(x) = g(x, k). Принцип простой: если где-то получился вызов вида g(x,k), заменяем его на g_k(x) и генерируем определение функции g_k. При этом, с технической точки зрения, можно откладывать переименование вызовов g(x, k) в g_k(x) можно делать не сразу, а посредством отдельного прохода по программе. Т.е., просто считается, что значения S-параметров - это "часть имени функции".

А начинается процесс с генерации определения для входной функции f.

Получается так (после вычисления всех подвыражений, содержащих только S-переменные, значение которых известно):

g(u) = g(u, 0);
g(x, 0) = if x == 0 then 0 else g(x-1, 1);
g(x, 1) = if x == 0 then 1 else g(x-1, 2);
g(x, 2) = if x == 0 then 2 else g(x-1, 3);
g(x, 3) = if x == 0 then 3 else g(x-1, 4);
...

Или, после переименования функций,

g(u) = g_0(u, 0);
g_0(x) = if x == 0 then 0 else g_1(x-1);
g_1(x) = if x == 0 then 1 else g_2(x-1);
g_2(x) = if x == 0 then 2 else g_3(x-1);
g_3(x) = if x == 0 then 3 else g_4(x-1);
...

Генерируется бесконечная программа, которая для каждого k содержит определение функции вида

g_k(x) = if x == 0 then k else g_k+1(x-1);

Эта проблема характерна практически для всех частичных вычислителей (особенно - для самоприменимых). Но стоит не так остро для run-time specialization, поскольку можно не генерировать специализированные версии функций "про запас", а по мере надобности. А понадобиться могут не все варианты.

Из сказанного может сложиться ложное впечатление, что частичные вычислители, по сравнению с суперкомпиляторами, - это что-то ущербное. Зачем вообще заниматься частичными вычислениями, если суперкомпиляция "круче"? Но это - не совсем так.

Класс программ, с которыми успешно "справляются" частичные вычислители - некоторое подмножество, по сравнению с классом программ, с которыми можно делать что-то интересное с помощью суперкомпиляции.

Однако, если частичный вычислитель с какими-то программами всё же справляется, он делает это гораздо лучше, чем суперкомпилятор!

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

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

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

  • Выполняется генерация остаточной программы в соответствии с разметкой. При этом всё, что помечено как "статическое", быстро и "бездумно" вычисляется.

Первое преимущество такого подхода очевидно: генерация остаточной программы идёт быстрее.

Второе преимущество является, может быть, ещё более важным. Это - предсказуемость и стабильность результатов. Ибо уже после стадии разметки становится понятно, какие именно части исходной программы исчезнут, а какие - "выпадут" в остаточную программу, и какую именно структуру будет иметь остаточная программа.

А слабости суперкомпиляции являются "оборотной стороной" её силы. Суперкомпилятор "слишком умён", а значит - менее предсказуем! Результаты его применения в конкретной ситуации могут быть весьма неожиданными... Кстати, одно из определений "искусственного интеллекта" так и звучит: если результаты работы программы предсказуемы, значит, "интеллекта" в ней нет (она просто что-то "вычисляет" - и всё), а если результат предсказать невозможно - значит "интеллекта" в ней навалом. :-)

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

Есть и ещё одна интересная ситуация, когда проявляется преимущество (двухэтапных) частичных вычислений перед суперкомпиляцией: когда мы хотим применить специализатор программ к самому себе! Например, если у нас есть специализатор spec и интерпретатор int, то можно преобразовать интерпретатор в компилятор вычислив spec(spec,int). Это - "вторая проекция Футамуры" (которая была независимо открыта и Турчиным, хотя и немного позже).

Чем интересно выражение spec(spec,int)? Да тем, что специализатору предлагается "заглянуть в свою собственную душу" и разобраться в своём собственном поведении по отношению к самому себе. Здесь возникает некоторое противоречие: умному-то легко разобраться в душе дурака, но для дурака душа умного - потёмки. Вот и получается, что если специализатор - дурак, то самоприменять его бесполезно, поскольку сам в себе он разобраться не в состоянии. А если он слишком умён - то он всё равно не способен разобраться в себе, именно в силу своей сложности.

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

Подробнее об одном из таких частичных вычислителей можно почитать здесь:

  • С.А.Романенко. Генератор компиляторов, порожденный самоприменением специализатора, может иметь ясную и естественную структуру. - М.:ИПМ им.М.В.Келдыша АН СССР, 1987, препринт N 26. - 35 с. PDF, DJVU

  • S.A.Romanenko. A Compiler Generator Produced by a Self-Applicable Specializer Can Have a Surprisingly Natural and Understandable Structure. In D.Bjorner, A.P.Ershov and N.D.Jones, editors, Partial Evaluation and Mixed Computation, pages 445-463, North-Holland, 1988. PDF, DJVU

  • S. A. Romanenko. Arity Raiser and its Use in Program Specialization. In Proceedings of the Third European Symposium on Programming on ESOP '90 (Copenhagen, Denmark). N. Jones, Ed. Springer-Verlag New York, New York, NY, 341-360. PDF, DJVU

среда, 3 июня 2009 г.

Отнесёмся к "ленивости" со всей "строгостью"! (Или что лучше, блондинки или брюнетки?)

Похоже, что в заметке

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

Верно ли, что я - "враг Рефала"? Неверно! Особенно, если вспомнить, что я являюсь соавтором Рефала Плюс и книги по Рефалу Плюс:

Р.Гурин, С.Романенко. Язык программирования Рефал Плюс. Курс лекций. Учебное пособие для студентов университета города Переславля. - Переславль-Залесский: "Университет города Переславля" им.А.К.Айламазяна, 2006. - 222 с. PDF

А также и соавтором нескольких реализаций Рефала, например

Поэтому, для меня воевать с Рефалом - всё равно что рубить сук, на котором я сам же и сижу.

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

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

Говоря по-простому, язык является "строгим", если вычисление функции начинается только после того, как полностью вычислены ей аргументы. И, соответственно, "ленивым", если вычисление функции может начинаться ещё до того, как её аргументы полностью вычислены.

Естественно, что разных разновидностей "ленивости" существует много, ибо конкретизировать это понятие можно только конкретизировав понятие "частично вычисленный аргумент". Для языков вроде Хаскеля (Haskell) понятие "частичной вычисленности" определяется через "приведение к слабой головной нормальной форме", но возможны и другие варианты (например, "fuller laziness").

То, что различие между "строгой" и "ленивой" семантикой реально существует показывает хотя бы такая программка:

omega(x) = omega(x);
erase(x) = Stop;
f(u) = erase(omega(Nil));

В случае "строгого" исполнения вычисление f(Nil) никогда не завершается, а в случае "ленивого" - завершается всегда. Надеюсь, все согласны с тем, что между "никогда" и "всегда" всё-таки есть маленькое различие? :-)

Следующий вопрос такой: является ли Рефал "строгим" или "ленивым" языком? В абстрактной постановке ответить на него нельзя, поскольку никто никогда не запрещал всем желающим придумывать и реализовывать разные разновидности Рефала и вариации на тему Рефала. И семантика у этих вариаций может быть тоже разная.

Например, входным языком суперкомпилятора SCP4 является Рефал-5:

Является ли этот язык "строгим" или "ленивым" можно "методом научного тыка": переписав вышеприведённую программу на Рефале-5:

Omega { e.X = <Omega e.X>; }
Erase { e.X = Stop; }
F { e.U = <Erase <Omega Nil>>; }

Запускаем вычисление <F Nil> и смотрим: зациклится программа или нет? Судя по описанию Рефала-5 - зациклится (а я описанию верю :-) ). А то, что эта программа зациклится в случае Рефала Плюс - я не только верю, но и знаю...

Следующий вопрос: верно ли, что я считаю "ленивые" языки "хорошими", а "строгие" языки - "плохими". И что, на этом основании, я считаю Рефал-5 и Рефал Плюс "плохими" языками?

Это - неверно! Суперкомпиляторы HOSC и SPSC

хотя и обрабатывают программы на ленивых языках, но сами-то написаны на языке Скала (Scala). А язык Скала (если рассматривать его "функциональную" часть) - это типичный "строгий" язык. Если бы мы (я и Илья Ключников) свято верили в абсолютное превосходство "ленивых" языков над "строгими", то HOSC и SPSC были бы написаны на "ленивом" языке (например, на Хаселе).

И вообще, абстрактные рассуждения по поводу того, какие языки лучше, "ленивые" или "строгие", имеют не больше смысла, чем дискуссии на тему "Кто лучше: брюнетки или блондинки?" Зависит от того, какая именно блондинка/брюнетка, и в каких обстоятельствах...

В своей заметке я обсуждал достоинства "ленивости" для случая, когда суперкомпиляция используется как средство анализа программ, а не оптимизации программ. В этом случае удобнее использовать суперкомпилятор, который сохраняет семантику программ.

Например, нам хочется исследовать свойства завершаемости программы. Суперкомпилируем исходную программу и получаем остаточную программу, для которой можем легко показать, что она всегда завершается. Какой вывод мы можем на основании этого сделать по поводу исходной программы? Если суперкомпилятор сохраняет семантику программы, сразу же делаем заключение, что это верно и в отношении исходной программы. А если суперкомпилятор на обладает этим свойствам? Тогда мы о завершаемости исходной программы не узнаём НИЧЕГО.

Последний вопрос такой: если мы хотим, чтобы суперкомпилятор строго сохранял семантику программ, должен ли его входной язык быть обязательно "ленивым"? Ответ отрицательный: входной язык не обязательно должен быть "ленивым"! Если постараться, то можно обойтись и без этого. Вот статья на эту тему:

Jonsson, P. A. and Nordlander, J. 2009. Positive supercompilation for a higher order call-by-value language. In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Savannah, GA, USA, January 21 - 23, 2009). POPL '09. ACM, New York, NY, 277-288. DOI=http://doi.acm.org/10.1145/1480881.1480916 PDF

Но, если мы хотим использовать суперкомпилятор для анализа формальных систем, кодируя их в виде программ, написанных на входном языка суперкомпилятора, то зачем в качестве входного языка выбирать "строгий" язык?

Для того, чтобы обеспечить сохранение семантики в случае "строгого" языка, суперкомпилятор должен предпринимать какие-то дополнительные усилия: нужны дополнительные анализы, дополнительные проверки, рассмотрение разных особых случаев. От этого суперкомпилятор усложняется. А если суперкомпилятор используется как средство анализа или верификации, то "встаёт ребром" вопрос о корректности самого суперкомпилятора. Нужно доказывать теорему, что "всё чисто", что метавычисления правильно имитируют обычные вычисления. Чем "толще" и запутаннее сам суперкомпилятор, тем "толще" и запутаннее будет доказательство его корректности. И тем выше вероятность, что само доказательство корректности будет содержать ошибки. :-)

Постоянные читатели