Как работает компилятор Haskell?

Question

Где я могу получить некоторые документы / документы / что-либо, что описывает, как на самом деле работает компилятор Haskell?Я прочитал довольно много документов GHC, но прекратил после головной боли.Таким образом, что-то, что не требует доктора философии, чтобы понять это и не написано в стиле «Вы должны быть уже знакомы с ним», было бы предпочтительным.Это не проблема, если она действительно длинная и требует некоторого времени, чтобы понять это.

PS: Самое интересное было бы что-то о GHC, но все в порядке.

Answer 1

Вы можете получить ответ изо рта лошади!Саймон Пейтон Джонс (мастер GHC) написал книгу, объясняющую, как реализовать функциональные языки программирования.Он доступен бесплатно в Интернете, поскольку теперь он не печатается: http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/

Конечно, GHC продолжил работу после того, как книга была написана, но все еще очень актуальна.

Answer 2

Вы ищете подробности, особенно о компиляции отложенной оценки? Есть книга Саймона Пейтон-Джонса, упомянутая Максом Болингброком, а также книга, подробно описывающая реализацию Clean в Интернете:

http://wiki.clean.cs.ru.nl/Functional_Programming_and_Parallel_Graph_Rewriting

Если у вас есть университетская принадлежность и вы хотите что-то меньшее, вы можете попытаться получить эти книги (Henderson & Diller, безусловно, уже не в печати):

Антони Диллер "Языки функций компиляции" ISBN 0 471 92027 4

Питер Хендерсон "Применение и реализация функционального программирования" ISBN 0-13-331579-7

AJT Davie "Введение в системы функционального программирования с использованием Haskell" ISBN 0 521 27724 8

У Diller есть полный компилятор для ленивого языка (реализован в Pascal) через сокращение комбинатора. Это была техника реализации, изобретенная Дэвидом Тернером для SASL. У Хендерсона есть много частей компилятора для LISPkit, миниатюрного, ленивого варианта Lisp. Дэви подробно описывает механизм компиляции ленивого языка, например, есть описание STG, которое намного короче, чем книга Саймона Пейтона-Джонса (STG - это SPJ абстрактной машины, используемая для Haskell).

Разработчики Clean имеют достаточно информации о внедрении SAPL (Simple Applicative Language), если вы посмотрите их список публикаций:

https://clean.cs.ru.nl/Publications

Наконец, существует множество документов, документирующих аспекты UHC (и EHC) Utrecht Haskell Compiler. Я думаю, что большая часть информации о том, как организован компилятор (с помощью грамматик атрибутов и «Shuffle») и как реализованы системы типов (в EHC существуют разные уровни типов систем), а не о том, как внутренняя «компиляция» работает.

Answer 3

Компиляторы - огромная тема, и было бы невозможно полностью объяснить их здесь. Но вот обзор для общего компилятора. Надеемся, что это даст вам некоторое понимание, которое может сделать чтение вещей, в частности, о GHC, немного легче для понимания.

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

Первое преобразование - это превращение обычного текста во что-то более легкое для прохождения. Само это обычно делится на 2 части:

Лексический анализ или токенизация - Преобразование простого текста в небольшие куски (обычно операторы, идентификаторы, литералы и т. Д.).

Синтаксический анализ или анализ - Превращение этих маленьких кусочков в древовидную структуру. (обычно AST, абстрактное синтаксическое дерево )

Следующий этап - семантический анализ. На этом этапе компилятор обычно добавляет информацию в AST (например, информацию о типе) и создает таблицу символов. На этом мы заканчиваем интерфейс.

Следующее преобразование превращает AST в IR, промежуточное представление . Как правило, в настоящее время форма SSA, одно статическое назначение .

Затем оно оптимизируется с помощью постоянного распространения, анализа мертвого кода, векторизации и т. Д.

Последнее преобразование - генерация кода. Преобразование ИК в машинный код. Это может быть очень сложно. Это также иногда называют понижением.

Для получения дополнительной информации я рекомендую эту страницу википедии .

Answer 4

К сожалению, я подозреваю, что то, что вы ищете, не существует.Теория компиляторов и теория формальных языков являются достаточно сложными темами в области компьютерных наук, и Хаскелл ни в коем случае не является отправной точкой.

Во-первых, вы, вероятно, должны получить хорошее обоснование:

• Лексический анализ: http://en.wikipedia.org/wiki/Lexical_analysis
• Анализ: http://en.wikipedia.org/wiki/Parsing#Programming_languages
  • Контекстно-зависимые (и другие) грамматические системы (CFG, BNF)
• Генерация кода: http://en.wikipedia.org/wiki/Code_generation_(compiler)

Я подозреваю, что для объяснения чего-либо о внутренностях Хаскелла потребуется значительно лучшее понимание вышеупомянутых тем, чем, скажем, Си.

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

Answer 5

Википедия имеет хороший - читаемый - обзор внутренних органов GHC (аналогично объяснению @ dan_waterworth, но специфично для Haskell и GHC):

http://en.wikipedia.org/wiki/Glasgow_Haskell_Compiler#Architecture

Answer 6

Одна из лучших статей на эту тему, которую я прочитал:

• Компилятор Glasgow Haskell Саймон Марлоу и Саймон Пейтон-Джонс. Архитектура приложений с открытым исходным кодом.