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


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

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

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

      зы. а вообще забавно читать про метапрограммирование и не обнаружить слова lisp.
      • 0
        Меня интересуют в первую очередь си-подобные языки. Ну и конечно всего не охватить в одной статье… хотя конечно Rust можно было упомянуть, я просто не успел еще разобраться с его макросами. По Rust (как и по Nim) на данный момент крайне мало документации, надеюсь в ближайшее время что-то поменяется в лучшую сторону в связи с выходом 1.0. Что же касается lisp, то это язык с сильно отличающимся от «мейнстрима» синтаксисом, этот фактор усложняет понимание.
        • 0
          Голый AST усложняет понимание?
          • +3
            Непривычный синтаксис усложняет понимание. Это примерно то же самое как в статьях, в которых пытаются объяснить что же такое монады, используются примеры на Haskell. Возможно, внутри Haskell это даже достаточно простая и естественная концепция, но когда смотришь на код, мозгу с непривычки не за что зацепиться:)
            • 0
              Да, похоже, система программировения — прежде всего, задачи которые в ней решаются, вне их языки не имеют очевидной семантики.
          • 0
            По Rust есть целая большая официальная книга, на главу которой про макросы выше привели ссылку. И Rust, кстати, всё-таки по синтаксису гораздо ближе к C, чем Nim или Nemerle.
        • +5
          >> сплайсинга — фичи, известной всем, кто пишет на скриптовых языках, когда в строку с помощью специального синтаксиса можно вставлять имена различных переменных

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

              А где можно с этим ознакомиться подробнее? (интересно, на чем же он основан тогда?...)
              • +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, но как там что-то найти?).
          • –3
            Странно что не рассмотрен язык MUMPS В нем еще 100 лет назад проблема решена самым удачным способом.
            Средств метапрограммирования в этом языке несколько:
            Команда Xecute аргументом является строка с командами MUMPS которые и выполняются
            Косвенный синтаксис который позволяет имена переменных и аргументы команды задавать в виде выражения.
            Команда ZInsert позволяет строку вставить в любое место программы, таким образом можно сформировать в runtime любую программу.
            Команда ZSave сохраняет такую программу на диске и транслирует ее.
            Все просто и элегантно. При этом никакого другого языка кроме MUMPS не надо. В других языках метапрограммирование в зачаточном состоянии. Хотя конечно препроцессор Си вещь удобная, но говорить что это метапрограммирование довольно смело.
            • 0
              Это называется eval. Тоже метапрограммирование, но другое, применимое в основном для интерпретируемых языков.
              • 0
                Почти так. Но в MUMPS таких возможностей больше. Можно команды записать в дерево, а программой просто обходить такое дерево и выполнять команды хранящиеся в вершинах.
                Но я встречал упоминание о том что в Pascal можно в runtime оттранслировать команды и их выполнить.
                • +2
                  Когда в языке есть eval(), умеющий выполнять программы в виде строк, остальное неважно — хоть в дерево эти строки подвесить, хоть в список, хоть в циклический буфер:) Но это когда язык интерпретируемый. Если язык компилируемый, то для eval() программе нужно или тащить с собой компилятор (что совсем неразумно) или — что разумнее — иметь встроенный скриптинг на скриптовом языке и интерпретатор этого языка в виде библиотеки. Хотя языковая поддержка для таких вещей все равно желательна — например для прозрачного доступа к объектам компилируемого языка из скрипта.
                  • 0
                    Безусловно надо либо транслировать текст исходного языка либо интерпретировать. Насчет неразумности я с вами не согласен. Если приложение существенно использует метапрограммирование, то это необходимо и очень разумно. Но для этого возможно нет необходимости иметь мощный оптимизирующий компилятор.
            • +4
              Метапрограммирование: какое оно есть и каким должно быть: LISP.
              • 0
                В каком из? Так-то макросы CL и Racket отличаются друг от друга.
                • 0
                  Если честно, я не вижу фундаментальной разницы между ними. Да, они отличаются, но принцип — тот же.
                  При желании можно писать макросы как в CL:
                  gist.github.com/m1el/084477b3db4c5f6bd202
              • 0
                Интересно, а annotation processors в Java можно считать метапрограммированием? А манипулирование байт-кодом на уровне class loader'ов или на уровне агентов?
                • +1
                  Спасибо, интересная статья.

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

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

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

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

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