Лень

Помните, в главе с первыми вопросами о Haskell я упомянул, что этот язык является ленивым? Сейчас мы наконец-то узнаем о ленивых вычислениях и познакомимся с их светлой и тёмной сторонами.

Две модели вычислений

Как мы уже знаем, Haskell-программа состоит из выражений, а запуск программы суть начало длинной цепочки вычислений. Вспомним функцию square, возводящую свой единственный аргумент в квадрат:

main :: IO ()
main = print . square $ 4

Здесь всё просто: функция square применяется к нередуцируемому выражению 4 и даёт нам 16. А если так:

main :: IO ()
main = print . square $ 2 + 2

Теперь функция square применяется уже к редуцируемому выражению:

square   $            2 + 2

функция  применяется  редуцируемому
         к            выражению

Как вы думаете, что произойдёт раньше? Применение оператора сложения или же применение функции square? Вопрос хитрый, ведь правильного ответа на него нет, поскольку существует две модели вычисления аргументов, а именно энергичная (англ. eager) и ленивая (англ. lazy).

При энергичной модели (называемой ещё «жадной» или «строгой») выражение, являющееся аргументом функции, будет вычислено ещё до того, как попадёт в тело функции. На фоне определения функции square будет яснее:

square     x   = x * x
         /   \
square $ 2 + 2
         \   /
           4   = 4 * 4 = 16

То есть видим выражение 2 + 2, жадно на него набрасываемся, полностью вычисляем, а уже потом результат этого вычисления передаём в функцию square.

При ленивой же модели всё наоборот: выражение, являющееся аргументом функции, передаётся в функцию прямо так, без вычисления. Изобразить это можно следующим образом:

square     x   =    x    *    x
         /   \    /   \     /   \
square $ 2 + 2 = (2 + 2) * (2 + 2) = 16

Но какая разница, спросите вы? Всё равно в итоге получим 16, хоть там сложили, хоть тут. Так и есть: модель вычисления не влияет на результат этого вычисления, но она влияет на путь к этому результату.

Жадная модель нашла своё воплощение практически во всех современных языках программирования. Напишем на C:

#include <stdio.h>

int strange(int i) {
  return 22;
}

int main() {
  printf("%d\n", strange(2 / 0));
}

Функция strange действительно странная, ведь она игнорирует свой аргумент и просто возвращает число 22. И всё же при запуске этой программы вы гарантированно получите ошибку Floating point exception, ибо компилятор языка C категорически не терпит деления на ноль. А всё потому, что язык C придерживается энергичной модели вычислений: оператор деления 2 на 0 будет вызван ещё до того, как мы войдём в тело функции strange, поэтому программа упадёт.

Такой подход прямолинеен и строг: сказали нам сначала разделить на ноль — разделим, не задумываясь. Ленивая же модель придерживается иного подхода. Взгляните на Haskell-вариант:

strange :: Int -> Int
strange i = 22

main :: IO ()
main = print . strange $ 2 `div` 0

Удивительно, но при запуске этой программы мы увидим:

22

Впрочем, почему удивительно? Функция strange, проигнорировав свой аргумент, дала нам значение 22, которое, попав на вход функции print, вылетело в наш терминал. Но где же ошибка деления 2 на 0, спросите вы? Её нет.

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

Функция strange ленива и потому рациональна. Она смотрит на свой аргумент i:

strange i = 22

и понимает, что он нигде не используется в её теле. Значит, он не нужен. А раз так, то и вычислен он не будет. Кстати, если аргумент функции игнорируется, определение принято писать с универсальным образцом:

strange _     = 22

        ^
        нам
        всё
        равно

Так и получается:

strange       _     = 22
          /       \
strange $ 2 `div` 0 = 22

Выражение, содержащее деление на ноль, попадает внутрь функции, будучи ещё невычисленным, но поскольку в теле функции оно нигде не используется, оно так и останется невычисленным. Девиз лени: если результат работы никому не нужен — зачем же её делать? Вот почему фактического деления на ноль здесь не произойдёт и программа не рухнет.

Разумеется, если бы мы определили функцию strange иначе:

strange :: Int -> Int
strange i = i + 1

тогда другое дело: значение аргумента уже используется в теле функции, а значит вычисление аргумента непременно произойдёт:

strange       i     =      i      + 1
          /       \    /       \
strange $ 2 `div` 0 = (2 `div` 0) + 1

Оператору сложения требуется значение обоих своих аргументов, в том числе левого, а потому получите ошибку деления на ноль.

Как можно меньше

До тех пор, пока результат вычисления никому не нужен, оно не производится. Однако даже тогда, когда результат кому-то понадобился, вычисление происходит не до конца. Помните, выше я сказал, что при жадной модели вычисления выражение, являющееся аргументом, вычисляется «полностью»? А вот при ленивой модели мы вычисляем выражение лишь настолько, насколько это необходимо. Как вышеупомянутый ребёнок, убирающий игрушки в комнате, убирает их вовсе не до конца, а лишь до такой степени, чтобы его не ругали родители.

С точки зрения вычисления любое выражение в Haskell проходит через три стадии:

1. невычисленное,
2. вычисленное не до конца,
3. вычисленное до конца.

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

2 `div` 0

Мы увидели, что программа не упала, и это говорит нам о том, что деления не было. То есть функция div так и не была применена к своим аргументам. Вообще. Такое выражение называют thunk (можно перевести как «задумка»). То есть мы задумали применить функцию div к 2 и к 0, приготовились сделать это — но в итоге так и не сделали.

Вычисленным до конца называют такое выражение, которое вычислено до своей окончательной, нередуцируемой формы. О таком выражении говорят как о выражении в «нормальной форме» (англ. normal form).

А вот вычисленным не до конца называют такое выражение, которое начали было вычислять, но сделали это не до конца, то есть не до нормальной формы, а до так называемой «слабой головной формы» (англ. Weak Head Normal Form, WHNF). Вы спросите, как же это можно вычислить выражение не до конца? Рассмотрим пример:

main :: IO ()
main =
  let cx     = 2 / 6.054   -- thunk
      nk     = 4 * 12.003  -- thunk
      coeffs = [cx, nk]    -- thunk
  in putStrLn "Nothing..."

Есть у нас два коэффициента, cx и nk, и ещё список coeffs, в который мы поместили эти коэффициенты. Но, как мы видим, в итоге ни эти коэффициенты, ни этот список нам не понадобились: мы просто вывели строку и тихо вышли. В этом случае ни одно из этих выражений так и не было вычислено, оставшись в виде thunk. То есть оператор деления так и не был применён к 2 и 6.054, оператор умножения не прикоснулся ни к 4, ни к 12.003, а список остался лишь в наших умах. Ленивая стратегия рациональна: зачем тратить компьютерные ресурсы на создание того, что в итоге никому не понадобится?

Изменим код:

main :: IO ()
main =
  let cx     = 2 / 6.054   -- thunk
      nk     = 4 * 12.003  -- thunk
      coeffs = [cx, nk]    -- WHNF
  in print $ length coeffs

Ага, уже интереснее. В этот раз захотелось нам узнать длину списка coeffs. В этом случае нам уже не обойтись без списка, иначе как же мы узнаем его длину? Однако фокус в том, что выражение [cx, nk] вычисляется не до конца, а лишь до той своей формы, которая удовлетворит функцию length.

Задумаемся: функция length возвращает число элементов списка, но какое ей дело до содержимого этих элементов? Ровным счётом никакого. Поэтому в данном случае список формируется из thunk-ов:

coeffs = [thunk, thunk]

Первым элементом этого списка является thunk, ассоциированный с невычисленным выражением 2 / 6.054, а вторым элементом списка является thunk, ассоциированный с невычисленным выражением 4 * 12.003. Фактически, список coeffs получился как бы не совсем настоящим, пустышечным: он был сформирован в памяти как корректный список, однако внутри обоих его элементов — вакуум. И всё же даже такая его форма вполне подходит для функции length, которая и так прекрасно поймёт, что в списке два элемента. О таком списке говорят как о выражении в слабой головной форме.

Ещё чуток изменим код:

main :: IO ()
main =
  let cx     = 2 / 6.054   -- thunk
      nk     = 4 * 12.003  -- normal
      coeffs = [cx, nk]    -- WHNF
  in print $ coeffs !! 1

Необычного вида оператор !! извлекает из списка элемент по индексу, в данном случае нас интересует второй по счёту элемент. Теперь нам уже недостаточно просто сформировать список, нам действительно нужен его второй элемент, иначе как бы мы смогли вывести его на консоль? В этом случае выражение 4 * 12.003 будет вычислено до своей окончательной, нормальной формы, а результат этого вычисления ляжет вторым элементом списка, вот так:

coeffs = [thunk, 48.012]

Однако первый элемент списка так и остался невостребованным, поэтому выражение 2 / 6.054 по-прежнему остаётся лишь нашей мыслью, не более чем. В этом случае список coeffs всё равно остаётся в слабой головной форме, ведь внутри первого его элемента всё ещё вакуум.

И теперь напишем так:

main :: IO ()
main =
  let cx     = 2 / 6.054   -- normal
      nk     = 4 * 12.003  -- normal
      coeffs = [cx, nk]    -- normal
  in print coeffs

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

Вот философия ленивой стратегии: даже если нам нужно вычислить выражение, мы вычисляем его лишь до той формы, достаточной в конкретных условиях, и не более того.

Рациональность

Как уже было упомянуто, ленивая стратегия помогает программе быть рациональной и не делать лишнюю работу. Рассмотрим пример:

main :: IO ()
main = print $ take 5 evens
  where evens = [2, 4 .. 100]

Список evens, формируемый через арифметическую последовательность, содержит в себе чётные числа от 2 до 100 включительно. Используется этот список в качестве второго аргумента стандартной функции take, которая даёт нам N первых элементов из переданного ей списка:

take    5          evens

возьми  лишь
        пять
        элементов  из этого
                   списка

При запуске этой программы мы получим ожидаемый результат:

[2,4,6,8,10]

В чём же здесь рациональность, спросите вы? А в том, что список evens в итоге содержал в себе лишь 5 элементов. Да, но ведь чётных чисел от 2 до 100 куда больше, нежели пять! Совершенно верно, но лень позволяет нам сделать лишь столько работы, сколько реально требуется. Раз уж список evens нужен лишь функции take, которая, в свою очередь, хочет только пять первых его элементов — зачем же создавать оставшиеся элементы? Нужно первые пять — получи пять. Если же напишем так:

main :: IO ()
main = print $ take 50 evens
  where evens = [2, 4 .. 100]

тогда в списке evens окажется уже пятьдесят элементов, потому что именно столько запросила функция take. Повторю философию ленивого рационализма: сделаем не столько, сколько нам сказали, а лишь столько, сколько действительно понадобится.

Бесконечность

А что будет, если мы запросим из списка evens 500 элементов? Вот так:

main :: IO ()
main = print $ take 500 evens
  where evens = [2, 4 .. 100]

Ничего страшного не случится, функция take проверяет выход за границы и в случае, если её первый аргумент превышает длину списка, она просто даёт нам тот же список. Да, но ведь мы хотим увидеть пятьсот чётных чисел, а не пятьдесят! Можно было бы увеличить список:

main :: IO ()
main = print $ take 500 evens
  where evens = [2, 4 .. 100000]

но это ненадёжно, ведь потом опять может потребоваться ещё больше. Нужно что-нибудь универсальное, и в Haskell есть подходящее решение:

main :: IO ()
main = print $ take 500 evens
  where evens = [2, 4 ..]  -- Что это?

Теперь не сомневайтесь: в списке evens будет не менее пятисот чётных чисел. Но что это за конструкция такая? Начало дано, шаг дан, а где же конец? Познакомьтесь, это бесконечный список:

[2, 4 ..]

Ленивая модель вычислений позволяет нам работать с бесконечными структурами данных. Вот прямо так, начиная с двойки и, с шагом через один, уходим в бесконечные дали… Шучу. На самом деле, список получится вовсе не бесконечным, а настолько большим, насколько нам это понадобится.

В самом деле, если функция take требует от нас N элементов — зачем нам вообще задавать окончание диапазона списка? Всё равно в нём будет не более чем N. Бесконечная структура данных тем и полезна, что из неё всегда можно взять столько, сколько требуется.

Конечно, если бы мы решили похулиганить:

main :: IO ()
main = print evens  -- Дай нам всё!
  where evens = [2, 4 ..]

в этом случае в нашу консоль быстро посыпалось бы очень много чисел…

Space leak

Да, я должен рассказать вам правду: есть у ленивой стратегии вычислений тёмная сторона, получившая название space leak (букв. «утечка пространства»). И вот в чём её суть.

Вспомним пример с делением:

main :: IO ()
main = print . strange $ 2 `div` 0

Как мы помним, деления на ноль так и не произошло за ненадобностью его результата. В этом случае выражение осталось в виде thunk. Возникает вопрос: что же с ним стало? У нас есть функция div и есть два значения типа Int, 2 и 0. Если функция div так и не была применена к ним, где же всё это хозяйство находилось в процессе работы нашей программы? Оно находилось в памяти, в виде особого графа, который можно изобразить так:

 ┌─────────────┐
 │ div │   │   │
 └─────────────┘
         │   │
         v   v
      ┌───┐ ┌───┐
      │ 2 │ │ 0 │
      └───┘ └───┘

То есть сама функция и два значения, которые должны были занять место двух её аргументов. И вот этот граф в памяти так и остался невостребованным. Казалось бы, ну и в чём проблема? А проблема в количестве. Если мы смогли написать код, при работе которого в память отложился один thunk, значит теоретически мы можем написать и такой код, количество thunk-ов при работе которого будет исчисляться миллионами. А учитывая тот факт, что каждый thunk занимает в памяти хотя бы несколько байт, вы можете себе представить масштаб проблемы.

Причём возникнуть эта проблема может из весьма невинного на первый взгляд кода:

bad :: [Int] -> Int -> Int
bad []         c = c
bad (_:others) c = bad others $ c + 1

Простенькая рекурсивная функция, пробегающаяся по ненужному ей списку и увеличивающаяся свой второй аргумент на единицу. Но я не просто так назвал её bad. Давайте применим её:

bad [1, 2, 3] 0

Подставим в определение, содержащее зацикливание:

bad (_: others) c = bad others $ c + 1

bad [1, 2, 3]   0 = bad [2, 3] $ 0 + 1

        ____            ______

                =                =

«Голова» списка откусывается и игнорируется, а к 0 прибавляется 1. Но поскольку результат сложения пока что никому не нужен, сложение не производится. Вместо этого, на второй итерации, мы видим следующее:

bad [2, 3] $ 0 + 1 = bad [3] $ (0 + 1) + 1

К предыдущему выражению вновь прибавляется единица — и мы опять входим в очередную итерацию, так и не выполнив сложения:

bad [3] $ (0 + 1) + 1 = bad [] $ ((0 + 1) + 1) + 1

Опа! Упёрлись в пустой список, вспоминаем правило выхода из рекурсии:

bad [] c = c

Итак, в этом случае мы просто возвращаем значение второго аргумента. Сделаем же это:

bad [] $ ((0 + 1) + 1) + 1 = ((0 + 1) + 1) + 1 = 3

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

Вот в этом-то накоплении вся беда. Представим, что мы написали так:

main :: IO ()
main = print $ bad [1..50000000] 0

50 миллионов элементов, а значит, 50 миллионов раз сложение второго аргумента с единицей будет откладываться, накапливая гигантский «хвост» из (пока что) невычисленных выражений. Хотите знать, что произойдёт при запуске такой программы? Её выполнение, на MacBook Pro 2014 года, займёт приблизительно 63 секунды и скушает, ни много ни мало, 6,4 ГБ памяти! А теперь представьте, что случилось бы, если бы элементов в списке было не 50 миллионов, а 50 миллиардов…

Иногда space leak ошибочно путают с другой проблемой, называемой memory leak (англ. «утечка памяти»), однако это вовсе не одно и то же. Утечка памяти — это ошибка, характерная для языков с ручным управлением памятью, например, C. Если мы выделим память в куче (англ. heap), а затем потеряем указатель, связывающий нас с этой памятью — всё, выделенная память утекла, она потеряна для нас навеки. Но в случае space leak мы не теряем память: когда весь этот «хвост» из сложений в конце концов вычислится, память, занимаемая миллионами thunk-ов, освободится. Мы не теряем память, мы просто используем её слишком много.

Борьба

Проблема space leak вытекает из самой природы ленивых вычислений. Многие программисты, узнав об этой проблеме, отворачиваются от Haskell. Мол, если в этом языке можно легко написать код, сжирающий уймищу памяти, значит этот язык точно не подходит для серьёзного использования. Но не так страшен чёрт, как его малюют. Я расскажу о двух способах борьбы со space leak.

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

И как же мы можем разбавить лень строгостью? Вот два способа.

Оптимизация

Первый способа самый простой — оптимизация. Когда компилятор превращает наш код в программу, его можно попросить оптимизировать наш код, сделав его более эффективным, по тем или иным критериям. Чтобы попросить компилятор провести оптимизацию, мы должны использовать специальный флаг. Откроем сборочный файл нашего проекта real.cabal, найдём секцию executable real-exe, в которой есть строка:

  ghc-options:         ...

Эта строка содержит различные опции компилятора GHC, и оптимизационный флаг дописывается именно сюда. Попробуем подставить туда сначала флаг -O0, а затем -O2. Результаты запуска программы будут такими:

Оптимизация    Время    Память

-O0            63 c     6,4 ГБ

-O2            3,2 с    104 кБ

Впечатляющая разница, не правда ли? Флаг -O0 говорит компилятору о том, чтобы тот не производил никакую оптимизацию, в этом случае говорят о нулевом уровне оптимизации. Флаг -O2, напротив, устанавливает стандартный для production-проектов уровень оптимизации. Так вот при стандартном уровне компилятор способен распознать излишнюю ленивость в нашем коде и добавить чуток жадности. В примере выше компилятор увидит накопление thunk-ов сложения и пресечёт оное. Согласитесь, с гигабайтов прыгнуть сразу на килобайты — это круто.

Так что же, проблемы нет? Ну, если оптимизация -O2 и так стандартна — так давайте ставить её в наши проекты и забудем про space leak! К сожалению, не всё так просто.

Во-первых, компиляторная оптимизация сродни чёрной магии, на неё трудно полагаться. Мы очень благодарны компилятору GHC за попытку помочь нам, но эта помощь не всегда соответствует нашим ожиданиям. И во-вторых, к сожалению, компилятор не всегда способен распознать излишнюю лень в нашем коде, и в этом случае нам приходится-таки прибегнуть ко второму способу борьбы со space leak.

Вручную

Вернёмся к определению функции bad:

bad :: [Int] -> Int -> Int
bad []         c = c
bad (_:others) c = bad others $ c + 1

Проблема, как мы уже поняли, во втором аргументе:

bad others $ c + 1

             накопление
             thunk-ов...

Превратим же злую функцию в добрую:

good :: [Int] -> Int -> Int
good []         c = c
good (_:others) c = good others $! c + 1

Этот код даст нам приблизительно такой же выигрыш, что и оптимизация уровня -O2: секунды вместо минуты и килобайты вместо гигабайтов. Что же изменилось? Смотрим внимательно:

good others $! c + 1

             ^

Вместо привычного оператора применения $ мы видим оператор строго применения $! (англ. strict application operator). Этот оператор говорит аргументу: «Забудь о лени, я приказываю тебе немедленно вычислиться до слабой головной формы»:

good others $!       c + 1

            вычисли  этот
                     аргумент

            строго,
            а не
            лениво!

Вот потому-то наш «хвост» из thunk-ов и не будет накапливаться, ведь на каждой из 50 миллионов итераций будет происходить незамедлительное применение оператора сложения. Таким образом, заставить аргумент тут же вычислиться до слабой головной или нормальной формы можно как посредством того, что этот аргумент прямо сейчас кому-то понадобился, так и посредством строгого применения.

Лень и строгость вместе

Функцию называют ленивой по тем аргументам, которые не вычисляются, и строгой по тем аргументам, которые вычисляются. Примитивный пример:

fakeSum :: Int -> Int -> Int
fakeSum x _ = x + 100

Функция fakeSum строга по своему первому аргументу и ленива по своему второму аргументу. Первый аргумент x непременно будет вычислен, ведь он передаётся оператору сложения. Второй же аргумент игнорируется, оставшись невычисленным. И кстати, существует простой способ проверить, строга ли функция по некоторому аргументу или ленива.

В стандартной библиотеке Haskell определена особая функция undefined. Это — чёрная дыра: при попытке прикоснуться к ней программа гарантированно падает с ошибкой. Проверяем:

main :: IO ()
main = print $ fakeSum 1 undefined

В этом случае мы получим результат:

101

Чёрная дыра была проигнорирована, ведь функция fakeSum ленива по второму аргументу. Если же мы напишем так:

main :: IO ()
main = print $ fakeSum undefined 45

программа, попытавшись передать undefined оператору сложения, аварийно остановится. Или вот другой пример:

main :: IO ()
main = print . head $ [23, undefined, undefined]

Не сомневайтесь: программа спокойно вернёт нам 23, ведь функция head строга лишь по первому элементу переданного ей списка, остальное содержимое оного её абсолютно не интересует. Но если попробуете вытащить второй или третий элемент из подобного списка — крах неминуем.

Для любопытных

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

Что же касается проблемы space leak, то к счастью, существуют способы обнаружения функций, шибко прожорливых до памяти. В самом деле, представьте себе большой проект, тысячи функций, и что-то кушает гигабайты памяти. Как найти виновного? Этот процесс называют ещё «space leak профилированием». Рассказывать об этом здесь я не стану, материал довольно объёмный. Но для особо любопытных привожу ссылку на неплохую англоязычную статью по теме: Chasing a Space Leak in Shake.

И ещё вспомним вот это:

square     x   =    x      *    x
         /   \    /   \       /   \
square $ 2 + 2 = (2 + 2)   * (2 + 2)    = 16

                 вычисляем   и что,
                             опять
                             вычисляем?!

Внимательный читатель удивится, мол, неужели выражение 2 + 2 вычисляется дважды?! Ведь это нерационально. Конечно нерационально, поэтому в действительности оно будет вычислено единожды. В Haskell есть особый механизм «шаринга» (англ. sharing), позволяющий избежать напрасной работы. И если у нас есть несколько одинаковых выражений, вычисление оного происходит один раз, результат же сохраняется и потом просто подставляется в нужные места. Например:

main :: IO ()
main =
  let x = sin 2 in print x * x

Если бы не sharing-механизм, функция sin была бы применена к 2 дважды. К счастью, значение синуса будет вычислено единожды и тут же сохранено, чтобы потом просто встать на места тех двух x.