Лењо израчунавање

У теорији програмских језика, лењо израчунавање, или call-by-need је стратегија израчунавања која одлаже само израчунавање израза све док његова вредност није неопходна програму (non-strict evaluation) и која такође избегава поновно ирачунавање (дељење). Дељење може да смањи време извршавања одређених функција за експоненцијални фактор насупрот другим, не тако строгим стратегијама за ирачунавање, као што је позив по имену (call-by-name) .

Главне предности лењог израчунавања су:

• Повећавање учинка избегавањем непотребног израчунавања, као и стања грешке у процени сложених израза
• Способност да се створе потенцијално бескрајне структуре података.
• Способност да се дефинишу контроле тока (структуре) као апстракције

Лењо израчунавање је, врло често, комбиновано са мемоизацијом, као што је то описано у књизи Џона Бентлија, Писање ефикасних програма( Writing Efficient Programs , енг.). Након што је вредност функције израчуната за вредност јендог или више улазних параметара, резултат се смешта у упоредну табелу која је индексирана управо вредностима параметара; следеци пут када је та функција позвана, претражује се табела како би се видело да ли је резултат за те улазне параметре вец (из)рачунат. Ако јесте, резултат из таблице је просто враћен позиву функције. Међутим, ако вредност не постоји у таблици, рачуна се и потом смешта у исту.

Лењо израчунавање може да доведе до смањења меморије која нам је потребна, с обзиром да су вредности израчунате само онда када су потребне. Међутим, лењо израчунавање је врло тешко комбиновати са неким особинама императивних језика, као што су на пример управљање изузецима и улаз/излаз,јер постаје немогуће утврдити редослед извршавања одређених операција.

Супротно лењом израчунавању је похлепно израчунавање (eager) , познато и као строго израчунавање. Строго израчунавање је стратегија која је коришћена у већини програмских језика.

Апликације

Одложено израцунавање се претежно користи у функционалним програмским језицима. Када се овакво израчунавање користи, израз се не извршава одмах пошто добије вредност за променљиву коју садржи, већ када је вредност од њега захтевана. То је, на пример, израз x:=izraz; (тј. додела вредности израза променљивој) очигледно захтева од израза да његова вредност буде израчуната и смештена у променљиву x, али оно што се налази у променљивој x је, заправо, небитно све док њену вредност не потражује нека друга референца на променљиву x у каснијем делу извршавања програма, чије израчунавање, такође, може да буде одложено. На тај начин се ствара све веће дрво зависности, због којег је, на крају, програм принуђен да произведе резултат или симбол који је нетачан.

Предност одлагања израчунавања је и у томе што омогућава стварање израчунљивих бесконачних листи без коришцења бесконачних петљи или било каквих просторних ометача програма. На пример, може се направити функција која прави бесконачну листу (познатија као ток) Фибоначијевог низа. Израчунавање н-тог Фибонаацијевог броја , било би само извлачење тог броја из листе захтевајући, при том, израчунавање само првих н цланова листе.

На пример, у програмском језику Хаскел , листа свих елемената Фибоначијевог низа може бити записана као :

 fibonači = 0 : 1 : zipWith (+) fibonači (tail fibonači)

У синтакси језика Хаскелл, симбол ":" додаје елемент на почетак листе, tail враћа листу без њеног првог елемента, а функција zipWith користи наведену функцију (у овом случају сабирање) како би, комбиновањем елемената из две листе, форимирала трећу.[13]

Под условом да је програмер опрезан, само ће оне захтеване вредности бити израчунате. Ипак, одређене калкулације могу резултовати тиме да програм покушава да израчуна бесконачан број елемената; на пример, захтевање дужине листе или покушај сумирања елемената листе функцијом fold могу резултовати прекидањем(пуцањем) програма или заузимањем расположиве меморије.

Контролне структуре

У многим познатим нестрпљивим(eager) језицима, if наредбе израчунавају се лењо.

if a then b else c

израчунава (a) , затим, ако и само ако је вредност израчунатог израза (a) тачна(труе) израчунава се израз (b) , у супротном, израчунава се вредност израза (c) . То јест, или израз (b) или израз (c) неће бити израчунати. Супротно томе, у еагер програмском језику очекивано понашање је да define f(x, y) = 2 * x set k = f(d, e) ће ипак израчунати (е) израчунавајући израз f(d, e) чак иако функција f не користи вредност израза (e). Ипак, контролне структуре које дефинише корисник зависне су од саме синтаксе, нпр. define g(a, b, c) = if a then b else c l = g(h, i, j) I (i) и (j) ће бити израчунате у нестрпљивом (eager) језику. Док ће у наредби l' = if h then i else j или (i) или (j) бити израчунате, али никако обе вредности.

Лењо израчунавање дозвољава контролним структурама (control structures) да буду дефинисане нормално, а не као примитивни типови или технике компилирања. Ако (i) или (j) имају бочне ефекте или доводе до грешака у извршавању(run time errors), незнатне разлике између (l) и (l') могу постати веома комплексне. У еагер језицима, врло често је могуће кориснички дефинисане лење контролне структуре представити као функције, иако оне могу одударати од синтаксе самог језика за за нестрпљиво израчунавање: Често се делови кода (као (i) и (j)) морају упаковати у вредности функције, како би се извршили само онда када су позвани.

Краткоспојно (Short-circuit израчунавање логичких контролних структура(Boolean) се некада назива лењо.

Рад са бесконачним структурама података

Многи језици нуде управо оцену бесконачних структура података. Оне омогућавају да дефиниције података буду описане изразима бесконачних размера, или рекурзијом без излаза, али стварне вредности се израчунавају само онда када су потребне. Узмимо, на пример, овај тривијалан програм у програмском језику Хаскелл:

elementIzBeskonačneListe :: Int -> Int
elementIzBeskonačneListe n = beskonačna !! n - 1
    where beskonačna = [1..]

main = print $ elementIzBeskonaèneListe 4

У функцији elementIzBeskonačneListe, вредност која представља дужину бесконачне листе је бесконачна, али све док права вредност (прецизније, одређена вредност са одређеним индексом у листи) није потребна, листа се не израчунава, чак и тада , израчунава се само по потреби(тј. до жељеног индекса).

Још неке употребе

У прозорима система рачунара, приказивање информација на екрану вођено је догађајима излагања који покрећу код приказа у последњем тренутку. На овај начин, систем прозора избегаваја рачунање непотребних промена на екрану.[15]

Још један пример оваквог израчунавања у модерном рачунарству је copy-on-write алокација страница или demand paging, где се меморија алоцира само када је вредност која се налази на тој меморијској локацији промењена.[15]

Лењост може бити врло корисна код различитих сценарија са високим перформансама. Пример је Unix-ova mmap функција, која омогућује учитавање страница са диска директним захтевом, како би се само одређене странице учитале у меморију, а нежељена меморија се ни не алоцирана.

MATLAB имплементира цопy он едит, где копирани низови имају свој лични меморијски простор који се умножава само онда када је њихов садржај измењен, може довести до грешке недостатка меморије(out of memory error) ажурирајући елемент после, а не током операције копирања.[16]

Имплементација

Неки програмски језици уобичајено одлажу израчунавање израза док неки омогућују функције или специјалну синтаксу како би омогућили одлагање.У програмским језицима као што су Миранда и Хаскелл, израчунавање аргумената функција се подразумевано одлаже. У многим другим језицима, одлагање се може извести експлицитним прекидом рачунања коришћењем специјалне синтаксе (у језику Сцхеме речима "delay" и "force" и у језику ОЦамл наредбама "lazy" и "Lazy.force") или, уопштеније, умотавањем израза у thunk. Објекат који представља овакву одложену евалуацију назива се лења будућност(лазy футуре). Перл 6 користи овакво израчунавање над листама, тако да се бесконачне листе могу доделити променљивама које се могу користити као аргументи функција. Али насупрот језицима Хаскелл и Миранда, Перл 6 уобичајено не користи лењо израчунавање аритметичких оператора и функција.[12]

Лењост и нестрпљивост

Контрола нестрпљивости у лењим језицима

У лењим језицима (нпр. Хаскелл), где је одлагање израчунавања уобичајена, могуће је код учинити код нестрпљивијим или супротно, дајући му већу лењост након што је постао нестрпљив. Ово може бити спроведено кодирањем нечега што поспешује израчунавање (што може учинити сам код нестпљивијим) или избегавањем оваквог кода (што коду даје већу лењост). Строго израчунавање обично доводи до нестрпљивости, међутим, то су, у ствари, два сасвим различита концепта.

Упркос томе, постоји оптимизација имплементирана у одређеним компајлерима, која се назива анализа строгоће(стрицтнесс аналyсис), и која, у неким случајевима, дозвољава компајлеру да закључи да ће вредност увек бити употребљена. То може бити избор самог програмера при којем се он одлучује да ли да изнуди ту одређену вредност, или, пак, ирелевантним, јер ће анализа строгоће, свакако, приморати на строго израчунавање.

У Хаскелл-у, обележавањем поља конструктора стриктним омогућава моменталну потражњу вредности тих поља. Функција seq може, такоðе, бити коришћена за моментално захтевање вредности коју ће проследити даље, што може бити врло корисно ако поље конструктора, фактички, треба да буде лењо. Иако ни једна од ових техника не имплементира строгоћу рекурзије и управо због тога, измишљена је функција deepSeq.

Такође, упаривање шаблона(pattern matching) у језику Хаскелл 98 је стриктно, тако да се квантификатор(qualifier) ~ мора користити како би се постигла његова лењост.

Симулација лењости у нестрпљивим језицима

;Python

У Python-u 2.x, функција range() генерише листу целих бројева. Цела листа, смешта се у меморију у тренутку када се изврши прва додела, тако да ово представља пример нестрпљивог или непосредног израчунавања:

 >>> r = range(10)
 >>> print r
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 >>> print r[3]
 3

У Python-u 3.x, функција range() враћа специјални range object објекат који елементе листе генерише на захтев(on demand). Елементи ранге објекта се производе само када је то потребно (е.г., када се извршава наредба print(r[3]) у предстојећем примеру; ово представља пример одложеног или лењог израчунавања:

 >>> r = range(10)
 >>> print(r)
 range(0, 10)
 >>> print(r[3])
 3

Ово пребацивање на лењо израчунавање штеди меморију за велике опсеге који можда никада неће бити референцирани, где су у датом тренутку потребни један или само неколико елемената.

У -{Пyтхон-у 2.x-}, могуће је користити функцију xrange() чија је повратна вредност објекат који генерише бројеве у захтеваном интервалу. Предност ове функције је у томе да ће генерисани објекат увек заузети исту количину меморије.

>>> r = xrange(10)
>>> print(r)
xrange(10)
>>> lst = [x for x in r]
>>> print(lst)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Од верзије 2.2 па надаље, Пyтхон испољава одложено израчунавање имплементацијом итератора (лазy сеqуенцес) за разлику од торки(тупле) или секвенци листа. На пример (Пyтхон 2):

 >>> brojevi = range(10)
 >>> iterator = iter(numbers)
 >>> print brojevi
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 >>> print iterator
 <listiterator object at 0xf7e8dd4c>
 >>> print iterator.next()
 0

Овај пример показује да се листе рачунају онда када су позване, али, у случају итератора, први елемент '0' се штампа онда када је то потребно.

;.НЕТ Фрамеwорк

У .НЕТ Фрамеwорк-у, могуће је лењо рачунати коришћењем класе Сyстем.Лазy<Т>. Класа се може врло лако искористити у Ф#-у коришћењем кључне речи лазy, док ће метод форце да натера на израчунавање. Такође, постоје специјалне колекције попут Мицрософт.ФСхарп.Цоллецтионс.Сеq које омогућавају уграђену(буилт-ин) подршку лењом израчунавању.

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.nth 1000

У C#-у анд ВБ.НЕТ-у, класа Сyстем.Лазy<Т>, користи се директно.

public int Suma()
{
    int a = 0;
    int b = 0; 
    Lazy<int> x = new Lazy<int>(() => a + b);
    a = 3;
    b = 5;
    return x.Value; // vraæa 8
}

Или, илустративније:

// rekurzivno izračunavanje n-tog Fibonačijevog broja
{-public int Fib(int n)
{
   return (n == 1)? 1 : (n == 2)? 1 : Fib(n-1) + Fib(n-2);
}

public void Main()
{
    Console.WriteLine("Koji Fibonačijev broj želite da izračunate?");
    int n = Int32.Parse(Console.ReadLine()); 
    Lazy<int> fib = new Lazy<int>(() => Fib(n));}- // funkcija je spremna, ali nije izvršena
    {-bool izvrši; 
    if(n > 100)
    {
        Console.WriteLine("Ovo će potrajati. Da li stvarno želite da izračunate ovako veliki broj? [y/n]"); //y-da,n-ne
        izvrši = (Console.ReadLine() == "y"); 
    }
    else izvrši = true;
    }-
    -{if(izvrši) Console.WriteLine(fib.Value); }-// broj je izračunat samo ukoliko je to zahtevano}

Други начин је коришћењем кључне речи yиелд:

]-
// nestrpljivo izvršavanje 
-{public IEnumerable<int> Fibonači(int x)
{
    IList<int> brojevi = new List<int>();

    int prethodni = -1;
    int sledeći = 1;
    for (int i = 0; i < x; i++)
    {
     int suma = prethodni + sledeći;
        prethodni = sledeći;
        sledeći = suma;
        brojevi.Add(suma); 
    }
    return brojevi;
}

// lenjo izračunavanje 
public IEnumerable<int> LenjoFibonači(int x)
{
    int prethodni = -1;
    int sledeći = 1;
    for (int i = 0; i < x; i++)
    {
        int suma = prethodni + sledeći;
        prethodni = sledeći;
        sledeći = suma;
        yield return suma;
    }
}

Види још

• Комбинаторна логика
• Функционално програмирање
• Генератор (рачунарство)
• Смањивање графова
• Ламбда рачун
• Предувид

Литература

• Худак, Паул (септембар 1989). „Цонцептион, Еволутион, анд Апплицатион оф Фунцтионал Программинг Лангуагес”. АЦМ Цомпутинг Сурвеyс. 21 (3): 383—385. дои:10.1145/72551.72554. ЦС1 одржавање: Формат датума (веза)

Допунска литература

• Wадсwортх, Цхристопхер П. (1971). Семантицс анд Прагматицс оф тхе Ламбда Цалцулус.  ПхД тхесис, Оxфорд Университy
• Хендерсон, Петер; Моррис, Јамес Х. (јануар 1976). „А Лазy Евалуатор”. Цонференце Рецорд оф тхе Тхирд АЦМ сyмпосиум он Принциплес оф Программинг Лангуагес. 
• Фриедман, D. П.; Wисе, Давид С. (1976). С. Мицхаелсон анд Р. Милнер, ур. „Цонс схоулд нот евалуате итс аргументс” (ПДФ). Аутомата Лангуагес анд Программинг Тхирд Интернатионал Цоллоqуиум. Единбургх Университy Пресс. ЦС1 одржавање: Употреба параметра уредници (веза)
• Лаунцхбурy, Јохн (1993). „А Натурал Семантицс фор Лазy Евалуатион”. Процеедингс оф тхе 20тх АЦМ СИГПЛАН-СИГАЦТ сyмпосиум он Принциплес оф программинг лангуагес (ПОПЛ '93). дои:10.1145/158511.158618. 

Шаблони дизајна

• Јохн Хугхес. "Wхy фунцтионал программинг маттерс". Тхе Цомпутер Јоурнал - Специал иссуе он лазy фунцтионал программинг. Волуме 32 Иссуе 2, Април 1989.
• Пхилип Wадлер. "Хоw то реплаце фаилуре бy а лист оф суццессес а метход фор еxцептион хандлинг, бацктрацкинг, анд паттерн матцхинг ин лазy фунцтионал лангуагес". Фунцтионал Программинг Лангуагес анд Цомпутер Арцхитецтуре. Лецтуре Нотес ин Цомпутер Сциенце, 1985, Волуме 201/1985, 113-128.

Лазинесс ин стрицт лангуагес

• Пхилип Wадлер, Wалид Таха, анд Давид МацQуеен. "Хоw то адд лазинесс то а стрицт лангуаге, wитхоут евен беинг одд". Wорксхоп он Стандард ML, Балтиморе, Септембер 1998.

Блог постс бy цомпутер сциентистс

• Роберт Харпер. "Тхе Поинт оф Лазинесс"
• Леннарт Аугустссон. "Море поинтс фор лазy евалуатион"

Спољашње везе

• Лазy Евалуатион ат тхе Портланд Паттерн Репоситорy
• Лазy евалуатион ат Хаскелл Wики
• Тхе Инцомплете Гуиде то Лазy Евалуатион (ин Хаскелл) – А сериес оф туториалс он лазy евалуатион ин Хаскелл: Хоw ит wоркс, хоw ит хелпс макинг цоде море модулар, анд отхер тхингс.
• Фунцтионал программинг ин Пyтхон бецомес лазy
• Лазy фунцтион аргумент евалуатион ин тхе D лангуаге
• Лазy евалуатион мацрос ин Немерле
• Ламбда цалцулус ин Боост Либрариес Архивирано на сајту Wаyбацк Мацхине (10. јун 2009) ин C++ лангуаге
• Лазy Евалуатион ин Перл