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

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

Вот, например, это послание собирался настрочить Илья Ключников, но недавняя поездка в США (сопровождавшаяся посещением джаз-фестивалей и тому подобных мероприятий) окончательно подорвала его силы, остатков которых всё же хватило, чтобы докончить изготовление описания внутренностей суперкомпилятора HOSC:

Klyuchnikov I.G.
Supercompiler HOSC 1.0: under the hood>
KIAM Preprint No. 63, Moscow, 2009

The paper describes the internal structure of HOSC, an experimental supercompiler dealing with programs written in a higher-order functional language. A detailed and formal account is given of the concepts and algorithms the supercompiler is based upon.

http://library.keldysh.ru/preprint.asp?id=2009-63

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

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

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

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

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

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

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

Эта идея обсуждалась в послании

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

на примере функциональных парсеров.

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

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

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

А вот что получится, если попытаться заменить интерпретатор первого порядка на набор комбинаторов? Получится ли это? А если получиться, то получится ли лучше? Забегая вперёд, сразу же скажу что, во-первых, получится, а, во-вторых, получиться лучше!

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

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

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

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

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

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

data Nat = Z | S Nat;

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

Натуральные числа 0, 1, 2, ... будем представлять как Z, S Z, S (S (Z)), ... А все значения, обрабатываемые и возвращаемые лямбда-выражениями будут делиться на три категории: ошибки (изображаемые конструктором Error), натуральные числа и функции из значений в значения. (А конструкторы, служащие для различения данных различных типов в народе принято называть "тегами". В данном случае имеем три тега: Error, N и F.)

Как известно, в "чистом" лямда-исчислении любое выражение имеет один из следующих видов:

• x - переменная,
• (\x -> e) - лямбда-абстракция (определение функции),
  
• e1 e2 - аппликация (применение функции).
  

Но мы будем рассматривать расширенное лямбда-исчисление, умеющее работать с натуральными числами, поэтому добавим ещё две конструкции:

• 0 - нуль (вычисление которого даёт N Z), и
• S e - прибавление 1 к результату вычисления e.
  

Ну, чтобы было интереснее, ещё добавим конструкцию

• fix x -> e - нахождение неподвижной точки выражения e.
  

Конструкция fix позволяет записывать рекурсивные определения функций и бесконечных данных. Например, "бесконечное" натуральное число S (S (S ( ... ))) можно записать так: fix x -> S x .

Смысл конструкци fix можно объяснить через следующее эквивалентное преобразование:

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

Например,

(fix x -> S x) --> (\x -> S x)(fix x -> S x) --> S (fix x -> S x)

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

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

data VarName = VZ | VS VarName;

и будем считать, что

VZ, VS VZ, VS (VS VZ), ...

изображают переменные

x0, x1, x2, ...

после чего мы можем определить "абстрактный синтаксис" (первого порядка) для языка лямбда-исчисления

data Exp =

  NatZ | NatS Exp |

  Var VarName | App Exp Exp | Lam VarName Exp |

  Fix VarName Exp;

Например, лямбда-термы

S Z

\x -> x x

fix x -> S x

представляются в виде констант

NatS NatZ

Lam VZ (App (Var VZ) (Var VZ))

Fix VZ (NatS (Var VZ))

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

Теперь, определившись с формой записи программ, переходим к написанию интерпретатора. Первым делом надо решить, каким способом мы собираемся хранить значения переменных? Допустим, у нас есть переменные x₁, x₂, ..., x_n имеющие значения v₁, v₂, ..., v_n соответственно. Классический подход - использовать "среду" (или "окружение") вида

[(x₁,v₁), (x₂,v₂), ..., (x_n,v_n)]

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

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

data Env = Empty | Bind VarName Val Env;

Таким образом, среда [(x0, 0), (x1,1)], будет представлена следующим образом:

Bind VZ (N Z) (Bind (VS VZ) (N (S Z)) Empty

Теперь нам нужна функция lookup v env, которая для переменной v и среды env извлекает из env значение, соответствующее переменной v. Понятно, что для реализации этой функции нужно уметь сравнивать имена переменных на равенство, поэтому требуется ещё определить предикат varNameEq x y, проверяющий x и y на равенство. На входном языке HOSC-а эти функции можно определить так:

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 -> Error;
     Bind w val env1 ->
       case (varNameEq v w) of {
         True -> val;
         False -> lookup v env1;
     };
   };

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

lookup x (Bind VZ v1 (Bind (VS VZ) v2 Empty))

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

case x of { VZ -> v1; VS s2 -> case s2 of { VZ -> v2; VS t1 -> Error; }; }

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

А теперь, разделавшись с занудной частью работы, мы можем дописать интересную часть интерпретатора. Собственно говоря, интерпретатор - это функция eval e env, которая вычисляет значение выражения e при условии, что значения свободных переменных из e определены средой env.

eval = \e env ->
  case e of {
    NatZ -> N Z;
    NatS e1 -> evalNatS (eval e1 env);
    Var v -> lookup v env;
    Lam v body ->
      F (\x -> eval body (Bind v x env));
    App e1 e2 ->
      case eval e1 env of {
        Error -> Error;
        N n -> Error;
        F f -> f (eval e2 env);
      };
    Fix v body -> evalFix v body env;
  };

evalNatS = \x ->
  case x of {
    Error -> Error;
    N n -> N (S n);
    F f -> Error;
  };

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

run = \e -> eval e Empty;

Функция run e вычисляет значение выражения e, при условии, что e не содержит свободных переменных, и определена для удобства запуска тестов.

Можно погонять и посуперкомпилировать этот интерпретатор "вживую" используя заранее заготовленное задание для суперкомпилятора HOSC.

Например,

run NatZ ==> (N Z)

run (NatS NatZ) ==> (N (S Z))

run (Lam VZ (App (Var VZ) (Var VZ))) ==>

  (F (\t3-> case t3 of { Error -> Error; N t4 -> Error; F s6 -> (s6 (F s6)); }))

run (App (Lam VZ (Var VZ)) NatZ) ==> (N Z)

run (Lam VZ (NatS (Var VZ))) ==>

   (F (\w1-> case w1 of { Error -> Error; N p2 -> (N (S p2)); F s2 -> Error; }))

Вроде бы всё правильно... Но смотреть на такие результаты суперкомпиляции как-то неприятно: суть дела в них затемнена непрерывными манипуляциями с конструкторами ("тегами") Error, N и F. При каждой операции эти теги снимаются с данных, а потом тут же снова надеваются. Особенно наглядно это видно из реализации функции evalNatS x. Казалось бы, всего и делов-то: надеть на аргумент конструктор S. Да не тут-то было. Сначала нужно проверить: а действительно ли в качестве аргумента подано число? А друг в аргументе Error или функция? Если на входе действительно число, с него нужно содрать тег N, надеть на число конструктор S, а потом надеть тег N обратно. Куча тупой и глупой работы! Да и текст интерпретатора от этого заметно раздувается.

Но, как бы то ни было, интерпретатор первого порядка для языка с переменными изготовить удалось (что было изначально понятно из общих соображений). А теперь мы переходим к следующему, более интересному вопросу: а можно ли реализовать язык лямбда-исчисления с помощью комбинаторов? При этом хотелось бы сделать это не для лямбда-исчисления с динамической типизацией (в духе языков Lisp или Scheme), а со статической (в духе Standard ML и Haskell)? А не помешает ли статическая типизация собирать проблемно-ориентированные программы из комбинаторов? Допустим, каждый из комбинаторов по отдельности мы сумеем придумать, а при попытке их соединить вместе получим "по рукам" от проверяльщика типов (type-checker-а)?

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

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

Например, если интерпретируемый язык разрешает использовать конструкции со связанными переменными, значения переменных нужно хранить в виде "среды". Допустим, есть в программе переменная i типа Int, связанная со значением 25, и переменная s типа String, связанная со значением "abc". Тогда среда, связывающая переменные со значениями, выглядит так:

[(i, 25), (s, "abc")]

т.е. это список, состоящий из упорядоченных пар вида (v, a), где v - имя переменной, а a - её значение. В языке с динамической типизацией такие среды не создают никаких проблем. Но в языках вроде Standard ML и Haskell таким способом сконструировать среду нельзя! Ибо статическая полиморфная типизация по Хиндли-Милнеру требует, чтобы все элементы списка были одного типа! Стало быть, если значение одной переменной имеет тип Int, то и значения остальных переменных (из того же окружения) должны иметь тот же тип.

Ну и как же бороться с этим ограничением? Да очень просто: нужно, чтобы тип был одинаковый - сделаем. Определим такой тип данных:

data EnvVal = EnvInt Int | EnvString String;

и представим среду в виде

[(i, EnvInt 25), (s, EnvString "abc")]

(Собственно говоря, так и было сделано в интерпретаторе для лямбда-исчисления, рассмотренном выше.)

Теперь всё, вроде бы, становится "хорошо": в каждой паре имя переменной связывается со значением типа EnvVal, и интерпретатор языка становится типизируемым. А расплата за это состоит в том, что интерпретатор вынужден работать с данными типа Int и String не напрямую, а всё время надевая на них и снимая "теги", конструкторы EnvInt и EnvString.

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

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

Желающим ознакомиться с историей вопроса, с литературой посвящённой проблеме и с её решением советую покопаться в этой статье:

Carette, J., Kiselyov, O., and Shan, C. 2009. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. J. Funct. Program. 19, 5 (Sep. 2009), 509-543. DOI= http://dx.doi.org/10.1017/S0956796809007205

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

data List a = Nil | Cons a (List a);

У конструктора типов List a - только один типовый параметр, вот и получается, что все элементы списка должны иметь одинаковый тип. Но ведь нас никто не заставляет использовать для представления сред именно списки. А почему бы не изготавливать среды из пар? Например, кто нам мешает представить окружение, например, в таком виде:

((i, 25),  ((s, "abc"), ()))

т.е. соорудить среду из упорядоченных пар. А компоненты пары могут иметь разные типы!

Идея - проста и хороша, но если её попытаться применить к интерпретатору, написанному на языке первого порядка, она не работает. Причина в том, что такой интерпретатор представляет собой слишком "монолитное", "сильно связанное" сооружение. Есть в таком интерпретаторе такое место, в которую сходятся все пути: это то место, где происходит распознавание типа интерпретируемой конструкции. Все пути проходят через функцию eval e env. А эта функция должна быть рассчитана на любое выражение e и любую среду env. Вот и получается, что при попытке приписать тип функции eval e env приходится рассчитывать на самый худший вариант: считать, что env может иметь любую структуру, и что все её элементы должны иметь одинаковый тип.

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

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

\x -> \y -> \ z -> z y x

можно представить в виде

\ \ \ 0 1 2

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

Если уже мы решили все конструкции изображать комбинаторами, а комбинаторы - это функции, то отчего бы и индексы Де Брюйна не изобразить функциями?

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

data Unit = U;
data Pair a b = P a b;
data Bool = True | False;
data Nat = Z | S Nat;

fst = \v -> case v of {P x y -> x;};
snd = \v -> case v of {P x y -> y;};

А теперь принимаем такое решение: пусть индексы Де Брюйна 0, 1, 2, изображаются как varZ, varS varZ, varS (varS varZ)), где функции varZ и varS определены следующим образом:

varZ = \env -> fst env;
varS = \v env -> v (snd env);

Идея состоит в том, что переменные можно изображать функциями, которые как раз и осуществляют выборку нужных значений из среды! А сама среда при этом имён переменных не содержит, и состоит из одних значений переменных. Функция varZ извлекает из среды самое последнее значение, а функция (varS v) отбрасывает из среды верхнее значение и предлагает функции v выбрать из оставшейся части среды нужное значение.

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

natZ = \env -> Z;

natS = \n env -> S(n env);

lam = \e env x -> e (P x env);

app = \e1 e2 env -> (e1 env) (e2 env);

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

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

• natZ игнорирует среду и выдаёт Z.
• natS вычисляет свой аргумент n в среде env (просто применив аргумент к среде) и навешивает на результат S.
• lam запоминает e и ждёт, когда появится среда. Когда появляется среда env, порождается функция \x -> e (P x env). Эта функция, получив x добавляет x к среде и вычисляет x в пополненной среде.
• app вычисляет e1 в среде env. Получается функция, которая берёт в качестве аргумента выражение, вычисляющее e2 в среде env.
• fix реализован с помощью комбинации тех же приёмов, с помощью которых реализованы lam и app.
  

С помощью описанных выше комбинаторов, например, выражение \x -> \y -> y x записывается следующим образом:

lam (lam (app varZ (varS varZ)))

Ну что же, хоть и не сахар, но внешне такая запись выглядит примерно так же, как и в случае абстрактного синтаксиса первого порядка. Основная разница заключается в том, что раньше lam, app и fix писались с большой буквы, а теперь пишутся с маленькой. :-)

Однако, если сравнить текст интерпретатора первого порядка с реализацией комбинаторов, то простота реализации на основе комбинаторов прямо-таки поражает воображение!

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

Например, захотелось нам добавить конструкцию (cst a), результатом вычисления которой является a, определяем комбинатор:

cst = \a env -> a;

который игнорирует среду и выдаёт a. Теперь в программе можно писать cst True и cst False. А если захотелось добавить условные выражения, определяем комбинатор if:

if = \e0 e1 e2 env ->

  case e0 env of {

    True -> e1 env;

    False -> e2 env;

  };

А те комбинаторы, что уже есть, модифицировать не надо.

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

run = \e -> e U;

И вот теперь наступает интересный момент. А что получится, если посуперкомпилировать выражения лямбда-языка, представленные с помощью комбинаторов? Пробуем, и вот что получается:

run (natS (natS natZ)) ==> (S (S Z))

run (app (lam varZ) (cst True)) ==> True

run (lam (if (varZ) (natS natZ) natZ)) ==>

   (\y-> case y of { True -> (S Z); False -> Z; })

run (fix (natS varZ)) ==> (letrec f=(S f) in f)

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

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

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

Читать дальше...

Что означает по-японски "Ёсихико Футамура"

В предыдущих посланиях упоминались три "проекции Футамуры" (независимо открытые также и Валентином Турчиным).

И у некоторых господ/коллег/товарищей возник интересный вопрос: как пишется по-японски "Ёсихико Футамура" и что сие означает?

По-японски это пишется так:

二村良彦

При этом сначала пишется имя клана ("фамилии"), а потом - личное имя. Те 二村 - это Фута-мура, а 良彦 - это Ёси-хико. С точки зрения японцев это совершенно естественно: сначала сообщается самая важная информация (имя множества), а потом - менее важная (имя его элемента).

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

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

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

Итак, в совокупности имеем 村. Т.е. "деревья" или "лес" сталкиваются с идеей "порядка". А деревня - она ведь и стоит на грани между "цивилизацией" и "дикой природой, лесом"...

Теперь посмотрим на личное имя 良彦 (Ёси-хико, или в японской слоговой фонетической записи よしひこ = ё-си-хи-ко). Сразу заметим, что よし наиболее адекватно (хотя и не абсолютно точно) передается кириллическими буквами как "ёси". Проблема в том, что в японском языке звук "с" довольно похож на русский "с", но чуть-чуть шепелявый (для избавления от подобной легкой шепелявости, у нас детей к логопедам водят, а в Японии, видимо, наоборот, для ее приобретения). Поэтому если написать し кириллическими буквами как "си", то невыраженной оказывается шепелявость звука. Т.е., с точки зрения японца, "с" - звук правильный, но слегка "дефектный". А вот если написать "ши", то получается совсем плохо, поскольку в японском языке нет звука даже отдаленно похожего на наш "ы". А как учат наших детей в школе: "Жи-ши - пишется с буквой И!" Т.е. русский человек (без особой подготовки) после "ж" и "ш" звук "и" произнести вообще не в состоянии: он всегда говорит "ы"! А по законам русской орфографии полагается писать "и", а произносить "ы" (что детям с большим трудом и вдалбливают"). Поэтому, если よしひこ записать как Ёшыхико, то, с точки зрения японцев, звучание получается просто ужасное...

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

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

Итак, похоже, что наиболее адекватно понятие 良彦 (ёси-хико) можно передать по-русски, как "добрый молодец" или как "крутой парень"! (Ведь там содержиться не только идея внешней статности, но еще и "компетентности" или "эффективности".)

Итого, получаем:

二村良彦 = из двойной деревни добрый молодец

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

Читать дальше...

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

По поводу послания Проблемно-ориентированные языки и суперкомпиляция возник следующий правильный и законный вопрос. Ну хорошо, проблемно-ориентированные языки (ПО-языки) можно реализовывать с помощью интерпретаторов/комбинаторов с последующей обработкой программы частичным вычислителем или суперкомпилятором. Ну, и чем же отличается этот подход, от "многостадийного программирования" (multi-stage programming), реализованного в MetaOCaml, Template Haskell и шаблонах (templates) C++?

K. Czarnecki, J.T. O'Donnell, J. Striegnitz, W. Taha, DSL implementation in MetaOCaml, Template Haskell and C++, in: C. Lengauer, D. Batory, C. Consel, M. Odersky (Eds.), Domain-Specific Program Generation, in: Lecture Notes in Computer Science, vol. 3016, Springer-Verlag, 2004, pp. 51-72.

К сожалению, я не являюсь знатоком ни MetaOCaml, ни Template Haskell. Но ответить всё же попытаюсь. Поэтому заранее предупреждаю, что мой ответ может оказаться неправильным. Ну, или правильным - да не совсем... Тогда, как я надеюсь, общественность укажет на мои ошибки и заблуждения, и я постараюсь встать на путь исправления! :-)

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

Какие проблемы возникают при таком подходе?

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

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

В случае Template Haskell (если я правильно понимаю), предлагается начинать не с интерпретатора, а прямо сразу писать компилятор. Особенности такого подхода следующие:

• Вопрос о корректности реализации DSL теряет смысл. Если нет интерпретатора, то и непонятно, по отношению к чему корректен компилятор? Как человек напишет - так и будет "правильно" по-определению.

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

В случае шаблонов C++, как и для Template Haskell предлагается обходиться без интерпретатора и сразу изготавливать компилятор. И проблемы получаются те же самые:

• Вопрос о корректности реализации через шаблоны C++ даже непонятно как и поставить?

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

А подход основанный на использовании частичных вычислений и/или суперкомпиляции отличается следующим:

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

• Затем на интерпретатор/комбинаторы напускается частичный вычислитель/суперкомпилятор, который генерирует более эффективную остаточную программу, из которой изгнан интерпретатор/комбинаторы.

• Корректность остаточной программы обеспечивает частичный вычислитель/суперкомпилятор. Точнее тот, кто их изготовил. :-) А тот, кто пишет интерпретатор/комбинаторы от этой заботы избавлен.

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

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

Читать дальше...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать дальше...

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

В заметках

• Что такое суперкомпиляция?

• Какой язык лучше суперкомпилировать: "строгий" или "ленивый"?

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

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

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

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

d₁ ... d_N e₀ where f₁ = e₁; ... f_N = e_N;

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

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

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

• f₁ = e₁; ... f_N = e_N; - определения глобальных функций. Эти функции могут использоваться внутри целевого выражения e₀ .

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

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 -> e₀) e₁, и понятно, что нужно сделать дальше: применить функцию к аргументу. Т.е. в e₀ заменить все вхождения v на e₁. Конкретно, (\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, в виде формул и всего прочего, что должно быть в "научных" сочинениях.)

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

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

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

Читать дальше...

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

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

Теперь пришло время поговорить о суперкомпиляции функций "высших порядков". Что такое "высший порядок", хорошо знает любой поклонник функционального программирования (если, конечно, под "функциональными языками" подразумевать языки вроде 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 три раза.

Читать дальше...