Создаем свой язык программирования с блэкджеком и компилятором
В этом пособии с соответствующими примерами кода рассказываем о том, как написать при помощи Python свой язык программирования и компилятор к нему.
Введение
Изучение компиляторов и устройства языков программирования по видеоурокам и руководствам – дело для новичков тяжелое. В этих материалах нередко отсутствуют важные составляющие. Цель публикации – помочь людям, ищущим способ создать свой язык программирования и компилятор. Пример игрушечный, но позволит понять, с чего начать и в каком направлении двигаться.
Системные требования
Если вы незнакомы с нижеприведенными понятиями, не беспокойтесь – мы проясним необходимость этих компонентов далее, по ходу создания компилятора. В качестве лексера и парсера используется PLY. В роли низкоуровневого языка-посредника для генерации оптимизированного кода выступает LLVMlite.
Таким образом, к системе предъявляются следующие требования:
Свой язык программирования: с чего начать?
Начнем с того, что назовем свой язык программирования. В качестве примера он будет называться TOY. Пусть пример программы на языке TOY выглядит следующим образом:
Любой язык программирования включает множество составляющих его компонентов. Чтобы не застрять в мелочах, возьмем в качестве микропрограммы вызов одной функции нашего языка:
Как для этой однострочной программы формально описать грамматику языка? Чтобы это сделать, необходимо использовать расширенную Бэкус – Наурову форму (РБНФ) (англ. Extended Backus–Naur Form ( EBNF )). Это формальная система определения синтаксиса языка. Воплощается она при помощи метаязыка, определяющего в одном документе всевозможные грамматические конструкции. Чтобы в деталях разобраться с тем, как работает РБНФ, прочтите эту публикацию.
Создаем РБНФ (EBNF)
Создадим РБНФ, которая опишет минимальный функционал нашей микропрограммы. Начнем с операции суммирования:
Соответствующая РБНФ будет выглядеть следующим образом:
Дополним язык операцией вычитания:
В соответствующем РБНФ изменится первая строка:
Наконец, опишем функцию print:
В этом случае в РБНФ появится новая строка, описывающая работу с выражениями:
В таком ключе развивается описание грамматики языка. Как же научить компьютер транслироваться эту грамматику в бинарный исполняемый код? Для этого нужен компилятор.
Компилятор
Компилятор – это программа, переводящая текст ЯП на машинный или другие языки. Программы на TOY в этом руководстве будут компилироваться в промежуточное представление LLVM IR (IR – сокращение от Intermediate Representation) и затем в машинный язык.
Использование LLVM позволяет оптимизировать процесс компиляции без изучения самого процесса оптимизации. У LLVM действительно хорошая библиотека для работы с компиляторами.
Наш компилятор можно разделить на три составляющие:
Для лексического анализатора и парсера мы будем использовать RPLY, очень близкий к PLY. Это библиотека Python с теми же лексическими и парсинговыми инструментами, но с более качественным API. Для генератора кода будем использовать LLVMLite – библиотеку Python для связывания компонентов LLVM.
1. Лексический анализатор
Итак, первый компонент компилятора – лексический анализатор. Роль этого компонента заключается в том, чтобы разделять текст программы на токены.
Воспользуемся последней структурой из примера для РБНФ и найдем токены. Рассмотрим команду:
Наш лексический анализатор должен разделить эту строку на следующий список токенов:
Напишем код компилятора. Для начала создадим файл lexer.py, в программном коде которого будут определяться токены. Для создания лексического анализатора воспользуемся классом LexerGenerator библиотеки RPLY.
Создадим основной файл программы main.py. В этом файле мы впоследствии объединим функционал трех компонентов компилятора. Для начала импортируем созданный нами класс Lexer и определим токены для нашей однострочной программы:
При запуске main.py мы увидим на выходе вышеописанные токены. Вы можете изменить названия своих токенов, но для простоты согласования с функциями парсера их лучше оставить как есть.
2. Синтаксический анализатор
Второй компонент компилятора – синтаксический анализатор (он же парсер). Его роль – синтаксический анализ текста программы. Данный компонент принимает список токенов на входе и создает на выходе абстрактное синтаксическое дерево (АСД). Эта концепция более трудна, чем идея списка токенов, поэтому мы настоятельно рекомендуем хотя бы по приведенным выше ссылкам изучить принципы работы парсеров и синтаксических деревьев.
Чтобы воплотить в жизнь синтаксический анализатор, будем использовать структуру, созданную на этапе РБНФ. К счастью, анализатор RPLY использует формат, схожий с РБНФ. Самое сложное – присоединить синтаксический анализатор к АСД, но когда вы поймете идею, это действие станет действительно механическим.
Во-первых, создадим файл ast.py. Он будет содержать все классы, которые могут быть вызваны парсером, и создавать АСД.
Во-вторых, нам необходимо создать сам анализатор. Для этого в новом файле parser.py аналогично лексеру используем класс ParserGenerator из библиотеки RPLY:
Наконец, обновляем файл main.py, чтобы объединить возможности синтаксического и лексического анализаторов:
Теперь при запуске main.py мы получим значение 6. и оно действительно соответствует нашей однострочной программе «print(4 + 4 – 2);».
Таким образом, при помощи двух этих компонентов мы создали работающий компилятор, интерпретирующий язык TOY. Однако компилятор по-прежнему не создает исполняемый машинный код и не оптимизирован. Для этого мы перейдем к самой сложной части руководства – генерации кода с помощью LLVM.
3. Генератор кода
Третья и последняя часть компилятора – это генератор кода. Его роль заключается в том, чтобы преобразовывать АСД в машинный код или промежуточное представление. В нашем случае будет происходить преобразование АСД в промежуточное представление LLVM (LLVM IR).
LLVM может оказаться действительно сложным для понимания инструментом, поэтому обратите внимание на документацию LLVMlite. LLVMlite не имеет реализации для функции печати, поэтому вы должны определить собственную функцию.
Чтобы начать, создадим файл codegen.py, содержащий класс CodeGen. Этот класс отвечает за настройку LLVM и создание/сохранение IR-кода. В нем мы также объявим функцию печати.
Теперь обновим основной файл main.py, чтобы вызывать методы CodeGen:
Как вы можете видеть, для того, чтобы обработка происходила классическим образом, входная программа была вынесена в отдельный файл input.toy. Это уже больше похоже на классический компилятор. Файл input.toy содержит все ту же однострочную программу:
Еще одно изменение – передача парсеру методов module, builder и printf. Это сделано, чтобы мы могли отправить эти объекты АСД. Таким образом, для получения объектов и передачи их АСД необходимо изменить parser.py:
Наконец, самое важное. Мы должны изменить файл ast.py, чтобы получать эти объекты и создавать LLMV АСД, используя методы из библиотеки LLVMlite:
После изменений компилятор готов к преобразованию программы на языке TOY в файл промежуточного представления LLVM output.ll. Далее используем LLC для создания файла объекта output.o и GCC для получения конечного исполняемого файла:
Теперь вы можете запустить исполняем файл, для создания которого вами использовался свой язык программирования:
Следующие шаги
Мы надеемся, что после прохождения этого руководства вы разобрались в общих чертах в концепции РБНФ и трех основных составляющих компилятора. Благодаря этим знаниям вы можете создать свой язык программирования и написать оптимизированный компилятор при помощи Python. Мы призываем вас не останавливаться на достигнутом и добавить в свой язык и компилятор другие важные составляющие:
Итоговый программный код вы также найдете на GitHub.
Другие материалы по теме языков программирования
Пишем примитивный и никому не нужный компилятор
Я считаю, что каждый программист должен написать свой компилятор.
Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.
В посте мы рассмотрим, как можно написать свой компилятор C-подобного языка меньше чем за час, исписав всего 300 строчек кода. В качестве бонуса, сюда входит и код виртуальной машины, в байткод которой будет компилироваться исходник.
Компилятор будет писаться на Python. Я очень люблю этот язык, но код может быть местами корявым. Если что не так — пишите в личку.
Да, компилятор совершенно нагло основан на Tiny-С.
Грамматика
Прежде чем начать, давайте определимся, что именно будет уметь наш язык.
Уметь он будет очень мало:
— единственный тип данных — int
— все переменные — глобальные. Всего есть 26 переменных (a-z)
— из математических операций поддерживаются только «+» и «-»
— единственный оператор сравнения — это »
Это запись грамматики в форме EBNF. Вот что эта запись приблизительно означает.
Программа — это один оператор (statement).
Операторы бывают условными (if..else. ), циклическими (while. ) и просто операторами (напр., «a=2+3»).
Условные и циклические содержат в себе выражение-условие и тело (в виде оператора). Обычные операторы заканчиваются точкой с запятой. Можно группировать операторы в фигурных скобках, тогда получим составной оператор.
Выражения — это либо сумма, либо присваивание переменной значения.
Здесь сумма — это последовательность сложений-вычитаний термов.
Терм — это число, переменная или выражение в скобках.
Переменные — это символы от a до z. Числа — это набор цифр от 0 до 9.
Все эти сложности нужны для того, чтобы указать компилятору как именно автоматически анализировать исходный код. Например, встретили слово «if» — значит дальше идет выражение в скобках, а за ним — оператор.
Лексический анализатор
На вход компилятору поступает текстовый файл (исходник). Лексический анализатор нужен для того, чтобы выделить в этом файле токены. Т.е. строчку «a = 3 + 42;» лексический анализатор должен представить в виде «идентификатор: a», «оператор =», «число 3», «оператор +», «число 42», «символ ;». Лексический анализатор работает только с последовательностью букв, т.е. для него строчка «a b if =» тоже имеет смысл и является абсолютно корректной.
Итак, наш лексический анализатор должен узнавать следующие токены:
Дерево, которое строится парсером, состоит из узлов. У узла есть тип (IF, LESS, SET, VAR. ), значение (если это число или переменная) и несколько дочерних узлов-операндов (в коде — op1, op2, op3). Для if в них хранятся условие и ветки then/else, для циклов — условие и тело цикла.
Для описания узлов введем класс Node. Вот код класса парсера и класса Node:
Этот парсер работает рекурсивно, начиная с метода parse().
Вначале он создает узел «Программа», дочерним узлом которого становится главный оператор программы.
Операторы формируются в методе statement(). В этом методе проверяется первый токен и в зависимости от него формируется if, if/else, while, do/while, составной оператор (если начинается с фигурной скобки) или просто одиночный оператор, завершающийся точкой с запятой.
При построении операторов используются методы expr() — получить выражение и paren_expr() — получить выражение в скобках.
Выражения строятся из проверок, которые строятся из сумм, которые состоят из термов. А термы в свою очередь состоят из чисел, переменных и выражений в скобках. В доме, который построил Джек.
Такая вот рекурсия. Как видите, методы соответствуют понятиям описанной выше грамматики.
На выходе метода parse() получаем объект класса Node, который содержит дерево нашей программы. Это дерево теперь можно преобразовывать в машинный код.
Машинный код
Компилировать мы будем в простенький байт-код нашей специальной виртуальной машины. Виртуальная машина будет стековой, т.к. они значительно проще регистровых. Вот ее возможные инструкции:
Например, операторы «a = 2; b = 5;» преобразуется в такую последовательность инструкций:
Код виртуальной машины очень простой. Он весь описывается в методе run:
Осталось написать собственно компилятор — генератор кода.
Компилятор
Венец нашего творения. Вот его исходный код:
Метод gen() добавляет новый байт (команду или аргумент) в программу (список байт).
В методе compile() собирается вся программа. Фактически, этот метод рекурсивно обходит дерево узлов. и для каждого типа узла генерирует соответствующий код.
Обратите внимание на хитрость в условных операторах и циклах. После JMP/JZ сперва пишем 0, а когда сама ветка скомпилирована и известен адрес, на который надо перейти, чтобы не выполнять эту ветку — значение 0 меняем на фактический адрес.
Тестируем
Тут лежит полный исходник компилятора. Я использовал скриптик для запуска и проверки (у меня Lexer читал из stdin):
Ответы машина выдавала вроде бы правильные.
Пишем x86-64 JIT-комплятор с нуля в стоковом Python
В этой статье я покажу, как написать рудиментарный, нативный x86-64 just-in-time компилятор (JIT) на CPython, используя только встроенные модули.
Код предназначен для UNIX-систем, таких как macOS и Linux, но его должно быть легко транслировать на другие системы, типа Windows. Весь код опубликован на github.com/cslarsen/minijit.
Цель — сгенерировать в рантайме новые версии нижеприведённого ассемблерного кода и выполнить их.
Используем функцию mprotect для пометки блока памяти как доступного только для чтения и исполняемого. После этого должна появиться возможность вызова нашего свежескомпилированного блока кода посредством ctypes.
Шаблонная часть
Прежде чем что-либо сделать, нужно загрузить стандартную библиотеку C.
Есть и другие способы сделать это, например
Нам нужны несколько дополнительных констант для mmap и проч. Они записаны ниже. Может быть, вам придётся поискать их для других вариантов UNIX.
Хотя это не является строгим требованием, но очень полезно передать ctypes типы функций, которые мы собираемся использовать. Таким образом, будут подняты исключения в случае смешивания недопустимых типов. Например:
Это говорит ctypes, что функция sysconf принимает четырёхбайтовое целое число, а выдаёт длинное целое. После этого можно узнать текущий размер страницы следующей командой:
Машинный код, который мы собираемся сгенерировать, будет интерпретироваться как беззнаковые 8-битные байты, поэтому зарегистрируем беззнаковый тип указателя на эти байты:
На данном этапе сложно оправдать использование Python вместо C. В случае C нам не нужен вышеперечисленный шаблонный код. Но Python даст гораздо больше свободы в дальнейших экспериментах.
Эта функция использует mmap для выделения нам памяти, выровненной по границам страницы. Мы помечаем участок памяти флагами PROT как доступный для чтения и записи, а также помечаем его как приватный и анонимный. Последнее означает, что другие процессы не смогут увидеть этот участок памяти и что он не имеет файловой поддержки. Руководство по mmap в Linux более подробно раскрывает эту тему (только убедитесь, что открыли руководство именно для своей системы). Если вызов mmap неудачный, мы вызываем ошибку Python.
Чтобы пометить память как исполняемую:
Таким вызовом mprotect мы помечаем участок памяти как доступный для чтения и исполняемый. Если хотим, можем также сделать его доступным для записи, но некоторые системы откажутся исполнять код из памяти, открытой для записи. Иногда это называют функцией безопасности W^X.
Для уничтожения блока памяти делаем следующее:
Весёлая часть
Теперь мы наконец-то готовы написать безумно простой код JIT!
Вспомните листинг ассемблера из начала статьи: это небольшая функция — без локального стекового кадра — которая умножает число на входе на константу. На Python мы бы записали её так:
Это действительно надуманный пример, но соответствует определению JIT. В конце концов, мы действительно создаём нативный код в рантайме и исполняем его. Легко представить более продвинутые примеры, такие как JIT-компиляция Brainfuck в машинный код x86-64. Или использование инструкций AVX для молниеносных математических операций по векторизации.
Разборка машинного кода в начале статьи в реальности была выполнена путём компиляции и дизассемблирования следующего кода C:
Обратите внимание, что константа 0xdeadbeefed указана в формате с обратным порядком байтов (little-endian). Нужно не забыть сделать то же самое в коде.
Теперь мы готовы поместить всё в функцию Python.
В нижней части мы возвращаем тип функции ctypes для использования в этом коде. Это несколько произвольное размещение, но я подумал, что хорошо будет поместить его рядом с машинным кодом.
Финальная часть
Теперь у нас есть основные части, которые можно совместить. Сначала — выделить одну страницу памяти:
Затем сгенерировать машинный код. В качестве множителя выберем число 101.
Теперь помечаем участок памяти как исполняемый и доступный только для чтения:
Берём адрес первого байта в блоке памяти подаём его в вызываемую функцию ctypes с правильным типом:
Вуаля! Теперь у нас кусочек нативного кода, который можно вызвать из Python. Если вы находитесь в среде REPL, то можно сделать это напрямую:
Заметьте, что эта маленькая функция умножения работает медленнее, чем нативные вычисления Python. Это главным образом из-за чужеродной библиотеки ctypes, использование которой несёт много накладных расходов: каждый раз при вызове функции нужно проверить, какие динамические типы вы ей передаёте, затем распаковать их и преобразовать, а потом сделать то же самое с возвращаемым значением. Так что есть смысл использовать ассемблер или если у вас есть доступ к каким-то новым инструкциям Intel, или для компиляции чего-то вроде Brainfuck в нативный код.
В конце, если хотите, можете позволить системе повторно использовать участок памяти, в котором находится функция. Имейте в виду, что после этого, вероятно, произойдёт сбой процесса, если попытаться снова обратиться к коду. Так что наверное лучше одновременно удалить вообще все упоминания Python:
Если запустите код в его полном виде из репозитория GitHub, то можете указать константу для умножения прямо в командной строке:
$ python mj.py 101
Pagesize: 4096
Allocating one page of memory
JIT-compiling a native mul-function w/arg 101
Making function block executable
Testing function
OK mul(0) = 0
OK mul(1) = 101
OK mul(2) = 202
OK mul(3) = 303
OK mul(4) = 404
OK mul(5) = 505
OK mul(6) = 606
OK mul(7) = 707
OK mul(8) = 808
OK mul(9) = 909
Deallocating function
Отладка JIT-кода
Если хотите продолжить обучение с помощью этой маленькой программы, то вскоре возникнет мысль дизассемблировать сгенерированный машинный код. Как вариант, можно просто использовать gdb или lldb, но нужно знать, откуда начать. Есть такой трюк: просто вывести hex-значение адреса блока с ожиданием нажатия клавиши:
Затем просто запускаете программу в отладчике и во время паузы дизассемблируете область памяти. Конечно, также есть возможность пошаговой отладки ассемблерного кода, если хотите посмотреть, что происходит. Пример сессии lldb:
В этом месте нажмите CTRL+C для возвращения в отладчик, затем дизассемблируйте код из области памяти:
Обратите внимание, что 65 в hex — это 101 в десятичной системе, то есть тот аргумент командной строки, который мы ввели выше.
Если нужен дизассемблер только в Python, рекомендую модуль Capstone.
Что дальше?
Хорошим упражнением была бы JIT-компиляция программ Brainfuck в нативный код. Если хотите сразу этим заняться, я открыл репозиторий GitHub по адресу github.com/cslarsen/brainfuck-jit. Я даже сделал презентацию Speaker Deck. Там показана JIT-компиляция и оптимизации, но вместо подхода из этой статьи для компиляции нативного кода используется GNU Lightning. Но должно быть исключительно просто использовать примеры без GNU Lightning или сгенерировать собственный код. Интересное наблюдение по проекту Brainfuck: если вы выполните просто JIT-компиляцию всех инструкций Brainfuck одна за другой, то не получите особого увеличения производительности даже в нативном коде. Весь прирост производительности происходит на этапе оптимизации кода, где вы забиваете целочисленными операциями одну или несколько инструкций x86. Ещё один кандидат на такую компиляцию — язык Forth.
Прежде чем серьёзно взяться за расширение этого JIT-компилятора, взгляните на проект PeachPy. Это гораздо более продвинутый проект, чем у нас, он включает в себя дизассемблер и поддерживает как будто весь набор инструкций x86-64, вплоть до AVX.
Какие ещё есть примечательные варианты использования? Мне встречались некоторые математические библиотеки на Python, которые переходят на векторные операции для повышения производительности. Но могу представить и другие вещи. Например, инструменты для сжатия и декомпрессии нативного кода, доступа к примитивам виртуализации и так далее. Знаю, что некоторые инструменты BPF и модули regex тоже выполняют JIT-компиляцию запросов для более быстрой обработки данных.
Что интересно в этом упражнении — так это то, что мы вступаем на территорию за пределами чистого ассемблера. Например, приходит в голову мысль, как различные инструкции дизассемблируются в одинаковые символы. Так, у инструкции RETQ иной opcode, чем у обычной инструкции RET, потому что она обрабатывает 64-битные значения. Может, это и не важно при программировании на ассемблере, потому что такие детали не всегда имеют значение, но стоит помнить о разнице. Я видел, как gcc, lldb и objdump выдавали слегка разный листинг дизассемблера для инструкций RETQ и MOVABSQ в одном и том же коде.
Ещё одно замечание. Я упоминал, что сделанный мной нативный компилятор Brainfuck изначально выдаёт не очень быстрый код. Его нужно оптимизировать. То есть код не становится быстрее автоматически от того факта, что у вас есть AVX, CUDA или что-то ещё. Жестокая правда в том, что в компилятор gcc зашита большая база оптимизаций, которые практически невозможно воспроизвести вручную. Для дополнительной информации я бы рекомендовал классическую лекцию Феликса фон Лейтнера об оптимизации исходного кода.
Как скомпилировать Python
Я хочу рассказать об удивительном событии, о котором я узнал пару месяцев назад. Оказывается, одна популярная python-утилита уже более года распространяется в виде бинарных файлов, которые компилируются прямо из python. И речь не про банальную упаковку каким-нибудь PyInstaller-ом, а про честную Ahead-of-time компиляцию целого python-пакета. Если вы удивлены так же как и я, добро пожаловать под кат.
Объясню, почему я считаю это событие по-настоящему удивительным. Существует два вида компиляции: Ahead-of-time (AOT), когда весь код компилируется до запуска программы и Just in time compiler (JIT), когда непосредственно компиляция программы под требуемую архитектуру процессора осуществляется во время ее выполнения. Во втором случае первоначальный запуск программы осуществляется виртуальной машиной или интерпретатором.
Если сгруппировать популярные языки программирования по типу компиляции, то получим следующий список:
Ahead-of-time compiler: C, C++, Rust, Kotlin, Nim, D, Go, Dart;
Just in time compiler: Lua, С#, Groovy, Dart.
В python из коробки нет JIT компилятора, но отдельные библиотеки, предоставляющие такую возможность, существуют давно
Смотря на эту таблицу, можно заметить определенную закономерность: статически типизированные языки находятся в обеих строках. Некоторые даже могут распространяться с двумя версиями компиляторов: Kotlin может исполняться как с JIT JavaVM, так и с AOT Kotlin/Native. То же самое можно сказать про Dart (версии 2). A вот динамически типизированные языки компилируются только JIT-ом, что впрочем вполне логично.
При запуске виртуальная машина сначала накапливает информацию о типах переменных, затем после накопления статистики, запускается компиляция наиболее нагруженных частей программы. Виртуальная машина отслеживает типы аргументов и переключает выполнение программы между уже скомпилированными и не скомпилированными участками кода в зависимости от текущих значений переменных.
При использовании JIT компиляции типы не очень то и нужны, ведь информация о типах собирается во время работы программы. Поэтому все популярные динамически типизированные языки программирования распространяются именно с JIT компилятором. Но как быть с AOT компиляцией кода, в котором нет типов? Меня очень заинтересовал этот вопрос, и я полез разбираться.
С апреля 2019 года эта утилита распространяется в скомпилированном виде, о чем рассказывается в блоге проекта. А для компиляции используется еще одна утилита от тех же авторов — mypyc. Погуглив немного, я нашел достаточно большую статью “Путь к проверке типов 4 миллионов строк Python-кода” про становление и развитие mypy (на Хабре доступен перевод: часть 1, часть 2, часть 3). Там немного рассказывается о целях создания mypyc: столкнувшись с недостаточной производительностью mypy при разборе крупных python-проектов в Dropbox, разработчики добавили кеширование результатов проверки кода, а затем возможность запуска утилиты как сервиса. Но исчерпав очевидные возможности оптимизации, столкнулись с выбором: переписать все на go или на cython. В результате проект пошел по третьему пути — написание своего AOT python-компилятора.
Дело в том, что для правильной работы mypy и так необходимо построить то же синтаксическое дерево, что и интерпретатору во время исполнения кода. То есть mypy уже “понимает” python, но использует эту информацию только для статистического анализа, а вот mypyc может преобразовывать эту информацию в полноценный бинарный код.
Думаю тут многие решили, что разобрались в вопросе того, как скомпилировать динамически типизированный python-код. Python c версии 3.4 поддерживает аннотацию типов, а mypy как раз и используется для проверки корректности аннотаций. Получается, python как бы уже и не динамически типизированный язык, что позволяет применить AOT компиляцию. Но загвоздка в том, что mypyc может компилировать и неаннотированный код!
Функция bubble_sort
Для примера рассмотрим функцию сортировки “пузырьком”. Файл lib.py:
У типов нет аннотаций, но это не мешает mypyc ее скомпилировать. Чтобы запустить компиляцию, нужно установить mypyc. Он не распространяется отдельным пакетом, но если у вас установлен mypy, то и mypyc уже присутствует в системе! Запускаем mypyc, следующей командой:
После запуска в проекте будут созданы следующие директории:
.mypy_cache — mypy кэш, mypyc неявно запускает mypy для разбора программы и получения AST;
build — артефакты сборки;
lib.cpython-38-x86_64-linux-gnu.so — собственно сборка под целевую платформу. Данный файл представляет из себя готовый CPython Extension.
CPython Extension — встроенный в CPython механизм взаимодействия с кодом, написанным на С/C++. По сути это динамическая библиотека, которую CPython умеет загружать при импорте нашего модуля lib. Через данный механизм осуществляется взаимодействие с модулями, написанными на python.
Компиляция состоит из двух фаз:
Компиляция python кода в код С;
Компиляция С в бинарный .so файл, для этого mypyc сам запускает gcc (gcc и python-dev также должен быть установлены).
Файл lib.cpython-38-x86_64-linux-gnu.so имеет преимущество перед lib.py при импорте на соответствующей платформе, и исполняться теперь будет именно он.
Ну и давайте сравним производительность модуля до и после компиляции. Для этого создадим файл main.py с кодом запуска сортировки:
Получим примерно следующие результаты:
Ожидаемо скомпилированный код оказался быстрее (
в 2 раза), что неплохо, так как для такого результата нам потребовалось запустить лишь одну команду. Хотя от скомпилированного кода привычно ожидаешь большего.
Чтобы ответить на вопрос “как компилируется динамически типизированный код”, придется заглянуть в представление этой функции на С. Но разобрать ее будет достаточно сложно, поэтому давайте попробуем разобраться с примером попроще.
Функция sum(a, b)
Скомпилируем функцию суммы от двух переменных:
Перед запуском компиляции я ожидал увидеть примерно следующий код на С:
Однако результат оказался cущественно иным (код немного упрощен):
Рассмотрим, что тут происходит. Во-первых, так как мы не знаем типы входных переменных, функция в качестве аргументов принимает указатели на объекты класса PyObject, по сути это внутренние CPython структуры. Далее компилятор должен сложить эти объекты, но как, если настоящие типы аргументов неизвестны во время компиляции: это могут быть целые числа, числа с плавающей точкой, списки и вообще не факт, что аргументы можно складывать, тогда нужно вернуть ошибку. И что же делает в этом случае mypyc?
Как оказалось, все очень просто: он просит CPython самостоятельно сложить эти аргументы. Функция PyNumber_Add — это внутренняя функция СPython, которая доступна из расширения, ведь СPython отлично умеет складывать свои объекты.
Взаимодействие CPython c Extension можно изобразить следующим диалогом:
— А посчитай-ка мне функцию sum для A, B;
— Хорошо, но скажи сначала, сколько будет A + B;
Вот такой нехитрый прием используется при компиляции динамического кода: компилируем все, что можем, а все остальное отдаем интерпретатору.
Конечно, данный пример выглядит гротескно, но даже несмотря на такую неэффективность, mypyc позволяет добиться существенного прироста производительности, как в примере с сортировкой.
Функция sum(a: int, b: int)
Для повышения эффективности, нужно, чтобы расширение, получив управление, могло как можно дольше оставлять его у себя без обращения к CPython. Если бы у mypyc была информация о типах переменных, то он бы мог самостоятельно произвести сложение без возврата управления. Но вывести типы самостоятельно mypyc не может, он даже не контролирует код, из которого осуществляется вызов функции sum. Соответственно, ему нужно помочь, проставив аннотации вручную. Давайте посмотрим, как поменяется результирующая С-функция, если добавить аннотацию типов:
Скомпилированный результат на C (немного очищенный):
Главное, что можно заметить: функция существенно поменялась, а значит, компилятор реагирует на появление аннотации. Давайте разбираться, что изменилось.
Теперь CPyDef_sum получает на вход не указатели на PyObject, а структуры CPyTagged. Это все еще не int, но уже и не часть CPython, а часть библиотек mypyc, которую он добавляет в скомпилированный код расширения. Для ее инициализации в рантайме сначала проверяется тип, так что теперь функция sum работает только с int и обойти аннотацию не получится.
Далее происходит вызов CPyTaggetAdd вместо PyNumber_Add. Это уже внутренняя функция mypyc. Если заглянуть в код CPyTaggetAdd, то можно понять, что там происходит проверка диапазонов значений a и b, и если они укладываются в int, то происходит простое суммирование, а также проверка на переполнение:
— А посчитай-ка мне функцию sum для A, B;
— Хорошо, тогда держи ответ С.
Функция bubble_sort(data: List[int])
Настало время вернуться к функции сортировки, чтобы провести замеры скорости. Изменим начальную функцию, добавив аннотацию для data:
Скомпилируем результат и замерим время сортировки: