Odložené vyhodnocování

Odložené vyhodnocování (anglicky lazy evaluation nebo call-by-need, č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.

Opakem odloženého vyhodnocování je okamžité (striktní, hladové, dychtivé) vyhodnocování (anglicky eager evaluation), 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 displeje.

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]
 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[3]) 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])
 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]

V Pythonu od verze 2.2 se dosáhne odloženého vyhodnocování pomocí iterátoru, zatímco n-tice nebo seznamová posloupnost se vyhodnocuje okamžitě. Například (Python 2):

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

Tento příklad ukazuje, že seznamy se vyčíslují už při svém volání, zatímco v případě iterátoru se jednotlivé prvky zpřístupňují až v případě potřeby.

.NET Framework

.NET Framework umožňuje provádět odložené vyhodnocování pomocí třídy System.Lazy<T>. Tuto třídu lze snadno využívat v F# pomocí klíčového slova lazy, zatímco metoda force vynutí vyhodnocování. Existují také specializované kolekce jako Microsoft.FSharp.Collections.Seq, které poskytují vestavěnou podporu pro odložené vyhodnocování.

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

V jazycích C# a VB.NET lze přímo použít třídu System.Lazy<T>.

public int Sum()
{
    int a = 0;
    int b = 0; 
    Lazy<int> x = new Lazy<int>(() => + b);
    a = 3;
    b = 5;
    return x.Value; // vrátí 8
}

Praktičtější příklad:

// rekurzivní výpočet n-tého Fibonacciho číslo
public int Fib(int n)
{
   return (n == 1)? 1 : (n == 2)? 1 : Fib(n-1) + Fib(n-2);
}

public void Main()
{
    Console.WriteLine("Které Fibonacciho číslo chcete vypočítat?");
    int n = Int32.Parse(Console.ReadLine()); 
    Lazy<int> fib = new Lazy<int>(() => Fib(n)); // funkce je připravena, ale není provedena
    bool execute; 
    if (n > 100)
    {
        Console.WriteLine("Výpočet může trvat dlouho. Skutečně chcete vypočítat tak velké číslo? [y/n]");
        execute = (Console.ReadLine() == "y"); 
    }
    else execute = false;
    
    if (execute) Console.WriteLine(fib.Value); // hodnota se vypočítá, až když je potřeba
}

Další možností je použít klíčové slovo yield:

// dychtivé vyhodnocování
public IEnumerable<int> Fibonacci(int x)
{
    IList<int> fibs = new List<int>();

    int prev = -1;
    int další = 1;
    pro (int i = 0; i < x; i++)
    {
        int součet = prev + další;
        prev = další;
        další = sum;
        fibs.Add(sum); 
    }
    return fibs;
}

// odložené vyhodnocování
public IEnumerable<int> LazyFibonacci(int x)
{
    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++)
    {
        int sum = prev + next;
        prev = next;
        next = sum;
        yield return sum;
    }
}

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Lazy evaluation na anglické Wikipedii.

Související články

• Kombinatorická logika
• Currying
• Dataflow
• Dychtivé vyhodnocování
• Funkcionální programování
• Futures a promises
• Generátor (programování)
• Redukce grafu
• Inkrementální počítání – příbuzný koncept, při kterém se výpočty opakují, pouze pokud se jejich vstupy změní. Může být kombinované s odloženým vyhodnocováním.
• Lambda kalkul
• Odložená inicializace
• Look-ahead
• Nestriktní programovací jazyk
• Normální pořadí vyhodnocování
• Zkrácené vyhodnocování (minimální)

Literatura

• HUDAK, Paul. Conception, Evolution, and Application of Functional Programming Languages. ACM Computing Surveys. Září 1989. Dostupné online. DOI 10.1145/72551.72554. 
• REYNOLDS, John C., 1998. Teorie programovací jazyky. [s.l.]: Cambridge University Press. Dostupné online. ISBN 9780521594141. 
• WADSWORTH, Christopher P., 1971. Semantics and Pragmatics of the Lambda Calculus. [s.l.]: [s.n.].  PhD thesis, Oxford University
• HENDERSON, Peter; MORRIS, James H. A Lazy Evaluator. Conference Record of the Third ACM symposium on Principles of Programming Language. Leden 1976. Dostupné online. 
• FRIEDMAN, D. P.; WISE, David S., 1976. Cons should not evaluate its arguments. Automata Languages and Programming Third International Colloquium. Edinburgh University Press. Dostupné online. 
• LAUNCHBURY, John, 1993. A Natural Semantics for Lazy Evaluation. Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '93). Dostupné online. DOI 10.1145/158511.158618. 

Návrhové vzory

• John Hughes. "Why functional programming matters". The Computer Journal - Special issue on lazy functional programming. ročník 32 číslo 2, duben 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"^{[nedostupný zdroj]}. Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science, 1985, Volume 201/1985, 113-128.

Odložené vyhodnocování ve striktních jazycích

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

Příspěvky matematických informatiků na blozích

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

Externí odkazy

• Lazy Evaluation na Portland Pattern Repository
• Lazy evaluation na Haskell Wiki
• The Incomplete Guide to Lazy Evaluation (in Haskell) – Série tutoriálů o odloženém vyhodnocování v jazyce Haskell: jak odložené vyhodnocování funguje, jak pomáhá při zlepšování modularity kódu, a další.
• Functional programming in Python becomes lazy
• Lazy function argument evaluation v jazyce D
• Lazy evaluation macros v Nemerle
• Lambda calculus in Boost Libraries Archivováno 10. 6. 2009 na Wayback Machine. v jazyce C++
• Lazy Evaluation v ANSI C++ psaním kódu stylem, který používá třídy pro implementaci funkčních closur.
• Lazy Evaluation v jazyce Perl