• Посмотрите на приведение к СЗНФ в энергичных типах данных. Определите два типа:
data Strict a = Strict ! a
data Lazy
a = Lazy
a
И повычисляйте в интерпретаторе различные значения с undefined, const, ($! ) и seq:
> seq (Lazy undefined) ”Hi”
> seq (Strict undefined) ”Hi”
> seq (Lazy (Strict undefined)) ”Hi”
> seq (Strict (Strict (Strict undefined))) ”Hi”
• Посмотрите на такую функцию вычисления суммы всех чётных и нечётных чисел в списке.
Упражнения | 153
sum2 :: [Int] -> (Int, Int)
sum2 = iter (0, 0)
where iter c
[]
= c
iter c
(x:xs) = iter (tick x c) xs
tick :: Int -> (Int, Int) -> (Int, Int)
tick x (c0, c1) | even x
= (c0, c1 + 1)
| otherwise = (c0 + 1, c1)
Эта функция очень медленная. Кто-то слишком много ленится. Узнайте кто, и ускорьте функцию.
154 | Глава 9: Редукция выражений
Глава 10
Реализация Haskell в GHC
На момент написания этой книги основным компилятором Haskell является GHC. Остальные конкуренты
отстают очень сильно. Отметим компилятор Hugs (его хорошо использовать для демонстрации Haskell на
чужом компьютере, если вы не хотите устанавливать тяжёлый GHC). В этой главе мы обзорно рассмотрим
как язык Hаskell реализован в GHC. GHC – как ни парадоксально это звучит, это самая успешная программа
написанная на Haskell. GHC уже двадцать лет. Отметим основных разработчиков. Это Саймон Пейтон Джонс
(Simon Peyton Jones) и Саймон Марлоу (Simon Marlow).
GHC состоит из трёх частей. Это сам компилятор, основные библиотеки языка (такие как Prelude) и низ-
коуровневая система вычислений (она отвечает за управление памятью, потоками, вычисление примитив-
ных операций). Весь GHC кроме системы вычислений написан на Haskell. Система вычислений написана на
C. Компилятор принимает набор файлов с исходным кодом (а также возможно объектных и интерфейсных
файлов) и генерирует код низкого уровня. Система вычислений низкого уровня используется в этом коде
как библиотека. Она статически подключается к любому нативному коду, который генерируется GHC. Далее
мы сосредоточимся на изучении компилятора.
Но перед этим давайте освежим в памяти (или узнаем) несколько терминов. У нас есть код на Haskell, что
значит перевести в код низкого уровня? Код низкого уровня представляет собой набор инструкций, которые
изменяют значения в памяти компьютера. Изменение значений происходит с помощью базовых операций,
которые выполняются в процессоре компьютера. Память компьютера представляет собой ленту ячеек. У каж-
дой ячейки есть адрес и содержание. По адресу мы можем читать данные из ячейки и записывать их туда. Эти
операции также выполняются с помощью инструкций. Мы будем делить память на стек (stack), кучу (heap)
и регистры (registers).
Стек – это очередь с принципом работы “последним пришёл, первым ушёл”. Стек можно представить как
стопку книг. У нас есть две операции: положить книгу наверх, и снять верхнюю книгу. Стек очень удобен
для переключения контекстов вычисления. Представьте, что у нас есть функция, которая внутри вызывает
другую функцию, а та следующую. Находясь в верхней функции при заходе во вторую мы сохраняем контекст
внешней функции в стеке. Контекст – это та информация, которая нужна нам для того, чтобы продолжить
вычисления. Как только мы доходим до третьей функции, мы “кладём на стопку сверху” контекст второй
функции, как только третья функция вычислена, мы обращаемся к стеку и снимаем с него контекст второй
функции продолжаем вычислять и как только вторая функция заканчивается снова обращаемся к стеку. А
там сверху уже лежит контекст самой первой функции. Мы можем продолжать вычисления. Так происходит
вычисление вложенных функций в императивных языках программирования.
В куче мы храним разные данные. Данные бывают статическими (они нужны нам на протяжении выполне-
ния всей программы) и динамическими (время жизни динамических данных заранее неизвестно, например
это могут быть отложенные вычисления, мы не знаем когда ни нам понадобятся). У кучи также две опера-
ции: выделить блок памяти, эта операция принимает размер блока и возвращает адрес, по которому удалось
выделить память, и освободить память по указанному адресу. Регистры находятся в процессоре. В них можно
записывать и читать данные, при этом операции обращения к регистрам будут происходить очень быстро.
Посмотрим как GHC справляется с переводом процесса редукции синонимов на язык понятный нашему
компьютеру. Язык обновления стека и кучи. Это большая и трудная глава, читайте не спеша. Если покажется
совсем трудно – пропустите, вернётесь потом, когда захочется писать не только красивые, но и эффективные
программы.
10.1 Этапы компиляции
Рассмотрим этапы компиляции программы (рис. 10.1).
На первых трёх этапах происходит проверка ошибок. Сначала мы строим синтаксическое дерево про-
граммы. Если мы нигде не забыли скобки, не ошиблись в простановке ключевых слов, то этот этап успешно
| 155
Файл .hs
Построение синтаксического дерева
Разрешение имён
Проверка типов
Устранение синтаксического сахара
Core
Упрощение Core
Генерация кода для ghci
STG
Генерация Cmm
C
Native
LLVM
Рис. 10.1: Этапы компиляции
завершится. Далее мы приписываем ко всем функциям их полные имена. Дописываем перед всеми опреде-
лениями имя модуля, в котором они определены. Обычно на этом этапе нам сообщают о том, что мы забыли
определить какую-нибудь функцию, часто это связано с простой опечаткой. Следующий этап – самый важ-
ный. Происходит вывод типов для всех значений и проверка программы по типам. Блок кода, отвечающий
за проверку типов, является самым большим в GHC. Haskell имеет очень развитую систему типов. Многих
возможностей мы ещё не коснулись, часть из них мы рассмотрим в главе 17. Допустим, что мы исправили
все ошибки связанные с типами, тогда компилятор начнёт переводить Haskell в Core.
Core – это функциональный язык программирования, который является сильно урезанной версией
Haskell. Помните мы говорили, что в Haskell поддерживается несколько стилей (композиционный и декла-
ративный). Что хорошо для программиста, не очень хорошо для компилятора. Компилятор устраняет весь
синтаксический сахар и выражает все определения через простейшие конструкции языка Core. Далее проис-
ходит серия оптимизаций языка Core. На дереве описания программы выполняется серия функций типа Core
-> Core. Например происходит замена вызовов коротких функций на их правые части урвнений (встраивание
или inlining), выражения, которые проводят декомпозицию в case-выражениях по константам, заменяются
на соответствующие этим константам выражения. По требованию GHC может провести анализ строгости
(strictness analysis). Он заключается в том, что GHC ищет аргументы функций, которые могут быть вычисле-
ны более эфективно с помощью вычисления по значению и расставляет анотации строгости. И многие многие
другие оптимизации кода. Все они представлены в виде преобразования синтаксического дерева программы.
Также этот этап называют упрощением программы.
После этого Core переводится на STG. Это функциональный язык, повторяющий Core. Он содержит допол-
нительную информацию, которая необходима низкоуровневым бибилиотекам на этапе вычисления програм-
мы. Затем из STG генерируется код языка C–. Это язык низкого уровня, “портируемый ассемблер”. На этом
