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

Показаны сообщения с ярлыком проблемно-ориентированный язык. Показать все сообщения
Показаны сообщения с ярлыком проблемно-ориентированный язык. Показать все сообщения

пятница, 30 апреля 2010 г.

Комбинаторные парсеры. Часть 1

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






Возьмем простой язык L, алфавит которого состоит всего из двух символов - A и B. Рассмотрим следующее подмножество регулярных выражений для этого языка L:

re = a | b | concat re1 re2 | or re1 re2;


  • Слово w соответствует регулярному выражению a, если слово начинает с A, то есть w = A w1.
  • Слово w соответствует регулярному выражению b, если слово начинает с B, то есть w = B w1.
  • Слово w соответствует регулярному выражению (concat re1 re2), если слово w превставимо в виде w = w1 w2 w3, где w1 - соответсвует re1, а w2 - соответсвует re2.
  • Слово w соответствует регулярному выражению (or re1 re2), если оно соответствует либо выражению re1 либо выражению re2.

Для удобства чтения (or re1 re2) можно записывать как (re1|re2), а конкатенацию (concat re1 re2) - как (re1)(re2).

Результат сопоставление слова языка L с регулярным выражение re определяется так: если существует начальная часть слова, удовлетворяющая выражению, то от слова откусывается такая часть и возвращается оставшаяся часть слова; если же никакая начальная не соответствует выражению, то возвращается неудача.


Напишем парсеры и соответствующие комбинаторы для языка L в духе примера из упомянутого послания, но с одним отличием - в том примере алфавит языка и представление слов были жестко связаны вместе:


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

Мы же разделим понятие алфавит и слова. Конкретный алфавит языка будет представляться конкретным перечислением букв, а слово языка - это список букв.

Получаем что-то в таком духе:


data Symbol = A | B;
data List a = Nil | Cons a (List a);
data Option a = Some a | None;
par1 = concat (or a (concat a b)) (or (concat b b) a);
or = \p1 p2 word -> case p1 word of {
 Some word1 -> Some word1;
 None -> p2 word;
};
concat = \p1 p2 word -> case p1 word of {
 Some word1 -> p2 word1;
 None -> None;
};
a = \word -> case word of {
 Nil -> None;
 Cons sym word1 -> case sym of {
  A -> Some word1;
  B -> None;
 }; 
};
b = \word -> case word of {
 Nil -> None;
 Cons sym word1 -> case sym of {
  A -> None;
  B -> Some word1;
 }; 
};

Что делают функции - понятно:


  • a (парсер) - соответствует регулярному выражению a - откусывает (если можно) от слова символ A и возвращает оставшуюся часть. Если слово пустое или не начинается с A, возвращает неуспех.
  • b (парсер) - аналогично a
  • or (комбинатор парсеров) - берет два парсера p1 и p2 и делает новый парсер, который возвращает результат работы первого парсера, если это успех, а в противном случае возвращает результат второго парсера
  • concat (комбинатор парсеров) - конкатенирует (соединяет) два парсера, - делает новый парсер, который возвращает успех, тогда и только тогда, когда первый парсер завершается успешно и второй парсер, примененный к остатку слова, выплюнутому первым парсером, также завершатся успехом.
  • par1 - парсер, соответствующий регулярному выражению (a|ab)(bb|a)

Попробуем применить парсер par1 к слову ABB. A - соответсвует выражению a, BB - выражению bb. Ожидается, что результатом работы будет Some w1, где w1 - пустое слово.

Поскольку суперкомпилятор можно применять и в качестве интерпретатора, попросим HOSC вычислить выражение par1 (Cons A (Cons B (Cons B Nil))), - как и ожидалось в результате получается (Some Nil).

Пойдем дальше - применим парсер par1 к слову ABA. AB - соответсвует выражению ab, A - выражению a. Опять ожидаем, что результатом работы будет Some w1, где w1 - пустое слово.

Вычисляем выражение par1 (Cons A (Cons B (Cons A Nil))). Получаем ... None!

Как же так? Дерево вычислений, показанное HOSC'ом помогает найти ответ на вопрос - после некоторого числа шагов вычисление исходного выражения сводится (редуцируется) к вычислению выражения (or (concat b b) a) (Cons B (Cons A Nil)), которое завершается неудачей.


Можно еще отсукомпилировать выражение par1 w для неизвестного слова w. Получается следующий результат:


case  w  of {
  Nil  -> None;
  Cons u10 x11 ->
    case  u10  of {
      A  ->
        case  x11  of {
          Nil  -> None;
          Cons p3 u13 ->
            case  p3  of {
              A  -> (Some u13);
              B  -> case  u13  of { 
                 Nil  -> None; 
                 Cons z10 u8 -> case  z10  of { 
                    A  -> None; 
                    B  -> (Some u8); 
                 }; 
              };
            };
        };
      B  -> None;
    };
}


Видно, что на самом деле мы закодировали регулярное выражение a(a|bb), или (что то же самое) (aa|abb). Как же так получилось?


Дело в том, что парсер (or (a) (concat a b)) никогда не будет откусывать от слова AB - из-за того, что если парсер (concat a b) способен для данного слова выдать что-то наружу, то на это способен и парсер a, а он вызывается в нашей реализации первым - и получается, что наш комбинатор or работает для парсера (or p1 p2) правильно только в случае, если p1 и p2 не могут выдавать успех на одном и том же слове. Или (говоря более научно), когда языки, определяемые парсерами p1 и p2 не пересекаются.

Как же решить возникшую проблему? Как сделать, чтобы результирующий парсер (сконструированный из комбинаторов) пробовал все варианты? В нашем случае мы сделали так, что парсер возвращает ровно одно успешное сопоставление. Одно из решений проблемы -- заставить парсер возвращает не одно единственное сопоставление в случае успеха, а все возможные. Ясно, что тогда усложняется логика работы комбинаторов парсеров -- они должны анализировать все сопоставления парсеров, переданных как аргументы. Таким образом парсер or p1 p2 должен возращать объединение результатов парсеров p1 и p2. А парсер (concat p1 p2) должен к каждому из вариантов сопоставления p1 попробовать применить p2 и тоже объединить результаты. Этот подход изложен в классической статье Филиппа Уодлера "How to Replace Failure by a List of Successes (A method for exception handling, backtracking, and pattern matching in lazy functional languages)".

Но можно пойти и другим путем - можно каждому парсеру в качестве дополнительного аргумента передавать парсер, который будет вызван на следующем шаге сопоставления. Такой подход по духу очень близок стилю программированию в продолжениях (Continuation passing style). Действительно, в нашей первой наивной реализации парсер (or (a) (concat a b)) действовал по принципу "После нас хоть потоп" - возвращал всегда первое сопоставление - его не интересовало, пригоден ли его ответ для обработки следующим парсером в цепочке.

Легко кодируются в таком стиле парсеры для выражений a и b.


a = \next word -> case word of {
  Nil -> None;
  Cons sym word1 -> case sym of {
    A -> next word1;
    B -> None;
  }; 
};


b = \next word -> case word of {
  Nil -> None;
  Cons sym word1 -> case sym of {
    A -> None;
    B -> next word1;
  }; 
};


Дополнительный аргумент next - это следующий парсер. Логика парсера a проста - если слово начинается с A, то на остаток слова натравливается парсер next, в противном случае -- неудача.

Комбинатор or записывается так:


or = \p1 p2 next word -> case p1 next word of {
  Some word1 -> Some word1;
  None -> p2 next word;
};


А комбинатор concat записывается очень изящно:

concat = \p1 p2 next word -> p1 (p2 next) word;


Композиция парсеров представляется в виде композиции функций!


Неожиданно возникает вопрос а как применить парсер к слову? Ведь теперь любой парсер требует своего продолжения! Для этого потребуется специальный парсер return, который разрывает порочный круг из бесконечных продолжений:


return = \w -> Some w;

В итоге для сопоставления выражения (a|ab)(bb|a) со словом ABA получается следующая программа:


data Symbol = A | B;
data List a = Nil | Cons a (List a);
data Option a = Some a | None;
par1 (Cons A (Cons B (Cons A Nil)))
where
par1 = concat (or a (concat a b)) (or (concat b b) a) return;
return = \w -> Some w;
or = \p1 p2 next word -> case p1 next word of {
  Some word1 -> Some word1;
  None -> p2 next word;
};
concat = \p1 p2 next word -> p1 (p2 next) word;
a = \next word -> case word of {
  Nil -> None;
  Cons sym word1 -> case sym of {
    A -> next word1;
    B -> None;
  }; 
};
b = \next word -> case word of {
  Nil -> None;
  Cons sym word1 -> case sym of {
    A -> None;
    B -> next word1;
  }; 
};


Вычисляем это выражение с помощью суперкомпилятора и получаем (Some Nil)! Если посмотреть на трассировку вычислений, то видно, что новый парсер по очереди перебирает все варианты, пока не найдет успешный, - грубо говоря, неявным образом составляются все возможные комбинации парсеров и по очереди применяются ко входному слову. Первая комбинация завершиласть неудачно - пробуется вторая и т.д. Можно еще сказать, что новый комбинатор or как бы выносит разбор вариантов из глубины регулярного выражения наружу. То есть в каком то смысле переписывает регулярное выражение (re1|re2)re3 -> ((re1 re2) | (re1 re3)).

Вычисление par1 (Cons A (Cons B (Cons B Nil))) тоже выдает (Some Nil).


Платой за красоту такой записи регулярных выражений с помощью комбинаторов являются накладные расходы интерпретатора во время вычислений. Ведь выражение (a|ab)(bb|a) неявно трансформируется так:


(a|ab)(bb|a) -> (a(bb|a))| (ab(bb|a)) -> abb|aa|abbb|aba


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


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

А попробуем сопоставить наше игрушечное регулярное выражение с произвольным словом w, то есть вычислить concat (or a (concat a b)) (or (concat b b) a) return w с помощью суперкомпилятора HOSC. Результат такой:

case  w  of {
  Nil  -> None;
  Cons p40 v20 ->
    case  p40  of {
      A  ->
        case  v20  of {
          Nil  -> None;
          Cons v1 u30 ->
            case  v1  of {
              A  -> (Some u30);
              B  ->
                case  u30  of { 
                  Nil  -> None; 
                  Cons y18 p22 -> case  y18  of { 
                    A  -> (Some p22); 
                    B  -> (Some p22); 
                  }; 
                };
            };
        };
      B  -> None;
    };
}

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

Заключение

Было показано, как с использованием комбинаторного подхода реализуется проблемно-ориентированный язык для работы с подмножеством регулярных выражений. Реализовать этот язык у нас получилось только со второго раза, что является подтверждением того, что хотя работать с комбинаторным DSL легко и приятно, реализовать даже простой DSL не так то уж и тривиально. Оказалось, что суперкомпилятор HOSC способен устранять накладные расходы, вызванные использованием изящного, но требовательного к ресурсам DSL, реализованный через комбинаторы.

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

воскресенье, 14 февраля 2010 г.

Недетерминизм: выбор по надобности или выбор при вызове?

В послании

было показано, что недетерминированные программы можно писать в рамках детерминированного ленивого функционального языка, реализовав с помощью комбинаторов проблемно-ориентированный язык, содержащий конструкцию "произвольного выбора". Идея-то с виду простая: реализуем конструкцию choice2 e1 e2. И пусть вычисление этой конструкции сводиться к вычислению e1 или e2, а выбор между e1 и e2 делается произвольно.

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

choice2 e1 e2 --> e1

choide2 e1 e2 --> e2

Вроде бы, всё ясно и понятно... Однако, есть тут один "подводный камень". Рассмотрим такое недетерминированное выражение:

(\x -> P x x) (choice2 True False)

где P - конструктор, формирующий пару. Каковы возможные результаты вычисления этого выражения? Это зависит от того, в каком порядке выполнять редукцию. Если первый шаг редукции - применение функции (\x -> P x x) к аргументу (choice2 True False), то на первом шаге получается выражение

P (choice2 True False) (choice2 True False)

в результате дальнейшей редукции которого могут получиться 4 разных выражения: P True True, P True False, P False True, P False False.

А если первый шаге редукции - упрощение (choice2 True False), то получается одно из двух выражений

(\x -> P x x) True

(\x -> P x x) False

и дальнейшие вычисления дают только два возможных результата: P True True, P False False.

Когда выбирать: когда нужен результат или при передаче параметра?

Из рассмотренного примера видно, что результат вычисления недетерминированных конструкций может зависеть от порядка вычислений и от моментов, в которые производится выбор между возможностями. Можно затягивать выбор до последней возможности: выбирать только тогда, когда результат, возвращаемый конструкцией выбора реально понадобился. В литературе этот вариант называется "выбором по надобности" (need-time choice). А можно выбирать в тот момент, когда конструкция выбора оказывается аргументом функции. В литературе этот вариант называется "выбором при вызове" (call-time choice).

В послании

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

Это наглядно можно увидеть просуперкомпилировав выражение

(app (lam (\x -> pairP (var x) (var x))) (choice2 (cst True) (cst False))) c

Получается остаточная программа

case c of {

  D u z3 ->

    case z3 of {

      D u5 y5 -> (P case u5 of { L t4 -> True; R p4 -> False; }

                    case y5 of { L y8 -> True; R p2 -> False; });

  };}

из которой видно, что каждый из компонентов пары может принимать значение независимо от другого.

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

Если уж "выбор при вызове", то тогда уж и "вызов по значению"

Но тут сразу же выясняется, что если мы хотим, чтобы выбор происходил до передачи аргумента в тело функции, то это означает, что аргумент функции должен вычисляться до передачи аргумента в тело функции. Другими словами, параметры должны передаваться в тело функции не "по имени" (call by name), а "по значению" (call by value).

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

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

Реализация вызова по значению в ленивом языке через "продолжения"

Вызов параметров по значению можно реализовать в рамках "ленивого" язык, если использовать писать программу "в стиле передачи продолжений" (continuation passing style). А именно, к параметрам каждой функции f нужно добавить дополнительный параметр k (который называется "продолжением"). Если вызов функции f выглядел как f x1 x2 ... xN, то теперь он принимает вид f x1 x2 ... xN k. При этом, в тех местах, где функция возвращала результат a, нужно выдачу результата делать не напрямую, а вызывать k, передав ему результат в качестве аргумента: k a.

В послании

рассматривалась реализация "ленивого" лямбда-исчисления через набор комбинаторов (см. задание на суперкомпиляцию Lambda: higher-order syntax (transparent)):

var = \x -> x;

lam = \f -> f;

app = \e1 e2 -> e1 e2;

cst = \a -> a;

fix = \f -> f (fix f);

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

А теперь попробуем сделать так, чтобы аргумент функции сначала вычислялся и только после этого связывался с параметром функции, переписав комбинаторы в стиле с продолжениями (см. задание на суперкомпиляцию Lambda: HOAS, CPS, CBV)!

var = \x k -> k x;

lam = \f k -> k f;

app = \e1 e2 k -> e1 (\f -> e2 (\v -> f v k));

cst = \a k -> k a;

var, lam и cst устроены неинтересно: переменная подсовывает продолжению k своё значение, lam - функцию, а cst - свой аргумент. Весь интерес - в комбинаторе app! Он работает так. Сначала вычисляется e1, и результат этого вычисления подсовывается продолжению (и связывается с переменной f). Затем вычисляется e2, и результат этого вычисления подсовывается продолжению (и связывается с переменной v). После этого вычисляется результат применения f к v и подсовывается продолжению k. Вот и получается, что при вызове функции предварительно вычисляется ей аргумент. В рамках "ленивого" языка реализован вызов параметра по значению.

Самый тонкий вопрос - как определить fix! Определение fix - это некая смесь из определений app и lam:

fix = \e k -> k (fixLoop e);

fixLoop = \e x k -> e(fixLoop e)(\f -> f x k);

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

run = \e -> e (\x -> x);

Для того, чтобы можно было определять функции, что-то делающие с натуральными числами, определим ещё три комбинатора. natZ - вырабатывает ноль, natS сначала вычисляет свой аргумент, а потом прибавляет к тому, что получилось, единицу. natCase реализует разбор случаев: проверяет, является ли нулём её первый аргумент, а затем вызывает второй или третий аргумент.

data Nat = Z | S Nat;

natZ = \k -> k Z;

natS = \e k -> e (\v -> k(S v));

natCase = \e eZ eS k -> e (\v -> case v of {

  Z -> eZ k;

  S n -> eS n k;

  });

Теперь можно определять функции над натуральными числами

data Bool = True | False;

natIsZ = \e -> natCase e (cst True) (\n -> (cst False));
natPred = \e k -> e (\v -> case v of { S v1 -> k v1;});

А с помощью fix - и рекурсивные функции. Например, "тождественную" функцию, разбирающую на части натуральное число и собирающую его обратно, можно определить так:

run (fix(\natId -> lam(\x ->

  natCase (var x)

    natZ

    (\x1 -> (natS (app (var natId) (var x1)))))))

Просуперкомпилировав это выражение, получаем остаточную программу

\x k->

   letrec f = \x0 k0 -> case x0 of {

     Z -> k0 Z;

     S x1 -> f x1 (\x2 -> k0 (S x2)); }

   in f x k

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

Реализация "выбора при вызове" через комбинаторы

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

но используем в комбинаторах, реализующих недетерминированный язык стиль с продолжениями. Результат можно увидеть заглянув в задание на суперкомпиляцию Lambda: non-determinism (HOAS, CPS k c, CBV).

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

data Bool = True | False;

data Choice = L Choice | R Choice;

data Nat = Z | S Nat;

data Pair a b = P a b;

Здесь интересно то, что при реализации выбора по надобности в определении Choice нам понадобились три конструтора: L (левый выбор), R (правый выбор) и D (разделение последовательности выборов на две подпоследовательности). А теперь в определении Choice - только два конструктора: L и R. Это связано с тем, что при реализации языка с передачей параметров по значению и выбором при вызове получается, что последовательность, в которой выполняются вычисления, проста и заранее предсказуема. Поэтому нет и надобности "разветвлять" последовательность выборов: можно аккуратно "протаскивать" одну последовательность через весь процесс вычислений.

Основная идея проста. Пусть у нас есть выражение e. При вычислении этого выражения ему должно подсовываться два дополнительных аргумента: продолжение k и последовательность выборов c. Другими словами, хотим получить значение e - вычисляем e k c. При этом, в отличие от случая детерминированных программ, продолжение k должно принимать не только результат, вырабатываемый выражением e, но ещё и некоторую последовательность выборов c1. Т.е., k должно иметь вид (\v1 c1 -> e1). Откуда же берётся c1? Дело в том, что если выражение e содержит конструкции choice2, то эти конструкции могут потреблять выборы из входной последовательности выборов c. И продолжение должно получить оставшуюся "неизрасходованную" часть последовательности выборов через параметр c1.

Для исполнения недетерминированных программ, определим функцию run, возвращающую результат вычисления выражения e для заданной последовательности выборов c:

run = \e с -> e (\v c1 -> v) с;

Эта функция подсовывает выражению e продолжение \v c1 -> v и последовательность выборов c. Продолжение принимает результат, возвращаемый выражением e и выдаёт этот результат. А остаток последовательности выборов просто игнорирует. Ведь исполнение программы завершено, и этот остаток больше ни для чего не нужен.

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

cst = \a k с -> k a с;

cst просто передаёт продолжению k константу a и неизменённую последовательность выборов (при вычислении константы выбирать ничего не приходится). Определение cst можно немного упростить используя "eta-редукцию". Зачем принимать и передавать c продолжению k в явном виде? Просто выдаём k a, т.е. функцию. И пусть уж она сама и забирает c! Те же соображения применимы и к функции run. Упростив run и cst получаем:

run = \e -> e (\v c -> v);

cst = \a k -> k a;

Теперь можно попробовать просуперкомпилировать первое выражение

run (cst True) --> (\c -> True)

Результат получается вполне разумный: для любой последовательности выборов всегда выдаётся True.

Теперь "возьмём быка за рога" и определим самую интересную конструкцию - choice2 (ради реализации которой всё и затевалось):

choice2 = \e1 e2 k c ->

   case c of {

     L c1 -> e1 k c1;

     R c2 -> e2 k c2;};

choice2 должен решить, какое выражение вычислять: e1 или e2? Для этого и используется c. Если c начинается с L, то выбираем e1, а если с R - то выбираем e2. После чего передаём остаток последовательности выборов либо в e1, либо в e2.

Теперь пробуем просуперкомпилировать некоторые выражения:

run (choice2 (cst True) (cst False)) -->

  \c -> case c of { L c1 -> True; R c2 -> False; }

run (choice2 (cst Z) (choice2 (cst (S Z)) (cst (S(S Z))))) -->

  \c -> case c of {

    L c1 -> Z;

    R c2 -> case c2 of { L c21 -> S Z; R c22 -> S (S Z); }; }

Теперь определим самые главные комбинаторы - var, lam и app:

var = \x k -> k x;
lam = \f k -> k f;
app = \e1 e2 k -> e1 (\f -> e2 (\v -> f v k));

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

var = \x k c -> k x c;
lam = \f k c -> k f c;
app = \e1 e2 k c -> e1 (\f c1 -> e2 (\v c2 -> f v k c2) c1) c;

Поскольку в реализуемом языке параметры передаются по значению, то с переменными связываются уже "полностью готовые" результаты, а не выражения, которые ещё нужно вычислять (как в случае передачи по имени). Т.е., в значениях переменных уже всё вычислено и никакого недетерминизма уже нет! Поэтому при вычислении var x k c значение переменной x в неизменном виде передаётся продолжению k. Последовательность выборов c тоже передаётся в k без изменения.  То же самое происходит и при вычислении lam f k c. f - это готовая функция, с которой ничего делать не надо.

А вот вычисление app e1 e2 k c - это уже более интересный случай. Сначала вычисляется e1. Ему подсовывается продолжение и последовательность выборов c. Продолжение получает результат f и остаток последовательности выборов c1. Затем c1 подсовывается под e2, и продолжение получает результат v и остаток последовательности выборов c2. После этого имеется известная функция f, известный аргумент v и остаток последовательности выборов c2. Вычисляем f v k c2.

Тонким местом является то, что f - это не просто функция от одного аргумента v, а функция, которая принимает ещё два дополнительных аргумента: продолжение k и последовательность выборов c2!

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

lam (\x -> var x) -->

  \k-> k (\x k1-> k1 x)

run (app (lam (\x -> (var x))) (cst True)) -->

  (\c -> True)

Теперь наступил момент, когда мы можем вернуться к вопросу о том, какой результат должен получаться в результате вычисления выражения (\x -> P x x) (choice2 True False). Для этого определим комбинатор pairP, формирующий пару из своих двух аргументов:

pairP = \e1 e2 k ->

  e1 (\v1 -> e2 (\v2 -> k (P v1 v2)));

Здесь просто выписано то, что при вычислении pairP e1 e2 нужно сначала вычислить e1, получив v1, затем - e2, получив v2, а затем - выдать P v1 v2. Ну, естественно, при этом должны надлежащим образом выполняться манипуляции с продолжениями и с последовательностью выборов.

Теперь суперкомпилируем

run (app (lam (\x -> pairP (var x) (var x)))

              (choice2 (cst True) (cst False))) -->

  \c -> case c of { L c1 -> P True True; R c2 -> P False False; }

и видим, что, как мы и хотели, возможными результатами вычисления этого выражения могут быть только P True True и P False False. За что боролись, то и получили.

Теперь, для интереса, напишем недетерминированную программу, генерирующую "произвольное натуральное число". Для этого определим комбинаторы, работающие с натуральными числами:

natZ = \k -> k Z;

natS = \e k -> e (\v -> k (S v));

natCase = \e eZ eS k -> e (\v -> case v of {

  Z -> eZ k;

  S n -> eS n k;

  });

natZ возвращает ноль Z, а natS e вычисляет e, получает значение v и выдаёт S v. Теперь мы умеем генерировать натуральные числа!

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

fix = \e k -> k (fixLoop e);
fixLoop = \e x k -> e(fixLoop e)(\f c1 -> f x k c1);

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

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

Заведём переменную и присвоим ей 0. А дальше будем крутить цикл и на каждом шаге решать: остановиться или продолжать. Если останавливаемся, то выдаём значение переменной в качестве результата. Если решаем не останавливаться, то прибавляем к переменной 1 и крутим цикл дальше.

В функциональных понятиях это можно переформулировать так. Определим функцию

f x = choice2 x (f (S x));

и вычислим выражение

f Z

Теперь расписываем всё это в виде имеющихся у нас комбинаторов. Определение функции f принимает вид

fix (\f -> lam (\x -> choice2 (var x) (app (var f)(natS (var x)))))

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

run (app (fix (\f -> lam (\x -> choice2 (var x) (app (var f)(natS (var x)))))) natZ) c

Суперкомпилируем его и получаем:

letrec g = \v c1 -> case c1 of {

  L c11 -> v;

  R c12 -> g (S v) c12; }

in g Z c

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

среда, 6 января 2010 г.

Реализация недетерминизма в проблемно-ориентированных языках через абстрактный синтаксис высшего порядка

В посланиях

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

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

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

В некоторых случаях написать программу, формализующую некую систему, труда не составляет. Это в тех случаях, когда язык программирования уже содержит в готовом виде те понятия, которые нужны для описания системы. А если нет? Тогда может оказаться, что изготовление такой программы превращается в занудное и трудоёмкое дело.

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

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

choice2 e1 e2

которая дожна исполняться следующим образом. При вычислении choice2 e1 e2 следует произвольно выбрать одно из выражений e1 или e2 и вычислить выбранное выражение. И результат этого вычисления должен считаться результатом вычисления всей конструкции choice2 e1 e2.

Как и в предыдущих посланиях, мы реализуем "недетерминированное" лямбда-исчисление как расширение языка HLL. HLL - это подмножество языка Haskell, являющееся входным языком суперкомпилятора HOSC.

Итак, нам нужно реализовать недетерминизм, а любая программа на языке HLL - детерминированная. Откуда же может взяться недетерминизм? Ответ прост: из внешнего мира. Используем следующий тривиальный приём: будем считать, что при запуске программы ей на вход подаётся бесконечная последовательность, которая говорит, какое из выражений в choice2 e1 e2 нужно выбрать: левое или правое. Будем считать, что эта последовательность имеет следующий тип:

data Choice = L Choice | R Choice;

А когда возникает необходимость вычислить choice2 e1 e2, программа должна заглянуть в эту последовательность и посмотреть на верхний конструктор. Если вверху конструктор L (left), нужно выбрать левое выражение, а если конструктор R (right) - то правое.

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

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

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

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

В послании

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

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

А именно, в качестве "переменных" реализуемого ПО-языка можно использовать прямо переменные того языка, поверх которого реализуется ПО-язык. В литературе этот трюк известен под именем "использование абстрактного синтаксиса высшего порядка". Суть дела проще всего объяснить на конкретном примере, посмотрев следующее задание на суперкомпиляцию Lambda: higher-order syntax 2.

Будем считать, что в нашем лямбда-исчислении имеются булевские значения и натуральные числа, которые определяются так

data Bool = True | False;

data Nat = Z | S Nat;

После чего определяются комбинаторы var (переменная), lam (лямбда-абстракция), app (аппликация) и cst (константа). Основная идея заключается в том, что переменную x можно представлять прямо в виде var x, а лямбда-абстракцию \x -> e в виде lam (\x -> e). При этом x - это, одновременно, и переменная реализуемого языка, и переменная языка реализации (т.е. HLL). Тогда, например, выражение (\x -> x) True изображается следующим образом: app (lam (\x -> var x)) (cst True).

А теперь посмотрим, как определяются комбинаторы:

var = \x -> x;

lam = \f -> f;

app = \e1 e2 -> e1 e2;

cst = \a -> a

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

Для полноты картины определим ещё fix, if и прибавление единицы к числу:

fix = \f -> f (fix f);


if = \e0 e1 e2 ->

  case e0 of {

    True -> e1;

    False -> e2;

  };


natS = \n -> S n;

Ну, ежели по-честному fix определять, то его следовало бы определить как

fix = \f -> app (lam f) (fix f)

но, выполнив пару редукций вручную, убеждаемся, что app (lam f) (fix f) быстро превращается в f (fix f). Поэтому я и не удержался от искушения, и подоптимизировал определение fix.

Теперь пробуем просуперкомпилировать несколько выражений. Получается:

cst (S (S Z)) --> (S (S Z))

app (lam (\x -> var x)) (cst True) --> True

lam (\x -> if x False True) --> (\r-> case r of { True -> False; False -> True; })

fix (\x -> natS x) --> (letrec f=(S f) in f)

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

Переопределим комбинаторы так, чтобы они "потихоньку" передавали друг-другу дополнительный параметр типа Choice, содержащий последовательность выборов.

data Choice = L Choice | R Choice;

Тогда комбинатор choice2 можно будет реализовать так:

choice2 = \e1 e2 c ->

  case c of {

    L c1 -> e1;

    R c2 -> e2;

  };

Есть, правда, одна проблема: в некоторых случаях вычисление "разветвляется": нужно вычислить два разных выражения e1 и e2. При этом, поскольку язык "ленивый", e1 и e2 могут вычисляться не сразу, а постепенно по мере надобности. Немного e1 повычисляли, а потом повычисляли e2, и т.д. Хорошо было бы снабдить e1 и e2 независимыми последовательностями выборов: передать в e1 и e2 две последовательности выборов - и не заботиться о взаимодействии этих двух вычислений.

Мы можем добиться возможности "разветвлять" последовательности выборов переопределив тип данных Choice следующим образом:

data Choice = L Choice | R Choice | D Choice Choice;

Теперь L - "левый" выбор, R - "правый" выбор, а D - "разделение" последовательности на две независимые последовательности.

После этого мы переписываем комбинаторы так, как это сделано в задании на суперкомпиляцию Lambda: non-determinism (direct). И вот что получается.

Каждый из комбинаторов получает дополнительный параметр c. Комбинаторы cst и natZ его просто игнорируют:

cst = \a c -> a;

natZ = \c -> Z;

Комбинатор natS должен вычислить свой аргумент и надеть на результат конструктор S. Он так и делает, но передаёт c своему аргументу:

natS = \e c -> S (e c);

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

var = \x c -> x c;

lam f с просто отбрасывает c (как и cst a c):

lam = \f c -> f;

Самые интересные случаи - app e1 e2 с и choice2 e1 e2. В случае с app e1 e2 c проблема в том, что сначала нужно вычислить e1, а потом применить то, что получится к e2. При этом мы не знаем, какую часть последовательности выборов "съест" e1. Поэтому, мы требуем, чтобы последовательность выборов c разветвилась на c1 и c2:

app = \e1 e2 c ->

  case c of {

    D c1 c2 -> (e1 c1) e2 c2;

  };

c1 используется при вычислении e1, а e2 - при применении результата вычисления e1 к e2.

Ну, а определение choice2 e1 e2 c говорит само за себя:

choice2 = \e1 e2 c ->

  case c of {

    L c1 -> e1 c1;

    R c2 -> e2 c2;

  };

Есть, правда, в определениях app и choice2 одна тонкость: используются case-выражения, в которых набор конструкторов - неполный. До какого-то момента так делать не разрешалось, но недавно это ограничение в HOSC было снято. Семантика неполных case-выражений такая. Если в процессе исполнения программы требуется выполнить редукцию выражения вида

case C ... of { ... }

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

Поэтому, если в app попадает c, у которого на верхнем уровне не D, то программа просто "грохается". А если в choice2 попадает c, у которого на верхнем уровне не L и не R, то и тогда программа аварийно завершается.

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

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

В определении комбинатора if используется тот же приём, что и в реализации app: разделение последовательности выборов:

if = \e0 e1 e2 c ->

  case c of {

    D c1 c2 ->

      case e0 c1 of {

        True -> e1 c2;

        False -> e2 c2;

    };

  };

И, наконец, определение комбинатора fix:

//fix = \f c -> app (lam f) (fix f) c;

fix = \f c -> f (fix f) c;

Выражение f (fix f) c является слегка оптимизированной версией выражения app (lam f) (fix f) c, учитывающей, что lam f просто игнорирует c.

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

(choice2 (cst True) (cst False)) c -->

    case c of { L c1 -> True; R c2 -> False; }

(choice2 (cst Z) (choice2 (cst (S Z)) (cst (S(S Z))))) c -->

    case c of { L c1 -> Z; R c2 -> case c2 of { L c3 -> (S Z); R c4 -> (S (S Z)); }; }

(app (lam (\x -> if (var x) (cst False) (cst True))) (cst True)) c -->

    case c of { D c1 c2 -> case c2 of { D c3 c4 -> False; }; }

(fix (\x -> choice2 natZ (natS (var x)))) c -->

    (letrec f=(\c1 ->

       case c1 of {

         L c2 -> Z;

         R c3 -> S (f c3); })

     in (f c))

Наиболее интересен последний пример, показывающий генерацию "недетерминированного" натурального числа произвольной величины. Если развернуть fix, то получится бесконечная последовательность вложенных конструкций choice2:

choice2 natZ (natS (

  choice2 natZ (natS (

    choice2 natZ (natS ( ... )) )) ))

Происходит выбор между Z и S(x), где x - "недетерминированное" натуральное число. Вот и получается, что может породиться любое натуральное число. Красота!

понедельник, 4 января 2010 г.

Специализация интерпретаторов и проблема устранения тегов

В посланиях

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

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

Общий вывод был такой:

  • Для программиста реализовывать ПО-язык через комбинаторы удобнее и проще.
  • Для устранения комбинаторов полезен суперкомпилятор, умеющий работать с функциями высших порядков.
  • Суперкомпилятор HOSC справляется со снятием слоя интерпретации и для интерпретатора первого порядка, и для набора комбинаторов.
  • При попытке написать интерпретатор первого порядка возникает "проблема тегов": данные приходится погружать в "универсальный тип данных", а после суперкомпиляции теги остаются в остаточной программе.

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

Итак, в послании

был рассмотрен интерпретатор первого порядка, для бестипового лямбда-исчисления. При этом лямбда-исчисление было "нечистым": в лямбда-термах можно было использовать натуральные числа и записывать рекурсивные определения с помощью конструкции fix f-> e, эквивалентной letrec f = e in f .

Однако же, не приводилось ни одного примера того, что получается при попытке просуперкомпилировать выражения, содержащие fix. И неспроста, ибо при суперкомпиляции получаются явные гадости, и обсуждение этих интересных и поучительных гадостей отвлекло бы нас от главной темы послания. Но теперь наступил подходящий момент, чтобы выложить все карты на стол и узнать горькую правду. Раскрываем уже известное нам задание на суперкомпиляцию Lambda: first-order syntax 2 и пробуем просуперкомпилировать выражение

run (Fix VZ (NatS (Var VZ)))

в более "человеческом" синтаксисе это выражение выглядит так: fix(\n -> S n). А поскольку главное свойство конструкции fix состоит в том, что fix f = f(fix f), имеем

fix(\n-> S n) --> (\n-> S n)(fix(\n-> S n)) --> S (fix(\n-> S n))

Наружу вытолкнулся конструктор S а в его аргументе оказалось исходное выражение. Отсюда очевидно, что вычисление fix(\n -> S n) должно порождать "бесконечное" натуральное число S (S (S ( ... ))).

Отлично, суперкомпилируем run (Fix VZ (NatS (Var VZ))) и что получаем? А получаем такой замечательный результат:

(letrec f=case f of { Error -> Error; F u3 -> Error; N p2 -> (N (S p2)); } in f)

Когда я увидел это в первый раз, то я некоторое время хлопал глазами, а потом мне прямо-таки стало нехорошо... Что бы такой результат мог означать? Ну хорошо, есть в нём дурацкие манипуляции с тегами. Вместо того, чтобы просто надеть на число n конструктор S, мы сначала снимаем с n тег N, потом надеваем S, а потом снова надеваем N. Ну, ещё и проверять приходится, что число - это число. Ладно! Это всё - зло понятное и необходимое (для интерпретатора первого порядка). Смущает другое! В данном случае, letrec - это форма записи уравнения

f=case f of { Error -> Error; F u3 -> Error; N p2 -> (N (S p2)); }

и решение этого уравнения является "смыслом" конструкции. Есть ли у этого уравнения решение? О да! Например, подставим в правую часть в качестве значения f бесконечное выражение N (S(S(...))) и выполним шаг редукции

case N(S(S(...))) of { Error -> Error; F u3 -> Error; N p2 -> (N (S p2)); }

N(S(S(S(...))))

И в результате получилось то же самое выражение N(S(S(...))) ! Оно, конечно, один конструктор S внутри добавился, но раз выражение S(S(...)) - бесконечное, от этого ничего не изменилось. Стало быть, N(S(S(...))) является решением уравнения. Чего и следовало ожидать. Хоть и выглядит этот letrec диковато, но решение-то правильное даёт! А что получится, если мы попробуем подставить f = Error ? И Error подходит в качестве решения!

case f of { Error -> Error; F u3 -> Error; N p2 -> (N (S p2)); }

Error

А если попробовать f = F (\x -> x) ? Получается

case F (\x -> x) of { Error -> Error; F u3 -> Error; N p2 -> (N (S p2)); }

Error

Ну, слава Богу, хоть F (\x -> x) в качестве решения не годится, поскольку в результате редукции получается что-то другое (Error).

Итак, подозрение, что в конструкции

(letrec f=case f of { Error -> Error; F u3 -> Error; N p2 -> (N (S p2)); } in f)

таится какая-то гнильца, вполне оправдывается. При этом, патология не в том, что эта конструкция не имеет смысла, а в том, что этих смыслов слишком много: один смысл N(S(S(...))), а другой - Error. А какой же из них является "истинным"? Как говорят в кино, "в конце должен остаться только один" (ну, или "Росинант не вынесет двоих).

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

Если встать на математическую точку, то конструкция

(letrec f=case f of { Error -> Error; F u3 -> Error; N p2 -> (N (S p2)); } in f)

имеет не два смысла, а только один! Как написано в учебниках, посвящённых денотационной семантике программ, смыслом программы является не любая неподвижная точка, а минимальная неподвижная точка! А минимальной неподвижной точкой в данном случае является "дно" (bottom). А Error и N(S(S(...))) хотя и являются решения уравнения, но они не минимальны.

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

Действительно, чтобы надеть конструктор S на f, нужно сначала снять тег N с f. А откуда мы знаем, что этот тег - именно N ? Нужно "пощупать" f, проанализировать его структуру. Для этого нужно вместо f подставить его определение. И, в процессе редукции, начинает порождаться бесконечная последовательность выражений

case f of ...

case (case f of ...) of ...

case (case (case f of ...) of ...) of ...

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

Ведь fix в исходном интерпретаторе реализован простым и "естественным" путём. В чём состоит главное свойство конструкции fix(\v -> e) ? В том, что

fix (\v -> e) = (\v -> e)(fix (\v -> e))

Стало быть, вычисление

eval (Fix v body) env

должно давать тот же результат, что и вычисление

eval (App (Lam v body) (Fix v body)) env

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

evalFix = \v body env -> eval (App (Lam v body) (Fix v body)) env;

и сделал несколько шагов редукции в правой части вручную. Получилось такое определение функции evalFix:

evalFix = \v body env ->  eval body (Bind v (evalFix v body env) env);

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

Применительно к интерпретатору это означает, что он должен разломать каждую конструкцию на части, и свести её вычисление к вычислению её отдельных частей. Определение смысла eval (Fix v body) env через смысл

eval (App (Lam v body) (Fix v body)) env

принципу "композиционности" не удовлетворяет, поскольку тут происходит не объяснение целого на основе его частей, а объяснение выражения eval (Fix v body) env через ещё ещё более "навороченное" (внутри которого, кстати, снова появляется само же выражение eval (Fix v body) env). Вообще-то суперкомпилятор умеет справляться и с "некомпозиционными" определениями функций и превращать их в "композиционные" (или хотя бы в "более композиционные"). Но из-за "некомпозиционности" граф конфигураций раздувается, его потом труднее изучать. Вот я и решил немного помочь суперкомпилятору (и себе).

Всё это я говорю, чтобы объяснить, что та реализация конструкции fix, которая описана в послании

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

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

Тут возник естественный вопрос: а можно ли исправить интерпретатор первого порядка так, чтобы он выдавал для конструкции fix что-то соответствующее здравому смыслу? Я призадумался. Ответ сразу был неочевиден... А Новый Год был уже на носу! Что было делать? Поэтому я поступил так: вымарал из послания все примеры на суперкомпиляцию конструкции fix и отправился пить шампанское. Расчёт был на то, что и читатели тоже уже приготовились пить шампанское, и будут не в состоянии заметить, что с реализацией fix-а в интерпретаторе что-то "не того" (или "того"?).

Встретив и проводив, я вернулся к изучению вопроса. :-)

Начал снова перечитывать интерпретатор. И пришёл к выводу, что он написан не совсем "честно". Раз сказано, что интерпретатор должен быть "первого порядка", значит, не только исходная программа должна быть задана в виде константы первого порядка, но и сам интерпретатор должен быть написан на языке первого порядка! А между тем, в среде env у меня использовались функции (для того, чтобы изображать "замыкания", т.е. "задержанные вычисления"). Неправильно! Замыкания, для чистоты эксперимента, нужно тоже представлять в виде констант первого порядка.

В результате у меня получился вариант интерпретатора, представленный в задании Lambda: first-order syntax 1.

Первым делом я заменил определение универсального типа данных

data Val = Error | N Nat | F (Val -> Val);

на определение "первого порядка"

data Val = Error | N Nat | C VarName Exp Env;

и "подкрутил" реализацию вычисления App и Lam. Потом снова попробовал просуперкомпилировать выражение

run (Fix VZ (NatS (Var VZ)))

Получилось такое остаточное выражение:

(letrec f=case f of { C r1 y1 v1 -> Error; Error -> Error; N w6 -> (N (S w6)); } in f)

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

Как сделать так, чтобы генерировался letrec, которому не надо было бы "щупать" теги? Ведь без тегов тоже обойтись нельзя? Функция eval exp env ведь заранее не знает, что получится в результате вычисления выражения exp: ошибка, число или функция. Значит, тип результата надо как-то помечать. Возникает, вроде бы, неразрешимая дилемма... Мучился я мучился, и вдруг вспомнил, что одно из решений проблемы было описано в статье:

Mogensen, T. Æ. 1995. Self-applicable online partial evaluation of the pure lambda calculus. In Proceedings of the 1995 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (La Jolla, California, United States, June 21 - 23, 1995). PEPM '95. ACM, New York, NY, 39-44. DOI=http://doi.acm.org/10.1145/215465.215469

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

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

Полностью это решение приведено в задании на суперкомпиляцию Lambda: first-order syntax 1 (pair).

Первым делом определяются вспомогательные типы данных:

data Unit = U;
data Bool = True | False;

Затем определяем тип данных Val, который изображает результат вычисления лямбда-выражения:

data Nat = Z | S Nat;
data Closure = C VarName Exp Env;
data Val = Val Nat Closure;

Каждое значение типа Val - это пара из числа и замыкания.

Теперь определяем абстрактный синтаксис лямбда-выражений:

data VarName = VZ | VS VarName;


data Exp =

  NatZ | NatS Exp |

  Var VarName | App Exp Exp | Lam VarName Exp |

  Fix VarName Exp;

Среды состоят только из значений первого порядка:

data Env = Empty | Bind VarName Val Env;

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

error = \u -> error U;

Функции getN и getC достают из пары число и замыкание, соответственно. varNameEq сравнивает имена переменных, а lookup вытаскивает из среды значение переменной по её имени:

getN = \v -> case v of { Val n c -> n;};

getC = \v -> case v of { Val n c -> c;};


varNameEq = \x y ->

   case x of {

     VZ -> case y of {VZ -> True; VS y1 -> False;};

     VS x1 -> case y of {VZ -> False; VS y1 -> varNameEq x1 y1;};

};


lookup = \v env ->

   case env of {

     Empty -> Val (error U)(error U);

     Bind w val env1 ->

       case (varNameEq v w) of {

         True -> val;

         False -> lookup v env1;

       };

   };

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

eval = \e env -> Val (evalN e env) (evalC e env);


evalN = \e env ->

   case e of {

     NatZ -> Z;

     NatS e1 -> S (evalN e1 env);

     Var v -> getN(lookup v env);

     Lam v body -> error U;

     App e1 e2 ->

       case evalC e1 env of {

         C v body env1 ->

           evalN body (Bind v (eval e2 env) env1);};

     Fix v body -> evalFixN v body env;

};


evalC = \e env ->

   case e of {

     NatZ -> error U;

     NatS e1 -> error U;

     Var v -> getC(lookup v env);

     Lam v body -> C v body env;

     App e1 e2 ->

       case evalC e1 env of {

         C v body env1 ->

           evalC body (Bind v (eval e2 env) env1);};

     Fix v body -> evalFixC v body env;

};

Теперь, естественно, выясняется, что вместо одной функции evalFix получилось две функции: evalN и evalC. Каждая из них ищет неподвижную точку "своего" типа. Поэтому им не надо снимать и надевать теги. А в этом-то и была проблема!

evalFixN = \v body env ->

   evalN body (Bind v (Val (evalFixN v body env) (error U)) env);


evalFixC = \v body env ->

   evalC body (Bind v (Val (error U) (evalFixC v body env)) env);


run = \e -> eval e Empty;

И вот теперь, наконец, попытаемся просуперкомпилировать выражение

run (Fix VZ (NatS (Var VZ)))

Получается такой результат:

(Val (letrec f=(S f) in f) (letrec g=g in g))

Ура! Наконец, получился осмысленный результат! Это хорошо... Но только если забыть о том, что при использовании комбинаторов хороший результат получился сразу же и без "вставаний на уши". :-)

В заключение уместно отметить, что данный вариант интерпретатора написан на том варианте HLL (входного языка суперкомпилятора HOSC), который существует в момент написания данного послания. А в данный момент в HLL наборы образцов в case-выражениях должны быть "исчерпывающими": сколько разных конструкторов имеется в типе данных, столько и должно быть перечислено в case-выражении. Из-за этого и пришлось вставить в интерпретатор вызовы функции error U. Можно разрешить опускать часть конструкторов в case-выражениях, и считать, что при возникновении ситуации, не предусмотренной в case-выражении, возникает "ошибка" (приводящая к аварийной остановке программы). Тогда часть ветвей в интерпретаторе можно будет просто опустить. Он от этого станет поменьше, но извращённость и противоестественность его конструкции от этого никуда не денется.

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