Як працюють ледачі обчислення

Маленька Лямбда вирішила, що прибирання в кімнаті можна відкласти і на потім.

Ледачі обчислення — часто використовувана методика при виконанні комп'ютером програм на Haskell. Вони роблять наш код простіше і модульнее, але можуть викликати і розгубленість, особливо коли мова заходить про використання пам'яті, стаючи для новачків поширеною пасткою. Наприклад, невинно виглядає вираз
foldl(+) 0 [1..10^8]
зажадає для свого обчислення гігабайти пам'яті.

У цьому керівництві я хочу пояснити, як працюють ледачі обчислення і що вони означають для часу виконання та обсягу пам'яті, витрачає програмами на Haskell. Я почну розповідь з основ редукції графів, а після перейду до обговорення суворої лівої згортки — найпростішого прикладу для розуміння і ліквідації витоків пам'яті.

Тема ледачих обчислень розглядалася в багатьох підручниках (наприклад, в книзі Саймона Томпсона «Haskell — The Craft of Functional Programming»), але інформацію про них, здається, все ще проблематично знайти в мережі. Сподіваюся, моє керівництво посприяє вирішенню цієї проблеми.

Ледачі обчислення — це компроміс. З одного боку, вони допомагають нам зробити більш код модульним. З іншого боку, буває неможливо до кінця розібратися, як відбувається обчислення в конкретній програмі — завжди існують невеликі відмінності між реальністю і тим, що ви про неї думаєте. В кінці статті я дам рекомендації, як діяти в ситуаціях такого роду. Отже, приступимо!


Основи: редукція графів

Вирази, графи і редексы

Виконання програм на Haskell означає обчислення виразів. Основна ідея, що ховається за цим, називається застосуванням функції. Нехай дана функція
square x = x*x

Ми можемо обчислити вираз
square (1+2),

замінюючи
square
в лівій частині визначення його правою частиною до тих пір, поки не отримаємо значення змінної
x
для поточного аргументу.
square (1+2)
=> (1+2)*(1+2)

Тут використовуються дві функції:
+
та
*

(1+2)*(1+2)
=> 3*(1+2)
=> 3*3
=> 9

Зверніть увагу, що в цьому випадку нам доводиться двічі обчислювати
(1+2)
. Однак, зрозуміло, що насправді відповіді однакові, оскільки обидва вирази пов'язані з одним і тим же аргументом
x
.

Щоб уникнути непотрібного дублювання, ми використовуємо метод під назвою "редукція графів". Взагалі кажучи, будь-який вираз може бути представлена у вигляді графа. Для нашого прикладу це виглядає наступним чином:
image
Кожен блок співвідноситься з застосуванням відповідної функції, чиє ім'я написано на білому полі, а сірі поля вказують на аргументи. Ця графічна нотація схожа на те, як компілятор насправді представляє вираз з покажчиками на комірки пам'яті.

Кожна функція, визначена програмістом, відповідає редукционному правилом. Наприклад, правило
square
виглядає наступним чином:
image
Обведений кружком
x
замінює собою підграф. Зверніть увагу: обидва аргументи функції множення вказують на один підграф. Такий спосіб спільного його використання — ключ до відсутності дублювання.

Будь підграф, що відповідає правилу, називається скорочуваним виразом (reducible expression) або редексом (redex) для стислості. Де б ми не зустріли редекс, ми можемо скоротити його, ніж оновимо відповідний правилу виділений прямокутник. У нашому прикладі є два редекса: можна скоротити або функцію
square
, або додавання
(+)
.
image
Якщо ми почнемо з редекса
square
, а потім продовжимо обчислення з редексом додавання, то отримаємо ланцюжок
image
На кожному кроці редекс, виділений кольором, оновлюється. На передостанньому графі з'являється новий редекс, пов'язаний з правилом множення. Виконавши цю редукцію, ми отримаємо підсумковий результат
9
.

Нормальна форма і слабка заголовкова нормальна форма

Якщо вираз (граф) не містить редексов, тобто в ньому нічого не можна скоротити, то справу зроблено. Коли так відбувається, ми кажемо, що вираз знаходиться у нормальній формі. Це підсумковий результат обчислення. У попередньому прикладі нормальною формою було єдине число, представлене графом
image
Але конструктори зразок
Just
,
Nothing
або конструкторів списків
:
та
[]
також зводяться до нормальної форми. При цьому вони виглядають, як функції, але оскільки представлені декларацією
data
та не мають правій частині, то правило редукції для них відсутня. Наприклад, граф
image
нормальна форма списку
1:2:3:[]
.

Взагалі кажучи, є ще дві вимоги до графу, щоб його можна було називати знаходиться в нормальній формі. По-перше, він повинен бути кінцевим, а по-друге, не мати циклів. Протилежне цим умовам іноді зустрічається при рекурсії. Наприклад, вираз, певне
ones = 1 : ones

співвідноситься з циклічним графом
image
Він не має редексов, але і не знаходиться в нормальній формі: хвіст списку рекурсивно вказує на сам список, в результаті породжуючи нескінченний цикл.

В Haskell ми зазвичай не виводимо нормальну форму повністю. Більш того, частіше всього ми зупиняємося, коли граф досягає слабкою заголовній нормальної форми (weak head normal form, WHNF). Кажуть, що граф знаходиться в WHNF, якщо самий верхній його вузол є конструктором. Наприклад, вираз
(7+12):[]
або
image
знаходиться в WHNF, оскільки його верхній вузол — конструктор списку
(:)
. І це не нормальна форма, так як перший аргумент містить редекс.

З іншого боку, будь-граф, , що знаходиться в WHNF, називається не обчисленим виразом або перетворювачем. Вираз, що починається з конструктора, знаходиться в WHNF, але його аргументи запросто можуть бути обчисленими.

Дуже цікавим прикладом графа в WHNF є граф функції
ones
, згаданої вище. Врешті-решт, самий верхній його елемент — конструктор. В Haskell ми можемо створювати і маніпулювати нескінченними списками! Вони чудово підходять для того, щоб код був більш модульним.

Порядок обчислень, ледачі обчислення

Часто вираз містить кілька редексов. Наскільки принципова послідовність, в якій ми будемо скорочувати їх?

Один з порядків редукції, званий енергійним обчисленням, обчислює аргументи функції до їх нормальної форми перш, ніж редукувати її саму. Ця стратегія використовується в більшості мов програмування.

Однак, компілятори Haskell зазвичай використовують інший порядок обчислень, званий ледачим, коли перш всього редукується верхнє застосування функції. При цьому може виникнути необхідність обчислити деякі аргументи, але тільки в необхідній кількості. Розглянемо функцію, визначену кількома рівняннями з використанням зіставлення із зразком. Для кожного з них аргументи будуть обчислюватися зліва направо до тих пір, поки їх верхній вузол не стане утримувати конструктор, що відповідає зразку. Якщо порівняння відбувається з звичайної змінної, то не обчислюються аргументи. Якщо ж зразком є конструктор, то це означає обчислення до WHNF.

Сподіваюся, приклад зробить цю концепцію зрозуміліше. Нехай дана функція
(&&)
, що реалізує логічне В. Її визначення виглядає наступним чином:
(&&) :: Bool -> Bool -> Bool
True && x = x
False && x = False

Воно представлене двома правилами редукції, залежать від значення першого аргументу:
True
або
False
.
image

image
Тепер розглянемо вираз
('H' == 'i') && ('a' == 'm')

запропонований
image

Обидва аргументи в ньому — редексы. Перше рівняння функції
(&&)
перевіряє, чи відповідає перший аргумент конструктору
True
. Таким чином, ліниве обчислення починається з редукування першого аргументу:
image

Другий аргумент не обчислюється, оскільки саме верхнє застосування функції вже є редексом. Ліниве обчислення завжди починає редукування з самого верхнього вузла, що ми і зробимо, використовуючи правило для функції
(&&)
. Отримаємо
image
Це вираз знаходиться в нормальній формі — отже, все готово!

Зверніть увагу, що якщо редукувати застосування
(&&)
так швидко, як тільки можливо, то шукати значення другого аргументу ніколи і не знадобиться, що зменшить загальні витрати часу. Деякі імперативні мови використовують схожий трюк, званий "замкнутий накоротко обчислення". Проте, зазвичай цей функціонал «вшитий» в мову і працює тільки для логічних операцій. В Haskell такий метод може застосовуватися до всіх функцій — це лише послідовність ледачих обчислень.

У загальному випадку нормальна форма, одержана за допомогою ледачих обчислень, ніколи не відрізняється від результату виконання того ж самого виразу їх енергійним колегою. Так що в цьому сенсі не важливо, в якому порядку відбувається редукція. Однак, ледачі обчислення виконуються за меншу кількість кроків і можуть мати справу з циклічними (нескінченними) графами, що недоступно енергійним обчислень.

Текстове представлення

Сподіваюся, візуальне подання виразів у вигляді графів допомогло вам отримати загальне поняття про ледачих обчислень, оскільки воно наочно підкреслює концепцію редекса і необхідний порядок редукції. Тим не менш, для конкретних розрахунків малювання картинок кілька обтяжливо. Для відстеження процесу редукції ми зазвичай працюємо з текстовим представленням з використанням синтаксису Haskell.

Графи допомагають легше візуалізувати загальні підграфи. В текстовому поданні нам потрібно позначати загальні вирази, даючи їм імена з використанням ключового слова
let
. Наприклад, наш найперший приклад редукування виразу
square (1+2)
буде виглядати так:
square (1+2)
=> let x = (1+2) in x*x
=> let x = 3 in x*x
=> 9

Синтаксис
let in
дозволяє зробити загальним вираз
x = (1+2)
. Зверніть увагу, що ліниве обчислення спочатку редукує функцію
square
, а тільки потім обчислює аргумент
x
.

Наш другий приклад — логічне І — перетворюється в
('H' == 'i') && ('a' == 'm')
=> False && ('a' == 'm')
=> False

У цьому випадку немає необхідності робити загальним якесь підвираз, так що ключове слово
let
в коді відсутня.

З цього моменту ми будемо використовувати тільки текстове представлення.

& пам'ять
Розглянемо тепер, що означають ледачі обчислення часу для роботи і необхідного обсягу пам'яті програм на Haskell. Якщо досі ви мали справу тільки з енергійними обчисленнями, то приготуйтеся до сюрпризів (особливо, коли мова піде про пам'ять).

Скільки кроків займає обчислення виразу? Для енергійних обчислень відповідь проста: у кожного застосування функції ми складаємо час, необхідний для обчислення аргументів, з часом, необхідним на виконання самого тіла функції. А що на рахунок ледачих обчислень? На щастя, ситуація тут сприятлива. Ми маємо наступний верхня межа:

Теорема: ледачі обчислення ніколи не скоюють більше обчислювальних кроків, ніж енергійні обчислення.

Це означає, що в процесі аналізу часу виконання алгоритму ми завжди можемо зробити вигляд, ніби обчислюються аргументи «енергійно». Наприклад, можна транслітерувати код сортувального алгоритму в Haskell і бути впевненими, що результат буде мати ту ж саму (а іноді і кращу) алгоритмічну складність, що і його енергійний двійник.

Тим не менш, реалізація ледачих обчислень вимагає певних адміністративних витрат. Для додатків з високою продуктивністю, на зразок обробки зображень або цифрових симуляцій, вигідно «не лінуватися» і залишатися ближче до «заліза». В іншому випадку, мантра «простий і модульний код» приводить нас до ледачих обчислень. Наприклад, оптимізація компілятора під назвою "злиття потоків" має на меті підвищення продуктивності операцій з масивами, як з модульним, спископодобным інтерфейсом. Ця ідея втілена в бібліотеці vector .

Пам'ять

На жаль, ситуація з використанням пам'яті не так проста, як з часом. Суть проблеми полягає в тому, що обсяг пам'яті, необхідний не обчисленому висловом, може значно відрізнятися від обсягу, займаного його нормальною формою. Вираз використовує тим більше місця, чим більше сайтів містить граф. Наприклад,
((((0 + 1) + 2) + 3) + 4)

посяде під зберігання більше пам'яті, ніж його нормальна форма
10
. Контрприкладом може служити вираз
enumFromTo 1 1000

чий більш знайомий синтаксис виглядає як
[1..1000]
. Це застосування функції складається всього з трьох вузлів, чому займає значно менше пам'яті, ніж список
1:2:3:...:1000:[]
, що містить як мінімум тисячу елементів.

Коли варіант з обчисленим виразом виходить з-під контролю, відбувається витік пам'яті. Рішенням тут стане контроль всього процесу обчислення, щоб гарантувати його завершення як можна швидше. Для цієї мети в Haskell є комбінатор
seq :: a -> b> b

Як припускає оголошення типів, по суті він просто повертає другий аргумент і веде себе в більшій мірі, як функція
const
. Однак, у вираження
seq x y
спочатку до WHNF вычислится
y
, а тільки потім
x
. Навпаки, при обчисленні
const x y
ми залишаємо
y
в спокої і негайно обчислюємо
x
.

Розглянемо прототипичный приклад, що показує, як використовувати
seq
, і який повинен знати кожен програміст на Haskell: сувору ліву згортку. Нехай дано завдання підсумувати всі числа від
1
100
. Ми будемо це робити, використовуючи акумулює параметр, тобто як в лівій згортку
foldl (+) 0 [1..100]

Для довідки: функція foldl визначена Haskell Prelude
foldl :: (a -> b> a) -> a -> [b] -> a
foldl f a [] = a
foldl f a (x:xs) = foldl f (f a x) xs

Процес обчислення виглядає наступним чином:
foldl (+) 0 [1..100]
=> foldl(+) 0 (1:[2..100])
=> foldl(+) (0 + 1) [2..100]
=> foldl(+) (0 + 1) (2:[3..100])
=> foldl(+) ((0 + 1) + 2) [3..100]
=> foldl(+) ((0 + 1) + 2) (3:[4..100])
=> foldl(+) (((0 + 1) + 2) + 3) [4..100]
=> ...

Як ви можете бачити, що акумулює параметр зростає від гілки до гілки — відбувається витік пам'яті. Щоб її уникнути, потрібна гарантія постійного знаходження акумулятора в WHNF. Наступна версія
foldl
проробляє цей трюк:
foldl' :: (a -> b> a) -> a -> [b] -> a
foldl' f a [] = a
foldl' f a (x:xs) = let a' = f a x
in seq a' (foldl' f a' xs)

Її можна знайти в модулі Data.List. Тепер процес обчислення виглядає так:
foldl' (+) 0 [1..100]
=> foldl' (+) 0 (1:[2..100])
=> let a' = 0 + 1 in seq a' (foldl' (+) a' [2..100])
=> let a' = 1 in seq a' (foldl' (+) a' [2..100])
=> foldl' (+) 1 [2..100]
=> foldl' (+) 1 (2:[3..100])
=> let a' = 1 + 2 in seq a' (foldl' (+) a' [3..100])
=> let a' = 3 in seq a' (foldl' (+) a' [3..100])
=> foldl' (+) 3 [3..100]
=> ...

Під час обчислення вираз має постійний розмір. Використання
seq
гарантує виведення WHNF акумулюючого параметра до того, як буде розглянутий наступний елемент списку.

Як правило, функція
foldl
схильна до витоків пам'яті, так що краще використовувати замість неї
foldl'
або
foldr
.

До речі, зверніть увагу, що мовою з енергійними обчисленнями для завдання підсумувати цифри від
1
100
ви ніколи не зможете написати код, подібний до наведеного вище. Справді, в цьому випадку спочатку вычислится до нормальної форми список
[1..100]
, що займе стільки ж місця в пам'яті, скільки потрібно неефективною версії
foldl
. Якщо потрібно вирішити завдання ефективно, то треба писати рекурсивний цикл. Але в Haskell ледачі обчислення дозволяють це зробити одним застосуванням комбінатора загального призначення для списку
[1..100]
, який обчислюється «на вимогу». Це ще один приклад того, як можна зробити код більш модульним.

Інший важливий урок, який можна зробити з розглянутої задачі, наступний: насправді обчислення, яке я показав, відбувається не зовсім так. Якщо ми визначимо список перерахування
[n..m]

enumFromTo n m = if n < m 
then n : enumFromTo (n+1) m 
else []

то редукція в WHNF насправді буде виглядати так:
[1..100]
=> 1 : [(1+1)..100]

тобто новий перший аргумент не
2
, а не обчислене вираз
(1+1)
. Не те щоб тут була велика різниця, але майте на увазі: ви повинні бути дуже обережні при точній трасуванні ледачих обчислень — вони ніколи не роблять в точності так, як ви собі це уявляєте. Справжній код для enumFromTo дещо відрізняється від показаного вище. Зокрема, зверніть увагу, що
[1..]
будується, як список чисел, які не перебувають у WHNF.

В принципі, я так довго про це розповідав, щоб підвести до простого висновку: з ледачими обчисленнями не представляється можливим детально відстежити трасування, крім зовсім уже простих прикладів. Таким чином, аналіз використання пам'яті програмами на Haskell — завдання не з тривіальних. Моя порада: робіть що-небудь тільки в тих випадках, коли має місце явна втрата пам'яті. Для цього я рекомендував би скористатися профілюючими інструментами, що дозволяють розібратися в тому, що відбувається. Після того, як проблема сформульована, інструменти на зразок інваріанти простору та
seq
може гарантувати обчислення відповідних виразів в WHNF, незалежно від дрібних деталей виконання ледачих обчислень.

Ось і все, що я хотів розповісти про ледачих обчислень та використанні пам'яті. Є ще один важливий приклад витоку, який я не торкнувся, але який не менш хрестоматиен:
let small' = fst (small, large) in ... small' ...

Вираз
small'
зберігає посилання на вираз
large
навіть коли воно відкидається функцією
fst
. Можливо, вам слід якимось чином обчислювати вираз
small'
в WHNF, щоб можна було без проблем використовувати пам'ять, зайняту
large
.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.