Компилятор Glasgow Haskell

Глава 5 из книги "Архитектура приложений с открытым исходным кодом", том 2.

Оригинал: The Glasgow Haskell Compiler
Авторы: Simon Marlow и Simon Peyton-Jones
Перевод: Н.Ромоданов

Проверка типов исходного языка

Одно интересное проектное решение связано с тем, должна ли проверка типов осуществляться до или после приведения исходного языка к языку Core. Компромиссы, таковы:

Большинство компиляторов выполняет проверку типов после приведения программы, но для компилятора GHC мы сделали иной выбор: мы делаем проверку типов для полного синтаксиса исходного языка Haskell, а затем для полученного результата осуществляем приведение. Кажется, что добавлять новые синтаксические конструкции станет сложно, но (следуя французской школе разработки компиляторов) мы структурировали движок вывода типов таким образом, что это делается достаточно просто. Вывод типов состоит из двух частей:

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

Без таблиц символов

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

В компиляторе GHC мы используем таблицы символов довольно скупо — главным образом при переименовании и проверке типов. Там, где это возможно, мы используем альтернативные стратегии: переменная является структурой данных, в которой содержится вся информация о самой переменной. Действительно, когда мы проходим через структуру данных переменной, то можем получить большое количество информации: из переменной мы можем узнать ее тип, в котором есть конструкторы типа, которые содержат конструкторы данных, в которых самих есть типы данных, и так далее. Например, вот некоторые типы данных компилятора GHC (сильно сокращенный и упрощенный вариант):

data Id      = MkId Name Type
  data Type    = TyConApp TyCon [Type]
               | ....
  data TyCon   = AlgTyCon Name [DataCon]
               | ...
  data DataCon = MkDataCon Name Type ...

Идентификатор Id содержит свой тип Type. Тип Typ может быть применением конструктора типа к некоторым аргументам (например, Maybe Int), в этом случае он содержит тип TyCon. Tип TyCon может быть алгебраическим типом данных, в этом случае в нем указывается список его конструкторов данных. В каждом конструкторе DataCon есть свой собственный тип Type, о котором, конечно, упоминается в типе TyCon. И так далее. Все составляющие структуры тесно взаимосвязаны. В самом деле может быть цикл: тип данных TyCon может содержать конструктор DataCon, в котором есть тип Type, в которое содержится тот самый тип TyCon, с которого мы начали.

В таком подходе есть ряд преимуществ и недостатков:

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

Межмодульная оптимизация

Функциональные языки поощряют программиста писать небольшие определения. Например, определение && из стандартной библиотеки выглядит следующим образом:

(&&) :: Bool -> Bool -> Bool
True && True = True
_    && _    = False

Если при каждом использовании такой функции действительно потребуется вызов функции, то эффективность будет ужасной. Одним из решений является заставить компилятор обрабатывать некоторые функции специальным образом, другое решение состоит в использовании препроцессора, который заменит вызов «call» прямой вставкой кода в строку (inline code). Все эти решения неудовлетворительны в той или иной форме, тем более, что настолько очевидно другое решение: просто вставить функцию. «Вставить функцию» означает замену вызова функции на копию тела функции с подстановкой соответствующих экземпляров ее параметров.

В компиляторе GHC мы систематически использовали этот подход [PM02]. В компилятор практически ничего не встроено. Вместо этого, мы для того, чтобы устранить накладные расходы, как можно больше определяем все в библиотеках и агрессивно используем вставки в код. Это означает, что программисты могут определять свои собственные библиотеки, которые будут вставляться в код и будут оптимизироваться, а также те библиотеки, которые приходят вместе с компилятором GHC.

Следствием является то, что в компиляторе GHC должна быть возможность делать в код межмодульные вставки и даже межпакетные вставки. Идея проста:

По умолчанию компилятор GHC будет показывать определение функции в интерфейсном файле только в том случае, если функция «маленькая» (есть флаги, контролирующие размер этого порога). Но мы также поддерживаем параметр INLINE Pragma, который указывает компилятору GHC в любом случае вставлять следующим образом определение везде, где используется вызов, причем независимо от его размера:

foo :: Int -> Int 
{-# INLINE foo #-}
foo x = <некоторое большое выражение>

Кросс-модульная вставка в код является абсолютно необходимым средством для получения супер-эффективных библиотек, но это имеет свою цену. Если автор обновляет свою библиотеку, то недостаточно перекомпоновать файл Client.o с новой библиотекой Lib.o, поскольку в Client.o есть фрагменты старой библиотеки Lib.hs, которые вставлены непосредственно в код и которые могут оказаться несовместимыми с новой библиотекой. Другой способ — это указать, что ABI (Application Binary Interface) библиотеки Lib.o был изменен так, что требуется перекомпиляция клиентских модулей.

На самом деле, единственным способом компиляции кода, сгенерированного с фиксированным предсказуемым интерфейсом ABI, является отключение межмодульной оптимизации, а это, как правило, слишком высокая цена, чтобы заплатить за совместимость с ABI. У пользователей, работающих с компилятором GHC обычно есть весь исходный код, поэтому перекомпиляция, как правило, не является проблемой (и, как мы далее узнаем, пакет system создан именно для такого режима работы). Тем не менее, есть ситуации, когда с практической точки зрения перекомпиляция не подходит: например, распространение исправлений ошибок в библиотеках, которые поставляются в двоичном дистрибутиве ОС. В будущем, как мы надеемся, возможно удастся найти компромиссное решение, которое позволит сохранить совместимость с ABI и, то же время, позволит использовать некоторые варианты межмодульной оптимизации.

---

Продолжение статьи: Средства расширяемости

---

---