В последнем семестре университета я выбрал курс компиляторов CS444. Там каждая группа из 1-3 человек должна была написать компилятор из существенного подмножества Java в x86. Язык на выбор группы. Это была редкая возможность сравнить реализации больших программ одинаковой функциональности, написанных очень компетентными программистами на разных языках, и сравнить разницу в дизайне и выборе языка. Такое сравнение породило массу интересных мыслей. Редко можно встретить такое контролируемое сравнение языков. Оно не идеально, но намного лучше, чем большинство субъективных историй, на которых основано мнение людей о языках программирования.
Мы сделали наш компилятор на Rust, и сначала я сравнил его с проектом команды на Haskell. Я ожидал, что их программа будет намного короче, но она оказалась того же размера или больше. То же самое для OCaml. Затем сравнил с компилятором на C++, и там вполне ожидаемо компилятор был примерно на 30% больше, в основном, из-за заголовков, отсутствия типов sum и сопоставлений с образцом. Следующее сравнение было с моей подругой, которая сделала компилятор самостоятельно на Python и использовала менее половины кода, по сравнению с нами, из-за мощности метапрограммирования и динамических типов. У другого товарища программа на Scala тоже была меньше нашей. Больше всего меня удивило сравнение с другой командой, которая тоже использовала Rust, но у них оказалось в три раза больше кода из-за разных дизайнерских решений. В конце концов, самая большая разница в количестве кода оказалась в пределах одного языка!
Я расскажу, почему считаю это хорошим сравнением, приведу некоторую информацию о каждом проекте и объясню некоторые причины различий в размере компилятора. Также сделаю выводы из каждого сравнения. Не стесняйтесь использовать эти ссылки, чтобы перейти к интересующему разделу:
Прежде чем вы скажете, что количество кода (я сравнил как строки, так и байты) — ужасная метрика, хочу заметить, что в данном случае она может обеспечить хорошее понимание. По крайней мере, это наиболее хорошо контролируемый пример, когда разные команды пишут одну и ту же большую программу, о котором я слышал или читал.
Таким образом, я думаю, что количество кода обеспечивает приличное понимание того, сколько усилий потребуется для поддержки каждого проекта, если бы он был долгосрочным. Думаю, что не слишком большая разница между проектами также позволяет опровергнуть некоторых экстраординарные утверждения, которые я читал, например, что компилятор на Haskell будет более чем вдвое меньше C++ в силу языка.
Я и один из моих товарищей раньше каждый написал более 10k строк на Rust, а третий коллега написал, возможно, 500 строк на каких-то хакатонах. Наш компилятор вышел в 6806 строк
Я обнаружил, что в других проектах эти пропорции примерно соблюдаются, с небольшими исключениями, которые я отмечу. Для остальной части статьи, когда я ссылаюсь на строки или сумму, я имею в виду
Я написал другую статью с описанием нашего дизайна, который прошёл все публичные и секретные тесты. Он также содержит несколько дополнительных функций, которые мы сделали для удовольствия, а не для прохождения тестов, что, вероятно, добавило около 400 строк. Также в нём около 500 строк наших модульных тестов.
В команду Haskell входило два моих друга, которые написали, возможно, пару тысяч строк Haskell каждый, плюс прочитали много онлайн-контента о Haskell и других подобных функциональных языках, таких как OCaml и Lean. У них был ещё один товарищ по команде, которого я не очень хорошо знал, но, похоже, сильный программист и раньше использовал Haskell.
Их компилятор составил 9750 строк по
Важно отметить, что включение тестов больше всего сказалось именно на этой команде. Поскольку они тщательно подошли к правильности кода, то включили 1600 строк тестов. Они поймали несколько пограничных ситуаций, которые наша команда не отловила, но просто эти случаи не проверялись тестами курса. Так что без тестов с обеих сторон (6,3 тыс. строк против 8,1 тыс. строк) их компилятор всего на 30% больше нашего.
Здесь я склоняюсь к байтам как более разумной мере сравнения объёма, потому что в проекте Haskell в среднем более длинные строки, поскольку у него нет большого количество строк из одной закрывающей скобки, и у них
Покопавшись с одним из моих друзей по команде, мы придумали следующее объяснение этой разнице:
Эти различия плюс тесты объясняют все различия в объёме. На самом деле наши файлы для свёртывания констант и разрешения контекста очень близки по размеру. Но всё равно остаётся некоторая разница в байтах из-за более длинных строк: вероятно, потому что требуется больше кода для перезаписи целого дерева на каждом проходе.
В итоге, отложив решения в области дизайна, по-моему, Rust и Haskell одинаково выразительны, возможно, с небольшим преимуществом Rust из-за способности легко использовать мутацию, когда это удобно. Было также интересно узнать, что мой выбор метода рекурсивного спуска и рукописный лексический анализатор окупились: это был риск, который противоречил рекомендациям и указаниям профессора, но я решил, что так легче и это правильно.
Поклонники Haskell возразят, что та команда, вероятно, не использовала в полной мере возможности Haskell, и если бы они лучше знали язык, то могли бы сделать проект с меньшим количеством кода. Согласен, кто-то вроде Эдварда Кметта может написать тот же компилятор в значительно меньшем объёме. Действительно, команда моего друга не использовала много причудливых суперпродвинутых абстракций и причудливых библиотек комбинаторов, таких как lens. Однако всё это сказывается на читаемости кода. Все люди в команде — опытные программисты, они знали, что Haskell способен на очень причудливые вещи, но решили не использовать их, потому что решили, что на их понимание потребуется больше времени, чем они сэкономят, и сделает код сложнее для понимания другими. Это кажется мне реальным компромиссом, а утверждение, что Haskell волшебно подходит для компиляторов, переходит в нечто вроде «Haskell требует чрезвычайно высокой квалификации для написания компиляторов, если вы не заботитесь о поддержке кода людьми, которые также не очень искусны в Haskell».
Ещё интересно отметить, что в начале каждого проекта профессор говорит, что студенты могут использовать любой язык, который работает на университетском сервере, но предупреждает, что команды на Haskell отличаются от остальных: у них самый большой разброс в оценках. Многие переоценивают свои способности и у команд на Haskell больше всего плохих оценок, хотя другие справляются отлично, как мои друзья.
Затем я поговорил с моим другом из команды C++. Я знал только одного человека в этой команде, но C++ используется на нескольких курсах в нашем университете, поэтому, вероятно, у всех в команде был опыт C++.
Их проект состоял из 8733 строк и 280 КБ, не включая тестовый код, но включая около 500 строк дополнительных функций. Что делает его в 1,4 раза больше нашего кода без тестов, у которого тоже около 500 строк дополнительных функций. Они прошли 100% публичных тестов, но только 90% секретных тестов. Предположительно потому, что они не реализовали причудливые массивы vtables, требуемые спецификацией, которые занимают, возможно, 50-100 строк кода.
Я не очень глубоко копался в этих различиях по размеру. Предполагаю, это в основном объясняется:
Ещё мы сравнивали время компиляции. На моём ноутбуке чистая отладочная сборка нашего компилятора занимает 9,7 с, чистый релиз 12,5 с, а инкрементная отладочная сборка — 3,5 с. У моего друга не было таймингов под рукой для их билда C++ (используя parallel make), но он сказал, что цифры похожие, с оговоркой, что они помещают реализации множества небольших функций в заголовочные файлы, чтобы уменьшить дублирование сигнатур ценой более длительного времени (именно поэтому я не могу измерить чистые накладные расходы на строки в заголовочных файлах).
Мой друг, очень хороший программист, решила сделать проект в одиночку на Python. Она также реализовала больше дополнительных функций (для удовольствия), чем любая другая команда, включая промежуточное представление SSA с распределением регистров и другими оптимизациями. С другой стороны, поскольку она работала в одиночку и реализовывала множество дополнительных функций, она уделяла наименьшее внимание качеству кода, например, бросая недифференцированные исключения для всех ошибок (полагаясь на бэктрейсы для отладки) вместо того, чтобы реализовать типы ошибок и соответствующие сообщения, как у нас.
Её компилятор состоял из 4581 строки и прошёл все публичные и секретные тесты. Она также реализовала больше дополнительных функций, чем любая другая команда, но трудно определить, сколько дополнительного кода это заняло, потому что многие из дополнительных функций были более мощными версиями простых вещей, которые всем нужно было реализовать, таких как свёртывание констант и генерация кода. Дополнительные функции, вероятно, составляют 1000-2000 строк, по крайней мере, поэтому я уверен, что её код по крайней мере вдвое выразительнее нашего.
Одна большая часть этого различия, вероятно, динамическая типизация. Только в нашем
Мощное метапрограммирование также объясняет часть разницы. Например, хотя она использовала LR-парсер вместо метода рекурсивного спуска, в её случае я думаю, что он занял меньше кода, потому что вместо прохода с перезаписью дерева её грамматика LR включала фрагменты кода Python для построения AST, которые генератор мог превратить в функции Python с помощью
Другой пример мощи метапрограммирования и динамической типизации — 400-строчный файл
Как поклонник Rust и статически типизированных языков в целом, я склонен отметить, что система типов очень полезна для предотвращения ошибок и для производительности. Необычное метапрограммирование также может затруднить понимание того, как работает код. Однако это сравнение удивило меня тем, что я не ожидал, что разница в количестве кода будет настолько большой. Если разница в целом действительно близка к необходимости писать в два раза больше кода, я все ещё думаю, что Rust подходящий компромисс, но всё-таки в два раза меньше кода — аргумент, и в будущем я склонен что-то сделать на Ruby/Python, если нужно просто быстро что-то построить в одиночку, а затем выбросить.
Cамое интересное для меня сравнение было с моим другом, который тоже делал проект в Rust с одним товарищем по команде (которого я не знал). У моего друга был хороший опыт Rust. Он внёс вклад в разработку компилятора Rust и много читал. О его товарище ничего не знаю.
Их проект состоял из 17 211 необработанных строк, 15k исходных строк и 637 КБ, не включая тестовый код и сгенерированный код. У него не было дополнительных функций, и он прошёл только 4 из 10 секретных тестов и 90% публичных тестов на генерацию кода, потому что у них не хватило времени перед дедлайном для реализации более причудливых частей спецификации. Их программа в три раза больше нашей, написана на том же языке, и с меньшей функциональностью!
Этот результат был действительно удивителен для меня и затмевал все различия между языками, которые я исследовал до сих пор. Поэтому мы сравнили списки размеров файлов
Похоже, всё сводится к последовательному принятию различных дизайнерских решений. Например, их фронтенд (лексический анализ, синтаксический анализ, построение AST) занимает 7597 строк против наших 2164. Они использовали лексический анализатор на DFA и синтаксический анализатор LALR(1), но другие группы делали подобные вещи без такого количества кода. Глядя на их weeder-файл, я заметил ряд дизайнерских решений, которые отличались от наших:
Я не смотрел на код проходов анализа их компилятора, но они тоже велики. Я поговорил со своим другом, и, похоже, они не реализовали ничего похожего на инфраструктуру визиторов, как у нас. Предполагаю, что это, наряду с некоторыми другими меньшими различиями в дизайне, объясняет разницу в размере этой части. Визитор позволяет нашим проходам анализа обращать внимание только на части AST, в которых они нуждались, вместо того, чтобы сопоставлять шаблон по всей структуре AST. Это экономит много кода.
Их часть для генерации кода состоит из 3594 строк, а наша — 1560. Я посмотрел на их код и кажется, что почти вся разница в том, что они выбрали промежуточную структуру данных для инструкций ассемблера, где мы просто использовали форматирование строк для прямого вывода ассемблера. Им пришлось определять типы и функции вывода для всех используемых инструкций и типов операндов. Это также означало, что построение инструкций ассемблера заняло больше кода. Где у нас был оператор форматирования с короткими инструкциями, такими как
Наша команда рассматривала возможность использования такой абстракции, как у них. Было проще иметь возможность либо выводить текстовую сборку, либо непосредственно выдавать машинный код, однако это не являлось требованием курса. То же самое можно было сделать с меньшим количеством кода и лучшей производительностью, используя трейт
Хорошо сравнить это с промежуточным представлением, которое команда C++ использовала в качестве дополнительной функции, что отняло у них всего 500 дополнительных строк. Они использовали очень простую структуру (для простых определений типов и кода построения), которая использовала операции, близкие к тому, что требовала Java. Это означало, что их промежуточное представление было намного меньше (и, следовательно, требовало меньше кода построения), чем результирующий ассемблер, поскольку многие языковые операции, такие как вызовы и приведения, расширялись во многие ассемблерные инструкции. Они также говорят, что это действительно помогло отладке, так как вырезало много мусора и улучшала читаемость. Представление более высокого уровня также позволило сделать некоторые простые оптимизации на их промежуточном представлении. Команда C++ придумала действительно хороший дизайн, который принёс им гораздо больше пользы с гораздо меньшим количеством кода.
В целом, похоже, что общая причина трёхкратной разницы в объёме обусловлен последовательным принятием различных проектных решений как больших, так и малых в направлении большего количества кода. Они реализовали ряд абстракций, которые мы не сделали — они добавили больше кода, и пропустили некоторые из наших абстракций, которые уменьшают количество кода.
Этот результат действительно удивил меня. Я знал, что дизайнерские решения имеют значение, но я бы не догадался заранее, что они приведут к каким-либо различиям такого размера, учитывая, что я только обследовал людей, которых я считаю сильными компетентными программистами. Из всех результатов сравнения это самый значительный для меня. Наверное, мне помогло, что я много читал о том, как писать компиляторы, прежде чем пошёл на этот курс, поэтому мог воспользоваться умными проектами, которые другие люди придумали и нашли хорошо работающими, вроде визиторов AST и метода рекурсивного спуска, хотя их не преподавали у нас на курсе.
Что действительно заставило меня задуматься — это стоимость абстракции. Абстракции могут облегчить расширение в будущем или защитить от некоторых типов ошибок, но их нужно учитывать с учётом того, что вы можете получить в три раза больше кода для понимания и рефакторинга, в три раза больше возможных мест для ошибок и меньше времени на тестирование и дальнейшую разработку. Наш учебный курс отличался от реального мира: мы точно знали, что никогда не коснёмся кода после разработки, это исключает преимущества упреждающей абстракции. Однако, если мне пришлось бы выбрать, какой компилятор расширить произвольной функцией, которую вы скажете позже, я бы выбрал наш, даже не учитывая своё знакомство с ним. Просто потому что в нём намного меньше кода, который нужно понять, и я мог бы потенциально выбрать лучшую абстракцию для требований (например, промежуточное представление команды C++), когда буду знать конкретные требования.
Также в моём представлении укрепилась таксономия абстракций: есть те, которые сокращают код, учитывая только текущие требования, как наш шаблон визитора, а есть абстракции, которые добавляют код, но обеспечивают преимущества расширяемости, отладочности или корректности.
Я также поговорил с другом, который в предыдущем семестре делал проект на Scala, но проект и тесты были точно такими же. Их компилятор состоял из 4141 строки и ~160 КБ кода, не считая тестов. Они прошли 8 из 10 секретных тестов и 100% открытых тестов и не реализовали никаких дополнительных функций. Таким образом, по сравнению с нашими 5906 строками без дополнительных функций и тестов, их компилятор меньше на 30%.
Одним из факторов дизайна в малого объёма стал другой подход к парсингу. Курс позволял использовать инструмент командной строки для генератора таблиц LR. Его никто не использовал, кроме этой команды. Это избавило их от необходимости реализовывать генератор таблиц LR. Им также удалось избежать написания грамматики LR с помощью 150-строчного скрипта Python, который скрапил веб-страницу грамматики Java, которую они нашли в интернете, и переводил её во входной формат генератора. Им всё ещё нужно было сделать какое-то дерево в Scala, но в целом этап парсинга составил 1073 строк по сравнению с нашими 1443, хотя наш метод градиентного спуска здесь давал преимущество по объёму по сравнению со всеми другими командами.
Остальная часть их компилятора была тоже меньше нашей, без каких-то очевидных больших различий в дизайне, хотя я не копался в коде. Подозреваю, что это связано с различиями в выразительности Scala и Rust. Scala и Rust имеют схожие функциональные возможности программирования, полезные для компиляторов, такие как сопоставление шаблонов, но управляемая память Scala экономит код, необходимый для работы borrow checker в Rust. Кроме того, в Scala более разнообразный синтаксический сахар, чем в Rust.
Поскольку все члены нашей команды проходят стажировку в Jane Street (технологическая компания вычислительного трейдинга — прим. пер.), мне было особенно интересно посмотреть на результат других бывших стажёров Jane Street, которые выбрали для написания компилятора язык OCaml.
Их компилятор составлял 10914 строк и 377 КБ, включая небольшое количество тестового кода и никаких дополнительных функций. Они прошли 9/10 секретных тестов и все публичные тесты.
Как и другие группы, похоже, что основная разница в размерах связана с использованием для синтаксического анализа LR-парсера и перезаписи дерева, а также конвейера преобразования regex->NFA->DFA для лексического анализа. Их фронтенд (лексический анализ, синтаксический анализ, конструкция AST) составляет 5548 строк, а наш — 2164, с аналогичными соотношениями для байтов. Они также использовали для своего парсера тестирование с ожиданием, что похоже на наши snapshot-тесты, которые помещают ожидаемый вывод за пределы кода, поэтому их тесты парсера составляли ~600 строк из общего числа, а наши — около 200.
Это оставляет для остальной части компилятора 5366 строк у них (461 строка из которых — интерфейсные файлы с объявлениями типов) и 4642 у нас, разница всего на 15%, если считать их интерфейсные файлы, и практически одинаковый размер, если не считать. Похоже, что, не считая наших дизайнерских решений по парсингу, Rust и OCaml кажутся одинаково выразительными, за исключением того, что OCaml нужны интерфейсные файлы, а Rust — нет.
В целом я очень рад, что сделал это сравнение, я многому научился и много раз удивлялся. Думаю, общий вывод заключается в том, что дизайнерские решения имеют гораздо большее значение, чем язык, но язык имеет значение, поскольку даёт вам инструменты для реализации разного дизайна.
Мы сделали наш компилятор на Rust, и сначала я сравнил его с проектом команды на Haskell. Я ожидал, что их программа будет намного короче, но она оказалась того же размера или больше. То же самое для OCaml. Затем сравнил с компилятором на C++, и там вполне ожидаемо компилятор был примерно на 30% больше, в основном, из-за заголовков, отсутствия типов sum и сопоставлений с образцом. Следующее сравнение было с моей подругой, которая сделала компилятор самостоятельно на Python и использовала менее половины кода, по сравнению с нами, из-за мощности метапрограммирования и динамических типов. У другого товарища программа на Scala тоже была меньше нашей. Больше всего меня удивило сравнение с другой командой, которая тоже использовала Rust, но у них оказалось в три раза больше кода из-за разных дизайнерских решений. В конце концов, самая большая разница в количестве кода оказалась в пределах одного языка!
Я расскажу, почему считаю это хорошим сравнением, приведу некоторую информацию о каждом проекте и объясню некоторые причины различий в размере компилятора. Также сделаю выводы из каждого сравнения. Не стесняйтесь использовать эти ссылки, чтобы перейти к интересующему разделу:
Содержание
- Почему я считаю это содержательным
- Rust (основа для сравнения)
- Haskell: 1,0-1,6 размера в зависимости от того, как считать, по интересным причинам
- C++: 1,4 размера по очевидным причинам
- Python: 0,5 размера из-за причудливого метапрограммирования!
- Rust (другая группа): трёхкратный размер из-за иного дизайна!
- Scala: 0,7 размера
- OCaml: 1,0-1,6 размера в зависимости от того, как считать, похоже на Haskell
Почему я считаю это содержательным
Прежде чем вы скажете, что количество кода (я сравнил как строки, так и байты) — ужасная метрика, хочу заметить, что в данном случае она может обеспечить хорошее понимание. По крайней мере, это наиболее хорошо контролируемый пример, когда разные команды пишут одну и ту же большую программу, о котором я слышал или читал.
- Никто (включая меня) не знал, что я буду измерять этот параметр, поэтому никто не пытался играть в метрики, все просто пытались закончить проект быстро и правильно.
- Все (за исключением проекта Python, о котором я расскажу позже) реализовывали программу с единственной целью пройти один и тот же автоматизированный набор тестов в одни и те же сроки, поэтому результаты не могут быть сильно искажены группами, решающими разные проблемы.
- Проект был выполнен в течение нескольких месяцев, с командой, и должен был постепенно расширяться и проходить как известные, так и неизвестные тесты. Это означает, что было полезно писать чистый понятный код.
- Кроме прохождения тестов курса, код не будет использоваться ни для чего другого, никто не будет его читать и, будучи компилятором для ограниченного подмножества Java в текстовый ассемблер, он не будет полезен.
- Никакие библиотеки, кроме стандартной библиотеки, не разрешены, и никакие хелперы для парсинга, даже если они есть в стандартной библиотеке. Это означает, что сравнение не может быть искажено мощными библиотеками компилятора, которые есть только у некоторых команд.
- Были не только публичные, но и секретные тесты. Они запускались один раз после окончательной сдачи. Это означало, что был стимул написать свой собственный тестовый код и убедиться, что компилятор надёжный, правильный и обрабатывает сложные пограничные ситуации.
- Хотя все участники — студенты, но я считаю их вполне компетентными программистами. Каждый по крайней мере два года проходил стажировку, в основном, в высокотехнологичных компаниях, иногда даже работал над компиляторами. Почти все они программируют в течение 7-13 лет и являются энтузиастами, которые много читают в интернете за рамками своих курсов.
- Сгенерированный код не учитывался, но учитывались файлы грамматики и код, который генерировал другой код.
Таким образом, я думаю, что количество кода обеспечивает приличное понимание того, сколько усилий потребуется для поддержки каждого проекта, если бы он был долгосрочным. Думаю, что не слишком большая разница между проектами также позволяет опровергнуть некоторых экстраординарные утверждения, которые я читал, например, что компилятор на Haskell будет более чем вдвое меньше C++ в силу языка.
Rust (основа для сравнения)
Я и один из моих товарищей раньше каждый написал более 10k строк на Rust, а третий коллега написал, возможно, 500 строк на каких-то хакатонах. Наш компилятор вышел в 6806 строк
wc -l, 5900 строк исходника (без пробелов и комментариев), и 220 КБ wc -c.Я обнаружил, что в других проектах эти пропорции примерно соблюдаются, с небольшими исключениями, которые я отмечу. Для остальной части статьи, когда я ссылаюсь на строки или сумму, я имею в виду
wc -l, но это не имеет значения (если я не замечаю разницы), и вы можете конвертировать с коэффициентом.Я написал другую статью с описанием нашего дизайна, который прошёл все публичные и секретные тесты. Он также содержит несколько дополнительных функций, которые мы сделали для удовольствия, а не для прохождения тестов, что, вероятно, добавило около 400 строк. Также в нём около 500 строк наших модульных тестов.
Haskell
В команду Haskell входило два моих друга, которые написали, возможно, пару тысяч строк Haskell каждый, плюс прочитали много онлайн-контента о Haskell и других подобных функциональных языках, таких как OCaml и Lean. У них был ещё один товарищ по команде, которого я не очень хорошо знал, но, похоже, сильный программист и раньше использовал Haskell.
Их компилятор составил 9750 строк по
wc -l, 357 КБ и 7777 строк кода (SLOC). У этой команды также единственные существенные различия между этими соотношениями: их компилятор в 1,4 раза больше нашего по строкам, в 1,3 раза по SLOC и в 1,6 раза по байтам. Они не реализовали никаких дополнительных функций, прошли 100% публичных и секретных тестов.Важно отметить, что включение тестов больше всего сказалось именно на этой команде. Поскольку они тщательно подошли к правильности кода, то включили 1600 строк тестов. Они поймали несколько пограничных ситуаций, которые наша команда не отловила, но просто эти случаи не проверялись тестами курса. Так что без тестов с обеих сторон (6,3 тыс. строк против 8,1 тыс. строк) их компилятор всего на 30% больше нашего.
Здесь я склоняюсь к байтам как более разумной мере сравнения объёма, потому что в проекте Haskell в среднем более длинные строки, поскольку у него нет большого количество строк из одной закрывающей скобки, и у них
rustfmt не разбивает однострочные цепочки функций на несколько строк.Покопавшись с одним из моих друзей по команде, мы придумали следующее объяснение этой разнице:
- Мы использовали рукописный лексический анализатор и метод рекурсивного спуска, а они — генератор на NFA и DFA и LR-парсер, а затем проход для преобразования дерева синтаксического анализа в AST (абстрактное синтаксическое дерево, более удобное представление кода). Это дало им существенно больше кода: 2677 строк по сравнению с нашим 1705, примерно на 1000 строк больше.
- Они использовали причудливый генерик AST, который переходил к различным параметрам типа, поскольку больше информации добавлялось в каждом проходе. Это и больше вспомогательных функций для перезаписи, вероятно, объясняют, почему их код AST примерно на 500 строк больше, чем наша реализация, где мы собираем с литералами struct и мутируем поля
Option<_>для добавления информации по мере прохождения.
- У них ещё около 400 строк кода при генерации, которые в основном связаны с большей абстракцией, необходимой для генерации и объединения кода чисто функциональным способом, где мы просто используем мутацию и запись строк.
Эти различия плюс тесты объясняют все различия в объёме. На самом деле наши файлы для свёртывания констант и разрешения контекста очень близки по размеру. Но всё равно остаётся некоторая разница в байтах из-за более длинных строк: вероятно, потому что требуется больше кода для перезаписи целого дерева на каждом проходе.
В итоге, отложив решения в области дизайна, по-моему, Rust и Haskell одинаково выразительны, возможно, с небольшим преимуществом Rust из-за способности легко использовать мутацию, когда это удобно. Было также интересно узнать, что мой выбор метода рекурсивного спуска и рукописный лексический анализатор окупились: это был риск, который противоречил рекомендациям и указаниям профессора, но я решил, что так легче и это правильно.
Поклонники Haskell возразят, что та команда, вероятно, не использовала в полной мере возможности Haskell, и если бы они лучше знали язык, то могли бы сделать проект с меньшим количеством кода. Согласен, кто-то вроде Эдварда Кметта может написать тот же компилятор в значительно меньшем объёме. Действительно, команда моего друга не использовала много причудливых суперпродвинутых абстракций и причудливых библиотек комбинаторов, таких как lens. Однако всё это сказывается на читаемости кода. Все люди в команде — опытные программисты, они знали, что Haskell способен на очень причудливые вещи, но решили не использовать их, потому что решили, что на их понимание потребуется больше времени, чем они сэкономят, и сделает код сложнее для понимания другими. Это кажется мне реальным компромиссом, а утверждение, что Haskell волшебно подходит для компиляторов, переходит в нечто вроде «Haskell требует чрезвычайно высокой квалификации для написания компиляторов, если вы не заботитесь о поддержке кода людьми, которые также не очень искусны в Haskell».
Ещё интересно отметить, что в начале каждого проекта профессор говорит, что студенты могут использовать любой язык, который работает на университетском сервере, но предупреждает, что команды на Haskell отличаются от остальных: у них самый большой разброс в оценках. Многие переоценивают свои способности и у команд на Haskell больше всего плохих оценок, хотя другие справляются отлично, как мои друзья.
С++
Затем я поговорил с моим другом из команды C++. Я знал только одного человека в этой команде, но C++ используется на нескольких курсах в нашем университете, поэтому, вероятно, у всех в команде был опыт C++.
Их проект состоял из 8733 строк и 280 КБ, не включая тестовый код, но включая около 500 строк дополнительных функций. Что делает его в 1,4 раза больше нашего кода без тестов, у которого тоже около 500 строк дополнительных функций. Они прошли 100% публичных тестов, но только 90% секретных тестов. Предположительно потому, что они не реализовали причудливые массивы vtables, требуемые спецификацией, которые занимают, возможно, 50-100 строк кода.
Я не очень глубоко копался в этих различиях по размеру. Предполагаю, это в основном объясняется:
- Они используют LR-парсер и рерайтер деревьев (tree rewriter) вместо метода рекурсивного спуска.
- Отсутствие типов sum и сопоставлений с образцом в C++, которые мы широко использовали и которые были очень полезны.
- Необходимость дублировать все сигнатуры в заголовочных файлах, чего нет в Rust.
Ещё мы сравнивали время компиляции. На моём ноутбуке чистая отладочная сборка нашего компилятора занимает 9,7 с, чистый релиз 12,5 с, а инкрементная отладочная сборка — 3,5 с. У моего друга не было таймингов под рукой для их билда C++ (используя parallel make), но он сказал, что цифры похожие, с оговоркой, что они помещают реализации множества небольших функций в заголовочные файлы, чтобы уменьшить дублирование сигнатур ценой более длительного времени (именно поэтому я не могу измерить чистые накладные расходы на строки в заголовочных файлах).
Python
Мой друг, очень хороший программист, решила сделать проект в одиночку на Python. Она также реализовала больше дополнительных функций (для удовольствия), чем любая другая команда, включая промежуточное представление SSA с распределением регистров и другими оптимизациями. С другой стороны, поскольку она работала в одиночку и реализовывала множество дополнительных функций, она уделяла наименьшее внимание качеству кода, например, бросая недифференцированные исключения для всех ошибок (полагаясь на бэктрейсы для отладки) вместо того, чтобы реализовать типы ошибок и соответствующие сообщения, как у нас.
Её компилятор состоял из 4581 строки и прошёл все публичные и секретные тесты. Она также реализовала больше дополнительных функций, чем любая другая команда, но трудно определить, сколько дополнительного кода это заняло, потому что многие из дополнительных функций были более мощными версиями простых вещей, которые всем нужно было реализовать, таких как свёртывание констант и генерация кода. Дополнительные функции, вероятно, составляют 1000-2000 строк, по крайней мере, поэтому я уверен, что её код по крайней мере вдвое выразительнее нашего.
Одна большая часть этого различия, вероятно, динамическая типизация. Только в нашем
ast.rs 500 строк определений типов, и ещё много типов, определённых в других местах компилятора. Мы также всегда ограничены самой системой типов. Например, нам нужна инфраструктура для эргономичного добавления новой информации в AST по мере прохождения и доступа к ней позже. В то время как в Python вы можете просто установить новые поля на узлах AST.Мощное метапрограммирование также объясняет часть разницы. Например, хотя она использовала LR-парсер вместо метода рекурсивного спуска, в её случае я думаю, что он занял меньше кода, потому что вместо прохода с перезаписью дерева её грамматика LR включала фрагменты кода Python для построения AST, которые генератор мог превратить в функции Python с помощью
eval. Часть причины, по которой мы не использовали LR-парсер, заключается в том, что построение AST без перезаписи дерева потребует много церемоний (создание либо файлов Rust, либо процедурных макросов), чтобы связать грамматику с фрагментами кода Rust.Другой пример мощи метапрограммирования и динамической типизации — 400-строчный файл
visit.rs, это в основном повторяющийся шаблонный код, реализующий визитора на куче структур AST. В Python это может быть короткая функция примерно на 10 строк, которая рекурсивно интроспектирует поля узла AST и посещает их (используя атрибут __dict__).Как поклонник Rust и статически типизированных языков в целом, я склонен отметить, что система типов очень полезна для предотвращения ошибок и для производительности. Необычное метапрограммирование также может затруднить понимание того, как работает код. Однако это сравнение удивило меня тем, что я не ожидал, что разница в количестве кода будет настолько большой. Если разница в целом действительно близка к необходимости писать в два раза больше кода, я все ещё думаю, что Rust подходящий компромисс, но всё-таки в два раза меньше кода — аргумент, и в будущем я склонен что-то сделать на Ruby/Python, если нужно просто быстро что-то построить в одиночку, а затем выбросить.
Rust (другая группа)
Cамое интересное для меня сравнение было с моим другом, который тоже делал проект в Rust с одним товарищем по команде (которого я не знал). У моего друга был хороший опыт Rust. Он внёс вклад в разработку компилятора Rust и много читал. О его товарище ничего не знаю.
Их проект состоял из 17 211 необработанных строк, 15k исходных строк и 637 КБ, не включая тестовый код и сгенерированный код. У него не было дополнительных функций, и он прошёл только 4 из 10 секретных тестов и 90% публичных тестов на генерацию кода, потому что у них не хватило времени перед дедлайном для реализации более причудливых частей спецификации. Их программа в три раза больше нашей, написана на том же языке, и с меньшей функциональностью!
Этот результат был действительно удивителен для меня и затмевал все различия между языками, которые я исследовал до сих пор. Поэтому мы сравнили списки размеров файлов
wc -l, а также проверили, как каждый из нас реализовал некоторые конкретные вещи, которые вылились в разный размер кода.Похоже, всё сводится к последовательному принятию различных дизайнерских решений. Например, их фронтенд (лексический анализ, синтаксический анализ, построение AST) занимает 7597 строк против наших 2164. Они использовали лексический анализатор на DFA и синтаксический анализатор LALR(1), но другие группы делали подобные вещи без такого количества кода. Глядя на их weeder-файл, я заметил ряд дизайнерских решений, которые отличались от наших:
- Они решили использовать полностью типизированное дерево синтаксического анализа вместо стандартного однородного дерева синтаксического анализа на основе строк. Вероятно, это потребовало намного больше определений типов и дополнительного кода преобразования на этапе синтаксического анализа или более сложного генератора синтаксического анализа.
- Они использовали реализации трейтов
tryfromдля преобразования между типами дерева синтаксического анализа и типами AST при проверке их правильности. Это приводит к множеству 10-20-строчных блоковimpl. Мы для этого использовали функции, возвращающие типыResult, что генерирует меньше строк, а также немного освобождает нас от структуры типов, упрощая параметризацию и повторное использование. Некоторые вещи, которые для нас были однострочными ветвямиmatch, у них были представляли собой 10-строчные блокиimpl.
- Наши типы структурированы так, чтобы уменьшить копипаст. Например, они использовали отдельные поля
is_abstract,is_nativeиis_static, где код проверки ограничений необходимо было скопировать дважды: один раз для void-типизированных методов и один раз для методов с типом return, с небольшими изменениями. В то время как у насvoidбыл просто специальным типом, и мы придумали таксономию модификаторов сmodeиvisibility, которые применяли ограничения на уровне типа, а ошибки ограничений были сгенерированы по умолчанию для оператора match, который перевёл наборы модификаторов вmodeиvisibility.
Я не смотрел на код проходов анализа их компилятора, но они тоже велики. Я поговорил со своим другом, и, похоже, они не реализовали ничего похожего на инфраструктуру визиторов, как у нас. Предполагаю, что это, наряду с некоторыми другими меньшими различиями в дизайне, объясняет разницу в размере этой части. Визитор позволяет нашим проходам анализа обращать внимание только на части AST, в которых они нуждались, вместо того, чтобы сопоставлять шаблон по всей структуре AST. Это экономит много кода.
Их часть для генерации кода состоит из 3594 строк, а наша — 1560. Я посмотрел на их код и кажется, что почти вся разница в том, что они выбрали промежуточную структуру данных для инструкций ассемблера, где мы просто использовали форматирование строк для прямого вывода ассемблера. Им пришлось определять типы и функции вывода для всех используемых инструкций и типов операндов. Это также означало, что построение инструкций ассемблера заняло больше кода. Где у нас был оператор форматирования с короткими инструкциями, такими как
mov ecx, [edx], им нужен был гигантский оператор rustfmt, разбитый на 6 строк, которые строили инструкцию с кучей промежуточных вложенных типов для операндов, включающих до 6 уровней вложенных скобок. Мы также могли выводить блоки связанных инструкций, таких как преамбула функции, в одном операторе форматирования, где им пришлось указывать полную конструкцию для каждой инструкции.Наша команда рассматривала возможность использования такой абстракции, как у них. Было проще иметь возможность либо выводить текстовую сборку, либо непосредственно выдавать машинный код, однако это не являлось требованием курса. То же самое можно было сделать с меньшим количеством кода и лучшей производительностью, используя трейт
X86Writer с методами вроде push(reg: Register). Мы учитывали также, что это могло бы упростить отладку и тестирование, но мы поняли, что просмотр сгенерированного текстового ассемблера на самом деле легче читать и тестировать с помощью тестирования моментальных снимков, если либерально вставлять комментарии. Но мы (видимо, правильно) предсказали, что это займёт много дополнительного кода, и не было никакой реальной выгоды, учитывая наши реальные потребности, поэтому мы не беспокоились.Хорошо сравнить это с промежуточным представлением, которое команда C++ использовала в качестве дополнительной функции, что отняло у них всего 500 дополнительных строк. Они использовали очень простую структуру (для простых определений типов и кода построения), которая использовала операции, близкие к тому, что требовала Java. Это означало, что их промежуточное представление было намного меньше (и, следовательно, требовало меньше кода построения), чем результирующий ассемблер, поскольку многие языковые операции, такие как вызовы и приведения, расширялись во многие ассемблерные инструкции. Они также говорят, что это действительно помогло отладке, так как вырезало много мусора и улучшала читаемость. Представление более высокого уровня также позволило сделать некоторые простые оптимизации на их промежуточном представлении. Команда C++ придумала действительно хороший дизайн, который принёс им гораздо больше пользы с гораздо меньшим количеством кода.
В целом, похоже, что общая причина трёхкратной разницы в объёме обусловлен последовательным принятием различных проектных решений как больших, так и малых в направлении большего количества кода. Они реализовали ряд абстракций, которые мы не сделали — они добавили больше кода, и пропустили некоторые из наших абстракций, которые уменьшают количество кода.
Этот результат действительно удивил меня. Я знал, что дизайнерские решения имеют значение, но я бы не догадался заранее, что они приведут к каким-либо различиям такого размера, учитывая, что я только обследовал людей, которых я считаю сильными компетентными программистами. Из всех результатов сравнения это самый значительный для меня. Наверное, мне помогло, что я много читал о том, как писать компиляторы, прежде чем пошёл на этот курс, поэтому мог воспользоваться умными проектами, которые другие люди придумали и нашли хорошо работающими, вроде визиторов AST и метода рекурсивного спуска, хотя их не преподавали у нас на курсе.
Что действительно заставило меня задуматься — это стоимость абстракции. Абстракции могут облегчить расширение в будущем или защитить от некоторых типов ошибок, но их нужно учитывать с учётом того, что вы можете получить в три раза больше кода для понимания и рефакторинга, в три раза больше возможных мест для ошибок и меньше времени на тестирование и дальнейшую разработку. Наш учебный курс отличался от реального мира: мы точно знали, что никогда не коснёмся кода после разработки, это исключает преимущества упреждающей абстракции. Однако, если мне пришлось бы выбрать, какой компилятор расширить произвольной функцией, которую вы скажете позже, я бы выбрал наш, даже не учитывая своё знакомство с ним. Просто потому что в нём намного меньше кода, который нужно понять, и я мог бы потенциально выбрать лучшую абстракцию для требований (например, промежуточное представление команды C++), когда буду знать конкретные требования.
Также в моём представлении укрепилась таксономия абстракций: есть те, которые сокращают код, учитывая только текущие требования, как наш шаблон визитора, а есть абстракции, которые добавляют код, но обеспечивают преимущества расширяемости, отладочности или корректности.
Scala
Я также поговорил с другом, который в предыдущем семестре делал проект на Scala, но проект и тесты были точно такими же. Их компилятор состоял из 4141 строки и ~160 КБ кода, не считая тестов. Они прошли 8 из 10 секретных тестов и 100% открытых тестов и не реализовали никаких дополнительных функций. Таким образом, по сравнению с нашими 5906 строками без дополнительных функций и тестов, их компилятор меньше на 30%.
Одним из факторов дизайна в малого объёма стал другой подход к парсингу. Курс позволял использовать инструмент командной строки для генератора таблиц LR. Его никто не использовал, кроме этой команды. Это избавило их от необходимости реализовывать генератор таблиц LR. Им также удалось избежать написания грамматики LR с помощью 150-строчного скрипта Python, который скрапил веб-страницу грамматики Java, которую они нашли в интернете, и переводил её во входной формат генератора. Им всё ещё нужно было сделать какое-то дерево в Scala, но в целом этап парсинга составил 1073 строк по сравнению с нашими 1443, хотя наш метод градиентного спуска здесь давал преимущество по объёму по сравнению со всеми другими командами.
Остальная часть их компилятора была тоже меньше нашей, без каких-то очевидных больших различий в дизайне, хотя я не копался в коде. Подозреваю, что это связано с различиями в выразительности Scala и Rust. Scala и Rust имеют схожие функциональные возможности программирования, полезные для компиляторов, такие как сопоставление шаблонов, но управляемая память Scala экономит код, необходимый для работы borrow checker в Rust. Кроме того, в Scala более разнообразный синтаксический сахар, чем в Rust.
OCaml
Поскольку все члены нашей команды проходят стажировку в Jane Street (технологическая компания вычислительного трейдинга — прим. пер.), мне было особенно интересно посмотреть на результат других бывших стажёров Jane Street, которые выбрали для написания компилятора язык OCaml.
Их компилятор составлял 10914 строк и 377 КБ, включая небольшое количество тестового кода и никаких дополнительных функций. Они прошли 9/10 секретных тестов и все публичные тесты.
Как и другие группы, похоже, что основная разница в размерах связана с использованием для синтаксического анализа LR-парсера и перезаписи дерева, а также конвейера преобразования regex->NFA->DFA для лексического анализа. Их фронтенд (лексический анализ, синтаксический анализ, конструкция AST) составляет 5548 строк, а наш — 2164, с аналогичными соотношениями для байтов. Они также использовали для своего парсера тестирование с ожиданием, что похоже на наши snapshot-тесты, которые помещают ожидаемый вывод за пределы кода, поэтому их тесты парсера составляли ~600 строк из общего числа, а наши — около 200.
Это оставляет для остальной части компилятора 5366 строк у них (461 строка из которых — интерфейсные файлы с объявлениями типов) и 4642 у нас, разница всего на 15%, если считать их интерфейсные файлы, и практически одинаковый размер, если не считать. Похоже, что, не считая наших дизайнерских решений по парсингу, Rust и OCaml кажутся одинаково выразительными, за исключением того, что OCaml нужны интерфейсные файлы, а Rust — нет.
Заключение
В целом я очень рад, что сделал это сравнение, я многому научился и много раз удивлялся. Думаю, общий вывод заключается в том, что дизайнерские решения имеют гораздо большее значение, чем язык, но язык имеет значение, поскольку даёт вам инструменты для реализации разного дизайна.
