type FilePath = String
-- чтение файла
readFile
:: FilePath -> IO String
-- запись строки в файл
writeFile
:: FilePath -> String -> IO ()
-- добавление строки в конеци файла
appendFile
:: FilePath -> String -> IO ()
Напишем программу, которая сначала запрашивает путь к файлу. Затем показывает его содержание. За-
тем запрашивает ввод строки из терминала. А после этого добавляет текст в конец файла.
main = msg1 >> getLine >>= read >>= append
where read
file = readFile file >>= putStrLn >> return file
append file = msg2 >> getLine >>= appendFile file
msg1
= putStr ”input file: ”
msg2
= putStr ”input text: ”
В самом левом вызове getLine мы читаем имя файла, затем оно используется в локальной функции
read. Там мы читаем содержание файла (readLine), выводим его на экран (putStrLn), и в самом конце мы
возвращаем из функции имя файла. Оно нам понадобится в следующей части программы, в которой мы
будем читать новые записи и добавлять их в файл. Новая запись читается функцией getLine в локальной
функции append.
Сохраним в модуле File. hs и посмотрим, что у нас получилось. Перед этим создадим в текущей дирек-
тории тестовый пустой файл под именем test. В него мы будем добавлять новые записи.
*Prelude> :l File
[1 of 1] Compiling File
( File. hs, interpreted )
Ok, modules loaded: File.
*File> main
input file: test
input text: Hello!
*File> main
input file: test
Hello!
input text: Hi)
*File> main
input file: test
Hello!Hi)
В самом начале наш файл пуст, поэтому сначала мы видим пустую строчку вместо содержания, но потом
мы начинаем добавлять в него новые записи.
Ленивое и энергичное чтение файлов
С чтением файлов связана одна тонкость. Функция readFile читает содержимое файла в ленивом стиле.
Подробнее о ленивой стратегии вычислений мы поговорим в следующей главе. По ка отметим, что readFile
не читает следующую порцию файла до тех пор пока она не понадобится в программе. Иногда это очень удоб-
но. Например мы можем читать содержание очень большого файла и составлять какую-нибудь статистику
на основе прочитанного текста. При этом в памяти будет храниться лишь малая часть файла. Но иногда
это свойство мешает. Рассмотрим такую задачу: перевернуть текст в файле под именем ”test”. Мы должны
сначала считать текст из файла, затем перевернуть его и в конце записать в тот же файл. Мы могли бы
написать эту программу так:
module Main where
main :: IO ()
main = inFile reverse ”test”
inFile :: (String -> String) -> FilePath -> IO ()
inFile fun file = writeFile file . fun =<< readFile file
Типичные задачи IO | 131
Функция inFile обновляет текст файла с помощью некоторого преобразование. Но если мы запустим эту
программу:
*Main> main
*** Exception: test: openFile: resource busy (file is locked)
Мы получили ошибку. Мы пытаемся писать в файл, который уже занят для чтения. Дело в том, что функ-
ция readFile заняла файл, за счёт чтения по кусочкам. Для решения этой проблемы необходимо воспользо-
ваться энергичной версией функции readFile, она будет читать файл целиком. Эта функция живёт в модуле
System.IO.Strict:
import qualified System.IO.Strict as StrictIO
inFile :: (String -> String) -> FilePath -> IO ()
inFile fun file = writeFile file . fun =<< StrictIO. readFile file
Функция main осталась прежней. Теперь наша программа спокойно переворачивает текст файла.
Аргументы программы
Пока программы, которые мы создавали просили пользователя ввести данные вручную при выполнении
программы, они работали в интерактивном режиме, но чаще всего программы принимают какие-нибудь
начальные данные, установки или флаги. Читать начальные данные можно с помощью функций из модуля
System.Environment.
Узнать, что передаётся в программу можно функцией getArgs :: IO [String]. Она возвращает список
строк. Это те строки, что мы написали за именем программы через пробел при вызове в терминале. Напишем
простую программу, которая распечатывает свои аргументы по порядку, в виде пронумерованного списка.
module Main where
import System.Environment
main = getArgs >>= mapM_ putStrLn . zipWith f [1 .. ]
where f n a = show n ++ ”: ” ++ a
В локальной функции f мы присоединяем к строке номер через двоеточие. Функцией mapM_ мы пробегаем
по списку строк, отображая их с помощью функции putStrLn. Обратите внимание на краткость программы,
с помощью функции композиции мы легко составили функцию, которая приписывает к аргументам числа, а
затем выводит их на экран.
Скомпилируем программу в интерпретаторе и вызовем её.
*Main> :! ghc --make Args
[1 of 1] Compiling Main
( Args. hs, Args. o )
Linking Args ...
*Main> :! ./Args hey hey hey 23 54 ”qwe qwe qwe” fin
1: hey
2: hey
3: hey
4: 23
5: 54
6: qwe qwe qwe
7: fin
Если мы хотим, чтобы аргумент-строка содержал пробелы мы заключаем его в двойные кавычки.
С помощью функции getProgName можно узнать имя программы. Создадим программу, которая здоро-
вается при вызове. И отвечает в зависимости от настроения программы. Настроение задаётся аргументом
программы.
module Main where
import Control.Applicative
import System.Environment
main = putStrLn =<< reply <$> getProgName <*> getArgs
132 | Глава 8: IO
reply :: String -> [String] -> String
reply name (x:_) = hi name ++ case x of
”happy”
-> ”What a lovely day. What’s up?”
”sad”
-> ”Ooohh. Have you got some news for me?”
”neutral”
-> ”How are you?”
reply name _
= reply name [”neutral”]
hi :: String -> String
hi name = ”Hi! My name is ” ++ name ++ ”.\n”
В функции reply мы составляем реплику программы. Она зависит от имени программы и поступающих
на вход аргументов. Посмотрим, что у нас получилось:
*Main> :! ghc --make HowAreYou.hs -o ninja
[1 of 1] Compiling Main
( HowAreYou. hs, HowAreYou. o )
Linking ninja ...
*Main> :! ./ninja happy
Hi! My name is ninja.
What a lovely day. What’s up?
*Main> :! ./ninja sad
Hi! My name is ninja.
Ooohh. Have you got some news for me?
Вызов других программ
Мы можем вызвать любую программу из нашей программы. Это делается с помощью функции system,
которая живёт в модуле System.
system :: String -> IO ExitCode
Она принимает строку и запускает её в терминале. Так же как мы делали это с помощью приставки :! в
интерпретаторе. Значение типа ExitCode говорит о результате выполнения строки. Он может быть успешным,
тогда функция вернёт ExitSuccess и закончиться ошибкой, тогда мы сможем узнать код ошибки по значению
ExitFailure Int.
Случайные значения
Функции для создания случайных значений определены в модуле System.Random. Модуль System.Random
входит в библиотеку random. Если в вашей поставке ghc его не оказалось, вы можете установить его вручную
через интернет, набрав в командной строке cabal install random. Сначала давайте разберёмся как гене-
рируются случайные числа. Стандартные случайные числа очень похожи на те, что были у нас, когда мы
рассматривали примеры специальных функций. У нас есть генератор случайных чисел типа g и с помощью
функции next мы можем получить обновлённый генератор и случайное целое число:
next :: g -> (Int, g)
Не правда ли этот тип очень похож на тип результата функций с состоянием. В качестве состояния теперь
выступает генератор случайных чисел g. Это поведение описывается классом RandomGen:
class RandomGen g where
next
:: g -> (Int, g)
split
:: g -> (g, g)
geтRange :: g -> (Int, Int)
Функция next обновляет генератор и возвращает случайное значение типа Int. Функция split раска-
лывает один генератор на два. Функция genRange возвращает диапазон значений генерируемых случайных
чисел. Первое значение в паре результата genRange должно быть всегда меньше второго. Для этого класса
определён один экземпляр, это тип StdGen. Мы можем создать первый генератор по целому числу с помощью
функции mkStdGen:
mkStdGen :: Int -> StdGen
Давайте посмотрим как это происходит в интерпретаторе:
Типичные задачи IO | 133
Prelude> :m System.Random
Prelude System.Random> let g0 = mkStdGen 0
Prelude System.Random> let (n0, g1) = next g0
Prelude System.Random> let (n1, g2) = next g1
Prelude System.Random> n0
2147482884
Prelude System.Random> n1
2092764894
Мы создали первый генератор, а затем начали получать новые. Для того, чтобы получать новые случайные
числа, нам придётся таскать везде за собой генератор случайных чисел. Мы можем обернуть его в функцию
с состоянием и пользоваться методами классов Functor, Applicative и Monad. Обновление генератора будет
происходить за ширмой, во время применения функций. Но у нас есть и другой путь.
Вместо монады State мы можем воспользоваться монадой IO. Если нам лень определять генератор слу-
чайных чисел, мы можем попросить компьютер определить его за нас. В этом случае мы взаимодействуем с
компьютером, мы запрашиваем глобальное для системы случайное значение, поэтому возвращаемое значе-
ние будет завёрнуто в тип IO. Для этого определены функции:
getStdGen :: IO StdGen
newStdGen :: IO StdGen
Функция getStdGen запрашивает глобальный для системы генератор случайных чисел. Функция
newStdGen не только запрашивает генератор, но также и обновляет его. Мы пользуемся этими функци-
ями так же как и mkStdGen, только теперь мы спрашиваем первый аргумент у компьютера, а не передаём его
вручную. Также есть ещё одна полезная функция:
getStdRandom
:: (StdGen -> (a, StdGen)) -> IO a
Посмотрим, что получится, если передать в неё функцию next:
Prelude System.Random> getStdRandom next
1386438055
Prelude System.Random> getStdRandom next
961860614
И не надо обновлять никаких генераторов. Но вместо одного неудобства мы получили другое. Теперь
значение завёрнуто в оболочку IO.
Генератор StdGen делает случайные числа из диапазона всех целых чисел. Что если мы хотим получить
только числа из некоторого интервала? И как получить случайные значения других типов? Для этого суще-
ствует класс Random. Он является удобной надстройкой над классом RandomGen. Посмотрим на его основные
методы:
class Random a where
randomR :: RandomGen g => (a, a) -> g -> (a, g)
random
:: RandomGen g => g -> (a, g)
Метод randomR принимает диапазон значений, генератор случайных чисел и возвращает случайное число
из указанного диапазона и обновлённый генератор. Метод random является синонимом метода next из класса
RandomGen, только теперь мы можем получать не только целые числа.
Есть и дополнительные методы. Есть методы, которые позволяют генерировать список всех возможных
случайных значений для данного генератора:
randomRs :: RandomGen g => (a, a) -> g -> [a]
randoms
:: RandomGen g => g -> [a]
За счёт лени мы будем получать новые значения по мере необходимости.
randomRIO
:: (a, a) -> IO a
randomIO
:: IO a
Эти функции выполняют тоже, что и основные функции класса, но им не нужен генератор случайных
чисел, они создают его с помощью функции getStdRandom. Экземпляры Random определены для Bool, Char,
Double, Float, Int и Integer. Например так мы можем подбросить кости десять раз:
134 | Глава 8: IO
Prelude System.Random> fmap (take 10 . randomRs (1, 6)) getStdGen
[5,6,5,5,6,4,6,4,4,4]
Prelude System.Random> fmap (take 10 . randomRs (1, 6)) getStdGen
[5,6,5,5,6,4,6,4,4,4]
Обратите внимание на то, что функция getStdGen не обновляет генератор случайных чисел. Мы запра-
шиваем глобальное состояние. Поэтому, дважды подбросив кубик, мы получили одни и те же результаты.
Генератор будет обновляться, если воспользоваться функцией newStdGen:
Prelude System.Random> fmap (take 10 . randomRs (1, 6)) newStdGen
[1,1,5,6,5,2,5,5,5,3]
Prelude System.Random> fmap (take 10 . randomRs (1, 6)) newStdGen
[5,4,6,5,5,5,1,5,5,2]
Создадим случайные слова из пяти букв:
Prelude System.Random> fmap (take 5 . randomRs (’a’, ’z’)) newStdGen
”maclg”
Prelude System.Random> fmap (take 5 . randomRs (’a’, ’z’)) newStdGen
”nfjoa”
Цитатник
Напишем небольшую программу, которая будет выводить на экран в случайном порядке цитаты. Цитаты
хранятся в виде списка пар (автор, высказывание). Сначала мы генерируем случайное число в диапазоне
длины списка, затем выбираем цитату под этим номером и выводим её на экран.
module Main where
import Control.Applicative
import System.Random
main =
format . (quotes !! ) <$> randomRIO (0, length quotes - 1)
>>= putStrLn
format (a, b) = b
++ space ++ a ++ space
where space = ”\n\n”
quotes = [
(”Бьёрн Страуструп”,
”Есть лишь два вида языков программирования: те, \
\ на которые вечно жалуются, и те, которые никогда \
\ не используются.”),
(”Мохатма Ганди”, ”Ты должен быть теми изменениями, которые\
\ ты хочешь видеть вокруг.”),
(”Сократ”, ”Я знаю лишь то, что ничего не знаю.”),
(”Китайская народная мудрость”, ”Сохранив спокойствие в минуту\
\ гнева, вы можете избежать сотни дней сожалений”),
(”Жан Батист Мольер”, ”Медленно растущие деревья приносят лучшие плоды”),
(”Антуан де Сент-Экзюпери”, ”Жить это значит медленно рождаться”),
(”Альберт Эйнштейн”, ”Фантазия важнее знания.”),
(”Тони Хоар”, ”Внутри любой большой программы всегда есть\
\ маленькая, что рвётся на свободу”),
(”Пифагор”, ”Не гоняйся за счастьем, оно всегда находится в тебе самом”),
(”Лао Цзы”, ”Путешествие в тысячу ли начинается с одного шага”)]
Функция format приводит цитату к виду приятному для чтения. Попробуем программу в интерпретаторе:
Prelude> :! ghc --make Quote -o hi
[1 of 1] Compiling Main
( Quote. hs, Quote. o )
Linking hi ...
Prelude> :! ./hi
Путешествие в тысячу ли начинается с одного шага
Лао Цзы
Типичные задачи IO | 135
Prelude> :! ./hi
Не гоняйся за счастьем, оно всегда находится в тебе самом
Пифагор
Исключения
Мы уже знаем несколько типов, с помощью которых функции могут сказать, что что-то случилось не
так. Это типы Maybe и Either. Если функции не удалось вычислить значение она возвращает специальное
значение Nothing или Left reason, по которому следующая функция может опознать ошибку и предпринять
какие-нибудь действия. Так обрабатываются ошибки в чистых функциях. В этом разделе мы узнаем о том,
как обрабатываются ошибки, которые происходят при взаимодействии с внешним миром, ошибки, которые
происходят внутри типа IO.
Ошибки функций с побочными эффектами обрабатываются с помощью специальной функции catch, она
определена в Prelude:
catch :: IO a -> (IOError -> IO a) -> IO a
Эта функция принимает значение, которое содержит побочные эффекты и функцию, которая обрабаты-
вает исключительные ситуации. К примеру если мы попытаемся прочитать данные из файла, к которому у
нас нет доступа, произойдёт ошибка. Мы можем не дать программе упасть и обработать ошибку с помощью
функции catch.
Например программа, в которой мы дописывали данные в файл, упадёт, если мы передадим не существу-
ющий файл. Но мы можем исправить это поведение с помощью функции catch. Мы можем перезапускать
программу, если произошла ошибка:
module FileSafe where
import Control.Applicative
import Control.Monad
main = try ‘catch‘ const main
try = msg1 >> getLine >>= read >>= append
where read
file = readFile file >>= putStrLn >> return file
append file = msg2 >> getLine >>= appendFile file
msg1
= putStr ”input file: ”
msg2
= putStr ”input text: ”
Часто функции двух аргументов называют так, чтобы при инфиксной форме записи получалась фраза
из английского языка. Так если мы запишем catch в инфиксной форме получится очень наглядное выраже-
ние. Функция обработки ошибок реагирует на любую ошибку перезапуском программы. Попробуем взломать
программу:
*FileSafe> main
input file: fsldfksld
input file: sd;fls;dfl;vll; d;fld;f
input file: dflks;ldkf ldkfldkfld
input file: lsdkfksdlf ksdkflsdfkls;dfk
input file: bfk
input file: test
Hello!Hi)
input text: HowHow
Функция будет запрашивать файл до тех пор, пока мы не введём корректное значение. Мы можем доба-
вить сообщение об ошибке, немного изменив функцию обработки:
main = try ‘catch‘ const (msg >> main)
where msg = putStrLn ”Wrong filename, try again.”
А что делать если нам хочется различать ошибки по типу и предпринимать различные действия в зави-
симости от типа ошибки? Ошибки распознаются с помощью специальных предикатов, которые определены
в модуле System.IO.Error. Рассмотрим некоторые из них.
136 | Глава 8: IO
Например с помощью с помощью предиката isDoesNotExistErrorType мы можем опознать ошибки,
которые случились из-за того, что один из аргументов функции не существует. С помощью предиката
isPermissionErrorType мы можем узнать, что ошибка произошла из-за того, что мы пытались получить до-
ступ к данным, на которые у нас нет прав. Мы можем, немного изменив функцию-обработчик исключений,
выводить более информативные сообщения об ошибках перед перезапуском:
main = try ‘catch‘ handler
handler :: IOError -> IO ()
handler = ( >> main) . putStrLn . msg2 . msg1
msg1 e
| isDoesNotExistErrorType e = ”File does not exist. ”
| isPermissionErrorType e
= ”Access denied. ”
| otherwise
= ””
msg2 = (++ ”Try again.”)
В модуле System.IO.Error вы можете найти ещё много разных предикатов.
Потоки текстовых данных
Обмен данными, чтение и запись происходят с помощью потоков. Каждый поток имеет дескриптор
(handle), через него мы можем общаться с потоком, например считывать данные или записывать. Функции
для работы с потоками данных определены в модуле System.IO.
В любой момент в системе открыты три стандартных потока:
• stdin – стандартный ввод
• stdout – стандартный вывод
• stderr – поток ошибок и отладочных сообщений
Например когда мы выводим строку на экран, на самом деле мы записываем строку в поток stdout. А
когда мы читаем символ с клавиатуры, мы считываем его из потока stdin.
Файлы также являются потоками. При открытии файлу присваивается дескриптор через который, мы
можем обмениваться данными. Файл может быть открыт для чтения, записи, дополнения (записи в конец
файла) или чтения и записи. Файл открывается функцией:
openFile :: FilePath -> IOMode -> IO Handle
Функция принимает путь к файлу и режим работы с файлом и возвращает дескриптор. Режим может
принимать одно из значений:
• ReadMode – чтение
• WriteMode – запись
• AppendMode – добавление (запись в конец файла)
• ReadWriteMode – чтение и запись
Открыв дескриптор, мы можем начать обмениваться данными. Для этого определены функции аналогич-
ные тем, что мы уже рассмотрели. Функции для записи данных:
-- запись символа
hPutChar :: Handle -> Char -> IO ()
-- запись строки
hPutStr :: Handle -> String -> IO ()
-- запись строки с переносом каретки
hPutStrLn :: Handle -> String -> IO ()
-- запись значения
hPrint :: Show a => Handle -> a -> IO ()
Типичные задачи IO | 137
Все функции принимают первым аргументом дескриптор потока. Дескриптор должен позволять записы-
вать данные. Например для дескриптора, открытого в режиме ReadMode, выполнение этих функций приведёт
к ошибке.
Из потоков также можно читать данные. Эти функции похожи на те, что мы уже рассмотрели:
-- чтение одного символа
hGetChar :: Handle -> IO Char
-- чтение строки
hGetLine :: Handle -> IO String
-- ленивое чтение строки
hGetContents :: Handle -> IO String
Как только, мы закончим работу с файлом, его необходимо закрыть. Нам нужно освободить дескриптор.
Сделать это можно функцией hClose:
hClose :: Handle -> IO ()
Стандартные функции ввода/вывода, которые мы рассмотрели ранее определены через функции работы
с дескрипторами. Например так мы выводим строку на экран:
putStr
:: String -> IO ()
putStr s
=
hPutStr stdout s
А так читаем строку с клавиатуры:
getLine
:: IO String
getLine
=
hGetLine stdin
В этих функциях используются дескрипторы стандартных потоков данных stdin и stdout. Отметим функ-
цию withFile:
withFile :: FilePath -> IOMode -> (Handle -> IO r) -> IO r
Она открывает файл в заданном режиме выполняет функцию на его дескрипторе и и закрывает файл.
Например через эту функцию определены функции readFile и appendFile:
appendFile
:: FilePath -> String -> IO ()
appendFile f txt = withFile f AppendMode (\hdl -> hPutStr hdl txt)
writeFile :: FilePath -> String -> IO ()
writeFile f txt = withFile f WriteMode (\hdl -> hPutStr hdl txt)
8.5 Форточка в мир побочных эффектов
В самом начале главы я сказал о том, что из мира IO
нет выхода. Нет функции с типом IO a -> a. На самом деле выход есть. Функция с таким типом живёт в
модуле System.IO.Unsafe:
unsafePerformIO :: IO a -> a
Длинное имя функции намекает на то, что её необходимо использовать с крайней осторожностью. По-
скольку последствия могут быть непредсказуемыми.
Эта функция используется при чтении конфигурационных файлов. Если есть уверенность в том, что файл
будет только читаться и во время выполнения программы файл не может быть изменён другой программой,
то мы можем считать, что его значение окажется неизменным на протяжении работы программы. Это говорит
о том, что нам не важно когда читать данные. Поэтому здесь мы вроде бы ничем не рискуем. “Вроде бы”
потому что ответственность за постоянство файла лежит на наших плечах.
Эта функция часто используется при вызове функций С через Haskell. В Haskell есть возможность вызывать
функции, написанные на C. Но по умолчанию такие функции заворачиваются в тип IO. Если функция является
чистой в С, то она будет чистой и при вызове через Haskell. Мы можем поручиться за её чистоту и вычислитель
нам поверит. Но если мы его обманули, мы пожнём плоды своего обмана.
138 | Глава 8: IO
Отладка программ
Раз уж речь зашла о “грязных” возможностях языка стоит упомянуть функцию trace из модуля
Debug.Trace. Посмотрим на её тип:
trace :: String -> a -> a
Это служебная функция эхо-печати. Когда дело доходит до вычисления функции trace на экран выводит-
ся строка, которая была передана в неё первым аргументом, после чего функция возвращает второй аргумент.
Это функция id с побочным эффектом вывода сообщения на экран. Ею можно пользоваться для отладки. На-
пример так можно вернуть значение и распечатать его:
echo :: Show a => a -> a
echo a = trace (show a) a
8.6 Композиция монад
Эта глава завершает наше путешествие в мире типов-монад. Мы начали наше знакомство с монадами с
композиции, мы определили класс Monad через класс Kleisli, который упрощал составление специальных
функций вида a -> m b. Тогда мы познакомились с самыми простыми типами монадами (списки и частично
определённые функции), потом мы перешли к типам посложнее, мы научились проводить вычисления с
состоянием. В этой главе мы рассмотрели самый важный тип монаду IO. Мне бы хотелось замкнуть этот
рассказ на теме композиции. Мы поговорим о композиции нескольких монад.
Если вы посмотрите в исходный код библиотеки transformers, то увидите совсем другое определение для
State:
type State s = StateT s Identity
newtype StateT s m a = StateT { runStateT :: s -> m (a,s) }
newtype Identity a = Identity { runIdentity :: a }
Но так ли оно далеко от нашего? Давайте разберёмся. Identity это тривиальный тип обёртка. Мы просто
заворачиваем значение в конструктор и ничего с ним не делаем. Вы наверняка сможете догадаться как опре-
делить экземпляры всех рассмотренных в этой главе классов для этого типа. Тип StateT больше похож на
наше определение для State, единственное отличие – это дополнительный параметр m в который завёрнут
результат функции обновления состояния. Если мы сотрём m, то получим наше определение. Это и сказано
в определении для State
type State s = StateT s Identity
Мы передаём дополнительным параметром в StateT тип Identity, который как раз ничего и не делает
с типом. Так мы получим наше исходное определение, но зачем такие премудрости? Такой тип принято
называть монадным трансформером (monad transformer). Он определяет композицию из нескольких монад в
данном случае одной из монад является State. Посмотрим на экземпляр класса Monad для StateT
instance (Monad m) => Monad (StateT s m) where
return a = StateT $ \s -> return (s, a)
a >>= f = StateT $ \s0 ->
runStateT a s0 >>= \(b, s1) -> runStateT (f b) s1
В этом определении мы пропускаем состояние через сито методов класса Monad для типа m. В остальном
это определение ничем не отличается от нашего. Также определены и ReaderT, WriterT, ListT и MaybeT.
Ключевым классом для всех этих типов является класс MonadTrans:
class MonadTrans t where
lift :: Monad m => m a -> t m a
Этот тип позволяет нам заворачивать специальные значения типа m в значения типа t. Посмотрим на
определение для StateT:
instance MonadTrans (StateT s) where
lift m = StateT $ \s -> liftM (,s) m
Композиция монад | 139
Напомню, что функция liftM это тоже самое , что и функция fmap, только она определена через методы
класса Monad. Мы создали функцию обновлнения состояния, которая ничего не делает с состоянием, а лишь
прицепляет его к значению.
Приведём простой пример применения трансформеров. Вернёмся к примеру FSM из предыдущей главы.
Предположим, что наш конечный автомат не только реагирует на действия, но и ведёт журнал, в который
записываются все поступающие на вход события. За переход состояний будет по прежнему отвечать тип State
только теперь он станет трансформером, для того чтобы включить воможность журналирования. За ведение
журнала будет отвечать тип Writer. Ведь мы просто накапливаем записи.
Интересно, что для добавления новой возможности нам нужно изменить лишь определение типа FSM и
функцию fsm, теперь они примут вид:
module FSMt where
import Control.Monad.Trans.Class
import Control.Monad.Trans.State
import Control.Monad.Trans.Writer
import Data.Monoid
type FSM s = StateT s (Writer [String]) s
fsm :: Show ev => (ev -> s -> s) -> (ev -> FSM s)
fsm transition e = log e >> run e
where run e = StateT $ \s -> return (s, transition e s)
log e = lift $ tell [show e]
Все остальные функции останутся прежними. Сначала мы подключили все необходимые модули из биб-
лиотеки transformers. В подфункции log мы сохраняем сообщение в журнал, а в подфункции run мы вы-
полняем функцию перехода. Посмотрим, что у нас получилось:
*FSMt> let res = mapM speaker session
*FSMt> runWriter $ runStateT res (Sleep, Level 2)
(([(Sleep, Level 2),(Work, Level 2),(Work, Level 3),(Work, Level 2),
(Sleep, Level 2)],(Sleep, Level 3)),
[”Button”,”Louder”,”Quieter”,”Button”,”Louder”])
*FSMt> session
[Button, Louder, Quieter, Button, Louder]
Мы видим, что цепочка событий была успешно записана в журнал.
Для трансформеров с типом IO определён специальный класс:
class Monad m => MonadIO m where
liftIO :: IO a -> m a
Этот класс живёт в модуле Control.Monad.IO.Class. С его помощью мы можем выполнять IO-действия
ввнутри другой монады. Эта возможность бывает очень полезной. Вам она обязательно понадобится, если вы
начнёте писать веб-сайты на Haskell (например в happstack) или будете пользоваться библиотеками, которые
надстроены над C (например физический движок Hipmunk).
8.7 Краткое содержание
Наконец-то мы научились писать программы! Программы, которые можно исполнять за пределами ин-
терпретатора. Для этого нам пришлось познакомиться с типом IO. Экземпляр класса Monad для этого типа
интерпретируется специальным образом. Он вносит упорядоченность в выполнение программы. В нашем
статическом мире описаний появляются такие понятия как “сначала”, “затем”, “до” и “после”. Но они не
смогут нанести много вреда.
Вычисление операций с побочными эффектами разбивает программу на кадры. Но это не мешает нам
писать основные функции в чистом виде, подставляя их по мере необходимости в изменчивый мир побочных
эффектов с помощью методов из классов Functor, Applicative, Monad.
Мы узнали как в Haskell обстоят дела с такими типичными задачами мира побочных эффектов как
ввод/вывод, чтение/запись файлов, генерация случайных значений, выполнение внешних программ, ини-
циализация программ с помощью флагов. Также мы узнали о том, как обрабатываются специфические для
типа IO исключения.
140 | Глава 8: IO
8.8 Упражнения
Старайтесь свести присутствие функций с побочными эффектами к минимуму. Идеальный случай, когда
тип IO встречается только в функции main. Часто программы устроены более хитрым образом и функции
с побочными эффектами пытаются расползтись по всему коду. Но даже в этом случае программу можно
разделить на две части: в одной живут подлинные источники побочных эффектов, такие как чтение файлов,
генерация случайных значений, а в другой – чистые функции. Старайтесь устроить программу так, чтобы
она была максимально чистой. Чистые функции гораздо проще комбинировать, понимать, изменять.
• Это упражнение даёт вам возможность почувствовать преимущества чистого кода. Вспомните функ-
цию поиска корней методом неподвижной точки (этот пример встречался в главе о ленивых вычисле-
ниях). Напишите на основе этого примера программу, которая будет распечатывать решение и после-
довательность приближений. Последовательность приближений состоит из текущего значения корня
и расстоянии между корнями.
Напишите два варианта программы, в одном вы измените алгоритм так, чтобы печать происходила
одновременно с вычислениями (не пользуясь функцией из модуля Debug.Trace). А в другом вариан-
те алгоритм останется прежним. Но теперь вместо решения найдите список первых приближений до
решения. А затем передайте его в отдельную функцию печати результатов.
В первом варианте алгоритм смешан с печатью. А во втором программа распадается на две части, часть
вычислений и часть вывода результатов на экран. Сравните два подхода.
• Напишите программу для угадывания чисел. Компьютер загадал число в заданном диапазоне и про-
сит вас угадать его. Если вы ошибаетесь он подсказывает: “холодно-горячо” или “больше-меньше”.
Программа принимает два аргумента, которые определяют диапазон возможных значений для неиз-
вестного числа.
• С помощью стандартных функций для генерации случайных чисел напишите программу, которая про-
водит состязание по игре в кости. Программа принимает аргументом суммарное число очков необходи-
мых для победы. Двое игроков бросают по очереди кости побеждает тот, кто первым наберёт заданную
сумму.
Сделайте так чтобы результаты выводились постепенно. С каждым нажатием на Enter вы подбрасы-
ваете кости (два шестигранных кубика). После каждого раунда программа выводит промежуточные
результаты.
• Напишите программу, которая принимает два аргумента: набор слов разделённых пробелами и файл.
А выводит она строки файла, в которых встречается данное слово.
Воспользуйтесь стандартными функциями из модуля Data.List
-- разбиение строки на подстроки по переносам каретки
lines :: String -> [String]
-- разбиение строки на подстроки по пробелам
words :: String -> [String]
-- возвращает True только в том случае, если
-- первый список полностью содержится во втором
isInfixOf :: Eq a => [a] -> [a] -> Bool
• Классы Functor и Applicative замкнуты относительно композиции. Это свойство говорит о том, что
композиция (аппликативных) функторов снова является (аппликативным) функтором. Докажите это!
Пусть дан тип, который описывает композицию двух типов:
newtype O f g a = O { unO :: f (g a) }
Определите экземпляры классов:
instance (Functor f, Functor g) => Functor (O f g) where ...
instance (Applicative f, Applicative g) => Applicative (O f g) where ...
Подсказка: если совсем не получается, ответ можно подсмотреть в библиотеке TypeCompose. Но пока мы
не знаем как устанавливать библиотеки и где они живут, всё-таки попытайтесь решить это упражнение
самостоятельно.
Упражнения | 141
Глава 9
Редукция выражений
В этой главе мы поговорим о том как вычисляются программы. В самом начале мы говорили о том, что
процесса вычисления значений нет. В том смысле, что у нас нет новых значений, у нас ничего не меняется,
мы лишь расшифровываем синонимы значений.
Вкратце вспомним то, что мы уже знаем о вычислениях. Сначала мы с помощью типов определяем мно-
жество всех возможных значений. Значения – это деревья в узлах которых записаны конструкторы, которые
мы определяем в типах. Так например мы можем определить тип:
data Nat = Zero | Succ Nat
Этим типом мы определяем множество допустимых значений. В данном случае это цепочки конструкто-
ров Succ, которые заканчиваются конструктором Zero:
Zero, Succ Zero, Succ (Succ Zero), ...
Затем начинаем давать им новые имена, создавая константы (простые имена-синонимы)
zero
= Zero
one
= Succ zero
two
= Succ one
и функции (составные имена-синонимы):
foldNat :: a -> (a -> a) -> Nat -> a
foldNat z
s
Zero
= z
foldNat z
s
(Succ n)
= s (foldNat z s n)
add a = foldNat a
Succ
mul a = foldNat one (add a)
Затем мы передаём нашу программу на проверку компилятору. Мы просим у него проверить не создаём
ли мы случайно какие-нибудь бессмысленные выражения. Бессмысленные потому, что они пытаются создать
значение, которое не вписывается в наши типы. Например если мы где-нибудь попробуем составить выра-
жение:
add Zero mul
Компилятор напомнит нам о том, что мы пытаемся подставить функцию mul на место обычного значения
типа Nat. Тогда мы исправим выражение на:
add Zero two
Компилятор согласится. И передаст выражение вычислителю. И тут мы говорили, что вычислитель начи-
нает проводить расшифровку нашего описания. Он подставляет на место синонимов их определения, правые
части из уравнений. Этот процесс мы называли редукцией. Вычислитель видит два синонима и одно значение.
С какого синонима начать? С add или two?
142 | Глава 9: Редукция выражений
9.1 Стратегии вычислений
Этот вопрос приводит нас к понятию стратегии вычислений. Поскольку вычисляем мы только константы,
то наше выражение также можно представить в виде дерева. Только теперь у нас в узлах записаны не только
конструкторы, но и синонимы. Процесс редукции можно представить как процесс очистки такого дерева от
синонимов. Посмотрим на дерево нашего значения:
Оказывается у нас есть две возможности очистки синонимов.
Cнизу-вверх начинаем с листьев и убираем все синонимы в листьях дерева выражения. Как только в данном
узле и всех дочерних узлах остались одни конструкторы можно переходить на уровень выше. Так мы
поднимаемся выше и выше пока не дойдём до корня.
Cверху-вниз начинаем с корня, самого внешнего синонима и заменяем его на определение (с помощью урав-
нения на правую часть от знака равно), если на верху снова окажется синоним, мы опять заменим его
на определение и так пока на верху не появится конструктор, тогда мы спустимся в дочерние деревья
и будем повторять эту процедуру пока не дойдём до листьев дерева.
Посмотрим как каждая из стратегий будет редуцировать наше выражение. Начнём со стратегии от ли-
стьев к корню (снизу-вверх):
add Zero two
-- видим два синонима add и two
-- раскрываем two, ведь он находится ниже всех синонимов
=>
add Zero (Succ one)
-- ниже появился ещё один синоним, раскроем и его
=>
add Zero (Succ (Succ zero))
-- появился синоним zero раскроем его
=>
add Zero (Succ (Suсс Zero))
-- все узлы ниже содержат конструкторы, поднимаемся вверх до синонима
-- заменяем add на его правую часть
=>
foldNat Succ Zero (Succ (Succ Zero))
-- самый нижний синоним foldNat, раскроем его
-- сопоставление с образцом проходит во втором уравнении для foldNat
=>
Succ (foldNat Succ Zero (Succ Zero))
-- снова раскрываем foldNat
=>
Succ (Succ (foldNat Zero Zero))
-- снова раскрываем foldNat, но на этот раз нам подходит
-- первое уравнение из определения foldNat
=>
Succ (Succ Zero)
-- синонимов больше нет можно вернуть значение
-- результат:
Succ (Succ Zero)
В этой стратегии для каждой функции мы сначала вычисляем до конца все аргументы, потом подставляем
расшифрованные значения в определение функции.
Теперь посмотрим на вычисление от корня к листьям (сверху-вниз):
add Zero two
-- видим два синонима add и two, начинаем с того, что ближе всех к корню
=>
foldNat Succ Zero two
-- теперь выше всех foldNat, раскроем его
Но для того чтобы раскрыть foldNat нам нужно узнать какое уравнение выбрать для этого нам нужно
понять какой конструктор находится в корне у второго аргумента, если это Zero, то мы выберем первое
уравнение, а если это Succ, то второе:
-- в уравнении для foldNat видим декомпозицию по второму
-- аргументу. Узнаем какой конструктор в корне у two
=>
foldNat Succ Zero (Succ one)
-- Это Succ нам нужно второе уравнение:
=>
Succ (foldNat Succ Zero one)
-- В корне м ыполучили конструктор, можем спуститься ниже.
-- Там мы видим foldNat, для того чтобы раскрыть его нам
-- снова нужно понять какой конструктор в корне у второго аргумента:
=>
Succ (foldNat Succ Zero (Succ zero))
-- Это опять Succ переходим ко второму уравнению для foldNat
Стратегии вычислений | 143
=>
Succ (Succ (foldNat Succ Zero zero))
-- Снова раскрываем второй аргумент у foldNat
=>
Succ (Succ (foldNat Succ Zero Zero))
-- Ага это Zero, выбираем первое уравнение
=>
Succ (Succ Zero)
-- Синонимов больше нет можно вернуть значение
-- результат:
Succ (Succ Zero)
В этой стратегии мы всегда раскрываем самый верхний уровень выражения, можно представить как мы
вытягиваем конструкторы от корня по цепочке. У этих стратегий есть специальные имена:
• вычисление по значению (call by value), когда мы идём от листьев к корню.
• вычисление по имени (call by name), когда мы идём от корня к листьям.
Отметим, что стратегию вычисления по значению также принято называть энергичными вычислениями
(eqger evaluation) или аппликативной (applicative) стратегией редукции. Вычисление по имени также принято
называть нормальной (normal) стратегией редукции.
Преимущества и недостатки стратегий
В чём преимущества, той и другой стратегии.
Если выражение вычисляется полностью, первая стратегия более эффективна по расходу памяти.
Вычисляется полностью означает все компоненты выражения участвуют в вычислении. Например то вы-
ражении, которое мы рассмотрели так подробно, вычисляется полностью. Приведём пример выражения, при
вычислении которого нужна лишь часть аргументов, для этого определим функцию:
isZero :: Nat -> Bool
isZero Zero
= True
isZero _
= False
Она проверяет является ли нулём данное число, теперь представим как будет вычисляться выражение, в
той и другой стратегии:
isZero (add Zero two)
Первая стратегия сначала вычислит все аргументы у add потом расшифрует add и только в самом конце
доберётся до isZero. На это уйдёт восемь шагов (семь на вычисление add Zero two). В то время как вто-
рая стратегия начнёт с isZero. Для вычисления isZero ей потребуется узнать какой конструктор в корне у
выражения add Zero two. Она узнает это за два шага. Итого три шага. Налицо экономия усилий.
Почему вторая стратегия экономит память? Поскольку мы всегда вычисляем аргументы функции, мы
можем не хранить описания в памяти а сразу при подстановке в функцию начинать редукцию. Эту ситуацию
можно понять на таком примере, посчитаем сумму чисел от одного до четырёх с помощью такой функции:
sum :: Int -> [Int] -> Int
sum []
res = res
sum (x:xs)
res = sum xs (res + x)
Посмотрим на то как вычисляет первая стратегия, с учётом того что мы вычисляем значения при подста-
новке:
sum [1,2,3,4] 0
=>
sum [2,3,4]
(0 + 1)
=>
sum [2,3,4]
1
=>
sum [3,4]
(1 + 2)
=>
sum [3,4]
3
=>
sum [4]
(3+3)
=>
sum [4]
6
=>
sum []
(6+4)
=>
sum []
10
=>
10
144 | Глава 9: Редукция выражений
Теперь посмотрим на вторую стратегию:
sum [1,2,3,4] 0
=>
sum [2,3,4]
0+1
=>
sum [3,4]
(0+1)+2
=>
sum [4]
((0+1)+2)+3
=>
sum []
(((0+1)+2)+3)+4
=>
(((0+1)+2)+3)+4
=>
((1+2)+3)+4
=>
(3+3)+4
=>
6+4
=>
10
А теперь представьте, что мы решили посчитать сумму чисел от 1 до миллиона. Сколько вычислений
нам придётся накопить! В этом недостаток второй стратегии. Но есть и ещё один недостаток, рассмотрим
выражение:
(\x -> add (add x x) x) (add Zero two)
Первая стратегия сначала редуцирует выражение add Zero two в то время как вторая подставит это
выражение в функцию и утроит свою работу!
Но у второй стратегии есть одно очень веское преимущество, она может вычислять больше выражений
чем вторая. Определим значение бесконечность:
infinity
:: Nat
infinity
= Succ infinity
Это рекурсивное определение, если мы попытаемся его распечатать мы получим бесконечную последо-
вательность Succ. Чем не бесконечность? Теперь посмотрим на выражение:
isZero infinity
Первая стратегия захлебнётся, вычисляя аргумент функции isZero, в то время как вторая найдёт решение
за два шага.
Подведём итоги. Плюсы вычисления по значению:
• Эффективный расход памяти в том случае если все
составляющие выражения участвуют в вычислении.
• Она не может дублировать вычисления, как стратегия вычисления по имени.
Плюсы вычисления по имени:
• Меньше вычислений в том случае, если при вычислении выражения
участвует лишь часть составляющих.
• Большая выразительность. Мы можем вычислить больше значений.
Какую из них выбрать? В Haskell пошли по второму пути. Всё-таки преимущество выразительности языка
оказалось самым существенным. Но для того чтобы избежать недостатков стратегии вычисления по имени
оно было модифицировано. Давайте посмотрим как.
9.2 Вычисление по необходимости
Вернёмся к выражению:
(\x -> add (add x x) x) (add Zero two)
Нам нужно как-то рассказать функции о том, что имя x в её теле указывает на одно и то же значение. И
если в одном из x значение будет вычислено переиспользовать эти результаты в других x. Вместо значения мы
будем передовать в функцию ссылку на область памяти, которая содержит рецепт получения этого значения.
Напомню, что мы по-прежнему вычисляем значение сверху вниз, сейчас мы просто хотим избавиться от
проблемы дублирования. Вернитесь к примеру с вычислением по имени и просмотрите его ещё раз. Обратите
внимание на то, что значения вычислялись лишь при сопоставлении с образцом. Мы вычисляем верхний
конструктор аргумента лишь для того, чтобы понять какое уравнение для foldNat выбрать. Теперь мы будем
хранить ссылку на (add Zero two) в памяти и как только, внешняя функция запросит верхний конструктор
мы обновим значение в памяти новым вычисленным до корневого конструктора значением. Если в любом
другом месте функции мы вновь обратимся к значению, мы не будем его перевычислять, а сразу вернём
конструктор. Посмотрим как это происходит на примере:
Вычисление по необходимости | 145
--
выражение
| память:
--------------------------------------------|-------------------------
(\x -> add (add x x) x) M
| M = (add Zero two)
-- подставим ссылку в тело функции
|
=>
add (add M M) M
|
-- раскроем самый верхний синоним
|
=>
foldNat (add M M) Succ M
|
-- для foldNat узнаем верхний конструктор
|
-- последнего аргумента (пропуская
|
-- промежуточные шаги, такие же как выше)
|
=>
| M
= Succ M1
| M1 = foldNat Succ Zero one
-- по M выбираем второе уравнение
|
=> Succ (foldNat (add M M) Succ M1)
|
-- запросим следующий верхний конструктор:
|
=>
| M
= Succ M1
| M1 = Succ M2
| M2 = foldNat Succ Zero zero
-- по M1 выбираем второе уравнение
|
=> Succ (Succ (foldNat (add M M) Succ M2))
|
-- теперь для определения уравнения foldNat |
-- раскроем M2
|
=>
| M
= Succ M1
| M1 = Succ M2
| M2 = Zero
-- выбираем первое уравнение для foldNat:
|
=> Succ (Succ (add M M))
|
-- раскрываем самый верхний синоним:
|
=> Succ (Succ (foldNat M Succ M))
|
-- теперь, поскольку M уже вычислялось, в
|
-- памяти уже записан верхний конструктор,
|
-- мы знаем, что это Succ и выбираем второе |
-- уравнение:
|
=> Succ (Succ (Succ (foldNat M Succ M1)))
|
-- и M1 тоже уже вычислялось, сразу
|
-- выбираем второе уравнение
|----+
=> Succ (Succ (Succ (Succ (foldNat M Succ M2)))) |
-- M2 вычислено, идём на первое уравнение
|----+
=> Succ (Succ (Succ (Succ (Succ M))))
|
-- далее остаётся только подставить уже
|
-- вычисленные значения M
|
-- и вернуть значение.
|
Итак подставляется не значение а ссылка на него, вычисленная часть значения используется сразу в
нескольких местах. Эта стратегия редукции называется вычислением по необходимости (call by need) или
ленивой стратегией вычислений (lazy evaluation).
Теперь немного терминологии. Значение может находится в четырёх состояниях:
• Нормальная форма (normal form, далее НФ), когда оно полностью вычислено (нет синонимов);
• Слабая заголовочная НФ (weak head NF, далее СЗНФ), когда известен хотя бы один верхний конструк-
тор;
• Отложенное вычисление (thunk), когда известен лишь рецепт вычисления;
• Дно (bottom, часто рисуют как ⊥), когда известно, что значение не определено.
Вы могли понаблюдать за значением в первых трёх состояниях на примере выше. Но что такое ⊥? Вспом-
ним определение для функции извлечения головы списка head:
head :: [a] -> a
head (a:_)
= a
head []
= error ”error: empty list”
Второе уравнение возвращает ⊥. У нас есть две функции, которые возвращают это “значение”:
undefined
:: a
error
:: String -> a
146 | Глава 9: Редукция выражений
Первая – это ⊥ в чистом виде, а вторая не только возвращает неопределённое значение, но и приводит
к выводу на экран сообщения об ошибке. Обратите внимание на тип этих функций, результат может быть
значением любого типа. Это наблюдение приводит нас к ещё одной тонкости. Когда мы определяем тип:
data Bool
= False | True
data Maybe a
= Nothing | Just a
На самом деле мы пишем:
data Bool
= undefined | False | True
data Maybe a
= undefined | Nothing | Just a
Компилятор автоматически прибавляет ещё одно значение к любому определённому пользователем ти-
пу. Такие типы называют поднятыми (lifted type). А значения таких типов принято называть запакованными
(boxed). Не запакованное (unboxed) значение – это простое примитивное значение. Например целое или дей-
ствительное число в том виде, в котором оно хранится на компьютере. В Haskell даже числа “запакованы”.
Поскольку нам необходимо, чтобы undefined могло возвращать в том числе и значение типа Int:
data Int = undefined
| I# Int#
Тип Int# – это низкоуровневое представление ограниченного целого числа. Принято писать не запа-
кованные типы с решёткой на конце. I# – это конструктор. Нам приходится запаковывать значения ещё и
потому, что значение может принимать несколько состояний (в зависимости от того, насколько оно вычис-
лено), всё это ведёт к тому, что у нас хранится не просто значение, а значение с какой-то дополнительной
информацией, которая зависит от конкретной реализации языка Haskell.
Мы решили проблему дублирования вычислений, но наше решение усугубило проблему расхода памяти.
Ведь теперь мы храним не просто значения, но ещё и дополнительную информацию, которая отвечает за
проведение вычислений. Эта проблема может проявляться в очень простых задачах. Например попробуем
вычислить сумму чисел от одного до миллиарда:
sum [1 .. 1e9]
< interactive>: out of memory (requested 2097152 bytes)
Интуитивно кажется, что для решения этой задачи нам нужно лишь две ячейки памяти. В одной мы бу-
дем постоянно прибавлять к значению единицу, пока не дойдём до миллиарда, так мы последовательно
будем получать элементы списка, а в другой мы будем хранить значение суммы. Мы начнём с нуля и будем
прибавлять значения первой ячейки. У ленивой стратегии другое мнение на этот счёт. Если вы вернётесь к
примеру выше, то заметите, что sum копит отложенные выражения до самого последнего момента. Поскольку
память ограничена, такой момент не наступает. Как нам быть? В Haskell по умолчанию все вычисления про-
водятся по необходимости, но предусмотрены и средства для имитации вычисления по значению. Давайте
посмотрим на них.
9.3 Аннотации строгости
Языки с ленивой стратегией вычислений называют не строгими (non-strict), а языки с энергичной стра-
тегией вычислений соответственно~– строгими.
Принуждение к СЗНФ с помощью seq
Мы говорили о том, что при вычислении по имени значения вычисляются только при сопоставлении с
образцом или в case-выражениях. Есть специальная функция seq, которая форсирует приведение к СЗНФ:
seq :: a -> b -> b
Она принимает два аргумента, при выполнении функции первый аргумент приводится к СЗНФ и затем
возвращается второй. Вернёмся к примеру с sum. Привести к СЗНФ число – означает вычислить его полностью.
Определим функцию sum’, которая перед рекурсивным вызовом вычисляет промежуточный результат:
sum’ :: Num a => [a] -> a
sum’ = iter 0
where iter res []
= res
iter res (a:as)
= let res’ = res + a
in
res’ ‘seq‘ iter res’ as
Аннотации строгости | 147
Сохраним результат в отдельном модуле Strict. hs и попробуем теперь вычислить значение, придётся
подождать:
Strict> sum’ [1 .. 1e9]
И мы ждём, и ждём, и ждём. Но переполнения памяти не происходит. Это хорошо. Но давайте прервём
вычисления. Нажмём ctrl+c. Функция sum’ вычисляется, но вычисляется очень медленно. Мы можем су-
щественно ускорить её, если скомпилируем модуль Strict. Для компиляции модуля переключимся в его
текущую директорию и вызовем компилятор ghc с флагом –make:
ghc --make Strict
Появились два файла Strict. hi и Strict. o. Теперь мы можем загрузить модуль Strict в интерпретатор
и сравнить выполнение двух функций:
Strict> sum’ [1 .. 1e6]
5.000005e11
(0.00 secs, 89133484 bytes)
Strict> sum [1 .. 1e6]
5.000005e11
(0.57 secs, 142563064 bytes)
Обратите внимание на прирост скорости. Умение понимать в каких случаях стоит ограничить лень очень
важно. И в программах на Haskell тоже. Также компилировать модули можно из интерпретатора. Для этого
воспользуемся командой :! , она выполняет системные команды в интерпретаторе ghci:
Strict> :! ghc --make Strict
[1 of 1] Compiling Strict
( Strict. hs, Strict. o )
Отметим наличие специальной функции применения, которая просит перед применением привести ар-
гумент к СЗНФ, эта функция определена в Prelude:
($! ) :: (a -> b) -> a -> b
f $! a = a ‘seq‘ f a
С этой функцией мы можем определить функцию sum так:
sum’ :: Num a => [a] -> a
sum’ = iter 0
where iter res []
= res
iter res (a:as)
= flip iter as $! res + a
Функции с хвостовой рекурсией
Определим функцию, которая не будет лениться при вычислении произведения чисел, мы назовём её
product’:
product’ :: Num a => [a] -> a
product’ = iter 1
where iter res []
= res
iter res (a:as)
= let res’ = res * a
in
res’ ‘seq‘ iter res’ as
Смотрите функция sum изменилась лишь в двух местах. Это говорит о том, что пора задуматься о том,
а нет ли такой общей функции, которая включает в себя и то и другое поведение. Такая функция есть и
называется она foldl’, вот её определение:
foldl’ :: (a -> b -> a) -> a -> [b] -> a
foldl’ op init = iter init
where iter res []
= res
iter res (a:as)
= let res’ = res ‘op‘ a
in
res’ ‘seq‘ iter res’ as
Мы вынесли в аргументы функции бинарную операцию и начальное значение. Всё остальное осталось
прежним. Эта функция живёт в модуле Data.List. Теперь мы можем определить функции sum’ и prod’:
148 | Глава 9: Редукция выражений
sum’
= foldl’ (+) 0
product’
= foldl’ (*) 1
Также в Prelude определена функция foldl. Она накапливает значения в аргументе, но без принуждения
вычислять промежуточные результаты:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl op init = iter init
where iter res []
= res
iter res (a:as)
= iter (res ‘op‘ a) as
Такая функция называется функцией с хвостовой рекурсией (tail-recursive function). Рекурсия хвостовая
тогда, когда рекурсивный вызов функции является последним действием, которое выполняется в функции.
Посмотрите на второе уравнение функции iter. Мы вызываем функцию iter рекурсивно последним делом. В
языках с вычислением по значению часто хвостовая рекурсия имеет преимущество за счёт экономии памяти
(тот момент который мы обсуждали в самом начале). Но как видно из этого раздела в ленивых языках это не
так. Библиотечная функция sum будет накапливать выражения перед вычислением с риском исчерпать всю
доступную память, потому что она определена через foldl.
Тонкости применения seq
Хочу подчеркнуть, что функция seq не вычисляет свой первый аргумент полностью. Первый аргумент
не приводится к нормальной форме. Мы лишь просим вычислитель узнать какой конструктор находится в
корне у данного выражения. Например в выражении isZero $! infinity знак $! ничем не отличается от
простого применения мы и так будем приводить аргумент infinity к СЗНФ, когда нам понадобится узнать
какое из уравнений для isZero выбрать, ведь в аргументе функции есть сопоставление с образцом.
Посмотрим на один типичный пример. Вычисление среднего для списка чисел. Среднее равно сумме
всех элементов списка, разделённой на длину списка. Для того чтобы вычислить значение за один проход
мы будем одновременно вычислять и сумму элементов и значение длины. Также мы понимаем, что нам не
нужно откладывать вычисления, воспользуемся функцией foldl’:
mean :: [Double] -> Double
mean = division . foldl’ count (0, 0)
where count
(sum, leng) a = (sum+a, leng+1)
division (sum, leng) = sum / fromIntegral leng
Проходим по списку, копим сумму в первом элементе пары и длину во втором. В самом конце делим
первый элемент на второй. Обратите внимание на функцию fromIntegral она преобразует значения из це-
лых чисел, в какие-нибудь другие из класса Num. Сохраним это определение в модуле Strict скомпилируем
модуль и загрузим в интерпретатор, не забудьте импортировать модуль Data.List, он нужен для функции
foldl’. Посмотрим, что у нас получилось:
Prelude Strict> mean [1 .. 1e7]
5000000.5
(49.65 secs, 2476557164 bytes)
Получилось очень медленно, странно ведь порядок этой функции должен быть таким же что и у sum’.
Посмотрим на скорость sum’:
Prelude Strict> sum’ [1 .. 1e7]
5.0000005e13
(0.50 secs, 881855740 bytes)
В 100 раз быстрее. Теперь представьте, что у нас 10 таких функций как mean они разбросаны по всему
коду и делают своё чёрное ленивое дело. Причина такого поведения кроется в том, что мы опять завернули
значение в другой тип, на этот раз в пару. Когда вычислитель дойдёт до seq, он остановится на выражении
(thunk, thunk) вместо двух чисел. Он вновь будет накапливать отложенные вычисления, а не значения.
Перепишем mean, теперь мы будем вычислять значения пары по отдельности и попросим вычислитель
привести к СЗНФ каждое из них перед вычислением итогового значения:
mean’ :: [Double] -> Double
mean’ = division . iter (0, 0)
where iter res
[]
= res
iter (sum, leng)
(a:as)
=
let s = sum
+ a
l = leng + 1
in
s ‘seq‘ l ‘seq‘ iter (s, l) as
division (sum, leng) = sum / fromIntegral leng
Аннотации строгости | 149
Такой вот монстр. Функция seq право ассоциативна поэтому скобки будут группироваться в нужном
порядке. В этом определении мы просим вычислитель привести к СЗНФ числа, а не пары чисел, как в прошлой
версии. Для чисел СЗНФ совпадает с НФ, и всё должно пройти гладко, но сохраним это определение и
проверим результат:
Prelude Strict> :! ghc --make Strict
[1 of 1] Compiling Strict
( Strict. hs, Strict. o )
Prelude Strict> :load Strict
Ok, modules loaded: Strict.
(0.00 secs, 0 bytes)
Prelude Strict> mean’ [1 .. 1e7]
5000000.5
(0.65 secs, 1083157384 bytes)
Получилось! Скорость чуть хуже чем у sum’, но не в сто раз.
Энергичные образцы
В GHC предусмотрены специальные обозначения для принудительного приведения выражения к СЗНФ.
Они не входят в стандарт языка Haskell, поэтому для того, чтобы воспользоваться ими, нам необходимо
подключить их. Расширения подключаются с помощью специального комментария в самом начале модуля:
{-# LANGUAGE BangPatterns #-}
Эта запись активирует расширение языка с именем BangPatterns. Ядро языка Haskell фиксировано стан-
дартом, но каждый разработчик компилятора может вносить свои дополнения. Они подключаются через
директиву LANGUAGE:
{-# LANGUAGE
Расширение1,
Расширение2,
Расширение3 #-}
Мы заключаем директиву в специальные комментарии с решёткой, говорим LANGUAGE а затем через за-
пятую перечисляем имена расширений, которые нам понадобятся. Расширения активны только в рамках
данного модуля. Например если мы импортируем функции из модуля, в котором включены расширения, то
эти расширения не распространяются дальше на другие модули. Такие комментарии с решёткой называют
прагмами (pragma).
Нас интересует расширение BangPatterns (bang – восклицательный знак, вы сейчас поймёте почему оно
так называется). Посмотрим на функцию, которая использует энергичные образцы:
iter (! sum, ! leng) a = (step + a, leng + 1)
В декомпозиции пары перед переменными у нас появились восклицательные знаки. Они говорят вычис-
лителю о том, чтобы он так уж и быть сделал ещё одно усилие и заглянул в корень значений переменных,
которые были переданы в эту функцию.
Вычислитель говорит ладно-ладно сделаю. А там числа! И получается, что они не накапливаются. С помо-
щью энергичных образцов мы можем переписать функцию mean’ через foldl’, а не выписывать её целиком:
mean’’ :: [Double] -> Double
mean’’ = division . foldl’ iter (0, 0)
where iter (! sum, ! leng) a = (sum
+ a, leng + 1)
division (sum, leng) = sum / fromIntegral leng
Проверим в интерпретаторе
*Strict> :! ghc --make Strict
[1 of 1] Compiling Strict
( Strict. hs, Strict. o )
*Strict> :l Strict
Ok, modules loaded: Strict.
(0.00 secs, 581304 bytes)
Prelude Strict> mean’’ [1 .. 1e7]
5000000.5
(0.78 secs, 1412862488 bytes)
Prelude Strict> mean’ [1 .. 1e7]
5000000.5
(0.65 secs, 1082640204 bytes)
Функция работает чуть медленнее, чем исходная версия, но не сильно.
150 | Глава 9: Редукция выражений
Энергичные типы данных
Расширение BangPatterns позволяет указывать какие значения привести к СЗНФ не только в образцах,
но и в типах данных. Мы можем создать тип:
data P a b = P ! a ! b
Этот тип обозначает пару, элементы которой обязаны находиться в СЗНФ. Теперь мы можем написать
ещё один вариант функции поиска среднего:
mean’’’ :: [Double] -> Double
mean’’’ = division . foldl’ iter (P 0 0)
where iter (P sum leng) a = P (sum
+ a) (leng + 1)
division (P sum leng) = sum / fromIntegral leng
9.4 Пример ленивых вычислений
У вас может сложиться ошибочное представление, что ленивые вычисления созданы только для того,
чтобы с ними бороться. Пока мы рассматривали лишь недостатки, вскользь упомянув о преимуществе выра-
зительности. Ленивые вычисления могут и экономить память! Мы можем строить огромные промежуточные
данные, обрабатывать их разными способами при условии, что в конце программы нам потребуется лишь
часть этих данных или конечный алгоритм будет накапливать определённую статистику.
Рассмотрим такое выражение:
let longList = produce x
in
sum’ $ filter p $ map f longList
Функция produce строит огромный список промежуточных данных. Далее мы преобразуем эти данные
функцией f и фильтруем их предикатом p. Всё это делается для того, чтобы посчитать сумму всех элементов
в списке. Посмотрим как повела бы себя в такой ситуации энергичная стратегия вычислений. Сначала был
бы вычислен список longList, причём полностью. Затем все элементы были бы преобразованы функцией f.
У нас в памяти уже два огромных списка. Теперь мы фильтруем весь список и в самом конце суммируем.
Было бы очень плохо заставлять энергичный вычислитель редуцировать такое выражение.
А в это время ленивый вычислитель поступит так. Сначала всё выражение будет сохранено в виде опи-
сания, затем он скажет разверну сначала sum’, эта функция запросит первый элемент списка, что приведёт
к вызову filter. Фильтр будет запрашивать следующий элемент списка у подчинённых ему функций до
тех пор, пока предикат p не вернёт True на одном из них. Всё это время функция map будет вытягивать из
produce по одному элементу. Причём память, выделенная на промежуточные не нужные значения (на них
p вернул False) будет переиспользована. Как только sum’ прибавит первый элемент, она запросит следую-
щий, проснётся фильтр и так далее. Вся функция будет работать в постоянном ограниченном объёме памяти,
который не зависит от величины списка longList!
Примерам ленивых вычислений будет посвящена отдельная глава, а пока приведём один пример. Найдём
корень уравнения с помощью метода неподвижной точки. У нас есть функция f :: a -> a, и нам нужно
найти решение уравнения:
f x = x
Можно начать с какого-нибудь стартового значения, и подставлять, подставлять, подставлять его в f до
тех пор, пока значение не перестанет изменяться. Так мы найдём решение.
x1 = f x0
x2 = f x1
x3 = f x2
...
до тех пор пока abs (x[N] - x[N-1]) <= eps
Первое наблюдение: функция принимает не произвольные значения, а те для которых имеет смысл опе-
рации: минус, поиск абсолютного значения и сравнение на больще/меньше. Тип нашей функции:
f :: (Ord a, Num a) => a -> a
Ленивые вычисления позволяют нам отделить шаг генерации решений, от шага проверки сходимости.
Сначала мы сделаем список всех подстановок функции f, а затем найдём в этом списке два соседних элемента
расстояние между которыми достаточно мало. Итак первый шаг, генерируем всю последовательность:
Пример ленивых вычислений | 151
xNs = iterate f x0
Мы воспользовались стандартной функцией iterate из Prelude. Теперь ищем два соседних числа:
converge :: (Ord a, Num a) => a -> [a] -> a
converge eps (a:b:xs)
| abs (a - b) <= eps
= a
| otherwise
= converge eps (b:xs)
Поскольку список бесконечный мы можем не проверять случаи для пустого списка. Итоговое решение:
roots :: (Ord a, Num a) => a -> a -> (a -> a) -> a
roots eps x0 f = converge eps $ iterate f x0
За счёт ленивых вычислений функции converge и iterate работают синхронно. Функция converge запра-
шивает новое значение и iterate передаёт его, но только одно! Найдём решение какого-нибудь уравнения.
Запустим интерпретатор. Мы ленимся и не создаём новый модуль для такой “большой” функции. Опреде-
ляем её сразу в интерпретаторе.
Prelude> let converge eps (a:b:xs) = if abs (a-b)<=eps then a else converge eps (b:xs) Prelude> let roots eps x0 f = converge eps $ iterate f x0
Найдём корень уравнения:
x( x − 2) = 0
x 2 − 2 x = 0
1 x 2 = x
2
Prelude> roots 0.001 5 (\x -> x*x/2)
Метод завис, остаётся только нажать ctrl+c для остановки. На самом деле есть одно условие для сходи-
мости метода. Метод сойдётся, если модуль производной функции f меньше единицы. Иначе есть возмож-
ность, что мы будем бесконечно генерировать новые подстановки. Вычислим производную нашей функции:
d 1 x 2 = x
dx 2
Нам следует ожидать решения в интервале от минус единицы до единицы:
Prelude> roots 0.001 0.5 (\x -> x*x/2)
3.0517578125e-5
Мы нашли решение, корень равен нулю. В этой записи Ne-5 означает N · 10 − 5
9.5 Краткое содержание
В этой главе мы узнали о том как происходят вычисления в Haskell. Мы узнали, что они ленивые. Всё
вычисляется как можно позже и как можно меньше. Такие вычисления называются вычислениями по необ-
ходимости.
Также мы узнали о вычислениях по значению и вычислениях по имени.
• В вычислениях по значению редукция проводится от листьев дерева выражения к корню
• В вычислениях по имени редукция проводится от корня дерева выражения к листьям.
152 | Глава 9: Редукция выражений
Вычисление по необходимости является улучшением вычисления по имени. Мы не дублируем выражения
во время применения. Мы сохраняем значения в памяти и подставляем в функцию ссылки на значения. После
вычисления значения происходит его обновление в памяти. Так если в одном месте выражение уже было
вычислено и мы обратимся к нему по ссылке из другого места, то мы не будем перевычислять его, а просто
считаем готовое значение.
Мы познакомились с терминологией процесса вычислений. Выражение может находится в нормальной
форме. Это значит что оно вычислено. Может находится в слабой заголовочной нормальной форме. Это значит,
что мы знаем хотя бы один конструктор в корне выражения. Также возможно выражение ещё не вычислялось,
тогда оно является отложенным (thunk).
Суть ленивых вычислений заключается в том, что они происходят синхронно. Если у нас есть композиция
двух функций:
g ( f x)
Внутренняя функция f не начнёт вычисления до тех пор пока значения не понадобятся внешней функции
g. О последствиях этого мы остановимся подробнее в отдельной главе. Значения могут потребоваться только
при сопоставлении с образцом. Когда мы хотим узнать какое из уравнений нам выбрать.
Иногда ленивые вычисления не эффективны по расходу памяти. Это происходит когда выражение состоит
из большого числа подвыражений, которые будут вычислены в любом случае. В 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).
Стек – это очередь с принципом работы “последним пришёл, первым ушёл”. Стек можно представить как
стопку книг. У нас есть две операции: положить книгу наверх, и снять верхнюю книгу. Стек очень удобен
для переключения контекстов вычисления. Представьте, что у нас есть функция, которая внутри вызывает
другую функцию, а та следующую. Находясь в верхней функции при заходе во вторую мы сохраняем контекст
внешней функции в стеке. Контекст – это та информация, которая нужна нам для того, чтобы продолжить
вычисления. Как только мы доходим до третьей функции, мы “кладём на стопку сверху” контекст второй
функции, как только третья функция вычислена, мы обращаемся к стеку и снимаем с него контекст второй
функции продолжаем вычислять и как только вторая функция заканчивается снова обращаемся к стеку. А
там сверху уже лежит контекст самой первой функции. Мы можем продолжать вычисления. Так происходит
вычисление вложенных функций в императивных языках программирования.
В куче мы храним разные данные. Данные бывают статическими (они нужны нам на протяжении выполне-
ния всей программы) и динамическими (время жизни динамических данных заранее неизвестно, например
это могут быть отложенные вычисления, мы не знаем когда ни нам понадобятся). У кучи также две опера-
ции: выделить блок памяти, эта операция принимает размер блока и возвращает адрес, по которому удалось
выделить память, и освободить память по указанному адресу. Регистры находятся в процессоре. В них можно
записывать и читать данные, при этом операции обращения к регистрам будут происходить очень быстро.
Посмотрим как 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–. Это язык низкого уровня, “портируемый ассемблер”. На этом
языке не пишут программы, он предназначен для автоматической генерации кода. Далее из него получают
другие низкоуровневые коды. Возможна генерация C, LLVM и нативного кода (код, который исполняется
операционной системой).
10.2 Язык STG
STG расшифровывается как Spineless Tagless G-machine. G-machine или Г-машина – это низкоуровневое
описание процесса редукции графов (от Graph). Пока мы называли этот процесс редукцией синонимов.
Spineless и Tagless – это термины специфичные для G-машины, которая была придумана разработчиками
GHC. Tagless относится к особому представлению объектов в куче (объекты представлены единообразно, так
156 | Глава 10: Реализация Haskell в GHC
что им не нужен специальный тег для обозначения типа объекта), а Spineless относится к тому, что в от-
личие от машин-предшественников, которые описывают процесс редукции графов виде последовательности
инструкций, STG является небольшим функциональным языком. На (рис. ?? ) представлен синтаксис языка
STG. Синтаксис упрощён для чтения людьми. Несмотря на упрощения мы сможем посмотреть как происходит
вычисление выражений.
Переменные x, y, f, g
Конструкторы
C
Объявлены в определениях типов
Литералы
lit
::=
i | d
Незапакованные целые
или действительные числа
Атомы
a, v
::=
lit | x
Аргументы функций атомарны
Арность функции
k
::=
•
Арность неизвестна
|
n
Арность известна n ≥ 1
Выражения
e
::=
a
Атом
|
f k a 1 . . . an
Вызов функции ( n ≥ 1)
|
⊕ a 1 . . . an
Вызов примитивной функции ( n ≥ 1)
|
let x = obj in e
Выделение нового объекта obj в куче
|
case e of {alt 1; . . . ; altn}
Приведение выражения e к СЗНФ
Альтернативы
alt
::=
C x 1 . . . xn → e
Сопоставление с образцом ( n ≥ 1)
|
x → e
Альтернатива по умолчанию
Объекты в куче
obj
::=
F U N ( x 1 . . . xn → e)
Функция арности n ≥ 1
|
P AP ( f a 1 . . . an)
Частичное применение f может
указывать только на F UN
|
CON ( C a 1 . . . an)
Полное применение конструктора ( n ≥ 0)
|
T HU N K e
Отложенное вычисление
|
BLACKHOLE
Используется только во время
выполнения программы
Программа
prog
::=
f 1= obj 1 ; . . . ; fn= objn
Рис. 10.2: Синтаксис STG
По синтаксису STG можно понять, какие выражения языка Haskell являются синтаксическим сахаром. Им
просто нет места в языке STG. Например, не видим мы сопоставления с образцом. Оно как и if-выражения
переписывается через case-выражения. Исчезли where-выражения. Конструкторы могут применяться толь-
ко полностью, то есть для применения конструктора мы должны передать ему все аргументы. В STG let-
выражения разделяют на не рекурсивные (let) и рекурсивные (letrec). Разделение проводится в целях оп-
тимизации, мы же будем считать, что эти случаи описываются одной конструкцией.
На что стоит обратить внимание? Заметим, что функции могут принимать только атомарные значения
(либо примитивные значения, либо переменные). В данном случае переменные указывают на объекты в куче.
Так если в Haskell мы пишем:
foldr f (g x y) (h x)
В STG это выражение примет вид:
let gxy = THUNK (g x y)
hx
= THUNK (h x)
in
foldr f gxy hx
У функций появились степени. Что это? Степени указывают на арность функции, то есть на количество
принимаемых аргументов. Количество принимаемых аргументов определяется по левой части функции. По-
скольку в Haskell функции могут возвращать другие функции, очень часто мы не можем знать арность, тогда
мы пишем •.
Отметим два важных принципа вычисления на STG:
• Новые объекты создаются в куче только в let-выражениях
• Выражение приводится к СЗНФ только в case-выражениях
Язык STG | 157
Выражение let a = obj in e означает добавь в кучу объект obj под именем a и затем вычисли e.
Выражение case e of~{alt1; ... ;alt2} означает узнай конструктор в корне e и продолжи вычисления в
соответствующей альтернативе. Обратите внимание на то, что сопоставления с образцом в альтернативах
имеет только один уровень вложенности. Также аргумент case-выражения в отличие от функции не обязан
быть атомарным.
Для тренировки перепишем на STG пример из раздела про ленивые вычисления.
data Nat = Zero | Succ Nat
zero
= Zero
one
= Succ zero
two
= Succ one
foldNat :: a -> (a -> a) -> Nat -> a
foldNat z
s
Zero
= z
foldNat z
s
(Succ n)
= s (foldNat z s n)
add a = foldNat a
Succ
mul a = foldNat one (add a)
exp = (\x -> add (add x x) x) (add Zero two)
Теперь в STG:
data Nat = Zero | Succ Nat
zero
= CON(Zero)
one
= CON(Succ zero)
two
= CON(Succ one)
foldNat = FUN( z s arg ->
case arg of
Zero
-> z
Succ n
-> let next = THUNK (foldNat z s n)
in
s next
)
add
= FUN( a ->
let succ = FUN( x ->
let r = CON(Succ x)
in r)
in
foldNat a succ
)
mul
= FUN( a ->
let succ = THUNK (add a)
in
foldNat one succ
)
exp
= THUNK(
let f = FUN( x -> let axx = THUNK (add x x)
in
add axx x)
a = THUNK (add Zero two)
in
f a
)
Программа состоит из связок вида имя = объектКучи. Эти связки называют глобальными, они становятся
статическими объектами кучи, остальные объекты выделяются динамически в let-выражениях. Глобальный
объект типа THUNK называют постоянной аппликативной формой (constant applicative form или сокращённо
CAF).
10.3 Вычисление STG
Итак у нас есть упрощённый функциональный язык. Как мы будем вычислять выражения? Присутствие
частичного применения усложняет этот процесс. Для многих функций мы не знаем заранее их арность. Так
например в выражении
158 | Глава 10: Реализация Haskell в GHC
f x y
Функция f может иметь один аргумент в определении, но вернуть функцию. Есть два способа вычисления
таких функций:
• вставка-вход (push-enter). Когда мы видим применение функции, мы сначала вставляем все аргументы
в стек, затем совершаем вход в тело функции. В процессе входа мы вычисляем функцию f и узнаём чис-
ло аргументов, которое ей нужно, после этого мы извлекаем из стека необходимое число аргументов, и
применяем к ним функцию, если мы снова получаем функцию, тогда мы опять добираем необходимое
число аргументов из стека. И так пока аргументы в стеке не кончатся.
• вычисление-применение (eval-apply). Вместе с функцией мы храним информацию о том, сколько аргу-
ментов ей нужно. Если это статически определённая функция (определение выписано пользователем),
то число аргументов мы можем понять по левой части определения. В этой стратегии, если число ар-
гументов известно, мы сразу вычисляем значение с нужным числом аргументов, сохранив оставшиеся
в стеке, а затем извлекаем аргументы из стека и применяем к ним вычисленное значение.
Возвращаясь к исходному примеру, предположим, что арность функции f равна единице. Тогда страте-
гия вставка-вход сначала добавит на стек x и y, а затем будет добирать из стека необходимые аргументы.
Стратегия вычисление-применение сначала вычислит (f x), сохранив y на стеке, затем попробует приме-
нить результат к y. Почему мы говорим попробует? Может так случиться, что арность значения f x окажется
равным трём, но пока у нас есть лишь один аргумент, тогда мы создадим объект PAP, который соответствует
частичному применению.
Эти стратегии применимы как к ленивым, так и к энергичным языкам. Исторически сложилось, что лени-
вые языки тяготеют к первой стратегии, а энергичные ко второй. До недавнего времени и в GHC применялась
первая стратегия. Пока однажды разработчики GHC всё же не решили сравнить две стратегии. Реализовав
обе стратегии, и проверив их на большом количестве разных по сложности программ, они пришли к вы-
воду, что ни одна из стратегий не даёт существенного преимущества на этапе вычислений. Потребление
ресурсов оказалось примерно равным. Но вторая стратегия заметно выигрывала в простоте реализации. По-
дробнее об этом можно почитать в статье Simon Marlow, Simon Peyton Jones: Making a Fast Curry: Push/Enter
vs. Eval/Apply. Описание модели вычислений GHC, которое вы сейчас читаете копирует описание приведён-
ное в этой статье.
Куча
Объекты кучи принято называть замыканиями (closure). Их называют так, потому что обычно для вычис-
ления выражения нам не достаточно знать его текст, например посмотрим на функцию:
mul
= FUN( a ->
let succ = THUNK (add a)
in
foldNat one succ
)
Для того, чтобы вычислить THUNK(add a) нам необходимо знать значение a, это значение определено в те-
ле функции. Оно определяется из контекста. По отношению к объекту такую переменную называют свободной
(free). В куче мы будем хранить не только выражение (add a), но и ссылки на все свободные переменные, ко-
торые участвуют в выражении объекта. Эти ссылки называют довесок (payload). Объект кучи содержит ссылку
на специальную таблицу и довесок. В таблице находятся информация о типе объекта и код, который необ-
ходимо вычислить, а также другая служебная информация. При вычислении объекта мы заменяем ссылки
настоящими значениями или ссылками на конструкторы.
Объект кучи может быть:
• FUN – определением функции;
• PAP – частичным применением;
• CON – полностью применённым конструктором;
• THUNK – отложенным вычислением;
• BLACKHOLE – это значение используется во время вычисления THUNK. Этот трюк предотвращает появле-
ние утечек памяти.
Мы будем считать, что куча – это таблица, которая ставит в соответствие адресам объекты или вычис-
ленные значения.
Вычисление STG | 159
Стек
Стек служит для быстрого переключения контекста. Мы будем пользоваться стеком при вычислении case-
выражений и THUNK-объектов. При вычислении case-выражения мы сохраняем в стеке альтернативы и место
возврата значения, а сами начинаем вычислять аргумент case-выражения. При вычислении THUNK-объекта
мы запомним в стеке, адрес с которым необходимо связать полученное значение.
При вычислении в стратегии вставка-вход мы будем сохранять в стеке аргументы функции. А при вычис-
лении в стратегии вычисление-применение мы также будем сохранять аргументы функции в стеке. Какая
разница между этими вариантами? В первой стратегии мы можем доставать из стека произвольное число
аргументов, после определения арности функции мы добираем столько, сколько нам нужно, поэтому мы
будем хранить аргументы по одному. Во второй же стратегии нам нужно просто сохранить все оставшиеся
аргументы. Мы сохраняем и извлекаем их все сразу. Упрощая, объекты стека можно представить так:
k
::=
case • of {alt 1; . . . altn}
контекст case-выражения
|
U pd t •
Обновить отложенное вычисление
|
( • a 1 ...an)
Применить функцию к аргументам, только для
стратегии вычисление-применение
|
Arg a
Аргумент на потом, только для
стратегии вставка-вход
Рис. 10.3: Синтаксис STG
Правила общие для обеих стратегий вычисления
Состояние вычислителя состоит из трёх частей. Это выражение для вычисления e, стек s и куча H. Мы
рассмотрим правила по которым вычислитель переходит из одного состояния в другое. Все они имеют вид:
e 1;
s 1;
H 1
⇒ e 2; s 2; H 2
Левая часть переходит в правую, при условии, что левая часть имеет определённый вид. Начнём с правил,
которые одинаковы и в той и в другой стратегии вычисления. Для простоты пока мы будем полагать, что
объекты только добавляются в кучу и никогда не стираются. Мы будем обозначать добавление в стек как
добавление элемента в обычный список: elem : s.
Рассмотрим правило для let-выражений:
let x = obj in e;
s;
H
⇒ e[ x / x]; s; H[ x → obj] , x – новое имя
Рис. 10.4: Синтаксис STG
В этом правиле мы добавляем в кучу новый объект obj под именем (или по адресу) x . Запись e[ x / x]
означает замену x на x в выражении e.
Теперь разберёмся с правилами для case-выражений.
case v of {. . . ; C x 1 . . . xn → e; . . . };
⇒ e[ a 1/ x 1 . . . an/ xn]; s; H
s;
H[ v → CON ( C a 1 . . . an)]
case v of {. . . ; x → e};
s;
H
⇒ e[ v/ x]; s; H
Если v – литерал или H[ v] – значение,
которое не подходит ни по одной из альтернатив
case e of {. . . };
s;
H
⇒ e; case • of {. . . } : s; H
v;
case • of {. . . } : s;
H
⇒ case v of {. . . }; s; H
Рис. 10.5: Синтаксис STG
Вычисления начинаются с третьего правила, в котором нам встречается case-выражения с произвольным
e. В этом правиле мы сохраняем в стеке альтернативы и адрес возвращаемого значения и продолжаем вы-
числение выражения e. После вычисления мы перейдём к четвёртому правилу, тогда мы снимем со стека
160 | Глава 10: Реализация Haskell в GHC
информацию необходимую для продолжения вычисления case-выражения. Это приведёт нас к одному из
первых двух правил. В первом правиле значение аргумента содержит конструктор, подходящий по одной из
альтернатив, а во втором мы выбираем альтернативу по умолчанию.
Теперь посмотрим как вычисляются THUNK-объекты.
x;
s;
H[ x → T HU N K e]
⇒ e; Upd x • : s; H[ x → BLACKHOLE]
y;
U pd x • : s;
H
⇒ y; s; H[ x → H[ y]]
если H[ y] является значением
Рис. 10.6: Синтаксис STG
Если переменная указывает на отложенное вычисление e, мы сохраняем в стеке адрес по которому
необходимо обновить значение и вычисляем значение e. В это время мы записываем в по адресу x объ-
ект BLACKHOLE. У нас нет такого правила, которое реагирует на левую часть, если в ней содержится
объект BLACKHOLE. Поэтому во время вычисления T HUNK ни одно из правил сработать не может.
Этот трюк необходим для избежания утечек памяти. Как только выражнение будет вычислено мы извлечём
из стека адрес x и обновим значение.
Правила применения функций, если арность совпадает с числом аргументов в тексте выражения:
f n a 1 . . . an;
s;
H[ y → F U N ( x 1 . . . xn → e)]
⇒ e[ a 1/ x 1 . . . an/ xn]; s; H
⊕ a 1 . . . an; s; H
⇒ a; s; H
a – результат вычисления ( ⊕ a 1 . . . an)
Рис. 10.7: Синтаксис STG
Мы просто заменяем все вхождения аргументов на значения. Второе правило выполняет применение
примитивной функции к значениям.
Правила для стратегии вставка-вход
f k a 1 . . . am;
s;
H
⇒ f; Arg a 1 : … : Arg am : s; H
f ;
Arg a 1 : … : Arg an : s;
H[ f → F U N ( x 1 . . . xn → e)]
⇒ e[ a 1/ x 1 . . . an/ xn]; s; H
f ;
Arg a 1 : … : Arg am : s;
H[ f → F U N ( x 1 . . . xn → e)]
⇒ p; s; H[ p → P AP ( f a 1 . . . am)]
при m ≥ 1; m < n; верхний элемент s
не является Arg; p – новый адрес
f ;
Arg an+1 : s;
H[ f → P AP ( g a 1 . . . an)]
⇒ g; Arg a 1 : … : Arg an : Arg an+1 : s; H
Рис. 10.8: Синтаксис STG
Первое правило выполняет этап “вставка”. Если мы видим применение функции, мы первым делом со-
храняем все аргументы в стеке. Во втором правиле мы вычислили значение f, оно оказалось функцией с
арностью n. Тогда мы добираем из стека n аргументов и подставляем их в правую часть функции e. Если
в стеке оказалось слишком мало аргументов, то мы переходим к третьему правилу и составляем частичное
применение. Последнее правило говорит о том как расшифровывается частичное применение. Мы вставляем
в стек все аргументы и начинаем вычисление функции g из тела P AP .
Вычисление STG | 161
f • a 1 . . . an;
s;
H[ f → F U N ( x 1 . . . xn → e)]
⇒ e[ a 1/ x 1 . . . an/ xn]; s; H
f k a 1 . . . am;
s;
H[ f → F U N ( x 1 . . . xn → e)]
⇒ e[ a 1/ x 1 . . . an/ xn]; ( • an+1 . . . am) : s; H
при m ≥ n
⇒ p; s; H[ p → P AP ( f a 1 . . . am)]
при m < n, p – новый адрес
f • a 1 . . . am;
s;
H[ f → T HU N K e]
⇒ f; ( • a 1 . . . am) : s; H
f k an+1 . . . am;
s;
H[ f → P AP ( g a 1 . . . an)]
⇒ g• a 1 . . . an an+1 . . . am; s; H
f ;
( • a 1 . . . an) : s;
H
⇒ f• a 1 . . . an; s; H
H[ f ] является F U N или P AP
Рис. 10.9: Синтаксис STG
Правила для стратегии вычисление-применение
Разберёмся с первыми двумя правилами. В первом правиле статическая арность f неизвестна, но зна-
чение f уже вычислено, и мы можем узнать арность по объекту F UN, далее возможны три случая. Число
аргументов переданных в функцию совпадает с арностью F UN, тогда мы применяем аргументы к правой
части F UN. Если в функцию передано больше аргументов чем нужно, мы сохраняем лишние на стеке. Если
же аргументов меньше, то мы создаём объект P AP . Третье правило говорит о том, что нам делать, если зна-
чение f ещё не вычислено. Оно является T HUNK. Тогда мы сохраним аргументы на стеке и вычислим его.
В следующем правиле мы раскрываем частичное применение. Мы просто организуем вызов функции со все-
ми аргументами (и со стека и из частичного применения). Последнее правило срабатывает после третьего.
Когда мы вычислим T HUNK и увидим там F UN или P AP . Тогда мы составляем применение функции.
Сложность применения стратегии вставка-вход связана с плохо предсказуемым изменением стека. Если в
стратегии вычисление-выполнение мы добавляем и снимаем все аргументы, то в стратегии вставка-вход мы
добавляем их по одному и неизвестно сколько снимем в следующий раз. Кроме того стратегия вычисление-
применение позволяет проводить оптимизацию перемещения аргументов. Вместо стека мы можем хранить
аргументы в регистрах. Тогда скорость обращения к аргументам резко возрастёт.
10.4 Представление значений в памяти. Оценка занимаемой памяти
Ранее мы говорили, что полностью вычисленное значение – это дерево, в узлах которого находятся одни
лишь конструкторы. Процесс вычисления похож на очистку дерева выражения от синонимов. Мы начинаем с
самого верха и идём к листьям. Потом мы выяснили, что для предотвращения дублирования вычислений мы
подставляем в функции не сами значения, а ссылки на значения. Теперь нам понятно, что ссылки указывают
на объекты в куче. Ссылки – это атомарные переменные. Полностью вычисленное значение является сетью
(или графом) объектов кучи типа CON.
Поговорим о том сколько места в памяти занимает то или иное значение. Как мы говорили память ком-
пьютера состоит из ячеек, в которых хранятся значения. У каждой ячейки есть адрес. Ячейки памяти неде-
лимы, их также принято называть словами. Мы будем оценивать размер значения в словах.
Каждый конструктор требует столько слов сколько у него полей плюс ещё одно слово для ссылки на
служебную информацию (она нужна вычислителю). Посмотрим на примеры:
data Int = I# Int#
-- 2 слова
data Pair a b = Pair a b
-- 3 слова
У этого правила есть исключение. Если у конструктора нет полей, то есть он является константой или
примитивным конструктором, то в процессе вычисления значение этого конструктора представлено ссылкой.
Это означает, что внутри программы все значения ссылаются на одну область памяти. У нас действительно
есть лишь один пустой список или одно значение True или False.
Посчитаем число слов в значении [Pair 1 2]. Для этого для начала перепишем его в STG
nil = []
-- глобальный объект (не в счёт)
162 | Глава 10: Реализация Haskell в GHC
let x1
= I# 1
-- 2 слова
x2
= I# 2
-- 2 слова
p
= Pair x1 x2
-- 3 слова
val = Cons p nil
-- 3 слова
in
val
------------
-- 10 слов
Поскольку объект кучи CON может хранить только ссылки, нам пришлось введением дополнительных
переменных “развернуть” значение. Примитивный конструктор не считается, поскольку он сохранён гло-
бально, в итоге получилось 10 слов. Посмотрим на ещё один пример, распишем значение [Just True, Just
True, Nothing]:
nil
= []
true
= True
nothing = Nothing
let x1 = Just true
-- 2 слова
x2 = Just true
-- 2 слова
p1 = Cons nothing nil
-- 3 слова
p2 = Cons x2 p1
-- 3 слова
p3 = Cons x1 p2
-- 3 слова
in
p3
----------
-- 13 слов
Обычно одно слово соответствует 16, 32 или 64 битам. Эта цифра зависит от процессора. Мы считали,
что любое значение можно поместить в одно слово, но это не так. Возьмём к примеру действительные чис-
ла с двойной точностью, они не поместятся в одно слово. Это необходимо учитывать при оценке объёма
занимаемой памяти.
10.5 Управление памятью. Сборщик мусора
В прошлом разделе для простоты мы считали, что объекты только добавляются в кучу. На самом деле это
не так. Допустим во время вычисления функции нам нужно было вычислить какие-то промежуточные дан-
ные, например объявленные в локальных переменных, тогда после вычисления результата все эти значения
больше не нужны. При этом в куче висит много-много объектов, которые уже не нужны. Нам нужно как-то от
них избавится. Этой задачей занимается отдельный блок вычислителя, который называется сборщиком му-
сора (garbage collector), соответственно процесс автоматического освобождения памяти называется сборкой
мусора (garbage collection или GC).
На данный момент в GHC используется копирующий последовательный сборщик мусора, который рабо-
тает по алгоритму Чейни (Cheney). Для начала рассмотрим простой алгоритм сборки мусора. Мы выделяем
небольшой объём памяти и начинаем наполнять его объектами. Как только место кончится мы найдём все
“живые” объекты, а остальное пространство памяти будем считать свободным. Как только после очередной
очистки оказалось, что нам всё же не хватает места. Мы найдём все живые объекты, подсчитаем сколько ме-
ста они занимают и запросим у системы этот объём памяти. Скопируем все живые объекты на новое место, а
старую память будем считать свободной. Так например, если у нас было выделено 30 Мб памяти и оказалось,
что живые объекты занимают 10 Мб, мы выделим ещё 10 Мб, скопируем туда все живые объекты и общий
объём памяти станет равным 40 Мб.
Мы можем оптимизировать сборку мусора. Есть такая гипотеза, что большинство объектов имеют очень
короткую жизнь. Это промежуточные данные, локальные переменные. Нам нужен лишь результат функции,
но на подходе к результату мы сгенерируем много разовой информации. Ускорить очистку можно так. Мы
выделим совсем небольшой участок памяти внутри нашей кучи, его принято называть яслями (nursery area),
и будем выделять и собирать новые объекты только в нём, как только этот участок заполнится мы скопируем
все живые объекты из яслей в остальную память и снова будем наполнять ясли. Как только вся память закон-
чится мы поступим так же как и в предыдущем сценарии. Когда заканчивается место в яслях, мы проводим
поверхностную очистку (minor GC), а когда заканчивается вся память в текущей куче, мы проводим глубокую
очистку (major GC). Эта схема соответствует сборке с двумя поколениями.
10.6 Статистика выполнения программы
Процесс управления памятью скрыт от программиста. Но при этом в GHC есть развитые средства косвен-
ной диагностики работы программы. Пока мы пользовались самым простым способом проверки. Мы вклю-
чали флаг s в интерпретаторе. Пришло время познакомиться и с другими.
Управление памятью. Сборщик мусора | 163
Статистика вычислителя
Для начала научимся смотреть статистику работы вычислителя. Посмотреть статистику можно с помо-
щью флагов s[file] и S[file]. Эти флаги предназначены для вычислителя низкого уровня (realtime system
или RTS, далее просто вычислитель), они заключаются в окружение +RTS ... -RTS, если флаги идут в кон-
це строки и считается, что все последующие флаги предназначены для RTS мы можем просто написать ghc
–make file.hs +RTS ... Например скомпилируем такую программу:
module Main where
main = print $ sum [1 .. 1e5]
Теперь скомпилируем:
$ ghc --make sum.hs -rtsopts -fforce-recomp
Флаг rtsopts позволяет передавать скомпилированной программе флаги для вычислителя низкого уров-
ня, далее для краткости мы будем называть его просто вычислителем. С флагом fforce-recomp программа
будет каждый раз заново пересобираться. Теперь посмотрим на статистику выполнения программы (флаг
s[file], в этом примере мы перенаправляем выход в поток stderr):
$ ./sum +RTS -sstderr
5.00005e9
14,145,284 bytes allocated in the heap
11,110,432 bytes copied during GC
2,865,704 bytes maximum residency (3 sample(s))
460,248 bytes maximum slop
7 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed)
Avg pause
Max pause
Gen
0
21 colls,
0 par
0.00s
0.01s
0.0006s
0.0036s
Gen
1
3 colls,
0 par
0.01s
0.01s
0.0026s
0.0051s
INIT
time
0.00s
(
0.00s elapsed)
MUT
time
0.01s
(
0.01s elapsed)
GC
time
0.01s
(
0.02s elapsed)
EXIT
time
0.00s
(
0.00s elapsed)
Total
time
0.02s
(
0.03s elapsed)
%GC
time
60.0%
(69.5% elapsed)
Alloc rate
1,767,939,507 bytes per MUT second
Productivity
40.0% of total user, 26.0% of total elapsed
Был распечатан результат и отчёт о работе программы. Разберёмся с показателями:
bytes allocated in the heap
-- число байтов выделенных в куче
-- за всё время работы программы
bytes copied during GC
-- число скопированных байтов
-- за всё время работы программы
bytes maximum residency
-- в каком объёме памяти работала программа
-- в скобках указано число глубоких очисток
bytes maximum slop
-- максимум потерь памяти из-за фрагментации
total memory in use
-- сколько всего памяти было запрошено у ОС
Показатель bytes maximum residency измеряется только при глубокой очистке, поскольку новая память
выделяется именно в этот момент. Размер памяти выделенной в куче гораздо больше общего объёма памяти.
Так происходит потому, что этот показатель указывает на общее число памяти в куче за всё время работы
программы. Ведь мы переиспользуем не нужную нам память. По этому показателю можно судить о том,
сколько замыканий (объектов) было выделено в куче.
Следующие две строчки говорят о числе сборок мусора. Мы видим, что GC выполнил 21 поверхностную
очистку (поколение 0) и 3 глубоких (покколение 1). Дальше идут показатели скорости. INIT и EXIT – это
164 | Глава 10: Реализация Haskell в GHC
инициализация и завершение программы. MUT – это полезная нагрузка, время, которая наша программа тра-
тила на изменение (MUTation) значений. GC – время сборки мусора. Далее GHC сообщил нам о том, что мы
провели 60% времени в сборке мусора. Это очень плохо. Продуктивность программы очень низкая. Затратна
глубокая сборка мусора, поверхностная – это дело обычное. Теперь посмотрим на показатели строгой версии
этой программы:
module Main where
import Data.List(foldl’)
sum’ = foldl’ (+) 0
main = print $ sum’ [1 .. 1e5]
Скомпилируем:
$ ghc --make sumStrict.hs -rtsopts -fforce-recomp
Посмотрим на статистику:
$ ./sumStrict +RTS -sstderr
5.00005e9
10,474,128 bytes allocated in the heap
24,324 bytes copied during GC
27,072 bytes maximum residency (1 sample(s))
27,388 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed)
Avg pause
Max pause
Gen
0
19 colls,
0 par
0.00s
0.00s
0.0000s
0.0000s
Gen
1
1 colls,
0 par
0.00s
0.00s
0.0001s
0.0001s
INIT
time
0.00s
(
0.00s elapsed)
MUT
time
0.01s
(
0.01s elapsed)
GC
time
0.00s
(
0.00s elapsed)
EXIT
time
0.00s
(
0.00s elapsed)
Total
time
0.01s
(
0.01s elapsed)
%GC
time
0.0%
(3.0% elapsed)
Alloc rate
1,309,266,000 bytes per MUT second
Productivity 100.0% of total user, 116.0% of total elapsed
Мы видим, что произошла лишь одна глубокая сборка. И это существенно сказалось на продуктивности.
Кромке того мы видим, что программа заняла лишь 27 Кб памяти, вместо 2 Мб как в прошлом случае. Теперь
давайте покрутим ручки у GC. В GHC можно устанавливать разные параметры сборки мусора с помощью
флагов. Все флаги можно посмотреть в документации GHC. Мы обратим внимание на несколько флагов.
Флаг H назначает минимальное значение для стартового объёма кучи. Флаг A назначает объём памяти для
яслей. По умолчанию размер яслей равен 512 Кб (эта цифра может измениться). Изменением этих параметров
мы можем отдалить сборку мусора. Чем дольше работает программа между сборками, тем выше вероятность
того, что многие объекты уже не нужны.
Давайте убедимся в том, что поверхностные очистки происходят очень быстро и совсем не тормозят
программу. Установим размер яслей на 32 Кб вместо 512 Кб как по умолчанию (размер пишется сразу за
флагом, за цифрой идёт k или m):
$ ./sumStrict +RTS -A32k -sstderr
...
Tot time (elapsed)
Avg pause
Max pause
Gen
0
318 colls,
0 par
0.00s
0.00s
0.0000s
0.0000s
Gen
1
1 colls,
0 par
0.00s
0.00s
0.0001s
0.0001s
...
MUT
time
0.01s
(
0.01s elapsed)
GC
time
0.00s
(
0.00s elapsed)
...
%GC
time
0.0%
(11.8% elapsed)
Статистика выполнения программы | 165
Мы видим, что за счёт уменьшения памяти очистки существенно участились, но это не сказалось на об-
щем результате. С помощью флага H[size] мы можем устанавливать рекомендуемое минимальное значение
для размера кучи. Оно точно не будет меньше. Вернёмся к первому варианту и выделим алгоритму побольше
памяти, например 20 Мб:
./sum +RTS -A1m -H20m -sstderr
5.00005e9
14,145,284 bytes allocated in the heap
319,716 bytes copied during GC
324,136 bytes maximum residency (1 sample(s))
60,888 bytes maximum slop
22 MB total memory in use (1 MB lost due to fragmentation)
Tot time (elapsed)
Avg pause
Max pause
Gen
0
2 colls,
0 par
0.00s
0.00s
0.0001s
0.0001s
Gen
1
1 colls,
0 par
0.00s
0.00s
0.0007s
0.0007s
INIT
time
0.00s
(
0.00s elapsed)
MUT
time
0.02s
(
0.02s elapsed)
GC
time
0.00s
(
0.00s elapsed)
EXIT
time
0.00s
(
0.00s elapsed)
Total
time
0.02s
(
0.02s elapsed)
%GC
time
0.0%
(4.4% elapsed)
Alloc rate
884,024,998 bytes per MUT second
Productivity 100.0% of total user, 78.6% of total elapsed
Произошла лишь одна глубокая очистка (похоже, что эта очистка соответствует начальному выделению
памяти) и продуктивность программы стала стопроцентной. С помощью флага S вместо s мы можем по-
смотреть более детальную картину управления памяти. Будут распечатаны показатели памяти для каждой
очистки.
./sum +RTS -Sfile
В файле file мы найдём такую таблицу:
память
время
выделено скопировано в живых
GC
Total
Тип очистки
Alloc
Copied
Live
GC
GC
TOT
TOT
Page Flts
bytes
bytes
bytes
user
elap
user
elap
545028
150088
174632
0.00
0.00
0.00
0.00
0
0
(Gen:
1)
523264
298956
324136
0.00
0.00
0.00
0.00
0
0
(Gen:
0)
...
Итак у нас появился один существенный показатель качества программ. Это количество глубоких очи-
сток. Во время глубокой очистки вычислитель производит две затратные операции: сканирование всей кучи
и запрос у системы возможно большого блока памяти. Чем меньше таких очисток, тем лучше. Сократить их
число можно удачной комбинацией показателей A и H. Но не стоит сразу начинать обновлять параметры по
умолчанию, если ваша программа работает слишком медленно. Лучше сначала попробовать изменить ал-
горитм. Найти функцию, которая слишком много ленится и ограничить её с помощью seq или энергичных
образцов. В этом примере у нас была всего одна функция, поэтому поиск не составил труда. Но что если их
уже очень много? Скорее всего так и будет. Не стоит оптимизировать не рабочую программу. А в рабочей
программе обычно много функций. Но это не так страшно, помимо суммарных показателей GHC позволяет
собирать более конкретную статистику.
Стоит отметить функцию performGC из модуля System.Mem, она форсирует поверхностную сборку мусора.
Допустим вы чистаете какие-то данные из файла и тут же преобразуете их в структуру данных. После того
как чтение данных закончится, вы знаете, что промежуточные данные связаные с чтением вам уже не нужны.
Выполнив performGC вы можете подсказать об этом вычислителю.
Профилирование функций
Время и общий объём памяти
Процесс отслеживания показателей память/скорость называется профилированием программы. Всё вро-
де бы работает, но работает слишком медленно, необходимо установить причину. Рассмотрим такую про-
грамму:
166 | Глава 10: Реализация Haskell в GHC
module Main where
concatR = foldr (++) []
concatL = foldl (++) []
fun :: Double
fun = test concatL - test concatR
where test f = last $ f $ map return [1 .. 1e6]
main = print fun
У нас есть подозрение, что какая-то из двух функций concatX работает слишком медленно. Мы можем
посмотреть какая, если добавим к ним специальную прагму SCC:
concatR = {-# SCC ”right” #-} foldr (++) []
concatL = {-# SCC ”left”
#-} foldl (++) []
Напомню, что прагмой называется специальный блочный комментарий с решёткой. Это специальное со-
общение компилятору. Прагмой SCC мы устанавливаем так называемый центр затрат (cost center). Она пи-
шется сразу за знаком равно. В кавычках пишется имя, под которым статиситика войдёт в итоговый отчёт.
После этого вычислитель будет следить за нагрузкой, которая приходится на эту функцию. Теперь нам нужно
скомпилировать модуль с флагом prof, который активирует подсчёт статистики в центрах затрат:
$ ghc --make concat.hs -rtsopts -prof -fforce-recomp
$ ./concat +RTS -p
Второй командой мы запускаем программу и передаём вычислителю флаг p. После этого будет создан
файл concat. prof. Откроем этот файл:
concat +RTS -p -RTS
total time
=
1.45 secs
(1454 ticks @ 1000 us, 1 processor)
total alloc = 1,403,506,324 bytes
(excludes profiling overheads)
COST CENTRE MODULE
%time %alloc
left
Main
99.8
99.8
individual
inherited
COST CENTRE MODULE
no.
entries
%time %alloc
%time %alloc
MAIN
MAIN
46
0
0.0
0.0
100.0
100.0
CAF
GHC.Integer.Logarithms.Internals
91
0
0.0
0.0
0.0
0.0
CAF
GHC.IO.Encoding.Iconv
71
0
0.0
0.0
0.0
0.0
CAF
GHC.IO.Encoding
70
0
0.0
0.0
0.0
0.0
CAF
GHC.IO.Handle.FD
57
0
0.0
ТЕЛЕГРАМКанал с обзорами, анонсами новинок и книжными подборками
Книжный Вестник
Бот для удобного поиска книг (если не нашлось на сайте)
Поиск книг
Свежие любовные романы в удобных форматах
Любовные романы
О психологии, саморазвитии и личностном росте
Саморазвитие
Детективы и триллеры, все новинки
Детективы
Фантастика и фэнтези, все новинки
Фантастика
Отборные классические книги
Классика
ВКОНТАКТЕБиблиотека с любовными романами, которая наверняка придётся по вкусу женской части аудитории
Любовные романы
Библиотека с фантастикой и фэнтези, а также смежных жанров
Фантастика
Самые популярные книги в формате фб2
Топ фб2
книги