Русский
Русский
English
Статистика
Реклама

Из песочницы Как скомпилировать декоратор C, Python и собственная реализация. Часть 2

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


Я же расскажу про то, как решил попытаться реализовать декораторы в компилируемом языке программирования, для чего в итоге написал написал собственный небольшой компилятор на Haskell на основе LLVM.



Оглавление


  1. Как работают декораторы в Python
  2. Haskell и LLVM собственный компилятор
  3. Так как же скомпилировать декоратор?


Как работают декораторы в Python


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


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


Как работают декораторы в Python, в общем-то интуитивно понятно любому человеку, знакомому с этим языком:


Функции decorator, принимающей другую функцию как свой аргумент func, в момент применения декоратора в качестве данного аргумента передается декорируемая функция old. Результатом является новая функция new и с этого момента она привязывается к имени old

def decorator(func):    def new(*args, **kwargs):        print('Hey!')        return func(*args, **kwargs)    return new@decoratordef old():    pass# old() выведет "Hey!" - к имени old теперь приязан вызов new

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


Про интерпретатор CPython

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


Благодаря этому, интерпретатору не надо знать о типах объектов, соответстующих символам в коде, вплоть до момент выполнения операций над ними когда очередь дойдет до выполнения какой-либо "конкретной" инструкции тогда он и проверит тип. Сильно упрощая можно объяснить это так: BINARY_SUBSTRACT (вычитание) упадет с TypeError, если дальше на стэке лежат число 1 и строка 'a'. В тоже время, выполнение STORE_FAST для одного и того же имени (запись в одну и ту же переменную), когда один раз на стэке лежит число, а в другой раз строка, не приведет к TypeError, т.к. в инструкцию по выполнению команды STORE_FAST не входит проверка типа только связывание имени с новым объектом.


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


Проблема 1. Декораторы это просто функции


Декораторы применяются в рантайме. В примере выше значение decorator может меняться вплоть до самого его использования, например вот так:


name = input('Введите имя декоратора')def first(func):    ...  # тело декоратораdef second (func):    ...  # тело декоратораif name == 'first':    decorator = firstelif name == 'second':    decorator = secondelse:    decorator = lambda f: f   # оставляем функцию в покое@decorator def old():    pass

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


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


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


Проблема 2. Python мало интересуют типы


def decorator(func):    def two_args(x, y):        ...    return two_args@decoratordef one_arg(x):    ...

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


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


Это также подводит нас к обратной проблеме какой тип должен быть у аргумента декоратора в наших примерах это аргумент с названием func? Чаще всего этот аргумент, представляющий декорируемую функцию, вызвается внутри замыкания значит нам хотелось бы знать хотя бы тип возвращаемого значения, не говоря уже об аргументах. Если мы его строго зафиксируем с помощью объявления func как функции типа A, мы ограничили область применения декоратора функциями типа A. Если же мы и это объявляем как void* func, и предлагаем программисту самому везде приводить нужные типы, то проще писать на питоне.


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




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


  • Тип декорируемой функции какие аргументы принимает декоратор?
  • Тип итоговой функции какая сигнатура должна быть у результата работы декоратора?
  • Применение на этапе компиляции создает дополнительные ограничения, применение в рантайме уменьшает гарантии, которые компилятор может дать относительно результата (либо требует продвинутой системы типов)

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

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


Про этот компилятор я и расскажу далее.



Haskell и LLVM собственный компилятор


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


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


Grit expression-oriented (фразированный) язык


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


int main() = {    int i = 0;    i = i + if(someFunction() > 0) {        1;    }    else {        0;    };};

В данном примере, i будет равен 1, если функция someFunction вернет положительное значение, и нулю, если вернется 0 или меньше.


Нет ключевого слова return


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


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


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


int simple(int x) = {    /*       Данная фукция вернет результат сложения      своего аргумента x и переменной y    */    int y = someOtherFunction();    x + y;};/*  Для функций, состоящих из одного выражения, фигурные скобки можно опустить.  Эта функция вернет свой аргумент, увеличенный на единицу*/int incr(int x) = x + 1;int main() returns statusCode {    /*      В объявлении функции с помощью ключевого слова returns      можно указать название переменной, значение которой      будет возвращено после окончания работы функции.      Это переменная будет "объявлена" автоматически      с таким же типом, как у возвращаемого значения функции    */    int statusCode = 0;    int result = someFunction();    if (someFunction < 0) {        statusCode = 1;    };};

Auto компилятор Grit обладает базовой возможностью выведения типов


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


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


auto half (int x) = x / 2;   // для функции incr будет выведен тип float



Фразированность (expression-oriented), отсутствие return из произвольного места (тело функции тоже выражение) и базовое выведение типов это самые интересные для нас особенности Grit. Я выделил их потому, что они напрямую используются в реализации декораторов в этом языке.

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


А для нас теперь пришло время наконец ответить на главный вопрос этой серии статей как скомпилировать декоратор?



Так как же скомпилировать декоратор?


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


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


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


Посмотрим на конкретный пример и разберемся, как данный способ объявления декораторов решает указнные в первой части статьи проблемы:


@auto flatten = {    auto result = @target;    if (result < 0) {        0;    }    else {         result;    };};

Это декоратор, который вызовет исходную функцию, и вернет 0, если ее результат меньше 0, иначе он вернет результат без изменений.


@auto flatten объявление декоратора с именем flatten и типом @auto то есть тип будет выведен в зависимости от функции, к которой он применен (@ указатель но то, что это объявление декоратора, а не функции).


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


Вы наверняка уже обратили внимание на необычную метку в теле декоратора @target. Это указание компилятору на то, что в это место надо вставить целиком тело декорируемой функции. Аргументы функции будут скопированы как аргументы для данного инстанса декоратора (что на уровне синтаксического дерева превращает его в новую функцию), а блок кода, являющийся телом исходной функции, вернет свой результат в место вызова, поскольку язык фразированный (этот механизм был описан ранее).
Таким образом, подобное изменение AST эквивалентно вызову исходной функции на месте @target, с правильными аргументами. После этого, исходную функцию можно просто заменить получившейся новой функцией, и все декоратор применен. Если же декораторов у функции несколько, то этот процесс можно повторять несколько раз.


Варианты использования декораторов

Декораторы в виде, реализованном в Grit, позволяют делать множество различных вещей большинство из них те же, что и в Python.


Например, можно ожидать захвата ресурса:


@auto lockFunction = {    mutex.lock();    @target};

Или вызывать функцию, только если установлен какой-либо флаг:


@auto optional = if (checkCondition()) {    @target;}else {    someDefaultValue;};

И так далее


Рассмотрим этот механизм на примере сгенерированного компилятором Grit синтаксического дерева для простой программы с декораторами:


@auto flatten = {    auto result = @target;    if (result < 0) {        0;    }    else {         result;    };};@flattenint incr(int x) = x+1;

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


Так выглядит "сырое" внутреннее представление, до какой-либо обработки вообще:


Decorator "flatten" auto {  BinaryOp = (Def auto "result") (DecoratorTarget)  If (BinaryOp < (Var "result") (Int 0)) {    Int 0  }  else {    Var "result"  }}Function "incr" int ; args [Def int "x"] ; modifiers [Decorator "flatten"] ; returns Nothing {  BinaryOp + (Var "x") (Int 1)}

Не вдаваясь в конкретные обозначения, сразу видно две вещи определение декоратора это самостоятельная конструкция с типом Decorator, и функция incr на данном этапе существует в своем исходном виде, и хранит информацию о том что к ней применен модификатор Decorator "flatten". В теле декоратора же мы видим метку DecoratorTarget сюда будет вставленно тело функции incr.


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


Посмотрим на аннотированное, полностью обработанное и готовое к кодогенерации предсавление той же программы:


Function (int -> int) incr ["x"] {  BinaryOp i= (Def int "result") (    Block int {      BinaryOp i+ (Var int "x") (int 1)    }  )  If int (BinaryOp b< (Var int "result") (int 0)) {    int 0  }  else {    Var int "result"  }}

Здесь мы можем заметить несколько важных вещей:


  • Определение декоратора было удалено после его применения на этапе обработки AST, он больше не нужен.
  • Тело функции incr изменилось теперь оно такое же, каким было тело декоратора flatten, но на месте DecoratorTarget теперь Block {...} выражение вида "блок кода", совпадающее с исходным телом функции. Внутри этого выражения есть обращения к аргументам функции, и оно возвращает то же значение, которое вернула бы исходная функция это значение присваивается новой переменной int "result", с которой декоратор и работает дальше. BinaryOp i= это операция присваивания int-а, но в исходном коде тип result был указан как auto значит тип возвращаемого значения и переменных в теле функции, работающих с ним, был выведен правильно.

Таким образом, в процессе разработки этого компилятора, удалось вывести общий алгоритм применения декораторов для компилируемого, статически типизированного языка. Он не обладает всеми возможностями декораторов в Python, но приближается к ним настолько, насколько это возможно в таком языке, как Grit.


Разумеется, это не окончательная и не идеальная версия например, таким декораторам можно было бы добавить собственные, декораторные аргументы:


@auto lockF(mutex M) {    M.lock();    @target;};@lockF(мьютексКоторыйФункцияДолжнаЗахватить)int someFunction(...)

Это вполне сработало бы при текущем подходе самый простой вариант это при применении декоратора убрать аргумент mutex M, и в теле конкретного инстанса декоратора заменить обращения к этому аргументу обращениями к "мьютексКоторыйФункцияДолжнаЗахватить", который должен существовать в области видимости декорируемой функции исходя из объявления (кстати, такой способ создавать декораторы с аргументами выглядит гораздо привлекательнее того, как они реализованы в Python замыкание внутри замыкания внутри функции).


Кроме того, я экспереминтировал с меткой @args, дающей внутри декоратора доступ к аргументам целевой функции, и так же разварачивающейся в "обычный код" на этапе обработки синтаксического дерева. Например, @args.length количество аргументов, @args.1 ссылка на первый аргумент и так далее. Что-то из этого работает, что-то пока не совсем но принципиально сделать это возможно.


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


Код получившегося компилятора можно найти здесь, собирается он с помощью stack


P.S. Это был очень интересный и необычный для меня опыт надеюсь, что и вы смогли вынести для себя что-нибудь полезное из этого рассказа. Если нужна отдельная статья про написание компилятора на Haskell на основе LLVM пишите в комментарии.
На любые вопросы постараюсь ответить в комментариях, или в телеграмме @nu11_pointer_exception

Источник: habr.com
К списку статей
Опубликовано: 29.06.2020 22:07:32
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Haskell

Python

Компиляторы

Llvm

Closure

Syntax sugar

Сделай сам

Функциональное программирование

Abstract syntax tree

Категории

Последние комментарии

© 2006-2020, personeltest.ru