Мързелива оценка
Един от отличителните белези на Haskell е забавената или мързелива оценка. Тази функция на езика не само отваря много възможности, но създава и някои проблеми, особено със скоростта на програмите.
В тази статия ще се опитам да обясня какво е мързелива оценка, за какво може да се използва и как да избегнете загуба на производителност, когато я използвате.
Какво е мързелива оценка?
В конвенционалните, не-мързеливи езици за програмиране оценката е стриктна – т.е. аргументите на функцията се оценяват преди самата функция да бъде изпълнена. Например, в някакъв абстрактен строг език за програмиране:
А в мързеливите езици, включително Haskell, изчисленията се отлагат. Всички изчисления (с изключение на някои I / O функции) не се извършват незабавно, но, така да се каже, се отлагат, докато наистина са необходими. Същият пример в Haskell:
макс. (5+3) (4*4) -> нека x = 5+3; y = 4*4 в if x>= y then x else y -> нека x = 8; y = 4*4 in if 8 >= y then 8 else y -> нека x = 8; y = 16 in if 8 >= 16 then 8 else 16 -> 16
Този пример ясно показва, че изчисляването на подизразите (5 + 3 и 4 * 4) беше отложено до последно, а именно до момента, в който трябваше да бъдат сравнени. Тук „силата“, която е причинила изпълнението на изчислението, може да се счита за изход към конзолата, т.е. IO. Но това не е единственият начин.
Да вземем този пример:
нека z = (сума [1..10], обратен "haskell") в . (по-нататък приемаме, че z се използва в in част, в противен случай изразът let изобщо няма да бъде оценен)
z е обещание, просто неизчислена стойност. Какво се случва, ако го сравните с проба z?
Първо, z е просто обещание, както в предишния пример, но това, което компилаторът може да провери ече z действително съответства на модела, той трябва да "разшири" z до формата: (*обещание*, *обещание*) . x и y са обещания, съответстващи на компонентите на двойката z. Добавяне на друго сравнение на шаблони:
За да провери дали y е списък, компилаторът го изчислява към изгледа:* promise*:* promise* след това той изчислява първото обещание: 'l':* promise* и като се увери, че Y е списък, започващ с 'l', той сравнява с примера: “l '=' l ':* обещанието* в този пример YS ще бъде обещание, което да съответства на останалата част от списъка Y.
Нека да разгледаме как се е променила дълбочината на изчисление за z в примерите:
*обещание* (*обещание*, *обещание*) (*обещание*, 'l':*обещание*)
z е частично изчислен и както може би се досещате, почти всички стойности в Haskell могат да бъдат изчислени по този начин. Например, минималната възможна оценка за двойка е просто да се оцени конструктора: (*promise*, *promise*) . За списък това е *promise*:*promise* или []. А за числа от такава форма не съществува - те или се изчисляват, или не. Когато дадена стойност не е напълно изчислена, се казва, че е вНормална форма със слаба глава(WHNF), а когато е напълно оценена, се казва, че е вНормална форма. Стойността в WHNF, когато е напълно изчислена, "преминава" в нормалната форма. Например, ако покажем z на екрана, тогава нормалната му форма ще бъде (55,"lleksah") . Очевидно стойностите, чийто конструктор не приема аргументи, не могат да бъдат в WHNF. Тоест типове като Bool, Ord, Int и т.н. нямат WHNF, докато типовете Maybe, [a], Either и т.н. нямат WHNF. имат.
Мързеливи функции
Функциите могат да бъдат мързеливи и строги в своите аргументи. Мързеливите не изчисляват аргументите си, а строгите го правят донякъде. Трябва да се отбележи, че функцията може да бъдемързелив в един спор и строг в друг. Разбира се, повечето функции трябва да използват своите аргументи по някакъв начин, което означава, че се оценяват. Например функцията за дължина. За да разбере дължината на списъка, тя трябва да оцени неговите конструктори, но не и стойностите. Това означава, че length *promise* ще се "разшири" в нещо като: length (*promise* : *promise* : *promise* : []) .
Има лесен начин да проверите дали дадена функция е мързелива в някакъв аргумент. Просто трябва да му предадете недефиниран аргумент вместо това и ако резултатът е грешка, тогава функцията е строга в този аргумент, а ако не, тогава е мързелива. Няма да доведе до грешка:
const 5 undefined Само недефиниран
недефинирана дължина недефинирана глава
Мързеливо съвпадение на шаблони
Не само функциите могат да бъдат мързеливи, но и сравненията на шаблони. За разлика от стриктното съпоставяне на шаблони, което вече разгледахме, мързеливите не принуждават обещанията да бъдат оценени, тоест те не ги "развиват" по време на компилиране. Например:
(x, y)=1 > f недефиниран 1
(x, y) е мързелив модел. Има същото свойство като аргумент на мързелива функция: когато подадем undefined там, не възниква грешка. Това сравнение на шаблони може да се намери в Control.Arrow:
> (const 1 *** const 2) undefined (1, 2)
Но трябва да запомните, че мързеливият модел трябва да се използва само когато типът има един конструктор. Например:
глава'::[a]-> глава'
Тъй като посочихме, че не е необходимо да оценяваме аргумента на функцията, докато не е необходим, не е възможно да разберем какво е пред нас: празен списък или една от връзките му. Функцията винаги ще връща undefined, защото в първия израз използвахме неопровержим модел.
Използване на мързелива оценка
Изчисляване поизискване
Най-очевидното предимство на мързеливото оценяване е, че ако нещо не се изисква, то няма да бъде оценено. Например:
(&&) False _ = False (&&) True a = a
Ако първият аргумент на функцията and е False, защо да оценяваме втория, ако вече е ясно, че резултатът ще бъде False? Възможно е, за да разберете стойността на втория аргумент, да е необходимо да извършите много отнемащи време изчисления, които могат да бъдат избегнати, като се използва мързелива оценка.
Да приемем, че искате да намерите 3-те най-малки елемента от списък. В Haskell това може да се направи по следния начин:
Но на строг език това е разточително, тъй като трябва да сортирате целия списък. Но с мързелива оценка сортираме списъка до третия елемент и спираме, защото няма смисъл да продължаваме изчислението.
запомняне
Помислете за тази функция:
Колко пъти е изчислен сборът от 5 и 3? Правилен отговор: веднъж. Първоначално (5+3) е само обещание, но когато беше предадено на функцията плюс, то беше оценено и отговорът му замени самото обещание. Когато стойността на a беше поискана втори път, програмата просто взе крайния резултат от предишното обещание, без да прави никакви изчисления. Това е едно от най-важните свойства на мързеливата оценка – мемизацията. Обещание на мързелив език се оценява само веднъж и след това резултатът от изчислението „презаписва“ обещанието, като по този начин дава възможност на програмата просто да намери отговора, без да се налага да го изчислява отново. Това свойство на мързеливата оценка намира приложение в динамичното програмиране, което беше добре показано в статията Динамично програмиране и мързелива оценка.
Безкрайни и циклични структури от данни
Друго доста добре познато използване на мързелива оценка е създаванетобезкрайни структури от данни.
Тук създаваме безкраен списък от нечетни числа и вземаме неговия 10-ти елемент.
> fibs = 1:1:zipWith (+) fibs (tail fibs) > измислици!! 100 573147844013817084101
Създаването на безкрайни списъци е възможно само защото те не се оценяват веднага. Във втория пример fibs първоначално ще бъде 1:1:*promise*, но когато поискаме следващите елементи от този списък, програмата ще трябва да изпълни обещания, докато нашите нужди не бъдат удовлетворени. Едно обещание може да породи други, така че от малък списък и обещание фибовете могат да се разгърнат в огромна верига от числа на Фибоначи.
Сега нека да преминем към цикличните структури от данни.
данни Списък a = Списък
Как да свържем два елемента от този тип в пръстен, така че следващото поле на единия обект да сочи към другия? Ако искахме да направим това на императивен език, щяхме да използваме указатели, но в Haskell няма указатели. И така, как да създадете такава структура? Много просто:
нека x = Списък "x" y y = Списък "y" x в x
Това е всичко. Тъй като следващото поле на списъка е мързеливо (не забравяйте, че конструкторът на типа е същата функция и неговите аргументи могат да бъдат мързеливи), създаването на такъв "пръстен" няма да доведе до замразяване на програмата при опити за изчисляване на цялата структура.
> стойност . следващ $x "y"
Мързелив I/O
main = печат. map toUpper =
Програмата ще изведе текст с главни букви, когато пристигне.
Проблеми, свързани с използването на мързелива оценка
В цялата тази статия използвах термина „обещание“, за да обознача единица за мързелива оценка, но въпросът е, че това не е просто абстрактна концепция. Компилираната програма на Haskell всъщност използваобещания, които заемат място в паметта и в стека. Тоест събирането на отпадъци, разпределянето на паметта и разгръщането на обещания се добавят към разходите за редовни изчисления. Това е основният проблем с мързеливите оценки - за неграмотното им използване можете да платите със силно намаляване на производителността, препълване на стека и висока консумация на памет.
Но има начини да направите изчисленията по-малко мързеливи, които сега ще разгледаме.
Помислете за този прост пример:
Тук намираме сбора на числата от 1 до 1e6 и го отпечатваме на конзолата. Но ако се опитате да стартирате програмата, ще видите това съобщение:
$ ./test Препълване на стеково пространство: текущ размер 8388608 байта. Използвайте `+RTS -Ksize -RTS', за да го увеличите.
Защо се получава препълване на стека? Нека да видим как ще се изчисли функцията sum': 1 + (1 + (1 + . (1 + sum' [])))
Тъй като оценката на sum'ls се забавя, в крайна сметка имаме много вложени обещания, заемащи място в стека. За да се отървете от това, трябва по някакъв начин да принудите обещанията да бъдат изчислени, а не натрупани. И за това имаме функцията seq. Необходими са два аргумента, първият от които се оценява, а вторият се връща. Нека се опитаме да го приложим тук.
Първо, нека пренапишем функцията sum', за да използваме опашната рекурсия:
Сега няма да е трудно да принудите добавянето да бъде изчислено:
Seq кара сумата да бъде изчислена, вместо да отложи добавянето за по-късно.
Сега не възниква грешка.
Нека опитаме малко по-сложен пример: освен сбора на елементите, изчисляваме и техния брой.
$ ./test Препълване на стеково пространство: текущ размер 8388608 байта. Използвайте `+RTS -Ksize -RTS', за да го увеличите.
Отново същата грешка. Но защо? Ние смепринудени сумите да бъдат изчислени? Сега е време да поговорим за едно свойство на seq: то се оценява на стойност до WHNF. Обикновените числа, както беше споменато по-рано, нямат WHNF, така че събирането е напълно оценено от seq. Но в този случай се опитваме да изчислим двойка, която има WHNF, а именно (*обещание*, *обещание*). Така че обещанията все още се натрупват, което води до препълване на стека. Можем да използваме seq, за да принудим полетата да бъдат изчислени:
Малко грозно, но работи. Ситуацията, когато трябва да изчислите нещо напълно, не е толкова рядка, затова е създаден специален модул за това. Нека да го изпробваме:
Функцията deepseq изчислява стойностите изцяло, до нормалната форма.
Модел на бретон
За по-удобна индикация на тежестта е създадено разширение на компилатора - Bang patterns. Тя ви позволява да укажете тежестта на аргументите просто с удивителен знак. С това разширение можем да пренапишем нашия код по следния начин:
Всичко ще работи както преди. Банг шаблоните ни позволяват да уточним строгостта не само на аргументите на функцията, но и на полетата на структурите от данни, например:
$ ./test SPair 500000500000 1000000
SPAir е строга двойка. Стойностите в неговите полета винаги ще се изчисляват, което отново предотвратява натрупването на обещания.
Заключение
В тази статия се опитах да обясня как да се справя с мързеливото оценяване. Надявам се, след като го прочетете, ще започнете да разбирате къде и как е по-добре да използвате отложени изчисления, защо изобщо са необходими.
Списък на използваните материали
И тук можете да получите грант за тестов период на Yandex.Cloud. Необходимо е само да въведете "Habr" в полето "секретна парола".