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

пятница, 31 июля 2009 г.

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

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

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

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

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

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

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

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

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