Пользователь
0,0
рейтинг
4 ноября 2011 в 19:01

Разработка → Ленивые вычисления

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

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

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


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

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
@savask
карма
19,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (36)

  • 0
    Спасибо за статью.

    Ссылочная прозрачность же, а не мемоизация?

    Было бы интересно ещё про Fusion (как несколько map/filter/… выливаются в один цикл). Это, так сказать, обратный случай, где в обычных языках мы платим, а в ленивом — нет, за счёт высокой абстракции.
    • 0
      Всегда пожалуйста.

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

      А что насчёт Fusion, как я понимаю, это весьма редкая техника оптимизации, которую даже нужно отдельно включать. Может быть я поковыряю её на досуге и отпишусь о результатах.
  • +1
    «Но в строгом языке это расточительно, так как придётся отсортировать весь список. Но с ленивыми вычислениями, мы отсортируем список до третьего элемента и остановимся,»

    Как это вы сортируете список «до 3 элемента»?

    Чтобы найти эти элементы все равно весь список придется просмотреть.
    • 0
      Ну дак его ж не надо досортировывать до конца.
      • –1
        другими словами хаскел быдет использовать selection sort со сложностью O(n^2) там где все используют O(n log n)?

        неприятный сюрприз.

        • 0
          Никто этого не говорил.
        • +3
          Ну почему же? Можно, к примеру, сортировать qsort'ом, и при каждом разбиении идти только в меньшую половинку(за исключением случая, когда там мало элементов).
          • 0
            Так у qsort сложность в худшем случае и есть O(n^2).
            • 0
              Но ведь обычно рассматривается средний случай. И тогда уж точно отсортировать только половину будет быстрее, чем весь список.
              • 0
                Хых. Так это всё-равно будет медленней, чем выбрать известное количество K наименьших элементов — у которого сложность O(log(K) N). Когда скорость важна, нужно использовать специальный алгоритм. Беда Haskell в том, что он не позволит прямо выразить такой вот алгоритм, если вообще это возможно, то придётся танцевать с бубном, и в итоге, всё равно, будет медленней. Хых…
                • 0
                  Идея того примера была в том, чтобы показать, что в ленивом языке такой подход будет быстрее, чем в строгом. А так то да, специальный алгоритм лучше.
                • 0
                  В среднем, алгоритм с qsort'ом будет работать быстрее, т.к. работает за O(N), см. мой комментарий ниже.
                  Вы, вероятно, упоминаете интуитивный алгоритм в 1 пробег с чем-то вроде стека в руках. Я давно не писал на хаскеле, но вот — то, что пишется за пару минут(извините за некоторую корявость):
                  sink a (r1:rs) | r1 > a = r1:(sink a rs)
                  sink a l = a:l
                  
                  kmin k len r (a:l) = kmin k len1 r1 l
                   where
                    r1 = if len<k then sink a r
                     else drop 1 $ sink a r
                    len1 = if len<k then len+1 else len
                  
                  kmin _ _ r _ = r
                  
                  mink k l = reverse $ kmin k 0 [] l
                  

                  И это работает медленнее, чем take и самописный qsort(а также медленнее, чем take и встроенный sort из Data.List).
                  • 0
                    Я не особый специалист, но у меня такое ощущение, что оно медленней, потому что в такой реализации вызовы совсем не хвостовые и стэк используется не особо эффективно, и вся процедура не итеративная. Конечно, take 3 sort с оптимизированным sort будет лучше.
            • 0
              Ну давайте прикинем сложность этого алгоритма. В среднем, мы на каждой итерации будем брать половину списка до тех пор, пока там не станет k элементов, после чего просто выдадим их.
              Итого мы сделаем операций: N + N/2 + N/4 +..+k, что не превосходит 2N, так что асимптотическая сложность — O(N).
              Разумеется, все мои рассуждения не точны, но, думаю, суть ясна. Да, есть худший случай, где оно работает примерно за O(N^2-k^2), но это беда qsort'а. В среднем время работы линейно.
          • 0
            «и при каждом разбиении идти только в меньшую половинку»

            Половинку? При qsort нет половинок. Там берется опорный элемент и остальные элементы располагаются левее-правее относительно этого элемента. То есть попась в случай, когда опорный элемент оказался в хвосте — очень даже вероятно.

            Разумеется, для определенной части данных можно избежать сортировки — но говорить «отсортируем до 3 элемента» — это просто вводить в заблуждение. В подавляющем большинстве случаев будет массовая и затратная операция над данными.

            • 0
              То есть попась в случай, когда опорный элемент оказался в хвосте — очень даже вероятно.

              Столь же вероятно, сколь и попасть в случай, когда «опорный элемент» окажется в начале. Итого в среднем он оказывается в середине списка, т.е. делит список на «половинки».
              Прочитайте мой комментарий выше, там нестрого, на пальцах пояснено, почему алгоритм будет работать за O(N).

              В подавляющем большинстве случаев будет массовая и затратная операция над данными.

              В каком, простите, подавляющем большинстве? Что есть массовая и затратная операция? В среднем такой алгоритм будет работать за O(N). Вы случайно не считаете, что «в подавляющем большинстве случаев» qsort работает за O(N^2)?
              • –1
                А Вы что, считаете что o(n) это мало?
                • +1
                  А вы можете найти k наименьших элементов в массиве/списке менее, чем за O(N)? То есть не проходя весь массив/список?
                  • –2
                    если представить программиста, который пишет, ну… скажен на С или на go, он напишет просто один цикл по списку и выберет все три значения за 1 проход. За O(N) при любых данных.

                    А подход take 3 sort список, выберет то же самое за O(N) (если вы конечно правильно отгадали как именно действует haskell) в среднестатистическом случае. А в случае «плохих» данных результат будет хуже.

                    То есть как раз и весь разговор о том, что автор выбрал неудачный пример для демонстрации преимуществ. Если бы он просто написал take 3 [какая то тяжелая обработка x | x < — список], вопросов бы не возникло.

                    Но вариант take 3 sort список — пример провокационный и рождающий больше вопросов, чем дающий ответы.
                    • +2
                      Как я уже говорил, тот пример должен был показать, что из за ленивости Хаскеля, остальная часть списка не будет сортироваться, а в строгом языке будет. В этом и была демонстрация преимуществ.
                      • 0
                        остальная часть списка будет частично сортирована. Нетронутой она не останется.
                        • 0
                          Да, так оно и есть. Но ведь частично, не полностью.
                    • +2
                      В haskell'е вам тоже никто не запрещает пройти циклом по списку и подсчитать все, что нужно. Фишка в том, что можно написать нечто в среднем то же самое(и даже немного быстрее) в одну строчку. Более того, я не знаю, как работает стандартная сортировка (sort из Data.List), но на моем нетбуке она немного обгоняет как пробег по массиву, так и qsort(в плохих случаях).
                      Вообще пример с qsort я привел как самый очевидный, наверняка что-то подобное можно сделать и, к примеру, с mergesort.
                      Пока гипотетический C/go программист писал свой пробег по циклу, его товарищ написал на haskell'e одну строку и оставшиеся две минуты неспешно пил горячий кофе, с легкой усмешкой поглядывая на соседа.
    • +1
      Дабы было проще понять:
      head $ sort lst
      Выдаст минимальный элемент.
      Сравните, во что это выльется ленивому и энергичному языку?
      • –1
        Так если мне нужно будет наименьший элемент, то я на энергичном языке напишу какой-нибудь minlist с оптимизацией под AVX и OpenCL, и всё.

        А если мне не нужна будет скорость, буду писать в Bash: cat list | sort | head. Кстати, будет то же самое по способу вычисления. При этом, всё энергично, просто семантика у операций несколько другая.
        • 0
          Если бы всё было так просто, не было бы таких понятий, как итератор.
          • 0
            А всё действительно именно так просто. Но так же просто и то, что люди склонны к усложнениям, даже когда в этом нет необходимости: потому что итератор — это круто, а правильно организованные данные и простой цикл — нет, не звучит :) К сожалению именно так. Огромное количество сложного софта написано без всяких итераторов и всё прекрасно работает.
            • 0
              Итераторы нужны не для усложнения, а для разделения алгоритмов.
              Куда как проще и понятнее написать:
              filterData = filter somePredicate
              translateData = map someOp
              И затем
              filterData. translateData $ data
              и всё это выльется в один цикл.

              Нежели
              for (… )
              {
              if (somePredicate(*b))
              result.push_back(someOp(*b))
              }

              Так как в первом случае код разнесён в разные места (а что если эти обработки пишут разные люди?), а во втором — всё намешано в кучу.
              Мы, конечно, во втором случае тоже можем разнести в разные места, но тогда в энергичном языке у нас получится 2 цикла, а не один. А если обработок будет больше, чем 2? То и циклов будет сотня. Вот и придумывают всякие yield'ы, и отнюдь не ради забавы.
              • 0
                Эмс. А что мешает в энергичном языке писать то же самое? Те же самые map (Scheme же call-by-value язык)? И, вероятно, мы с вами под интераторами понимаем разные вещи. Вы имеете в виду итераторы как в Python?
                • 0
                  А разве этот map не пробежится по всему списку? А затем filter не пробежится ещё раз?
                  Тогда как в ленивом будет всего один проход.
                  • 0
                    Эмс. А что мешает просто накопить вычисления, а потом сделать map с композицией функций? Обычная практика.

                    Хотя… Конечно, если лень, то ленивый проход спасёт :)
                    • 0
                      Кому нужна лишняя связность там, где её может не быть?
                      Haskell сам вместо map f. map g делает map (f. g)
                      Можно вообще задавать свои правила оптимизации, язык-то чистый и есть гарантии отсутствия побочных эффектов :)
      • 0
        в «неленивом языке» это выльется в min(список). в неленивом языке никто не будет сортировать массив чтобы взять минимум.
        • 0
          В строгом языке это как раз таки и не выльется в min(список), поэтому никто и не будет сортировать его чтобы взять минимум.
        • 0
          Вы не поверите, но в «ленивом» языке тоже никто не будет сортировать весь массив. Отсортируется то, что нужно, остальное останется в стороне.
        • 0
          В неленивых языках поэтому куча абстракций типа итератор и енумератор. Так что на деле не всё так просто.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.