Язык програмирования — нелёгкий путь написания самодостаточного компилятора |
||
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Разработка ИИГородские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Авторизация |
2021-09-30 22:00 Уже несколько лет я веду разработку собственного языка программирования — ?. Около двух лет назад я публиковал вводную статью о нём на Хабре. Компилятор этого языка написан на C++ и долгое время он таковым и оставался. Но после той публикации я пришёл к выводу, что язык ? уже достаточно продвинут, чтобы написать на нём компилятор языка ?. О написании этого компилятора и будет повествовать данная статья. В данной статье описывается процесс разработки, имевший место (с перерывами) примерно с начала 2020-го года по начало лета 2021-го года. Далее я буду называть начальный компилятор, написанный на C++ "Компилятор0", а компилятор, написанный на ? — "Компилятор1". Логически разработку Компилятора1 можно разделить на три этапа. Первый этап — подготовительный/прототипный. Второй этап — собственно написание Компилятора1 до достижения самосборки. Третий этап — доделывание Компилятора1 и исправление недостатков. Подготовительный этап Данный этап проходил не сильно быстро и не интенсивно. На нём происходило больше теоретической и архитектурной работы, нежели просто написания кода. Поддержка рекурсивных структур данных В компиляторе почти что любого языка, да и вообще, во множестве программ, работающих с какими-либо формальными языками, широко используются рекурсивные структуры данных — напрямую или опосредованно включающие самих себя. Перед написанием Компилятора1 нужно было удостовериться, что язык и его стандартная библиотека поддерживают подобные структуры. Оказалось, что в Компиляторе0 есть некоторые особенности, которые мешали объявлять такие структуры. Пришлось изменять некоторые аспекты и убирать из некоторых мест требование полноты типов. Также оказалось, что даже после исправлений в Компиляторе0 не получается создать рекурсивные структуры с использованием контейнеров стандартной библиотеки Со вторым дело обстояло сложнее. Всё дело в том, что наличие конструктора копирования у класса Генерация отладочной информации Опыт подсказывает, что написание хоть сколько нибудь сложного кода требует возможности периодически его отлаживать. Соответственно, прежде чем начать писать Компилятор1, следовало добавить в Компилятор0 возможность генерировать отладочную информацию. Проект ? основан на библиотеке LLVM. В ней есть встроенная поддержка генерации отладочной информации. Код фронтенда языка заполняет соответствующие структуры, детально описывая через них всё, что может быть полезно для отладки. Генератор бинарного кода LLVM способен на основе этих структур генерировать платформозависимую отладочную информацию в форматах DWARF (GCC) и CodeView (MSVC). Из всего множества возможностей генерации отладочной информации понадобилась только небольшая часть. Во-первых, нужно создавать отладочную информацию о типах, используемых в программе — имена, состав, смещение полей и т. д. Во-вторых, нужно создавать отладочную информацию о стековых переменных — указать их локальный адрес и тип. В-третьих, нужно указывать связь фрагментов кода функций с их местоположением в файле исходного кода. Итак, все вышеописанные я реализовал. Результат вышел вполне сносным. Стало возможным ставить точки останова в программах, смотреть значения локальных переменных, осуществлять вход/выход из функций и т. д. Возможно, это ещё не всё и есть какие-то более продвинутые механизмы отладки, для которых понадобилась бы более полная отладочная информация. Но мне хватило вышеописанного, наверное, в 95% случаев этого достаточно. В процессе реализации генерации отладочной информации я столкнулся с, казалось бы, весьма странной ошибкой — отображение стека вызовов не работало, как надо. Оказалось, всему виною было использование атрибута Первый код Компилятора1 и первые проблемы Итак, я начал писать код Компилятора1. Начал я с кода разбора исходного текста программы на лексемы. И в первых же нескольких сотнях строк кода я выявил несколько ошибок в Компиляторе0. Первая ошибка была примерно в следующем коде: type Iterator = ust::array_view_imut</char8/>; fn ParseIdentifier( Iterator &mut it ) : Lexem { ReadNextUTF8Char( it ); var Lexem mut result; result.lexem_type= Lexem::Type::Identifier; while( !it.empty() ) { auto mut it_next= it; if( !IsIdentifierChar( ReadNextUTF8Char( it_next ) ) ) { break; } it= it_next; // Вот здесь Компилятор1 порождал ошибку } return result; } В чём же была проблема? А проблема была в коде контроля ссылок. Компилятор считал, что переменная Обдумав, я принял решение несколько изменить дизайн языка — сделать изменяемость внутренних ссылок свойством типа. К примеру: struct RefImut // тип с неизменяемой ссылкой внутри { i32 &imut r; } struct RefMut // тип с изменяемой ссылкой внутри { i32 &mut r; } struct NonRef // тип без ссылок внутри { i32 x; } Данное решение в дизайне языка в целом себя хорошо оправдало и до сих пор используется. Ошибка исправлена? Не совсем. Как оказалось, код выше выявил ещё одну проблему. В коде Компилятора0 локальные переменные и ссылки контролировались структурой типа ациклического направленного графа — для целей того самого контроля ссылок. Но, как оказалось, граф таки может содержать циклы. В примере выше переменная Взаимодействие с библиотекой LLVM Лексический и синтаксический разбор текста программы — это всего лишь малая часть работы фронтенда компилятора. В ?, например, код лексического/синтаксического разбора занимает лишь 20-25% объёма. Основная же часть фронтенда компилятора занимается построением промежуточного представления. В случае ? это IR код LLVM. В Компиляторе0 (на C++) промежуточный код строится непосредственно через соответствующие классы/функции библиотеки LLVM. Спрашивается, можно ли делать то же самое на ?, или на каком-то другом языке, отличном от C++? Ответ положительный — да, можно. Авторы LLVM предусмотрели такое использование библиотеки и поэтому написали биндинги на чистом Си для построения IR кода (и не только). Я решил взять за основу эти Си биндинги для написания Компилятора1. Но как же вызывать Си функции из ?? В начале у меня были планы автоматически сгенерировать ? биндинги из Си биндингов. И у меня для этого даже есть преобразователь заголовочных файлов Си в ?, написанный с использованием библиотеки ClangTooling. Но, как оказалось, выдаёт он весьма посредственный результат, который нельзя использовать напрямую. Автоматически преобразованные файлы в большинстве случаев оказывались нерабочими и требовали ручной доводки. Казалось бы, что мешает доработать преобразователь? В принципе, думаю его можно доработать до более-менее вменяемого состояния. Но эту задачу я счёл слишком трудоёмкой для того, чтобы преобразовать только лишь один или два файла. Вместо этого для написания Компилятора1 я вручную написал биндинги для нужных LLVM функций. Результирующий файл с биндингами вышел примерно в 500 строк размером, да и писался не за один раз, а постепенно. Кроме написания биндингов к уже имеющемуся Си интерфейсу LLVM пришлось вручную реализовать ряд биндингов, отсутствующих в нём. Это довольно специфичные функции, так что в принципе логично, что их нету в Си интерфейсе. В дополнении к этим функциям по ходу написания Компилятора1 понадобилось реализовывать ещё немного функций на C++ — там, где по той или иной причине это было невозможно сделать с использованием ?. Адаптация тестов Перед разработкой Компилятора1 для Компилятора0 было написано уже достаточно много тестов — около двух тысяч. Чуть менее половины этих тестов написаны на C++ и запускаются как исполняемый файл. Чуть более половины тестов — это тесты, написанные на Python и запускающиеся с использованием разделяемой библиотеки, реализующей функционал компилятора. Ещё несколько тестов — это тесты с полноценной компиляцией в бинарные файлы и компоновкой. Такое странное разделение родилось исторически. Сначала тесты писались на C++, потом, чтобы ускорить перезапуск тестов при их правке, было принято решение писать их на Python. Тесты на компоновку нужны там, где не достаточно просто запустить интерпретатор LLVM для IR кода тестируемой программы. Итак, перед написанием Компилятора1 все эти тесты надо было адаптировать для Компилятора0. Для C++ тестов была добавлена относительно тонкая абстракция над библиотекой компилятора. Для Python тестов была написана отдельная разделяемая библиотека с кодом Компилятора1. Тесты компоновки же были переделаны на двукратный запуск — с Компилятором0 и Компилятором1. Ещё одна проблема была в том, что не возможно за один мах написать весь Компилятор1. Надо было, чтобы в ходе его разработки были включены только те тесты, что тестируют уже созданный функционал. Эту проблему я решил через белый список тестов, которые стоит запускать в Компиляторе1. В начале белый список был пуст, в последствии он всё более и более пополнялся. Под самый конец разработки, когда в этом списке было уже более 90% тестов, белый список был заменён чёрным списком — с тестами, которые ещё не проходят. По правде говоря, даже сейчас в чёрном списке тестов Компилятора1 кое-что остаётся — в основном для экспериментального/сомнительного функционала. Доказательство возможности Исправив наиочевиднейшие ошибки в Компиляторе0 и стандартной библиотеке, выполнив ряд приготовлений я продолжил написание Компилятора1. Сразу писать весь Компилятор1 от начала и до конца я считал несколько рискованным. Поэтому я решил написать только небольшую его часть чтобы проверить, что это вообще возможно на текущем уровне развития языка. Целью было написать (недо)компилятор с минимумом базовых возможностей, проверяемых сотней-другой тестов. Сомнения были в возможности создать нужные компилятору структуры данных и в наличии необходимых для разработки конструкций языка и кода стандартной библиотеки. Как читатель уже наверное догадывается, первая стадия написания Компилятора1 удалась. Оказалось, что имеющихся конструкций языка (за некоторым исключением) вполне достаточно для написания C++-подобного кода. Имеющихся контейнеров стандартной библиотеки — Также уже на этом этапе обнаружились некоторые особенности языка, которые потребовали несколько иного подхода к организации структур данных в Компиляторе1 по сравнению с Компилятором0. Основные отличия были следующие:
Доделывание Компилятора1 Самая долгая, трудоёмкая и (относительно) скучная часть работы по написанию Компилятора1 состояла в реализации всех необходимых возможностей. Но даже про эту часть работы есть чего рассказать. Как оказалось, даже на этапе доделывания Компилятора1 в Компиляторе0 выявился ряд недостатков, один серьёзный и ряд более мелких. Отлавливание не очевидных ошибок Компилятора0 Несколько раз при написании Компилятора1 я замечал странное — код вёл себя не так, как ожидалось. После некоторого времени, потраченного на отладку, я локализовывал ошибку в конкретном месте и не мог найти, что же в этом коде не так. Прибегнув в просмотру ассемблерного кода, я находил, в чём же дело. Оказывалось, что ассемблерный код не соответствовал исходному. В одном из случаев я обнаружил ошибку, когда Компилятор0 пропускал ошибку с отсутствием Ещё несколько раз я натыкался на ошибки контроля ссылок, возникающие на пустом месте. В последствии оказывалось, что виною всему ошибки в Компиляторе0. В одном из таких случаев я обнаружил, что связывание ссылок проверяется не перед каждым оператором О вычислителе constexpr функций Реализация большинства возможностей Компилятора1 не представляла особых проблем. Но одним из немногим исключений оказался вычислитель Что же это такое? Это специальный компонент, задача которого, исполнять во время компиляции Так вот, по своей сути этот компонент представляет собой свою реализацию интерпретатора некоторого подмножества IR кода. Продвинутый читатель спросит, а зачем он нужен, если в библиотеке LLVM уже есть подобный интерпретатор? Ответ следующий — он не подошёл, т. к. завязан на параметры системы, на которой запускается интерпретатор, а не целевой системы. В Компиляторе это критично — размер указателя, выравнивание структур, порядок байт при вычислении С этим компонентом проблема оказалась следующая — он слишком завязан на структуры данных LLVM, полный доступ к которым не возможен через Си биндинги. Написать этот компонент на ? было весьма проблематичным. Оказалось, что гораздо проще переиспользовать его как есть в Компиляторе1, написав соответствующие прокладки. Кода прокладок вышло всего несколько десятков строк. Оператор for в стиле Си В ходе разработки Компилятора1 я обнаружил, что набор базовых конструкций языка всё-же не совсем достаточен. Оказалось, что цикла Данную проблему я посчитал весьма серьёзной — она мешала использовать Достижение самосборки В какой-то момент я реализовал большинство возможностей языка в Компиляторе1. Возможность собрать Компилятор2 (собранный Компилятором1 из исходного кода Компилятора1) показалась на горизонте. Но всё оказалось не столь простым. Удивительно, но в Компиляторе1 оказалось какое-то количество ошибок, которые не выявились юнит-тестами. Часть этих ошибок выявилась при запуске тестов стандартной библиотеки через Компилятор1. Исправление этих ошибок заняло какое-то время. Часть ошибок выявилась при попытке таки собрать Компилятор2, их тоже какое-то время пришлось исправлять. Но и это ещё не всё. Отладочная сборка работала, но не работала выпускная сборка — она падала где-то в оптимизаторах IR кода в недрах библиотеки LLVM. Оказалось, что кое-где Компилятор1 генерирует не совсем правильный IR код. Это пришлось исправлять. Наконец, спустя несколько месяцев активной разработки, мне удалось собрать Компилятор2. После этого я для проверки, что всё в порядке, по такой же схеме собрал ещё и Компилятор3. Послесамосборочные исправления Оказалось, что достижение самосборки — это ещё не конец. В процессе были выявлены недостатки как Компилятора0, так и самого языка. Это всё надо было исправлять. Многократное ускорение сборки По ходу разработки Компиятора1 я замечал, как всё медленнее и медленнее он собирается. К моменту достижения самосборки Компилятор1 собирался с нуля несколько минут, против нескольких десятков секунд Компилятора0 (на C++). Я стал искать причину столь долгой сборки. Ключ к решению проблемы дало наблюдение размера объектных файлов, созданных Компилятором1. Они оказались на порядки более объёмными и содержали кратно больше символов, чем аналогичные файлы Компилятора0. Анализ показал, что подавляющее большинство этих символов это методы шаблонных классов, шаблонные функции, сгенерированные конструкторы/операторы присваивания/деструкторы. Наличие этих символов казалось вполне логичным — для них ведь, как и для других символов используется публичная видимость. Когда я писал Компилятор0 и даже Компилятор1 я об этом не задумывался. Использование публичной видимости символов казалось само собою разумеющимся. Я решил пересмотреть этот подход. Оказалось, что для шаблонных/сгенерированных символов публичная видимость и не нужна, т. к. они по необходимости генерируются в каждой единице компиляции. Поэтому, сначала в качестве эксперимента, я изменил видимость таких символов на приватную. И это сработало! Оказалось, что проходы оптимизации LLVM выбрасывают приватные символы, если они не используются (были встроены), после чего генератор кода не создаёт для них бинарный код и в результирующий объектный файл они тоже не записываются. Компиляция Компилятора1 (и последующих поколений) кратно ускорилась и стала сравнимой по времени с компиляцией Компилятора0. Объектные файлы сильно потеряли в размере и их размер стал сравним с таковыми файлами Компиялтора0. У продвинутого читателя может возникнуть вопрос — а зачем вообще на уровне фронтенда компилятора генерировать символы, которые не используются? Для шаблонных классов это сознательное решение в дизайне языка. В отличие от C++, где методы шаблонных файлов генерируются лениво, в ? они генерируются сразу, чтобы убедиться в консистентности кода для заданных аргументов шаблона. Если какой-то метод не нужен в конкретных условиях, его можно явно отключить через Ведёт ли вышеописанный подход к снижению производительности компилятора? Да, в некоторой степени. Но как будет показано ниже, влияние его на производительность незначительно. Всё-же на всякий случай перед запуском оптимизирующих проходов библиотеки LLVM я добавил запуск прохода на удаление неиспользуемых символов, чтобы для них не запускались непосредственно проходы оптимизации. Реализация недостающих возможностей После достижения самосборки осталось реализовать в Компиляторе1 ещё ряд возможностей, которые не были необходимы для неё. Во-первых оставалось доделать создание отладочной информации. Не без проблем, но я это сделал. Во-вторых пришлось реализовать библиотечную функцию быстрой сортировки. До этого в Компиляторе1 (к моему стыду) использовалась тупо пузырьковая сортировка, которая в некоторых ситуациях значительно замедляла его работу. В-третьих, пришлось добавить генерацию ряда служебных символов (номера версии, поколения компилятора) в результирующие объектные файлы. Это нужно, иногда, для отладки. Облагораживание массивов Исторически так сложилось, что типы массивов были не совсем полноценными — их нельзя было передавать в функцию по значению и возвращать из функции, их нельзя было присваивать и инициализировать копией. Я решил, что такая дискриминация ни к чему и реализовал все эти возможности для массивов. Подобное изменение дало возможность использовать типы массивов, например, в шаблонах и работать в с ними так же, как и с любыми другими типами. Сырые указатели В языке до этого не было указателей, только ссылки. Там, где всё же были нужны указатели (в недрах стандартной библиотеки) использовался шаблонный класс, реализованный через целочисленный тип и преобразования число < — > ссылка. Такой подход порождал не совсем удобочитаемый IR код (с множеством операций Поэтому я решил реализовать типы сырых указателей на уровне языка. Данный класс типа предназначен для небезопасного кода и реализации всяческих контейнеров, для написания прикладного кода он не нужен. Использование этого типа не дозволено в Переделка типа void Долгое время тип Во-первых я сделал данный тип полноценным, чтобы можно было объявлять переменные/поля этого типа, инициализировать/копировать значения этого типа, явно передавать их в функцию, сравнивать на равенство. Данное изменение позволило использовать этот тип наравне со всеми другими типами в шаблонном коде. К примеру, после этого изменения я реализовал библиотечный контейнер Во-вторых, я убрал возможность неявных преобразований ссылок в Доработка контроля ссылок В ходе разработки Компилятора1 я периодически писал примерно такой код: fn Foo(T& x, T& y); /// var [ T, 2 ] mut arr= zero_init; Foo( arr[0], arr[1] ); На последней строке я получал ошибку контроля ссылок. В чём же дело? Оператор Foo( cast_imut(arr)[0], cast_imut(arr)[1] ); Оператор Я счёл, что необходимость написания данного кода — недостаток языка и от него необходимо избавится. Решил я эту проблему следующим способом — промежуточные узлы графа ссылок удалялись, после того, как стали ненужными. В примере в начале узел изменяемой ссылки, созданной оператором Внесение данного исправления позволило упростить подобные места в Компиляторе1 а также избавиться от ложных ошибок контроля ссылок в будущем. Замеры производительности Я произвёл замеры производительности Компилятора0 и Компилятора1. Для замеров использовался инструмент Valgrind. Компилятор0 был скомпилирован при помощи GCC. Компилятор1 был скомпилирован Компилятором0. В обоих случаях использовался уровень оптимизации Замеры производились путём компиляции одного из файлов Компилятора1. Ниже представлена таблица с результатами — общим временем работы компилятора, временем, затраченным на фронтенд компилятора и на бекенд (оптимизации, генерацию бинарного кода). В целом Компилятор1 работает дольше Компилятора0 на ~5.5%. Но при этом собственно работа фронтенда (отличающегося в разных компиляторах) занимает только 31-36% времени. Так что если сравнить производительность фронтендов, то в Компиляторе1 он работает дольше на 21%. С одной стороны это хорошо, что Компилятор1 по порядку производительности близок к Компилятору0. Но стоит ещё учесть, что даже во фронтенде Компилятора1 значительная часть исполняемого кода — это код на C++ внутри библиотеки LLVM. Так что сравнение чисто кода на ? по отношению к коду на C++ может дать ещё большее отставание первого. Вопрос — в чём же дело? Откуда такое отставание? Я предполагаю следующие причины:
Заключение В результате долгой и упорной работы самодостаточный (почти) компилятор таки был создан. В процессе сам язык был немного исправлен и дополнен. Изначальный компилятор (на C++) был местами доработан и исправлен. В дальнейшем я пока планирую продолжить поддержку двух версий компилятора. Это даёт некоторые преимущества вроде кросс-верификации и сравнения производительности. Да и чисто технически отказ от Компилятора0 пока что не возможен. Отказаться от начального компилятора можно будет только когда (и если) язык ? и его компилятор станут достаточно распространены, чтобы было можно разрабатывать Компилятор1 собирая его собранной ранее предыдущей версией себя же. Источник: m.vk.com Комментарии: |
|