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




Метапрограммирование — вид программирования, связанный с созданием программ, которые порождают другие программы как результат своей работы (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кие возможности открылись бы перед нами!

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (24):

  1. mx2000
    /#8432077 / +4

    макросы растишки (rust) вполне себе удовлетворяют ряду условий:
    — вы определенно знаете, что вызываете макрос (благодаря синтаксису)
    — язык макроса может быть любым (благодаря плагинам компилятора)
    — растишка умеет разворачивать макросы в «конечный» сырец, так что всегда можно увидеть во что превратился тот или иной макрос в конкретном месте

    doc.rust-lang.org/book/macros.html

    зы. а вообще забавно читать про метапрограммирование и не обнаружить слова lisp.

    • NeoCode
      /#8432287

      Меня интересуют в первую очередь си-подобные языки. Ну и конечно всего не охватить в одной статье… хотя конечно Rust можно было упомянуть, я просто не успел еще разобраться с его макросами. По Rust (как и по Nim) на данный момент крайне мало документации, надеюсь в ближайшее время что-то поменяется в лучшую сторону в связи с выходом 1.0. Что же касается lisp, то это язык с сильно отличающимся от «мейнстрима» синтаксисом, этот фактор усложняет понимание.

      • Duduka
        /#8432623

        Голый AST усложняет понимание?

        • NeoCode
          /#8432655 / +3

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

          • Duduka
            /#8432713

            Да, похоже, система программировения — прежде всего, задачи которые в ней решаются, вне их языки не имеют очевидной семантики.

      • Googolplex
        /#8433599

        По Rust есть целая большая официальная книга, на главу которой про макросы выше привели ссылку. И Rust, кстати, всё-таки по синтаксису гораздо ближе к C, чем Nim или Nemerle.

  2. lockywolf
    /#8432083 / +5

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

    Это, вроде, интерполяцией называется.

    • NeoCode
      /#8432265

      Да, вы правы, поправил.

  3. encyclopedist
    /#8432107 / +4

    1. В C++ есть ещё один способ — это constexpr, который позволяет выполнение кода во время компиляции (не любого, с ограничениями).
    2. Не все компиляторы C++ основаны на AST. Главный пример такого динозавра — это MS Visual Studio, из-за чего в VS сильно затруднена реализация мета-возможностей, в частности, как раз полноценной поддержки constexpr нет, и будет не скоро.

    • NeoCode
      /#8432295 / +2

      Не все компиляторы C++ основаны на AST. Главный пример такого динозавра — это MS Visual Studio

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

      • encyclopedist
        /#8433097 / +4

        Ну открытой информации нету. Я знаю это по комментариям Stephan T. Lavavej (псевдоним STL, мантейнер STL в микрософте), которому часто приходится на конференциях, в списках рассылки и в реддите оправдываться за плохую поддержку фич в C++.

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

        Источники тут:
        — ветка в рассылке Буста начиная отсюда: http://lists.boost.org/Archives/boost/2014/06/214317.php
        — Обсуждения в реддите:
        C++17 progress update!
        Visual C++: quality of error messages
        C++11/14/17 Features In VS 2015 RC

        Ещё это обсуждалось на каких-то конференциях (вероятно CPPCon 2014), но я не помню в каких именно докладах (видео есть на Youtube, но как там что-то найти?).

  4. misha_shar53
    /#8432245 / -3

    Странно что не рассмотрен язык MUMPS В нем еще 100 лет назад проблема решена самым удачным способом.
    Средств метапрограммирования в этом языке несколько:
    Команда Xecute аргументом является строка с командами MUMPS которые и выполняются
    Косвенный синтаксис который позволяет имена переменных и аргументы команды задавать в виде выражения.
    Команда ZInsert позволяет строку вставить в любое место программы, таким образом можно сформировать в runtime любую программу.
    Команда ZSave сохраняет такую программу на диске и транслирует ее.
    Все просто и элегантно. При этом никакого другого языка кроме MUMPS не надо. В других языках метапрограммирование в зачаточном состоянии. Хотя конечно препроцессор Си вещь удобная, но говорить что это метапрограммирование довольно смело.

    • NeoCode
      /#8432609

      Это называется eval. Тоже метапрограммирование, но другое, применимое в основном для интерпретируемых языков.

      • misha_shar53
        /#8432699

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

        • NeoCode
          /#8432765 / +2

          Когда в языке есть eval(), умеющий выполнять программы в виде строк, остальное неважно — хоть в дерево эти строки подвесить, хоть в список, хоть в циклический буфер:) Но это когда язык интерпретируемый. Если язык компилируемый, то для eval() программе нужно или тащить с собой компилятор (что совсем неразумно) или — что разумнее — иметь встроенный скриптинг на скриптовом языке и интерпретатор этого языка в виде библиотеки. Хотя языковая поддержка для таких вещей все равно желательна — например для прозрачного доступа к объектам компилируемого языка из скрипта.

          • misha_shar53
            /#8433083

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

  5. m1el
    /#8432261 / +4

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

  6. konsoletyper
    /#8432897

    Интересно, а annotation processors в Java можно считать метапрограммированием? А манипулирование байт-кодом на уровне class loader'ов или на уровне агентов?

  7. JIghtuse
    /#8433217 / +1

    Спасибо, интересная статья.

    Сегодня в обсуждении на reddit один товарищ рассказывал, что в Guile очень крутая система макросов. Не знаю, насколько можно доверять комментарию (комментируемая статья — довольно толстый вброс), но по слухам, guile довольно просто встраивается в софт.

    Ещё в Ruby поддерживается метапрограммирование (целая книга по теме), но в детали не вникал.

    Аналогично, сами шаблоны могут быть только классами (структурами) или функциями.
    И переменными.

  8. StreetStrider
    /#8437131

    Использование того же самого языка для программ и метапрограмм не обязательно
    Я с вами по большей части согласен, но и мысль иметь схожий синтаксис для языка и мета-языка тоже заманчива. В основе мета-генерации будут лежать всё равно все те же основы, что и при работе с «обычными» данными: определения, ветвления, циклы. А пройтись по мапе целых чисел или по мапе операторов языка разницы особой не имеет: суть цикл (за вычетом требования constexpr ко всем участникам последнего). Главное, чтобы вызов обычной функции и макроса в коде различались.

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