Учебник по Haskell

Иногда ленивые вычисления не эффективны по расходу памяти. Это происходит когда выражение состоит

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

борьбы с ленью. Это функция seq, энергичные образцы и энергичные типы данных.

Функция seq:

seq :: a -> b -> b

Сначала приводит к слабой заголовочной форме свой первый аргумент, а затем возвращает второй.

Взрывные образцы выполняют те же функции, но они используются в декомпозиции аргументов или в объ-

явлении типа.

9.6 Упражнения

• Потренируйтесь в понимании того как происходят ленивые вычисления. Вычислите на бумаге следу-

ющие выражения (если это возможно):

– sum $ take 3 $ filter (odd . fst) $ zip [1 .. ] [1, undefined, 2, undefined, 3, undefined,

undefined]

– take 2 $ foldr (+) 0 $ map Succ $ repeat Zero

– take 2 $ foldl (+) 0 $ map Succ $ repeat Zero

• Функция seq приводит первый аргумент к СЗНФ, убедитесь в этом на таком эксперименте. Определите

тип:

data TheDouble = TheDouble { runTheDouble :: Double }

Он запаковывает действительные числа в конструктор. Определите для этого типа экземпляр класса

Num и посмотрите как быстро будет работать функция sum’ на таких числах. Как изменится скорость

если мы заменим в определении типа data на newtype? как изменится скорость, если мы вернём data,

но сделаем тип TheDouble энергичным? Поэкспериментируйте.

• Посмотрите на приведение к СЗНФ в энергичных типах данных. Определите два типа:

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).

Стек – это очередь с принципом работы “последним пришёл, первым ушёл”. Стек можно представить как

стопку книг. У нас есть две операции: положить книгу наверх, и снять верхнюю книгу. Стек очень удобен

для переключения контекстов вычисления. Представьте, что у нас есть функция, которая внутри вызывает

другую функцию, а та следующую. Находясь в верхней функции при заходе во вторую мы сохраняем контекст

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

вычисления. Как только мы доходим до третьей функции, мы “кладём на стопку сверху” контекст второй

функции, как только третья функция вычислена, мы обращаемся к стеку и снимаем с него контекст второй

функции продолжаем вычислять и как только вторая функция заканчивается снова обращаемся к стеку. А