Odložené vyhodnocování ( nebo , česky též líné vyhodnocování) je v programování vyhodnocovací strategie, při které je vyhodnocení výrazu odloženo až do okamžiku, kdy je jeho hodnota skutečně potřebná (nestriktní vyhodnocování). Často se také vyhýbá opakovanému vyhodnocování (sdílení). Sdílení může zkrátit čas běhu určitých funkcí o exponenciální faktor oproti jiným nestriktním strategiím vyhodnocování např. volání jménem.
K výhodám odloženého vyhodnocování patří:
Možnost definovat řídicí struktury jako abstrakce nikoli jako primitiva. Možnost definovat potenciálně nekonečné datové struktury. To umožňuje přímočařejší implementaci některých algoritmů. Zvýšení výkonnosti neprováděním nepotřebných výpočtů a zabránění chybovým stavům při vyhodnocování složených výrazů.
Odložené vyhodnocování se často kombinuje s memoizací, jak popisuje Jon Bentley ve své knize Writing Efficient Programs. Když je hodnota funkce vypočítána pro určitý parametr nebo sadu parametrů, je výsledek uložen do vyhledávací tabulky, která je indexovaná hodnotami těchto parametrů; při dalším vyvolání funkce se zjistí, zda tabulka výsledek pro tuto kombinaci hodnot parametrů již neobsahuje. Pokud ano, bude jednoduše vrácen uložený výsledek. Pokud ne, provede se vyhodnocení funkce, a získaná hodnota bude přidána do vyhledávací tabulky pro případné opakované použití.
Odložené vyhodnocování může vést ke zmenšení zabrané paměti, protože hodnoty se vytvářejí, až když jsou potřebné. Odložené vyhodnocování se však obtížně kombinuje s imperativními vlastnostmi jako je například zpracovávání výjimek a vstupně-výstupní operace, protože řád operace se stane neurčitým. Odložené vyhodnocování může způsobovat úniky paměti.Edward Z. Yang. Space leak zoo.
Opakem odloženého vyhodnocování je okamžité (striktní, hladové, dychtivé) vyhodnocování (), které se používá ve většině imperativních programovacích jazyků.
Historie Odložené vyhodnocování zavedl pro lambda kalkul Christopher Wadsworth. Pro programovací jazyky je zavedli Peter Henderson a James H. Morris a nezávisle Daniel P. Friedman a David S. Wise.
Aplikace Odložené vyhodnocování se používá především ve funkcionálním programování. Při použití odloženého vyhodnocování nedochází k vyčíslení výrazu v okamžiku, kdy má být uložen do proměnné, ale až když je tato proměnná použita ve výrazu. To znamená, že příkaz jako x = výraz; (tj. přiřazení výsledku výrazu do proměnné) sice jasně vyžaduje vyhodnocení výrazu a uložení získané hodnoty do proměnné x, ale co je skutečně v proměnné x není důležité, dokud hodnota proměnné x není použita v některém pozdějším výrazu, jehož vyhodnocování může být také odloženo; rychle rostoucí strom závislostí musí být nakonec prořezán, aby hodnota příslušného symbolu byla použitelná mimo program.
Výhodou odloženého vyhodnocování je možnost vytvářet vypočitatelné nekonečné seznamy bez nekonečných smyček nebo při vyvozování, u něhož záleží na velikosti. Například můžeme vytvořit funkci, které vytváří nekonečný seznam (často nazývaný proud, angl. stream) Fibonacciho čísel. Výpočet n-tého Fibonacciho čísla tak bude pouze vybráním příslušného prvku z nekonečného seznamu, které si vynutí vyhodnocení prvních n členů seznamu.
Například v programovacím jazyce Haskell lze seznam všech Fibonacciho čísel zapsat takto:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
V syntaxi jazyka Haskell operátor „dvojtečka“ : přidá prvek na začátek seznamu, tail vrátí seznam bez prvního prvku a zipWith použije zadanou funkci (v tomto případě sčítání) pro zkombinování odpovídajících prvků ze dvou seznamů pro výrobu třetího.
Pokud je programátor pečlivý, budou vyhodnocovány pouze hodnoty, které jsou potřebné pro výpočet určitého výsledku. Některé výpočty však mohou způsobit, že se program pokusí vyhodnotit nekonečný počet prvků; například získání délky seznamu nebo pokus sečíst všechny prvky seznamu pomocí funkce vyššího řádu; výsledkem bude buď selhání programu nebo vyčerpání paměti.
Řídicí struktury V téměř všech obvyklých „striktních“ jazycích se odloženým způsobem vyhodnocují podmíněné příkazy:
if a then b else c
vyhodnotí (a), a pak právě tehdy, když (a) je splněno, vyhodnotí (b), jinak vyhodnotí (c). To znamená, že se buď (b) nebo (c) nebude vyhodnocovat. Naopak, v těchto jazycích se očekává, že define f(x, y) = 2 * x set k = f(d, e) bude při výpočtu f(d, e) stále vyhodnocovat (e), i když (e) se ve funkci f nepoužívá. Uživatelem definované řídicí struktury závisejí na přesné syntaxi, takže například define g(a, b, c) = if a then b else c l = g(h, i, j) bude ve striktním jazyce vyčíslováno (i) i (j). Zatímco jazyk s odloženým vyhodnocováním bude při vyhodnocování l' = if h then i else j vyhodnocovat parametry (i) nebo (j), ale nikdy ne oba.
Odložené vyhodnocování umožňuje, aby řídicí struktury byly definované normálně a ne jako primitiva nebo překladové techniky. Pokud (i) nebo (j) mají vedlejší účinky nebo způsobí běhové chyby, mohou nepatrné rozdíly mezi (l) a (l') způsobit velmi odlišné výsledky. Obvykle je možné zavést uživatelem definované líné řídicí struktury do dychtivých jazyků jako funkce, i když se mohou lišit od syntaxe jazyka pro dychtivé vyhodnocování: Často je třeba příslušné bloky kódu (jako (i) a (j)) zabalit do funkce, takže jsou prováděné pouze, když jsou volané.
Zkrácené vyhodnocování logických řídicích struktur se také někdy nazývá líné.
Práce s nekonečnými datovými strukturami Mnoho jazyků poskytuje koncept nekonečných datových struktur, které umožňují definovat data pomocí nekonečných rozsahů nebo nekonečné rekurze, přičemž skutečné hodnoty se počítají, až když jsou potřebné. Uvažujme například tento triviální program v jazyce Haskell:
numberFromInfiniteList :: Int -> Int numberFromInfiniteList n = infinity !! n - 1 where infinity = [1..]
main = print $ numberFromInfiniteList 4
Hodnota infinity ve funkci numberFromInfiniteList znamená nekonečný rozsah, ale dokud není potřebná žádná skutečná hodnota (nebo konkrétněji určitá hodnota s určitým indexem), seznam nebude vyčíslen, a dokonce i pak je vyčíslen podle potřeby (tj. do požadovaného indexu.)
Vyhýbání se složitému kódu Složený výraz může mít tvar EasilyComputed or LotsOfWork; pokud je první (snadno vyčíslitelná) část splněna, lze druhou (obtížně vyčíslitelnou) část přeskočit. Může se např. jednat o test, zda velké číslo N je prvočíslo; funkce IsPrime(N) je sice dostupná, ale může vyžadovat velké množství výpočtů na vyhodnocení. Použití N=2 or [Mod(N,2)≠0 and IsPrime(N)] může pomoci, pokud se má výraz vyhodnocovat mnohokrát s různými hodnotami N.
Vyhýbání se chybovým podmínkám Složený výraz může být tvaru SafeToTry and Výraz přičemž, pokud SafeToTry je false, nebude se Výraz vyhodnocovat, aby se signalizovala běhová chyba, např. dělení nulou nebo index mimo meze, atd. Například následující pseudokód vyhledá poslední nenulový prvek pole: L:=Délka(A); While L>0 and A(L)=0 do L := L-1; Pokud by všechny prvky pole byty nulové, smyčka bude pracovat až do L = 0, a v tomto případě musí být ukončena, aniž by byl referencován nultý prvek pole, který neexistuje.
Jiné použití V grafických uživatelských rozhraních používajících systém okének pro zobrazování, je vykreslení oken na obrazovku vyvolané událostí expose, která řídí kód pro zobrazení, aby vykreslil obsah v poslední možné chvíli. Díky tomu se okenní systémy vyhýbají počítání zbytečných aktualizací obsahu displejeLazy and Speculative Execution Butler Lampson Microsoft Research OPODIS, Bordeaux, Francie 12. prosince 2006.
Další příkladem odloženého vyhodnocování v moderních počítačových systémech je přidělování stránek využívající přístup copy-on-write nebo stránkování na žádost, kdy několik procesů může sdílet kopii téže stránky, a samostatná stránka je jim přidělena, až v okamžiku, kdy se jeden z procesů pokusí obsah paměti změnit.
Odložené vyhodnocování tak může být výhodné pro systémy s vysokými požadavky na výkon. Příkladem může být unixová funkce mmap, který poskytuje načtení stránky z disku na žádost, takže do paměti budou zavedeny pouze ty stránky, které se skutečně používají, a nebude přidělována žádná nepotřebná paměť.
MATLAB implementuje kopírování při změně, kdy se při kopírování pole vytváří jeho kopie, až když je změněn jeho obsah, což může vést k chybě vyčerpání paměti až při aktualizaci prvku, a ne při kopírování pole.
Implementace Některé programovací jazyky odkládají vyhodnocování výrazů implicitně; některé další jazyky poskytují funkce nebo speciální syntaxi pro odložené vyhodnocování. V programovacích jazycích Miranda a Haskell je vyhodnocování argumentů funkce odložené implicitně. V mnoha jiných jazycích lze vyžádat odložené vyhodnocování explicitně dočasným pozastavením výpočtu pomocí speciální syntaxe (jako „delay“ a „force“ v jazyce Scheme nebo „lazy“ a „Lazy.force“ v OCaml) nebo obecněji obalením výrazu pomocí konstrukce nazývané thunk. Objekt reprezentující takové explicitně odložené vyhodnocování se nazývá lazy future. Perl 6 používá odložené vyhodnocování seznamů, takže je možné přiřazovat nekonečné seznamy do proměnných a používat je jako argumenty funkcí, ale na rozdíl od Haskellu a Mirandy, Perl 6 implicitně nepoužívá odložené vyhodnocování aritmetických operátorů a funkcí.
Lenost a dychtivost
Řízení vyhodnocování v jazycích s odloženým vyhodnocováním V líných programovacích jazycích jako je například Haskell je implicitní vyhodnocování výrazů pouze, když je požadována jejich hodnota. Ale v některých případech je možné vytvořit dychtivější kód — nebo opačně, přepnout na línější vyhodnocování poté co bylo použito vyhodnocování dychtivější. Lze to provést explicitním kódováním něčeho, co vynutí vyhodnocování (což může učinit kód dychtivějším), nebo i nepoužitím takového kódu (což může učinit kód línějším). Striktní vyhodnocování obvykle naznačuje dychtivost, ale technicky to jsou různé koncepty.
V některých překladačích jsou dostupné optimalizace nazývané analýza striktnosti, které v některých případech, umožňuje překladači předpokládat, že hodnota bude použita. V takových případech může být volba programátora, zda vynutit vyhodnocení určité hodnoty, irrelevantní, protože analýza striktnosti vynutí striktní vyhodnocování.
V jazyce Haskell označení polí konstruktoru slovem strict znamená, že jejich hodnoty budou vždy vyžádané okamžitě. Pro okamžité vyžádané hodnoty lze také použít funkci seq, a pak ji předat dále, což je užitečné, pokud se má nějaká položka konstruktoru vyhodnocovat odloženě. Žádná z těchto technik však neimplementuje rekurzivní striktnost; k tomuto účelu byla navržena funkce deepSeq.
Také vyhledávání vzorků v Haskell 98 je implicitně striktní, takže se musí použít kvalifikátor ~, aby se provádělo odloženě.
Simulace odloženého vyhodnocování v dychtivých jazycích
Python V jazyce Python 2.x funkce range() počítá seznam celých čísel. Při prvním vyčíslení přiřazovacího příkazu bude celý seznam uložen do paměti, což je příkladem dychtivého nebo bezprostředního vyhodnocování: >>> r = range(10) >>> print r [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> print r 3
V Pythonu 3.x funkce range() vrátí speciální objektový rozsah, který počítá prvky seznamu podle potřeby. Prvky rozsahu se generují, až když jsou potřebné (například, když print(r) je vyčíslen v následujícím příkladu), tak toto je příkladem líného nebo odloženého vyhodnocování:
>>> r = range(10) >>> print(r) range(0, 10) >>> print(r) 3 Přechod na odložené vyhodnocování šetří čas běhu pro velké rozsahy, které nemohou být nikdy plně referencovány, i paměť pro velké rozsahy, z nichž je v každém okamžiku potřebný jen jeden nebo několik málo prvků.
V Pythonu 2.x byla zavedena funkce xrange(), která vrací objekt generující čísla v rozsahu podle potřeby. Výhodou xrange je, že generovaný objekt vždy bude zabírat stejné množství paměti.
>>> r = xrange(10) >>> print(r) xrange(10) >>> lst = [x pro x v r] >>> print(lst) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]