Одной из «визитных карточек» Хаскеля являются отложенные, или ленивые, вычисления. Эта особенность языка не только открывает множество возможностей, но и создаёт некоторые проблемы, особенно со скоростью работы программ.
В этой статье я постараюсь объяснить: что такое ленивые вычисления, для чего они могут применяться и как избежать потери производительности при их использовании.
В обычных, не ленивых, языках программирования вычисления строгие — то есть аргументы функции вычисляются перед выполнением самой функции.
Например, в каком-то абстрактном строгом языке программирования:
А в ленивых языках, в том числе Хаскеле, вычисления отложенные. Все вычисления (кроме некоторых функций ввода-вывода), не выполняются сразу, а как бы откладываются до реальной надобности.
Тот же пример в Хаскеле:
На этом примере хорошо видно, что вычисление подвыражений (5+3 и 4*4) откладывалось до последнего, а именно до момента, когда их пришлось сравнить.
Здесь «силой» что заставила вычисление выполниться можно считать вывод на консоль, т.е. IO. Но это не единственный способ.
Возьмём такой пример:
(далее мы предполагаем, что в in части используется z, иначе let выражение не будет вычислено вообще)
z представляет собой обещание (англ. thunk), просто не вычисленное значение.
А что будет если сравнить с образцом z?
Сначала z — простое обещание, как и в предыдущем примере, но что бы компилятор мог проверить, что z действительно соответствует образцу, ему приходится «развернуть» z до вида:
Добавим ещё одно сравнение с образцом:
Чтобы проверить, что y — список, компилятор вычисляет его до вида:
Потом, он вычисляет первое обещание:
И удостоверившись, что y — список, начинающийся с 'l', он производит сопоставление с образцом:
В данном примере, ys будет обещанием, соответствующим оставшейся части списка y.
Давайте посмотрим на то, как менялась глубина вычисления для z на протяжении всех примеров:
z было частично вычислено, и как можно догадаться, почти все значения в Хаскеле могут быть вычислены таким образом. Например, минимальное возможное вычисление для пары — это просто вычислить конструктор:
Когда значение вычислено не полностью, говорят, что оно в Weak Head Normal Form (WHNF), а когда полностью, то в Normal Form. Значение в WHNF будучи полностью вычислено, «переходит» в Normal Form. Например, если мы выведем z на экран, то его Normal Form будет
Функции бывают ленивыми и строгими в своих аргументах. Ленивые — не вычисляют свои аргументы, а строгие — вычисляют, до какой-либо глубины. Стоит отметить, что функция может быть ленивой в одном аргументе и строгой в другом. Конечно же, большинству функций нужно как-то использовать свои аргументы, что подразумевает их вычисление. Например, функция length. Чтобы узнать длину списка, ей приходится вычислить его конструкторы, но не значения. То есть,
Есть простой способ проверить ленива ли функция в каком-либо аргументе. Нужно просто передать ей заместо аргумента undefined, и если результатом будет ошибка, то функция строга в этом аргументе, а если нет, то ленива.
Не приведут к ошибке:
А эти приведут:
Ленивыми могут быть не только функции, но и сравнения с образцом. В отличии от строгих сопоставлений с образцом, которые мы уже рассматривали, ленивые не заставляют обещания вычисляться, то есть не «развёртывают» их во время компиляции.
Например:
Здесь
Такое сравнение с образцом можно встретить в Control.Arrow:
Но нужно помнить, что ленивый образец стоит использовать, только когда у типа один конструктор.
К примеру:
Так как мы указали, что не надо вычислять аргумент функции пока он не потребуется, не возможно узнать, что перед нами: пустой список или одно его звено. Функция будет всегда возвращать undefined, ведь в первом выражении мы использовали неопровержимый образец.
Самый очевидный плюс ленивых вычислений — если что-то не требуется, оно не будет вычислено.
Например:
Если первый аргумент функции and — False, зачем вычислять второй, если и так понятно, что результатом будет False? Возможно чтобы узнать значение второго аргумента, потребуется произвести множество трудоёмких вычислений, которых, используя ленивые вычисления, можно избежать.
Представим, что Вы хотите найти 3 наименьших элемента списка.
В Хаскеле это можно сделать так:
Но в строгом языке это расточительно, так как придётся отсортировать весь список. Но с ленивыми вычислениями, мы отсортируем список до третьего элемента и остановимся, потому что продолжать вычисление не имеет смысла.
Рассмотрим такую функцию:
Сколько раз была вычислена сумма 5 и 3? Правильный ответ: один раз. Сначала (5+3) — просто обещание, но когда оно было передано функции plus, оно вычислилось и его ответ заместил само обещание. Когда значение a потребовалось во второй раз, программа просто взяла готовый результат из бывшего обещания, не производя никаких вычислений. В этом заключается одно из важнейших свойств ленивых вычислений — мемоизация. Обещание в ленивом языке вычисляется только один раз, а потом результат вычисления «затирает» собой обещание, тем самым давая программе возможность просто узнать ответ, без необходимости вычислять его опять.
Такое свойство ленивых вычислений находит применение в динамическом программировании, что было хорошо показано в статье Динамическое программирование и ленивые вычисления.
Ещё одно, довольно известное применение отложенных вычислений — создание бесконечных структур данных.
Здесь мы создаём бесконечный список нечётных чисел, и берём его 10-ый элемент.
Пример посложнее:
Создание бесконечных списков возможно только потому, что они не вычисляются сразу. Во втором примере, fibs сначала будет
Теперь перейдём к цикличным структурам данных.
Как нам связать два элемента этого типа в кольцо, так, чтобы поле next одного объекта указывало на другой?
Если бы мы хотели осуществить это в императивном языке, мы бы использовали указатели, но в Хаскеле указателей нет. Так как создать такую структуру?
Очень просто:
Вот и всё. Так как поле next у List ленивое (надо помнить, что конструктор типов такая же функция, и его аргументы могут быть ленивыми) создание такого «кольца» не приведёт к зависанию программы в попытках вычислить всю структуру.
Действительно строгими являются только простые функции ввода-вывода, а остальные — ленивые. Это даёт возможность читать и писать в файлы на лету, как по конвейеру, без использования буферов.
Например:
Программа будет выводить текст в верхнем регистре по мере его поступления.
На протяжении всей статьи я использовал термин «обещание», чтобы обозначить некую единицу ленивого вычисления, но дело в том, что это не просто абстрактное понятие. Скомпилированная программа на Хаскеле в действительности использует обещания, которые занимают место в памяти и на стеке. То есть, к расходам на обычные вычисления добавляется сборка мусора, выделение памяти, разворачивание обещаний. В этом и заключается главная проблема ленивых вычислений — за их неграмотное использование можно поплатиться сильным снижением производительности, переполнениями стека и большим потреблением памяти.
Но существуют способы, как сделать вычисления менее ленивыми, которые мы сейчас и рассмотрим.
Рассмотрим такой простой пример:
Здесь мы находим сумму чисел от 1 до 1e6 и выводим её в консоль. Но если вы попытаетесь запустить программу, то увидите такое сообщение:
Почему возникает переполнение стека? Давайте посмотрим, как будет вычисляться функция sum':
Так как вычисление
Для начала перепишем функцию sum' на использование хвостовой рекурсии:
Теперь заставить сложение вычисляться будет не сложно:
Seq заставляет сумму вычислиться, заместо того, чтобы отложить сложение на потом.
Теперь ошибки не происходит.
Попробуем чуть усложнённый пример: кроме суммы элементов подсчитаем и их число.
Опять та же ошибка. Но почему? Мы ведь заставили суммы вычислиться?
Тут пора рассказать об одном свойстве seq: он вычисляет значение до WHNF. У обычных чисел, как было упомянуто ранее, нет WHNF, так что сложение было полностью вычислено seq. Но в этом случае мы пытаемся вычислить пару, которая имеет WHNF, а именно
Немного некрасиво, но работает. Ситуация, когда нужно вычислить что-либо полностью, не так редка, так что для этого был создан специальный модуль. Давайте его опробуем:
Функция deepseq вычисляет значения полностью, до Normal Form.
Для более удобного указания строгости, было создано расширение компилятора — Bang patterns. Оно позволяет указывать строгость аргументов просто восклицательным знаком. С использованием этого расширения, мы можем переписать наш код так:
Всё будет работать, как и прежде.
Bang patterns позволяют нам указывать строгость не только аргументов функций, но и полей структур данных, например:
SPair — строгая пара. Значения в её полях будут всегда вычислены, что, опять же, не позволяет обещаниям скапливаться.
В этой статье, я постарался объяснить как совладать с ленивыми вычислениями. Надеюсь после её прочтения Вы начнёте понимать, где и как лучше применять отложенные вычисления, зачем они вообще нужны.
Haskell/Laziness
Profiling and optimization
В этой статье я постараюсь объяснить: что такое ленивые вычисления, для чего они могут применяться и как избежать потери производительности при их использовании.
Что такое ленивые вычисления?
В обычных, не ленивых, языках программирования вычисления строгие — то есть аргументы функции вычисляются перед выполнением самой функции.
Например, в каком-то абстрактном строгом языке программирования:
max(5+3, 4*4) ->
max(8, 4*4) ->
max(8, 16)
16А в ленивых языках, в том числе Хаскеле, вычисления отложенные. Все вычисления (кроме некоторых функций ввода-вывода), не выполняются сразу, а как бы откладываются до реальной надобности.
Тот же пример в Хаскеле:
max (5+3) (4*4) ->
let x = 5+3; y = 4*4 in if x >= y then x else y ->
let x = 8; y = 4*4 in if 8 >= y then 8 else y ->
let x = 8; y = 16 in if 8 >= 16 then 8 else 16 ->
16На этом примере хорошо видно, что вычисление подвыражений (5+3 и 4*4) откладывалось до последнего, а именно до момента, когда их пришлось сравнить.
Здесь «силой» что заставила вычисление выполниться можно считать вывод на консоль, т.е. IO. Но это не единственный способ.
Обещания
Возьмём такой пример:
let z = (sum [1..10], reverse "haskell") in ...(далее мы предполагаем, что в in части используется z, иначе let выражение не будет вычислено вообще)
z представляет собой обещание (англ. thunk), просто не вычисленное значение.
А что будет если сравнить с образцом z?
let z = (sum [1..10], reverse "haskell")
(x, y) = z
in ...Сначала z — простое обещание, как и в предыдущем примере, но что бы компилятор мог проверить, что z действительно соответствует образцу, ему приходится «развернуть» z до вида:
(*обещание*, *обещание*). x и y здесь обещания, соответствующие компонентам пары z.Добавим ещё одно сравнение с образцом:
let z = (sum [1..10], reverse "haskell")
(x, y) = z
'l':ys = y
in ...Чтобы проверить, что y — список, компилятор вычисляет его до вида:
*обещание* : *обещание*Потом, он вычисляет первое обещание:
'l' : *обещание*И удостоверившись, что y — список, начинающийся с 'l', он производит сопоставление с образцом:
'l':ys = 'l':*обещание*В данном примере, ys будет обещанием, соответствующим оставшейся части списка y.
Давайте посмотрим на то, как менялась глубина вычисления для z на протяжении всех примеров:
*обещание*
(*обещание*, *обещание*)
(*обещание*, 'l':*обещание*)z было частично вычислено, и как можно догадаться, почти все значения в Хаскеле могут быть вычислены таким образом. Например, минимальное возможное вычисление для пары — это просто вычислить конструктор:
(*обещание*, *обещание*). Для списка это *обещание*:*обещание* или []. А для чисел такой формы не существует — они либо вычислены, либо нет.Когда значение вычислено не полностью, говорят, что оно в Weak Head Normal Form (WHNF), а когда полностью, то в Normal Form. Значение в WHNF будучи полностью вычислено, «переходит» в Normal Form. Например, если мы выведем z на экран, то его Normal Form будет
(55,"lleksah"). Очевидно, что значения, конструктор которых не имеет аргументов, не могут быть в WHNF. То есть, такие типы как Bool, Ord, Int и др. не имеют WHNF, а типы Maybe, [a], Either и т.п. имеют.Ленивые функции
Функции бывают ленивыми и строгими в своих аргументах. Ленивые — не вычисляют свои аргументы, а строгие — вычисляют, до какой-либо глубины. Стоит отметить, что функция может быть ленивой в одном аргументе и строгой в другом. Конечно же, большинству функций нужно как-то использовать свои аргументы, что подразумевает их вычисление. Например, функция length. Чтобы узнать длину списка, ей приходится вычислить его конструкторы, но не значения. То есть,
length *обещание* «раскроется» в что-то вроде: length (*обещание* : *обещание* : *обещание* : []).Есть простой способ проверить ленива ли функция в каком-либо аргументе. Нужно просто передать ей заместо аргумента undefined, и если результатом будет ошибка, то функция строга в этом аргументе, а если нет, то ленива.
Не приведут к ошибке:
const 5 undefined
Just undefinedА эти приведут:
length undefined
head undefinedЛенивое сравнение с образцом
Ленивыми могут быть не только функции, но и сравнения с образцом. В отличии от строгих сопоставлений с образцом, которые мы уже рассматривали, ленивые не заставляют обещания вычисляться, то есть не «развёртывают» их во время компиляции.
Например:
> let f ~(x, y) = 1
> f undefined
1Здесь
~(x, y) — ленивый образец. Он имеет то же свойство, что и аргумент ленивой функции: когда мы передаём туда undefined, ошибки не возникает.Такое сравнение с образцом можно встретить в Control.Arrow:
(***) f g ~(x, y) = (f x, g y)> (const 1 *** const 2) undefined
(1, 2)Но нужно помнить, что ленивый образец стоит использовать, только когда у типа один конструктор.
К примеру:
head' :: [a] -> a
head' ~[] = undefined
head' ~(x:xs) = xТак как мы указали, что не надо вычислять аргумент функции пока он не потребуется, не возможно узнать, что перед нами: пустой список или одно его звено. Функция будет всегда возвращать undefined, ведь в первом выражении мы использовали неопровержимый образец.
Использование ленивых вычислений
Вычисление по требованию
Самый очевидный плюс ленивых вычислений — если что-то не требуется, оно не будет вычислено.
Например:
(&&) False _ = False
(&&) True a = aЕсли первый аргумент функции and — False, зачем вычислять второй, если и так понятно, что результатом будет False? Возможно чтобы узнать значение второго аргумента, потребуется произвести множество трудоёмких вычислений, которых, используя ленивые вычисления, можно избежать.
Представим, что Вы хотите найти 3 наименьших элемента списка.
В Хаскеле это можно сделать так:
take 3 (sort xs)Но в строгом языке это расточительно, так как придётся отсортировать весь список. Но с ленивыми вычислениями, мы отсортируем список до третьего элемента и остановимся, потому что продолжать вычисление не имеет смысла.
Мемоизация
Рассмотрим такую функцию:
plus a = a+a> plus (5+3)
16Сколько раз была вычислена сумма 5 и 3? Правильный ответ: один раз. Сначала (5+3) — просто обещание, но когда оно было передано функции plus, оно вычислилось и его ответ заместил само обещание. Когда значение a потребовалось во второй раз, программа просто взяла готовый результат из бывшего обещания, не производя никаких вычислений. В этом заключается одно из важнейших свойств ленивых вычислений — мемоизация. Обещание в ленивом языке вычисляется только один раз, а потом результат вычисления «затирает» собой обещание, тем самым давая программе возможность просто узнать ответ, без необходимости вычислять его опять.
Такое свойство ленивых вычислений находит применение в динамическом программировании, что было хорошо показано в статье Динамическое программирование и ленивые вычисления.
Бесконечные и цикличные структуры данных
Ещё одно, довольно известное применение отложенных вычислений — создание бесконечных структур данных.
> [1, 3..] !! 10
21Здесь мы создаём бесконечный список нечётных чисел, и берём его 10-ый элемент.
Пример посложнее:
> fibs = 1:1:zipWith (+) fibs (tail fibs)
> fibs !! 100
573147844013817084101Создание бесконечных списков возможно только потому, что они не вычисляются сразу. Во втором примере, fibs сначала будет
1:1:*обещание*, но когда мы запросим следующие элементы этого списка, программе придётся выполнять обещания до того момента, пока наши потребности не будут удовлетворены. Одно обещание может порождать другие, поэтому из небольшого списка и обещания, fibs может развернуться в огромную цепочку чисел Фибоначчи.Теперь перейдём к цикличным структурам данных.
data List a = List {value :: a, next :: List a}Как нам связать два элемента этого типа в кольцо, так, чтобы поле next одного объекта указывало на другой?
Если бы мы хотели осуществить это в императивном языке, мы бы использовали указатели, но в Хаскеле указателей нет. Так как создать такую структуру?
Очень просто:
let x = List "x" y
y = List "y" x
in xВот и всё. Так как поле next у List ленивое (надо помнить, что конструктор типов такая же функция, и его аргументы могут быть ленивыми) создание такого «кольца» не приведёт к зависанию программы в попытках вычислить всю структуру.
> value . next $ x
"y"Ленивый ввод-вывод
Действительно строгими являются только простые функции ввода-вывода, а остальные — ленивые. Это даёт возможность читать и писать в файлы на лету, как по конвейеру, без использования буферов.
Например:
import Data.Char
main = print . map toUpper =<< getContentsПрограмма будет выводить текст в верхнем регистре по мере его поступления.
Проблемы, связанные с использованием ленивых вычислений
На протяжении всей статьи я использовал термин «обещание», чтобы обозначить некую единицу ленивого вычисления, но дело в том, что это не просто абстрактное понятие. Скомпилированная программа на Хаскеле в действительности использует обещания, которые занимают место в памяти и на стеке. То есть, к расходам на обычные вычисления добавляется сборка мусора, выделение памяти, разворачивание обещаний. В этом и заключается главная проблема ленивых вычислений — за их неграмотное использование можно поплатиться сильным снижением производительности, переполнениями стека и большим потреблением памяти.
Но существуют способы, как сделать вычисления менее ленивыми, которые мы сейчас и рассмотрим.
Seq
Рассмотрим такой простой пример:
main = print . sum' $ [1..1e6]
sum' [] = 0
sum' (l:ls) = l + sum' ls
Здесь мы находим сумму чисел от 1 до 1e6 и выводим её в консоль. Но если вы попытаетесь запустить программу, то увидите такое сообщение:
$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.Почему возникает переполнение стека? Давайте посмотрим, как будет вычисляться функция sum':
1 + (1 + (1 + ... (1 + sum' [])))Так как вычисление
sum' ls откладывается, мы получаем множество вложенных обещаний, занимающих место на стеке. Чтобы избавиться от этого, надо как-то заставить обещания вычисляться, а не накапливаться. И для этого у нас есть функция seq. Она принимает два аргумента, первый из которых вычисляется, а второй возвращается. Давайте попробуем применить её здесь.Для начала перепишем функцию sum' на использование хвостовой рекурсии:
main = print . sum' $ [1..1e6]
sum' ls = go 0 ls
where go n [] = n
go n (l:ls) = go (l + n) lsТеперь заставить сложение вычисляться будет не сложно:
main = print . sum' $ [1..1e6]
sum' ls = go 0 ls
where go n [] = n
go n (l:ls) = let s = l + n
in s `seq` go s lsSeq заставляет сумму вычислиться, заместо того, чтобы отложить сложение на потом.
$ ./test
5.000005e11Теперь ошибки не происходит.
Попробуем чуть усложнённый пример: кроме суммы элементов подсчитаем и их число.
main = print . sum' $ [1..1e6]
sum' ls = go (0, 0) ls
where go (n, d) [] = (n, d)
go (n, d) (l:ls) = let t = (l + n, d + 1)
in t `seq` go t ls$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.Опять та же ошибка. Но почему? Мы ведь заставили суммы вычислиться?
Тут пора рассказать об одном свойстве seq: он вычисляет значение до WHNF. У обычных чисел, как было упомянуто ранее, нет WHNF, так что сложение было полностью вычислено seq. Но в этом случае мы пытаемся вычислить пару, которая имеет WHNF, а именно
(*обещание*, *обещание*). Значит обещания всё равно скапливаются, что приводит к переполнению стека. Мы можем с помощью seq заставить вычисляться поля:main = print . sum' $ [1..1e6]
sum' ls = go (0, 0) ls
where go (n, d) [] = (n, d)
go (n, d) (l:ls) = let s = l + n
d' = d + 1
in s `seq` d' `seq` go (s, d') ls$ ./test
(5.000005e11,1000000)Немного некрасиво, но работает. Ситуация, когда нужно вычислить что-либо полностью, не так редка, так что для этого был создан специальный модуль. Давайте его опробуем:
import Control.DeepSeq (deepseq)
main = print . sum' $ [1..10^6]
sum' :: [Integer] -> (Integer, Int)
sum' ls = go (0, 0) ls
where go (n, d) [] = (n, d)
go (n, d) (l:ls) = let t = (l + n, d + 1)
in t `deepseq` go t lsФункция deepseq вычисляет значения полностью, до Normal Form.
Bang patterns
Для более удобного указания строгости, было создано расширение компилятора — Bang patterns. Оно позволяет указывать строгость аргументов просто восклицательным знаком. С использованием этого расширения, мы можем переписать наш код так:
{-# LANGUAGE BangPatterns #-}
main = print . sum' $ [1..10^6]
sum' :: [Integer] -> (Integer, Int)
sum' ls = go (0, 0) ls
where go (!n, !d) [] = (n, d)
go (!n, !d) (l:ls) = go (l + n, d + 1) lsВсё будет работать, как и прежде.
Bang patterns позволяют нам указывать строгость не только аргументов функций, но и полей структур данных, например:
{-# LANGUAGE BangPatterns #-}
data SPair a b = SPair !a !b deriving Show
main = print . sum' $ [1..10^6]
sum' :: [Integer] -> SPair Integer Int
sum' ls = go (SPair 0 0) ls
where go (SPair n d) [] = SPair n d
go (SPair n d) (l:ls) = go (SPair (l + n) (d + 1)) ls$ ./test
SPair 500000500000 1000000SPair — строгая пара. Значения в её полях будут всегда вычислены, что, опять же, не позволяет обещаниям скапливаться.
Заключение
В этой статье, я постарался объяснить как совладать с ленивыми вычислениями. Надеюсь после её прочтения Вы начнёте понимать, где и как лучше применять отложенные вычисления, зачем они вообще нужны.
Список используемых материалов
Haskell/Laziness
Profiling and optimization
