Ліниві обчислення
Однією з «візитних карток» Хаскеля є відкладені або ліниві обчислення. Ця особливість мови як відкриває безліч можливостей, а й створює деякі проблеми, особливо зі швидкістю роботи програм.
У цій статті я спробую пояснити: що таке ліниві обчислення, для чого вони можуть застосовуватися і як уникнути втрати продуктивності при їх використанні.
Що таке ліниві обчислення?
У звичайних, не лінивих мовах програмування обчислення суворі — тобто аргументи функції обчислюються перед виконанням самої функції. Наприклад, якоюсь абстрактною строгою мовою програмування:
А в лінивих мовах, у тому числі Хаскелі, обчислення відкладені. Усі обчислення (крім деяких функцій введення-виведення), не виконуються відразу, а як би відкладаються до реальної потреби. Той самий приклад у Хаскелі:
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 . (далі ми припускаємо, що в частині використовується z, інакше let вираз не буде обчислено взагалі)
z являє собою обіцянку (англ. Thunk), просто не обчислене значення. А що буде якщо порівняти із зразком z?
Спочатку z — проста обіцянка, як і в попередньому прикладі, але щоб компілятор міг перевірити,що z дійсно відповідає зразку, йому доводиться «розгорнути» z до вигляду: (*обіцянка*, *обіцянка*) . x та y тут обіцянки, що відповідають компонентам пари z. Додамо ще одне порівняння із зразком:
Щоб перевірити, що 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
Ліниве порівняння із зразком
Лінивими можуть бути не тільки функції, а й порівняння із зразком. На відміну від суворих зіставлень із зразком, які ми вже розглядали, ліниві не змушують обіцянки обчислюватися, тобто не «розгортають» їх під час компіляції. Наприклад:
(x, y) = 1 > f undefined 1
(x, y) - лінивий зразок. Він має ту ж властивість, що й аргумент лінивої функції: коли ми передаємо туди undefined, помилки не виникає. Таке порівняння із зразком можна зустріти в Control.Arrow:
> (const 1 *** const 2) undefined (1, 2)
Але треба пам'ятати, що лінивий зразок варто використовувати тільки коли у типу один конструктор. Наприклад:
head' :: [a] -> a head'
Так як ми вказали, що не треба обчислювати аргумент функції, поки він не буде потрібний, неможливо дізнатися, що перед нами: порожній список або одна його ланка. Функція завжди повертатиме undefined, адже в першому виразі ми використовували незаперечний зразок.
Використання лінивих обчислень
Обчислення завимогою
Найочевидніший плюс лінивих обчислень - якщо щось не потрібно, воно не буде обчислено. Наприклад:
(&&) False _ = False (&&) True a = a
Якщо перший аргумент функції and False, навіщо обчислювати другий, якщо і так зрозуміло, що результатом буде False? Можливо, щоб дізнатися значення другого аргументу, потрібно зробити безліч трудомістких обчислень, яких, використовуючи ліниві обчислення, можна уникнути.
Уявимо, що Ви хочете знайти 3 найменші елементи списку. У Хаскелі це можна зробити так:
Але в строгій мові це марнотратно, тому що доведеться відсортувати весь список. Але з лінивими обчисленнями, ми відсортуємо список до третього елемента і зупинимося, тому що продовжувати обчислення немає сенсу.
Мемоізація
Розглянемо таку функцію:
Скільки разів було обчислено суму 5 і 3? Правильна відповідь: один раз. Спочатку (5+3) — просто обіцянка, але коли вона була передана функції plus, вона обчислилася і її відповідь заступила сама обіцянка. Коли значення a знадобилося вдруге, програма просто взяла готовий результат із колишньої обіцянки, не роблячи жодних обчислень. У цьому полягає одна з найважливіших властивостей лінивих обчислень - мемоізація. Обіцянка в лінивій мові обчислюється лише один раз, а потім результат обчислення «затирає» собою обіцянку, тим самим даючи програмі можливість просто дізнатися відповідь, без необхідності обчислювати її знову. Така властивість лінивих обчислень знаходить застосування в динамічному програмуванні, що було добре показано в статті Динамічне програмування та ліниві обчислення.
Нескінченні та циклічні структури даних
Ще одне досить відоме застосування відкладених обчислень — створеннянескінченних структур даних.
Тут ми створюємо нескінченний список непарних чисел і беремо його десятий елемент.
> fibs = 1:1:zipWith (+) fibs (tail fibs) > fibs!! 100 573147844013817084101
Створення нескінченних списків можливе лише тому, що вони не обчислюються одразу. У другому прикладі, fibs спочатку буде 1:1:*обіцянка* , але коли ми запитаємо наступні елементи цього списку, програмі доведеться виконувати обіцянки доти, доки наші потреби не будуть задоволені. Одна обіцянка може породжувати інші, тому з невеликого списку та обіцянки, fibs може розвернутися у величезний ланцюжок чисел Фібоначчі.
Тепер перейдемо до циклічних структур даних.
data List a = List
Як нам зв'язати два елементи цього типу в кільце, так щоб поле next одного об'єкта вказувало на інший? Якби ми хотіли здійснити це в імперативній мові, ми використовували б покажчики, але в Хаскелі покажчиків немає. То як створити таку структуру? Дуже просто:
let x = List "x" y y = List "y" x in x
От і все. Так як поле next у List ліниве (треба пам'ятати, що конструктор типів така ж функція, і його аргументи можуть бути лінивими) створення такого «кільця» не призведе до зависання програми у спробах обчислити всю структуру.
> value. next $ x "y"
Ледаче введення-виведення
main = print. map toUpper =
Програма виводитиме текст у верхньому регістрі в міру його надходження.
Проблеми, пов'язані з використанням лінивих обчислень
Протягом усієї статті я використав термін «обіцяння», щоб позначити якусь одиницю лінивого обчислення, але річ у тому, що це не просто абстрактне поняття. Скомпільована програма на Хаскелі насправді використовуєобіцянки, які займають місце у пам'яті та на стеку. Тобто до витрат на звичайні обчислення додається складання сміття, виділення пам'яті, розгортання обіцянок. У цьому й полягає головна проблема лінивих обчислень — за їхнє неписьменне використання можна поплатитися сильним зниженням продуктивності, переповненнями стека та великим споживанням пам'яті.
Але існують способи, як зробити обчислення менш лінивими, які ми зараз розглянемо.
Розглянемо такий простий приклад:
Тут ми знаходимо суму чисел від 1 до 1e6 і виводимо її в консоль. Але якщо ви спробуєте запустити програму, то побачите таке повідомлення:
$ ./test Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' до збільшення it.
Чому виникає переповнення стека? Давайте подивимося, як обчислюватиметься функція sum': 1 + (1 + (1 + . (1 + sum' [])))
Так як обчислення sum'ls відкладається, ми отримуємо безліч вкладених обіцянок, що займають місце на стеку. Щоб позбавитися цього, треба якось змусити обіцянки обчислюватися, а не накопичуватися. І для цього ми маємо функцію seq. Вона приймає два аргументи, перший із яких обчислюється, а другий повертається. Спробуємо застосувати її тут.
Для початку перепишемо функцію sum' на використання хвостової рекурсії:
Тепер змусити додавання обчислюватися буде не складно:
Seq змушує суму обчислитися, натомість, щоб відкласти додавання потім.
Тепер помилок не відбувається.
Спробуємо трохи ускладнений приклад: крім суми елементів підрахуємо їх кількість.
$ ./test Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' до збільшення it.
Знову та сама помилка. Але чому? Адже мизмусили суми обчислитись? Тут час розповісти про одну властивість seq: він обчислює значення до WHNF. У звичайних чисел, як згадувалося раніше, немає WHNF, отже додавання було повністю обчислено seq. Але в цьому випадку ми намагаємося вирахувати пару, яка має WHNF, а саме (*обіцянка*, *обіцянка*) . Отже обіцянки все одно накопичуються, що призводить до переповнення стека. Ми можемо за допомогою seq змусити обчислюватись поля:
Трохи негарно, але працює. Ситуація, коли потрібно обчислити щось повністю, не така рідкісна, так що для цього був створений спеціальний модуль. Давайте його опробуємо:
Функція deepseq обчислює значення повністю до Normal Form.
Bang patterns
Для зручнішої вказівки суворості було створено розширення компілятора — Bang patterns. Воно дозволяє вказувати строгість аргументів просто знаком оклику. З використанням цього розширення, ми можемо переписати наш код так:
Все працюватиме, як і раніше. Bang patterns дозволяють нам вказувати строгість як аргументів функцій, а й полів структур даних, наприклад:
$ ./test SPair 500000500000 1000000
SPair - сувора пара. Значення в її полях завжди будуть обчислені, що, знову ж таки, не дозволяє обіцянкам накопичуватися.
Висновок
У цій статті, я постарався пояснити як впоратися з лінивими обчисленнями. Сподіваюся після її прочитання Ви почнете розуміти, де і як краще застосовувати відкладені обчислення, навіщо вони взагалі потрібні.
Список використаних матеріалів
А у нас тут можна отримати грант на тестовий період Яндекс.Хмари. Варто лише у полі «секретний пароль» запровадити «Хабр»