Почему так трудно написать компилятор для Perl 6?

Перевод статьи Why is it hard to write a compiler for Perl 6? с любезного согласия Moritz Lenz

Сегодняшний обманчиво простой вопрос на #perl6: труднее ли написать компилятор для Perl 6, чем для любого другого языка программирования?

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

Итак, давайте посмотрим. Первый момент - организационный: Perl 6 еще не полностью изучен и формально специфицирован; он гораздо более стабилен, чем раньше, но менее стабилен, чем, скажем, таргетинг C89.

Но даже если не принимать во внимание этот момент и ориентироваться на подмножество, которое, например, компилятор Rakudo Perl 6 реализует прямо сейчас, или подождать год и ориентироваться на первый релиз языка Perl 6, смысл остается актуальным.

Итак, давайте рассмотрим некоторые технические аспекты.

Статический vs. Динамический

Perl 6 имеет как статические, так и динамические углы. Например, лексический поиск является статическим, в том смысле, что он может быть решен во время компиляции. Но это не обязательно. Чтобы компилятор правильно поддерживал родные типы, он должен разрешать их во время компиляции. Мы также ожидаем, что компилятор будет уведомлять нас об определенных ошибках во время компиляции, поэтому статический анализ должен быть в достаточном объеме.

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

И даже несмотря на то, что вызовы методов связаны с опозданием, объединение ролей в классы - это операция времени компиляции, с обязательным анализом времени компиляции.

Изменяемая грамматика

Грамматика Perl 6 может изменяться в процессе разбора, например, за счет новых определенных операторов, а также за счет более инвазивных операций, таких как определение сленгов или макросов. Кстати, о сленгах: Perl 6 не имеет единой грамматики, он переключается туда-сюда между "основным" языком, регексами, классами символов внутри регексов, кавычками и всеми другими диалектами, которые вы можете придумать.

Поскольку расширения грамматики сделаны с помощью грамматик Perl 6, это заставляет парсер быть совместимым с регексами и грамматиками Perl 6. В этот момент вы можете с тем же успехом использовать их для парсинга всей вещи, и вы получаете некоторый уровень минимально необходимого self-hosting.

Мета-объектное программирование

В таких языках, как C++, поведение объектной системы жестко закодировано в языке, и поэтому компилятор может работать в соответствии с этим предположением и оптимизировать его.

В Perl 6 объектная система определяется другими объектами и классами, мета-объектами. Таким образом, появляется еще один уровень непрямолинейности, который необходимо обработать.

Смешение времени компиляции и выполнения

Декларации, такие как классы, а также блоки BEGIN и правая часть деклараций констант выполняются сразу после их разбора. Это означает, что компилятор должен быть способен выполнять код Perl 6, одновременно компилируя код Perl 6. А также наоборот, через EVAL.

Что еще более важно, он должен уметь запускать код Perl 6 до того, как закончит компиляцию всего блока компиляции. Это означает, что он даже не полностью построил лексические подкладки и не инициализировал все переменные. Поэтому нужны специальные "статические лекспады", к которым можно вернуться при использовании переменных во время компиляции. Также объектная система должна уметь работать с типами, которые еще не были полностью объявлены.

В общем, много всяких хитростей.

Сериализация, передача во владение

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

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

И есть очень много способов, как это может пойти не так.

Общие особенности

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

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