Метапрограммирование: какое оно есть и каким должно быть

Метапрограммирование — вид программирования, связанный с созданием программ, которые порождают другие программы как результат своей работы (wiki). Это достаточно общий термин, к которому, согласно той же википедии, относится и генерация исходного кода внешними инструментами, и различные препроцессоры, и «плагины к компилятору» — макросы с возможностью модификации синтаксического дерева не посредственно в процессе компиляции, и даже такая экзотическая возможность, как самомодифицирующийся код — модификация программы самой программой непосредственно во время выполнения.

Хотя, конечно, самомодифицирующийся код — это скорее отдельная большая тема, достойная отдельного исследования; здесь под метапрограммированием мы будем понимать процессы, происходящие во время компиляции программы.

Метапрограммирование реализовано в той или иной мере в очень разных языках; если не рассматривать экзотические и близкие к ним языки, то самым известным примером метапрограммирования является С++ с его системой шаблонов. Из «новых» языков можно рассмотреть D и Nim. Одна из самых удачных попыток реализации метапрограммирования — язык Nemerle. Собственно, на примере этой четверки мы и рассмотрим сабж.

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

Этапы компиляции

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

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

Следующий этап — синтаксический анализ, построение синтаксического дерева. На этом этапе линейная структура превращается в иерархическую; в такую, какой мы ее собственно и представляем при написании программ. Классы, функции, блоки кода, операции становятся узлами абстрактного синтаксического дерева (AST). Синтаксический анализ сам по себе состоит из многих этапов; куда входит и работа с типами (включая вывод типов), и различные оптимизации.

Завершающий этап — генерация кода. На основе синтаксического дерева генерируется виртуальный и/или машинный код; здесь все зависит от целевой архитектуры — распределяются регистры и память, узлы дерева превращаются в последовательности команд, проводится дополнительная оптимизация.

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

Лексические макросы

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

#define true false

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

Шаблоны С++

Следующий наиболее известный инструмент метапрограммирования — шаблоны С++ — конструкции, позволяющие создавать параметризированные классы и функции. Шаблоны, в отличие от сишных макросов, работают уже с синтаксическим деревом. Рассмотрим самый обычный шаблон в С++

template<class T, int N>
struct Array
{
  T data[N];
};

и его применение (инстанцирование):

Array<int,100> arr;

Что здесь происходит с точки зрения компилятора? Шаблонная структура — это отдельный, специальный узел AST; у шаблона есть два параметра — тип и целочисленная константа. В точке инстанцирования шаблона параметры шаблона (которые тоже на самом деле являются узлами AST) подставляются в тело шаблона вместо формальных имен параметров; в результате происходит создание (или поиск ранее созданного) узла, который и используется в основном синтаксическом дереве. Здесь важно следующее: и сам шаблон, и параметры шаблона в точке инстанцирования — это не просто тип и число, это ноды синтаксического дерева. То есть, передавая тип int и число 100, вы на самом деле конструируете и передаете два маленьких синтаксических дерева (в данном случае — с одним единственным узлом) в синтаксическое дерево побольше (тело шаблона) и получаете в результате новое дерево, которое вставляется в основное синтаксическое дерево. Похоже на механизм подстановки сишных макросов, но уже на уровне синтаксических деревьев.

Разумеется, параметры шаблона могут быть и более сложными конструкциями (например в качестве типа можно передать std::vector < std::set < int > > ). Но здесь самое время обратить внимание на принципиальную неполноту возможностей шаблонов С++. В соответствии с пунктом стандарта 14.1 параметрами шаблона могут быть только типы и некоторые не-типы: целые числа, элементы перечислений, указатели на члены класса, указатели на глобальные объекты и указатели на функции. В общем логика понятна — в списке есть то, что может быть определено на этапе компиляции. Но например, в нем по непонятным причинам нет строк и чисел с плавающей точкой. А если вспомнить то, что параметры — это ноды AST, то становится очевидно, что нет и многих других полезных вещей. Так, что мешает передать в качестве параметра произвольную ноду AST, например имя переменной или блок кода? Аналогично, сами шаблоны могут быть только классами (структурами) или функциями. А что мешает сделать шаблоном произвольный блок кода — как императивного (управляющие операторы, выражения), так и декларативного (например фрагмент структуры или перечисления)? Ничего, кроме отсутствия таких возможностей в самом С++.

От шаблонов — к синтаксическим макросам

Механизм шаблонов, даже в том виде в котором он существует в С++, предоставляет достаточно широкие возможности метапрограммирования. И тем ни менее, это всего лишь система подстановок одних фрагментов AST в другие. А что если пойти дальше, и, кроме подстановок, разрешить что-то еще — в частности, выполнение произвольных действий над нодами AST с помощью скрипта? Это и есть синтаксические макросы, самый мощный инструмент метапрограммирования на сегодняшний день. Произвольный код, написанный программистом и выполняющийся на этапе компиляции основной программы, имеющий доступ к API компилятора и к структуре компилируемой программы в виде AST, по сути — полноценные плагины к компилятору, встроенные в компилируемую программу. Не так уж много языков программирования реализует эту возможность; одна из лучших на мой взгляд реализаций — в языке Nemerle, поэтому рассмотрим ее более подробно.
Вот простейший пример из почти официальной документации:

macro TestMacro()
{
    WriteLine("compile-time\n");
    <[ WriteLine("run-time\n") ]>;
}

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

TestMacro();

то при компиляции мы получим сообщение «compile-time» в логе компилятора. А при запуске программы в консоль будет выведено сообщение «run-time».

Как мы видим, макрос — это обычный код (в данном случае на том же языке Nemerle, что и основная программа); отличие в том, что этот код выполняется на этапе компиляции основной программы. Таким образом, компиляция разделяется на две фазы: сначала компилируются макросы, а затем — основная программа, при компиляции которой могут вызываться скомпилированные ранее макросы. Первая строчка выполняется во время компиляции. Вторая строчка содержит интересный синтаксис — специальные скобки <[ ]>. С помощью таких скобок можно брать фрагменты кода как-бы в кавычки, по аналогии с обычными строками. Но в отличие от строк, это фрагменты AST, и они вставляются в основное синтаксическое дерево программы — в точности как шаблоны при инстанцировании.

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

macro TestMacro(myName)
{
  WriteLine("Compile-time. myName = " + myName.ToString());
  <[ WriteLine("Run-time.\n Hello, " + $myName) ]>;
}

Аргумент — нода AST (также как и для шаблонов); для вставки ноды в квазицитату используется символ $ перед ее именем.

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

new FunctionCall( new Literal("run-time\n") )

но ведь гораздо проще написать код «как есть» и доверить работу по построению AST компилятору — ведь именно для этого он и предназначен!

В языке D метапрограммирование представлено с помощью шаблонов (которые в общем похожи на шаблоны С++, хотя есть и определенные улучшения) и «миксинов». Рассмотрим их подробнее. Первый тип — шаблонные миксины; то самое расширение шаблонов возможностью делать шаблонным произвольные фрагменты кода. Например, эта программа выведет число 5.

mixin template testMixin()
{
      int x = 5;
}
int main(string [] argv)
{
     mixin testMixin!();
     writeln(x);
    return 0;
}

переменная, объявленная в миксине, становится доступна после включения миксина в код.

Второй тип миксинов — строковые миксины; в этом случае аргументом ключевого слова mixin становится строка с кодом на D:

mixin (`writeln("hello world");`);

Строка, разумеется, должна быть известна на момент компиляции; и это может быть не только константная явно определенная строка (иначе в этом не было бы никакого смысла), но и строка, сформированная программно во время компиляции! При этом для формирования строки могут использоваться обычные функции языка D — те же самые, которые можно использовать и в рантайме. Разумеется, с определенными ограничениями — компилятор должен иметь возможность выполнить код этих функций во время компиляции (да, в компилятор языка D встроен довольно мощный интерпретатор самого языка D).

В случае строковых миксинов мы не работаем с узлами AST в виде квазицитат; вместо этого мы работаем с исходным кодом языка, который формируется явно (например путем конкатенации строк) и проходит полный путь лексического и синтаксического анализа. У такого способа есть и преимущества и недостатки. Лично мне прямая работа с AST кажется более «чистой» и идеологически правильной, чем генерация строк исходного кода; впрочем, и работа со строками может оказаться в какой-то ситуации полезной.

Еще можно совсем кратко упомянуть язык Nim. В нем ключевое слово template работает похоже на mixin template из D (а для классических шаблонов в стиле раннего С++ используется другое понятие — generic). С помощью ключевого слова macro объявляются синтаксические макросы, чем-то похожие на макросы Nemerle. В Nim сделана попытка формализовать фазы вызова шаблонов — с помощью специальных прагм можно указать, вызывать ли шаблон до разрешения имен переменных или после. В отличие от D, есть некоторое API к компилятору, с помощью которого можно явно создавать узлы AST. Затрагиваются вопросы «гигиеничности» макросов (макрос «гигиеничен», если он гарантированно не затрагивает идентификаторы в точке его применения… мне бы следовало рассмотреть эти вопросы более подробно, но наверное в другой раз).

Выводы

Глядя на реализацию метапрограммирования в разных языках, появляются некоторые мысли о том, как оно должно выглядеть в идеальном случае. Вот некоторые мысли:

Метапрограммирование должно быть явным

Вызов макроса — это весьма специфическая вещь (на самом деле ОЧЕНЬ специфическая вещь!), и программист должен однозначно визуально идентифицировать такие макросы в коде (даже без подсветки синтаксиса). Поэтому синтаксис макросов должен явно отличаться от синтаксиса функций. Более-менее это требование выполняется только в D (специальное ключевое слово mixin в точке вызова); в Nemerle и Nim макросы неотличимы от функций. Более того, в Nemerle существует еще несколько способов вызова макроса — макроатрибуты и возможность переопределения синтаксиса языка… здесь можно немножко отвлечься и отметить, что синтаксис, в отличие от функций и классов — глобален; и я скорее отрицательно отношусь к такой возможности, потому что она приводит к размыванию языка и превращению его в генератор языков, что означает, что для каждого нового проекта придется изучать новый язык… перспектива, надо сказать, сомнительная)

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

Между тем, пример альтернативного подхода всегда лежал на поверхности: в web программировании используется язык разметки html и язык программирования javascript; javascript исполняется во время рендеринга (аналога компиляции) html, из скриптов доступна объектная модель документа html (HTML DOM) — достаточно близкий аналог AST. С помощью соответствующих функций можно добавлять, модифицировать и удалять узлы HTML DOM, причем на разных уровнях — как в виде исходного кода html, так и в виде узлов дерева DOM.

// формируем html в виде текста, аналогично mixin в D
document.getElementById('myDiv').innerHTML = '<ol><li>html data</li></ol>';
// формируем html в виде узлов дерева, аналогично Nim
var link = document.createElement('a');
link.setAttribute('href', 'mypage.htm');
document.getElementById('myDiv').appendChild(link);

Какие же преимущества и недостатки такого подхода?
Очевидно, метапрограмма не должна иметь возможности обрушить или подвесить компилятор. Очевидно, что если писать метапрограммы на СИ — с указателями и прочими низкоуровневыми вещами, то обрушить его будет очень просто. С другой стороны, использовать общий код в программах и метапрограммах — это удобно. Хотя этот «общий код» все равно ограничится какими-то совсем уж общими вещами вроде чистых алгоритмов: API компилятора неприменимо в программах, а библиотеки «реальной ОС» (в том числе графика, оконная система, сеть...) весьма слабоприменимы в метапрограммах. Конечно, можно во время компиляции создать пару своих окошек и вывести их на экран, но зачем?

Таким образом, совершенно необязательно, чтобы программы и метапрограммы были на одном языке. У программ и метапрограмм совершенно разные задачи и совершенно разные среды выполнения. Наверное, лучшее решение — оставить программисту свободу и использовать несколько языков: как безопасное подмножество основного языка, так и какой-нибудь распространенный скриптовый язык — тот же javascript вполне подойдет.

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

Поддержка со стороны IDE
Метапрограммирование может быть достаточно сложным. До сих пор все известные мне реализации не предполагали каких-либо средств, облегчающих труд программиста: а компилировать в уме — та еще затея (конечно есть любители...). Хотя метапрограммисты на С++ например именно этим и занимаются. Поэтому я считаю необходимым появление таких средств, как раскрытие шаблонов и макросов в специальном режиме IDE — как в режиме отладки, так и в режиме редактирования кода; какой-то аналог выполнения кода «из командной строки» REPL для макросов. У программиста должен быть полный набор инструментов для визуального доступа к AST, для отдельной компиляции и тестового запуска макросов, для «компиляции по шагам» (именно так — для просмотра в специальном отладчике как работает макрос при компиляции основного кода в пошаговом режиме).

Ну вот пожалуй и все. Очень многие вопросы остались за кадром, но думаю, даже этого достаточно, чтобы оценить невероятную мощь метапрограммирования. А теперь представьте, что это все уже сейчас было бы в С++. Посмотрите на библиотеку Boost, на те удивительные и невероятные вещи, которые делают люди даже на существующих шаблонах и лексических макросах…

Если бы это было так… какие поистине Хакерcкие возможности открылись бы перед нами!