Lenjo izračunavanje

U teoriji programskih jezika, lenjo izračunavanje, ili call-by-need je strategija izračunavanja koja odlaže samo izračunavanje izraza sve dok njegova vrednost nije neophodna programu (non-strict evaluation) i koja takođe izbegava ponovno iračunavanje (deljenje). Deljenje može da smanji vreme izvršavanja određenih funkcija za eksponencijalni faktor nasuprot drugim, ne tako strogim strategijama za iračunavanje, kao što je poziv po imenu (call-by-name) .

Glavne prednosti lenjog izračunavanja su:

• Povećavanje učinka izbegavanjem nepotrebnog izračunavanja, kao i stanja greške u proceni složenih izraza
• Sposobnost da se stvore potencijalno beskrajne strukture podataka.
• Sposobnost da se definišu kontrole toka (strukture) kao apstrakcije

Lenjo izračunavanje je, vrlo često, kombinovano sa memoizacijom, kao što je to opisano u knjizi Džona Bentlija, Pisanje efikasnih programa( Writing Efficient Programs , eng.). Nakon što je vrednost funkcije izračunata za vrednost jendog ili više ulaznih parametara, rezultat se smešta u uporednu tabelu koja je indeksirana upravo vrednostima parametara; sledeci put kada je ta funkcija pozvana, pretražuje se tabela kako bi se videlo da li je rezultat za te ulazne parametre vec (iz)računat. Ako jeste, rezultat iz tablice je prosto vraćen pozivu funkcije. Međutim, ako vrednost ne postoji u tablici, računa se i potom smešta u istu.

Lenjo izračunavanje može da dovede do smanjenja memorije koja nam je potrebna, s obzirom da su vrednosti izračunate samo onda kada su potrebne. Međutim, lenjo izračunavanje je vrlo teško kombinovati sa nekim osobinama imperativnih jezika, kao što su na primer upravljanje izuzecima i ulaz/izlaz,jer postaje nemoguće utvrditi redosled izvršavanja određenih operacija.

Suprotno lenjom izračunavanju je pohlepno izračunavanje (eager) , poznato i kao strogo izračunavanje. Strogo izračunavanje je strategija koja je korišćena u većini programskih jezika.

Aplikacije

Odloženo izracunavanje se pretežno koristi u funkcionalnim programskim jezicima. Kada se ovakvo izračunavanje koristi, izraz se ne izvršava odmah pošto dobije vrednost za promenljivu koju sadrži, već kada je vrednost od njega zahtevana. To je, na primer, izraz x:=izraz; (tj. dodela vrednosti izraza promenljivoj) očigledno zahteva od izraza da njegova vrednost bude izračunata i smeštena u promenljivu x, ali ono što se nalazi u promenljivoj x je, zapravo, nebitno sve dok njenu vrednost ne potražuje neka druga referenca na promenljivu x u kasnijem delu izvršavanja programa, čije izračunavanje, takođe, može da bude odloženo. Na taj način se stvara sve veće drvo zavisnosti, zbog kojeg je, na kraju, program prinuđen da proizvede rezultat ili simbol koji je netačan.

Prednost odlaganja izračunavanja je i u tome što omogućava stvaranje izračunljivih beskonačnih listi bez korišcenja beskonačnih petlji ili bilo kakvih prostornih ometača programa. Na primer, može se napraviti funkcija koja pravi beskonačnu listu (poznatija kao tok) Fibonačijevog niza. Izračunavanje n-tog Fibonaacijevog broja , bilo bi samo izvlačenje tog broja iz liste zahtevajući, pri tom, izračunavanje samo prvih n clanova liste.

Na primer, u programskom jeziku Haskel , lista svih elemenata Fibonačijevog niza može biti zapisana kao :

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

U sintaksi jezika Haskell, simbol ":" dodaje element na početak liste, tail vraća listu bez njenog prvog elementa, a funkcija zipWith koristi navedenu funkciju (u ovom slučaju sabiranje) kako bi, kombinovanjem elemenata iz dve liste, forimirala treću.[13]

Pod uslovom da je programer oprezan, samo će one zahtevane vrednosti biti izračunate. Ipak, određene kalkulacije mogu rezultovati time da program pokušava da izračuna beskonačan broj elemenata; na primer, zahtevanje dužine liste ili pokušaj sumiranja elemenata liste funkcijom fold mogu rezultovati prekidanjem(pucanjem) programa ili zauzimanjem raspoložive memorije.

Kontrolne strukture

U mnogim poznatim nestrpljivim(eager) jezicima, if naredbe izračunavaju se lenjo.

if a then b else c

izračunava (a) , zatim, ako i samo ako je vrednost izračunatog izraza (a) tačna(true) izračunava se izraz (b) , u suprotnom, izračunava se vrednost izraza (c) . To jest, ili izraz (b) ili izraz (c) neće biti izračunati. Suprotno tome, u eager programskom jeziku očekivano ponašanje je da define f(x, y) = 2 * x set k = f(d, e) će ipak izračunati (e) izračunavajući izraz f(d, e) čak iako funkcija f ne koristi vrednost izraza (e). Ipak, kontrolne strukture koje definiše korisnik zavisne su od same sintakse, npr. define g(a, b, c) = if a then b else c l = g(h, i, j) I (i) i (j) će biti izračunate u nestrpljivom (eager) jeziku. Dok će u naredbi l' = if h then i else j ili (i) ili (j) biti izračunate, ali nikako obe vrednosti.

Lenjo izračunavanje dozvoljava kontrolnim strukturama (control structures) da budu definisane normalno, a ne kao primitivni tipovi ili tehnike kompiliranja. Ako (i) ili (j) imaju bočne efekte ili dovode do grešaka u izvršavanju(run time errors), neznatne razlike između (l) i (l') mogu postati veoma kompleksne. U eager jezicima, vrlo često je moguće korisnički definisane lenje kontrolne strukture predstaviti kao funkcije, iako one mogu odudarati od sintakse samog jezika za za nestrpljivo izračunavanje: Često se delovi koda (kao (i) i (j)) moraju upakovati u vrednosti funkcije, kako bi se izvršili samo onda kada su pozvani.

Kratkospojno (Short-circuit izračunavanje logičkih kontrolnih struktura(Boolean) se nekada naziva lenjo.

Rad sa beskonačnim strukturama podataka

Mnogi jezici nude upravo ocenu beskonačnih struktura podataka. One omogućavaju da definicije podataka budu opisane izrazima beskonačnih razmera, ili rekurzijom bez izlaza, ali stvarne vrednosti se izračunavaju samo onda kada su potrebne. Uzmimo, na primer, ovaj trivijalan program u programskom jeziku Haskell:

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

main = print $ elementIzBeskonaèneListe 4

U funkciji elementIzBeskonačneListe, vrednost koja predstavlja dužinu beskonačne liste je beskonačna, ali sve dok prava vrednost (preciznije, određena vrednost sa određenim indeksom u listi) nije potrebna, lista se ne izračunava, čak i tada , izračunava se samo po potrebi(tj. do željenog indeksa).

Još neke upotrebe

U prozorima sistema računara, prikazivanje informacija na ekranu vođeno je događajima izlaganja koji pokreću kod prikaza u poslednjem trenutku. Na ovaj način, sistem prozora izbegavaja računanje nepotrebnih promena na ekranu.[15]

Još jedan primer ovakvog izračunavanja u modernom računarstvu je copy-on-write alokacija stranica ili demand paging, gde se memorija alocira samo kada je vrednost koja se nalazi na toj memorijskoj lokaciji promenjena.[15]

Lenjost može biti vrlo korisna kod različitih scenarija sa visokim performansama. Primer je Unix-ova mmap funkcija, koja omogućuje učitavanje stranica sa diska direktnim zahtevom, kako bi se samo određene stranice učitale u memoriju, a neželjena memorija se ni ne alocirana.

MATLAB implementira copy on edit, gde kopirani nizovi imaju svoj lični memorijski prostor koji se umnožava samo onda kada je njihov sadržaj izmenjen, može dovesti do greške nedostatka memorije(out of memory error) ažurirajući element posle, a ne tokom operacije kopiranja.[16]

Implementacija

Neki programski jezici uobičajeno odlažu izračunavanje izraza dok neki omogućuju funkcije ili specijalnu sintaksu kako bi omogućili odlaganje.U programskim jezicima kao što su Miranda i Haskell, izračunavanje argumenata funkcija se podrazumevano odlaže. U mnogim drugim jezicima, odlaganje se može izvesti eksplicitnim prekidom računanja korišćenjem specijalne sintakse (u jeziku Scheme rečima "delay" i "force" i u jeziku OCaml naredbama "lazy" i "Lazy.force") ili, uopštenije, umotavanjem izraza u thunk. Objekat koji predstavlja ovakvu odloženu evaluaciju naziva se lenja budućnost(lazy future). Perl 6 koristi ovakvo izračunavanje nad listama, tako da se beskonačne liste mogu dodeliti promenljivama koje se mogu koristiti kao argumenti funkcija. Ali nasuprot jezicima Haskell i Miranda, Perl 6 uobičajeno ne koristi lenjo izračunavanje aritmetičkih operatora i funkcija.[12]

Lenjost i nestrpljivost

Kontrola nestrpljivosti u lenjim jezicima

U lenjim jezicima (npr. Haskell), gde je odlaganje izračunavanja uobičajena, moguće je kod učiniti kod nestrpljivijim ili suprotno, dajući mu veću lenjost nakon što je postao nestrpljiv. Ovo može biti sprovedeno kodiranjem nečega što pospešuje izračunavanje (što može učiniti sam kod nestpljivijim) ili izbegavanjem ovakvog koda (što kodu daje veću lenjost). Strogo izračunavanje obično dovodi do nestrpljivosti, međutim, to su, u stvari, dva sasvim različita koncepta.

Uprkos tome, postoji optimizacija implementirana u određenim kompajlerima, koja se naziva analiza strogoće(strictness analysis), i koja, u nekim slučajevima, dozvoljava kompajleru da zaključi da će vrednost uvek biti upotrebljena. To može biti izbor samog programera pri kojem se on odlučuje da li da iznudi tu određenu vrednost, ili, pak, irelevantnim, jer će analiza strogoće, svakako, primorati na strogo izračunavanje.

U Haskell-u, obeležavanjem polja konstruktora striktnim omogućava momentalnu potražnju vrednosti tih polja. Funkcija seq može, takoðe, biti korišćena za momentalno zahtevanje vrednosti koju će proslediti dalje, što može biti vrlo korisno ako polje konstruktora, faktički, treba da bude lenjo. Iako ni jedna od ovih tehnika ne implementira strogoću rekurzije i upravo zbog toga, izmišljena je funkcija deepSeq.

Takođe, uparivanje šablona(pattern matching) u jeziku Haskell 98 je striktno, tako da se kvantifikator(qualifier) ~ mora koristiti kako bi se postigla njegova lenjost.

Simulacija lenjosti u nestrpljivim jezicima

;Python

U Python-u 2.x, funkcija range() generiše listu celih brojeva. Cela lista, smešta se u memoriju u trenutku kada se izvrši prva dodela, tako da ovo predstavlja primer nestrpljivog ili neposrednog izračunavanja:

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

U Python-u 3.x, funkcija range() vraća specijalni range object objekat koji elemente liste generiše na zahtev(on demand). Elementi range objekta se proizvode samo kada je to potrebno (e.g., kada se izvršava naredba print(r[3]) u predstojećem primeru; ovo predstavlja primer odloženog ili lenjog izračunavanja:

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

Ovo prebacivanje na lenjo izračunavanje štedi memoriju za velike opsege koji možda nikada neće biti referencirani, gde su u datom trenutku potrebni jedan ili samo nekoliko elemenata.

U -{Python-u 2.x-}, moguće je koristiti funkciju xrange() čija je povratna vrednost objekat koji generiše brojeve u zahtevanom intervalu. Prednost ove funkcije je u tome da će generisani objekat uvek zauzeti istu količinu memorije.

>>> 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]

Od verzije 2.2 pa nadalje, Python ispoljava odloženo izračunavanje implementacijom iteratora (lazy sequences) za razliku od torki(tuple) ili sekvenci lista. Na primer (Python 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

Ovaj primer pokazuje da se liste računaju onda kada su pozvane, ali, u slučaju iteratora, prvi element '0' se štampa onda kada je to potrebno.

;.NET Framework

U .NET Framework-u, moguće je lenjo računati korišćenjem klase System.Lazy<T>. Klasa se može vrlo lako iskoristiti u F#-u korišćenjem ključne reči lazy, dok će metod force da natera na izračunavanje. Takođe, postoje specijalne kolekcije poput Microsoft.FSharp.Collections.Seq koje omogućavaju ugrađenu(built-in) podršku lenjom izračunavanju.

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

U C#-u and VB.NET-u, klasa System.Lazy<T>, koristi se direktno.

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
}

Ili, ilustrativnije:

// 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}

Drugi način je korišćenjem ključne reči yield:

]-
// 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;
    }
}

Vidi još

• Kombinatorna logika
• Функционално програмирање
• Генератор (рачунарство)
• Smanjivanje grafova
• Ламбда рачун
• Preduvid

Literatura

• Hudak, Paul (септембар 1989). „Conception, Evolution, and Application of Functional Programming Languages”. ACM Computing Surveys. 21 (3): 383—385. doi:10.1145/72551.72554. CS1 одржавање: Формат датума (веза)

Dopunska literatura

• Wadsworth, Christopher P. (1971). Semantics and Pragmatics of the Lambda Calculus.  PhD thesis, Oxford University
• Henderson, Peter; Morris, James H. (januar 1976). „A Lazy Evaluator”. Conference Record of the Third ACM symposium on Principles of Programming Languages. 
• Friedman, D. P.; Wise, David S. (1976). S. Michaelson and R. Milner, ур. „Cons should not evaluate its arguments” (PDF). Automata Languages and Programming Third International Colloquium. Edinburgh University Press. CS1 одржавање: Употреба параметра уредници (веза)
• Launchbury, John (1993). „A Natural Semantics for Lazy Evaluation”. Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '93). doi:10.1145/158511.158618. 

Šabloni dizajna

• John Hughes. "Why functional programming matters". The Computer Journal - Special issue on lazy functional programming. Volume 32 Issue 2, April 1989.
• Philip Wadler. "How to replace failure by a list of successes a method for exception handling, backtracking, and pattern matching in lazy functional languages". Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science, 1985, Volume 201/1985, 113-128.

Laziness in strict languages

• Philip Wadler, Walid Taha, and David MacQueen. "How to add laziness to a strict language, without even being odd". Workshop on Standard ML, Baltimore, September 1998.

Blog posts by computer scientists

• Robert Harper. "The Point of Laziness"
• Lennart Augustsson. "More points for lazy evaluation"

Spoljašnje veze

• Lazy Evaluation at the Portland Pattern Repository
• Lazy evaluation at Haskell Wiki
• The Incomplete Guide to Lazy Evaluation (in Haskell) – A series of tutorials on lazy evaluation in Haskell: How it works, how it helps making code more modular, and other things.
• Functional programming in Python becomes lazy
• Lazy function argument evaluation in the D language
• Lazy evaluation macros in Nemerle
• Lambda calculus in Boost Libraries Архивирано на сајту Wayback Machine (10. јун 2009) in C++ language
• Lazy Evaluation in Perl