Pull to refresh

Ленивые вычисления

Reading time 8 min
Views 16K
Одной из «визитных карточек» Хаскеля являются отложенные, или ленивые, вычисления. Эта особенность языка не только открывает множество возможностей, но и создаёт некоторые проблемы, особенно со скоростью работы программ.

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

Что такое ленивые вычисления?


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

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 ls

Seq заставляет сумму вычислиться, заместо того, чтобы отложить сложение на потом.

$ ./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 1000000


SPair — строгая пара. Значения в её полях будут всегда вычислены, что, опять же, не позволяет обещаниям скапливаться.

Заключение


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

Список используемых материалов


Haskell/Laziness
Profiling and optimization
Tags:
Hubs:
+34
Comments 36
Comments Comments 36

Articles