Использование и реализация инструментов метапрограммирования в компилируемых языках

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»»

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению
09.03.04 Программная инженерия

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Использование и реализация инструментов метапрограммирования в компилируемых языках

Бесчастнов Игорь Владимирович

Научный руководитель

Старший преподаватель,

Бычков И. С.

Нижний Новгород, 2020

Оглавление

Оглавление

Введение

Метапрограммирование с современных языках

Цель работы

Постановка задачи

Компилятор Grit

Выбор инструментов

Архитектура компилятора

Токенизация

Построение AST

Кодогенерация

Язык Grit

Результаты

Заключение

Список литературы

• 

Введение

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

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

Все эти цели могут быть достигнуты, в частности, с помощью метапрограммирования. Идеи метапрограммирования на практике, вероятно, впервые стали использоваться в языке Lisp, в виде макросов. Весьма популярный ранее, сейчас Lisp не представлен в индустрии сколь-либо значительно.



Метапрограммирование с современных языках

Одной из простейших (Бартлетт, 2005) и самых ранних реализаций метапрограммирования в массово распространенном языке программирования, использующемся до сих пор, был макропроцессор в Си. Эта возможность широко используется именно для метапрограммирования, например, в коде ядра Linux. Простой пример - макрос EXPORT_SYMBOL, который используется для отметки символов, в основном функций, которые должны быть экспортированы -- что делает его своеобразной функцией высшего порядка -- не совсем точное определение, но достаточно хорошее чтобы продемонстрировать что имеется ввиду под «простым метапрограммированием».

В современности, массовое метапрограммирование представлено во многих новых языках -- например, в Python есть декораторы и, самое главное, метаклассы (в Python так же есть возможность напрямую взаимодействовать с AST AST - abstract syntax tree, абстрактное синтаксическое дерево, но это сложно и не слишком практично). Эти инструменты делают возможным существование таких инструментов с высоким уровнем абстракции как SQLAlchemy SQLAlchemy - слой абстракции над базами данных для Python и популярная ORM и Django Django - один из наиболее популярных веб-фреймворков. Python, будучи интерпретируемым языком, позволяет производить множество операций над внутренней структурой объектов во время выполнения программы, что невозможно сделать в большинстве компилируемых языков, но в обмен на это жертвует производительностью.

Одним из наиболее широко используемых инструментов метапрограммирования в компилируемых языках являются шаблоны в C++. Это весьма мощный и очень сложный инструмент, который сложно обуздать, и тем не менее все равно не такой функциональный как, скажем, ранее упомянутые метаклассы. Например, разработчикам Qt необходимо было нечто подобное метаклассам, но для С++. Чтобы достигнуть подобного поведения, им пришлось использовать много того, что программисты называют «магией» - сложные макросы, собственный компилятор -- moc (meta-object compiler), который все равно требует после себя использования другого компилятора.

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

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

Одно из основных применений метапрограммирования это создание DSLs (Худак, 1998) -- domain specific languages. В этой нише, Haskell чувствует себя особенно хорошо, благодаря широким возможностям метапрограммирование на уровне типов.

Python так же хорош в этом -- возможно, спорное утверждение, но достаточно посмотреть на SQLAlchemy и ее способ писать запросы к базам чтоб увидеть пример отличного DSL, реализованного на Python.

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

Цель работы

В промышленной разработке прочно закрепились лишь некоторые отдельные инструменты метапрограммирования, простые и понятные даже начинающим разработчикам, либо зарекомендовавшие себя годами использования -- например, шаблоны из C++. Многие другие инструменты и целые языки, основной частью которых является поддержка метапрограммирования, не получают широкого распространения как раз из-за необычности подхода, некоторой трудности в изучении и предполагаемого ухудшения читаемости.

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

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



Постановка задачи

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

Естественно, невозможно и не нужно реализовывать компилятор для полноценного языка программирования для достижения обозначенной ранее цели. Нет так же и прямой необходимости реализовывать продвинутые парадигмы разработки - объектно-ориентированную или функциональную. Достаточно реализовать базовый набор инструментов процедурного программирования, чтобы иметь возможность писать «реалистичные» программы, и при этом не погрязнуть в разработке нового полнофункционального языка, и уже поверх этой основы создать функционал для метапрограммирования.

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

Кроме того, такой исследовательский язык обязательно должен быть статически типизирован - это, во-первых, характерно для компилируемых языков, а во-вторых сделает реализацию инструментов метапрограммирования более показательной с точки зрения отдаления от методов, часто используемых в интерпретируемых языках (например, в Python многие высокоуровневые функции полагаются на изменения типа или сигнатуры объекта во время выполнения программы, что, очевидно, невозможно если все типы были однозначно зафиксированы).

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

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

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

· Базовые типы -- int и float

· Арифметические операции и операции сравнения

· if, цикл for

Компилятор Grit

Выбор инструментов

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

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

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

Для данного проекта необходим устоявшийся бэкенд, который не будет создавать проблем из-за багов или недоработок, и при этом не слишком специфичный, а также кроссплатформенный. Транспиляция Транспиляция - процесс перевода кода на одном языке программирования в код на другом в другой язык программирования не дает достаточной гибкости, а продукты с закрытым исходным кодом часто либо платные, либо могут вызвать проблемы с лицензией - кроме того, в сфере компиляторов разработки с открытым исходным кодом часто более высококачественные, т.к. их использует больше разработчиков - мало какой компании, даже самой большой, захочется разрабатывать под новый проект новый компиляторный бэкенд - например, Intel массово использует в своих разработках LLVM.

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

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

Во-первых, необходимо чтобы данный язык имел качественную библиотеку для интеграции с API кодогенерации LLVM. Сами разработчики проекта LLVM официально поддерживают библиотеки для OCaml и C++.

Во-вторых, язык должен быть удобен для написания обработчиков текстовых данных - лексера, парсера и прочих частей. С++ трудно назвать удобным языком для этой цели из-за довольно низкого уровня абстракции - например, даже работа с юникодом не так очевидна, как хотелось бы - однако он с лихвой компенсирует это производительностью и нулевыми накладными расходами во время выполнения. Для целей данной работы, однако, производительность не стоит на первом месте, так что C++ не подходит. OCaml - отличный выбор для такого рода задач, однако не идеальный - на мой взгляд, есть язык, парадигма которого значительно лучше подходит для этого.

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

Библиотека Parsec для Haskell является первоклассным инструментом для написания парсеров. Она основана на принципе комбинаторов парсеров. Она позволяет составлять сложный парсер, как например для языка программирования, из простых в написании небольших частей. Сама по себе эта идея не нова, однако каждый парсер отлично ложится в парадигму Haskell как специфичный вид монады, а операции комбинации парсеров полностью совпадают с монадными комбинаторами.

Интеграция LLVM с Haskell также не представляет никаких проблем - для этого существует первоклассная библиотека llvm-hs, используемая во множестве проектов.

Учитывая все выше сказанное, Haskell подходит идеально для целей этой работы. Таким образом, для разработки компилятора будет использоваться LLVM как бэкенд и Haskell для написания фронтенда, с Parsec для помощи в написании парсера.

Архитектура компилятора

Ранее было условлено, что компилятор будет обрабатывать один входной файл с исходным кодом. Это означает, что входными данным программы будет текст этого файла в виде строки. На выход проще всего, для отладки и проверки результата, отдавать код LLVM IR, который будет уже компилироваться в исполняемый файл - в дальнейшем научить наш компилятор производить генерацию машинных инструкций с помощью LLVM будет не трудно, а пока можно остановиться на этом.

Процесс обработки входных данный следующий:

1. Токенизация Токенизация - процесс разбиение входного текста на распознанные смысловые группы (разбиение на лексемы берет на себя Parsec)

2. Семантический анализ, предобработка AST

3. Кодогенерация IR

Таким образом, мы уже можем определить высокоуровневую структуру программы:

parseCode :: String -> Either ParserError [Expr]

processAST :: [Expr] -> [Expr]

buildIR :: [Expr] -> Module

-- Исходный код > parseCode > processAST > buildIR > код LLVM IR

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

Токенизация

Этот этап заключается, в основном, в создании описания синтаксиса в формате, понятном Parsec, и затем написании комбинаторов парсеров для всех синтаксических конструкций. Не будем вдаваться в детали реализации и остановимся только на внутреннем представлении синтаксиса.

Высокоуровневая структура языка очень простая - это массив выражений. В компиляторе имеется тип Expr, экземплярами которого являются все выражения в языке - объявления функций, условные выражения, объявления переменных и т.д.

Объявлен этот тип следующим образом:

data Expr Все data-типы, связанные с Expr, имеют в своем объявлении также deriving (Ord, Eq, Show). В тексте работы это опущено для упрощения читаемости кода

= Block CodeBlock

| Int Integer

| Float Double

| Var Name

| Def ExprType Name

| Call String [Expr]

| DecoratorDef ExprType Name CodeBlock

| DecoratorTarget

| Function [Modifier] ExprType Name [Expr] (Maybe Name) CodeBlock

| BinaryOp String Expr Expr

| UnaryOp String Expr

| If Expr CodeBlock CodeBlock

Можно заметить, что Expr ссылается на некоторые другие типы. Часть из них - это просто псевдонимы для удобства:

type Name = String

type CodeBlock = [Expr]

CodeBlock используется там, где мы ожидаем код программы, а [Expr] - там, где мы ожидаем серию выражений - аргументы функции, условия и т.д. Различие исключительно синтаксическое, для удобства чтения сигнатур - для компилятора Haskell разницы между CodeBlock и [Expr] по большому счету нет.

Другие - это дополнительная информация, «метаданные» о выражении:

data ExprType = IntType | FloatType

data Modifier

= Decorator Name

Тип Modifier имеет только один конструктор, т.к. в языке будет реализован только один «модификатор» кода - декораторы. Однако, вместо того чтобы оставить в определении функции только декораторы, разумно завести такой тип данных для перечисления применяемых модификаторов, чтобы применяемые в дальнейшем техники компиляции были обобщёнными и применимы не только для реализации декораторов.

Без углубления в описание языка, которой будет проведено дальше, пока просто скажем что язык подобен Си, но без многих конструкций, если коротко - доступны только int и float, нет структур и указателей, весь код - в одном файле.



Построение AST

Полученный после токенизации набор выражений уже можно, в некотором смысле, считать синтаксическим деревом - мы знаем, что точка входа это main, и имеем определения всех символов в программе. C этого я и начал разработку первой версии - не храня и не проверяя типы, кроме как для объявлений, без метаинформации, полностью доверяя программисту, написавшему код - обходить массив и генерировать LLVM IR. Этого было достаточно, пока дело не дошло до сообщений об ошибках, проверки типов, и, в первую очередь, декораторов. Первые две вещи не слишком сложны в реализации и не представляют большого интереса в контексте этой работы, а о декораторах стоит сказать подробнее.

Как должен выглядеть декоратор в не слишком высокоуровневом, компилируемом, статически типизированном языке? Это в любом случае будет некоторая конструкция, внутри себя имеющая дополнительный код и способ обратится к декорируемой функции. Я остановился на следующем синтаксисе:

@int decOne = {

return @target - 1;

};

Это простейший декоратор для функций возвращающих int, вычитающий из результата единицу и возвращающий получившееся число. @target - место, где будет вызвана исходная функция, с переданными ей аргументами, и возвращен результат её работы.

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

Гораздо более продуктивный и расширяемый способ -- это модифицировать тело декорируемой функции: завести переменную типа, совпадающего с возвращаемым, заменить return на запись в эту переменную, и в конце вставить код декоратора, заменив @target на обращение к новой переменной и новый return. Так мы избежим генерации новых объявлений и не создадим дополнительных вызовов. Однако это не позволит писать декораторы, которые совсем предотвращают вызов декорируемой функции:

@int decorator {

if (condition) {

return @target;

}

else {

return 0;

}

}

Для преодоления этого ограничения, надо поменять в описанном выше алгоритме функцию и декоратор местами - код функции надо вставить в тело декоратора в блоке с @target, заменить сам @target на ее результат, и получившееся синтаксическое дерево вставить на место исходного тела функции. Таким образом, поддержка применения нескольких декораторов к одной функции получится автоматически - этот процесс просто необходимо повторять снизу вверх со всеми декораторами.Манипулирование объявлениями «изнутри» программы отдаляет язык Grit от низкоуровневого Си, а замена каких-либо значений на целые вычисляемые синтаксические деревья делает его, по меньшей мере на уровне AST, похожим на фразированный (expression-oriented). Это очень интересная и, как мне кажется, улучшающая читаемость парадигма, так что разумно выставить этот функционал наружу и предоставить программисту - и сделать язык действительно фразированным. Таким образом, исчезает ключевое слово return и результатом любой конструкции, состоящей из более чем одного выражения, включая функции, становится значение последнего выполненного выражения. В качестве синтаксического сахара для функций, однако я решил добавить возможность указать название переменной (которая будет создана автоматически), значение которой будет возвращено после завершения выполнения функции - по сути, просто замена выражению «переменная;» в конце функции.

Учитывая все выше сказанное, пример функции, умножающей числа на 2, и примененного к ней декоратора, вычитающего из любого int единицу (простые примеры для демонстрации синтаксиса, более сложные будут приведены в другом разделе работы), будет выглядеть следующим образом:

@int decOne = {

@target - 1;

};

@decOne

int doubleI(int num) = num * 2;

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

ModificationsData { decorators = filter (\case DecoratorDef{} -> True; _ -> False) ast }

Где ast - наше синтаксическое дерево, а ModificationsData - структура данных с информацией о модификаторах.

После этого, мы идем по синтаксическому дереву, применяя к каждому элементу функции-модификаторы по очереди, как конвейер, и заменяя исходное выражение результатом (определение функции walkAST опускаю, функция use - это «map наоборот» - к одному значению по очереди применяется массив функций:

applyModifications :: ModificationsData -> [Expr] -> [Expr]

applyModifications modsData = walkAST (

use [ applyModificationsFunc modsData

-- в языке есть только одна модификация - применение декораторов

]

)

applyModificationsFunc :: ModificationsData -> Expr -> Expr

Тело функции applyModificationsFunc опускаю - она реализует алгоритм применения декораторов, описанный выше.

После подготовки AST, также разумно провести его «очистку» - удалить определения декораторов, поскольку для них не надо генерировать IR - они уже применены к функциям - и отбросить лишнюю метаинформацию.

Кодогенерация

После всех шагов, описанных выше, мы в итоге получаем синтаксическое дерево типа [Expr], где все верхнеуровневые выражения - это определения функций либо константы. Генерация LLVM IR для констант тривиальна, а вот для функций - гораздо сложнее. Рассмотрим ее подробнее.

Генерация IR для функций делится на два этапа: обработка самого определения функции - название, тип и аргументы - и генерация IR для тела функции. Построить IR для определения функции довольно просто, т.к. определения функций в Grit похожи на таковые в Си, которые в свою очередь почти совпадают с объявлениями функций в LLVM.

Таким образом, основная и самая сложная часть кодогенерации - это построение тел функций. Они также имеют тип [Expr], но, в отличии от верхнеуровневой структуры, содержат выражения самого разного вида - операции, объявления переменных, if-ы и так далее. Попробуем найти какой-либо инвариант для всех этих структур, чтобы упростить процесс генерации IR для каждого типа выражений.

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

Для какого вида структур данных необходимо строить IR? У нас в языке есть бинарные операции - определение конструктора для них состоит из двух выражений (левого и правого) и собственно операции, для унарных соответственно из одного выражения и операнда. Условные конструкции состоят из выражения-условия (которое может внутри себя содержать любые другие или даже быть вычисляемым блоком) и двух веток - блоков кода. Можно перечислять и далее, но основной паттерн уже виден - каждое выражение содержит либо сразу операнд (константу или объявление чего-либо), либо другие выражения или блоки выражений и операции над ними. Таким образом, генерировать IR для каждого выражения можно рекурсивно обходя его составные части.

Для этого необходимо две функции, которые будут обрабатывать входящие выражения, и вызывать друг друга, в зависимости от того, что они встретят внутри этих выражений - одна должна генерировать код LLVM IR для массива выражений, возвращая операнд, полученный из последнего выражения в наборе, как свой результат. Другая должна генерировать IR для отдельного «конкретного» выражения и возвращать полученный операнд как результат. Вот их сигнатуры:

buildCodeBlock :: (MonadFix m, MonadIRBuilder m) => [Expr] -> m Operand

emit :: (MonadFix m, MonadIRBuilder m) => Expr -> m Operand

MonadIRBuilder - наша интеграция с LLVM, а MonadFix необходим для рекурсивной работы с монадами.

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

buildCodeBlock exprBlock = do

ops <- mapM emit exprBlock

return (last ops)

Она, как и планировалось, применяет emit ко всем выражениям, и возвращает результат последнего.

Функция же emit работает через сопоставление полученного выражения с шаблоном, и выбора правильной реализации для генерирования LLVM IR. Например, если в коде программы встретится бинарная операция, то для этого выражения вызовется такая реализация:

emit (BinaryOp operator opr1 opr2) =

do

operand1 <- emit opr1

operand2 <- emit opr2

operation operand1 operand2

where

operation = -- алгоритм выбора LLVM оператора длинный, но простой и не представляет интереса

Если одним из операндов будет блок кода, то вызовется просто:

emit (Block codeBlock) = buildCodeBlock codeBlock

И так далее.

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



Язык Grit

В этом разделе проведем обзор получившегося языка.

Grit - статически сильно типизированный язык, фразированный (expression-oriented), с некоторыми возможностями для метапрограммирования. Встроенные типы: int (целочисленный) и float (дробное число. Точкой входа в программу является функция main.

Любое выражение, за исключением особо указанных исключений и объявлений функций, возвращает значение. Арифметические операции и операции сравнения возвращают свои результаты, операция присваивания возвращают присваиваемое значение (позволяя писать конструкции вида a = b = c = 1).

Конструкция if возвращает значение последнего выражения в выполняемой ветке. Пример:

if (1 > 2) {

// any code

}

else {

// any code

1 + 2;

};

Вернет 3 - результат вычисления 1 + 2

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

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

int doubleEven (int number) =

if (number % 2 == 0) {

number * 2;

}

else {

number;

};

Данная функция, как видно, эквивалентна выполнению одного выражения - if.

Поскольку язык expression-oriented, возможны такие выражения и внутри блоков кода, позволяя формировать более строго структурированную логику:

exitCode = if (someCondition) {

... // code evaluating something

} else { 1; }; // fail code

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

int x = {

// algorithm, that computes some value

1 + 2; // for example - variable `x' will be set to 3

};

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

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

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

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

В объявлении декоратора необходимо указать тип функций, которые он может декорировать (со знаком @ - отметка, что это декоратор, а не начало объявления функции) и его название. У декоратора нет аргументов - он только модифицирует тело декорируемой функции. Тело самого декоратора - это просто блок кода, работающий по тем же правилам, что и тело функции (за исключением того, что декораторы не поддерживают returns в объявлении). Внутри тела декоратора можно использовать специальную отметку @target - в этом месте вызовется декорируемая функция, с переданными ей аргументами, и вместо метки подставится результат её работы.

Пример объявления декоратора, заменяющего все отрицательные результаты на 0, а для остальных возвращающего исходное значение:

@int check = {

int val = @target;

if (val < 0) {

0;

}

else {

val;

};

};

Применение его к функции такое же как в Python:

@check

int someFunction(...) = {

…

};

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

На этом обзор функционала языка можно завершить, так как все самые интересные и, главное, релевантные в контексте цели этой работы моменты были рассмотрены.



Результаты

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

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

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

Метапрограммирование, по определению, изменяет код так, будто это данные. На уровне компилятора, код программы прежде всего представлен в виде AST. Гибким и легко расширяемым способом реализации продвинутого функционала языка является создание «мини-интерпретатора», работающего во время компиляции. Программист описывает изменения, которые он хотел бы произвести, в виде кода на самом языке (например, тело декоратора), а затем с помощью специального синтаксиса (например, символ @ для применения декоратора) указывает где он хотел бы их произвести - и компилятор модифицирует AST соответствующим образом.

Как было показано, данная техника не сложна в реализации, при должной хитрости не слишком ухудшает производительность, и может быть сведена к построению таблицы «синтаксическая особенность - функция, сопоставляющая выражения с правильным шаблоном, интерпретирующая затребованные изменения, и применяющая их к AST».



Заключение

Исходной целью работы было выяснение возможности реализации «динамических» инструментов метапрограммирования в компилируемых языках. Думаю, можно смело сказать, что по крайней мере на этот вопрос теперь можно ответить однозначно - написание такого компилятора возможно.

Другой стороной вопроса является изучение эффекта внедрения такого функционала на размер производимых исполняемых файлов и производительность программы. Как было показано, для реализации инструментов метапрограммирования часто необходимо модифицировать AST - этот процесс, обычно, не влияет на скорость выполнения самой программы, но может существенно замедлить компиляцию и увеличить размер итогового исполняемого файла. На скорость же может повлиять внедрение более продвинутых инструментов, которые полагаются на высокоуровневый функционал - функции как объекты первого класса, функции верхнего уровня и так далее - эти языковые особенности сами по себе довольно дороги в реализации, а в купе с метапрограммными инструментами, основанными на них, могут сильно ударить по производительности - за счет роста количества указателей и прыжков.

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

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

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



Список литературы

Компиляторы: принципы, технологии и инструментарий -- 2 изд. [Книга] / авт. Ахо Альфред В. [и др.]. - 2008 : Вильямс.

Введение В Метапрограммирование [В Интернете] / авт. Бартлетт Д. // Ibm.com. - 2005 г.. - https://www.ibm.com/developerworks/ru/library/l-metaprog1/index.html.

Lambda Lifting: Transforming Programs to Recursive Equations [Книга] / авт. Джонсон Томас. - [б.м.] : ACM Press, 1985.

Modular Domain Speci?c Languages and Tools [Книга] / авт. Худак Пол. - New Haven : IEEE Computer Society Press, Department of Computer Science, Yale University, 1998.

The Architecture of Open Source Applications [Книга] / авт. Браун Эми и Уилсон Грег. - Dallas, TX : lulu, 2012.

Размещено на Allbest.ru

...