Рейтинг@Mail.ru
[Войти] [Зарегистрироваться]

Наши друзья и партнеры

UnixForum
купить дешевый 
компьютер родом из Dhgate.com




Lines Club

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

Библиотека сайта или "Мой Linux Documentation Project"

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

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

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

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

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

  • Проверка типов до выполнения приведения означает, что программа проверки типов должна иметь дело непосредственно с очень большим синтаксисом языка Haskell, поэтому программа проверки типов должна рассматривать большое количество вариантов. Если мы сначала преобразуем исходный вариант в (бестиповый вариант) Core, то можно надеяться, что программа проверки типов станет гораздо меньше.
  • С другой стороны, проверка типов после выполнения приведения налагает значительные новые обязательства: приведение, которое не влияет ни на какие программы, является корректным с точки зрения типов. В конце концов, приведение подразумевает преднамеренную потерю информации. Вероятно, что в 95% случаев никаких проблем не будет, но любая возникающая здесь проблема требует некоторого компромисса в разработке Core с тем, чтобы сохранить некоторую дополнительную информацию.
  • Самым серьезным является то, что проверка типов в программе после приведения очень сильно усложняет выдачу сообщения об ошибках со ссылкой на оригинальный текст программы, а не на его (иногда сложную) версию, полученную после приведения программы.

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

  1. Генерация ограничений: выполняется обход синтаксического дерева исходного кода и генерируется коллекция ограничений типов. На этом шаге рассматривается полный синтаксис языка Haskell, но это очень простой код и в нем легко добавлять новые случаи.
  2. Решения, относящиеся к ограничениям: принимаются решения относительно каждого созданного ограничения. Это именно то место, где используется движок вывода типов, но он не зависит от синтаксиса исходного языка и был бы точно такой же для существенно меньшего или гораздо большего языка.

В целом, выбор варианта, когда проверка типов осуществляется перед приведением программы, дает больший выигрыш. Да, при этом увеличивается количество строк кода в программе проверки типов, но это простые строки. Исчезает ситуация, когда одному и тому же типу данных присваивается две противоречивые роли, и движок вывода типов становится менее сложным и его легче изменять. Кроме того, сообщения компилятора 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, с которого мы начали.

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

  • Многие запросы, для которых требуется поиск в таблице символов, сводятся к доступу к простому поле, что очень хорошо для обеспечения эффективности и ясности кода.
  • Нет необходимости иметь дополнительные таблицы символов, поскольку в абстрактном синтаксическом дереве уже есть вся информация.
  • Меньше накладные расходы по затратам памяти: все экземпляры одной и той же переменной совместно используют одну и ту же структуру данных, и для таблицы не нужно отводить дополнительную память.
  • Трудности возникают только в случае, когда нам нужно изменить какую-нибудь информацию, связанную с переменной. Это то, где у таблицы символов есть преимущество: мы просто изменяем запись в таблице символов. В компиляторе GHC мы должны обойти абстрактное синтаксическое дерево и заменить все экземпляры старой переменной на новую; более того, в блоке, с помощью которого происходит упрощение программы, это делается регулярно, поскольку ему необходимо обновлять определенную информацию о каждой переменной, относящуюся к вопросам оптимизации.

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

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

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

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

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

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

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

  • Когда компилируется модуль Lib.hs на языке Haskell, то компилятор GHC создает объектный код в файле Lib.o и «интерфейсный файл» в Lib.hi. В этом интерфейсном файле находится информация обо всех функциях, которые экспортируются в Lib, в том числе указываются как их типы, так и, если функции достаточно малы, и их определения.
  • Когда компилируется модуль Client.hs, в котором импортируется библиотека Lib, компилятор GHC читает интерфейс Lib.hi. Таким образом, если в Client вызывается функция Lib.f, определенная в Lib, то компилятор GHC может использовать информацию, имеющуюся в Lib.hi, для того, чтобы вставить в код функцию Lib.f.

По умолчанию компилятор 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 и, то же время, позволит использовать некоторые варианты межмодульной оптимизации.


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


Эта статья еще не оценивалась
Вы сможете оценить статью и оставить комментарий, если войдете или зарегистрируетесь.
Только зарегистрированные пользователи могут оценивать и комментировать статьи.

Комментарии отсутствуют