(pořadí vyhodnocování, striktní a normální redukce, líná redukce, efektivita, nekonečné datové struktury, definice funkcí nad nekonečnými strukturami)

Výrazy se skládají z aplikací funkcí a operátorů na argumenty a z lokálních definic.

Mějme funkci
A výraz tvaru

Redukční krok je úprava výrazu, při které se některý z jeho podvýrazů nahradí pravou stranou definice funkce, tedy výrazem , v němž se každý výskyt proměnně nahradí odpovídajícím výrazem . Redukčním krokem nazýváme i takové transformace, při kterých v jeho podvýrazu vyčíslíme jednoduchou operaci aplikovanou na jednoduché argumenty (ať už operaci aritmetickou či logickou).

Redukční krok vlastně znamená jeden krok zjednodušení výrazu, často se značí ~> (P se redukuje na Q).

Výrazy můžeme vyhodnocovat obecně mnoha způsoby, způsob vyhodnocování je určen redukční strategií. Redukční strategie je pravidlo, které pro každý výraz jednoznačně určuje první redukční krok. Tedy redukční strategie určuje, který podvýraz se bude redukovat jako první.

Volba redukční strategie může ovlivnit, zda vůbec dospějeme k výsledku. Nemůže se však stát, abychom dvěma různými strategiemi dospěli k různým výsledkům.

Striktní redukční strategie je taková strategie, při které vyhodnocujeme nejdříve argumenty, tedy aplikaci upravujeme tak, že nejdříve, pokud to jde, redukujeme podvýraz použitím striktní strategie. Pokud nelze, redukujeme striktně , pokud také nelze tak a tak dále. Pokud nelze redukovat žádný z podvýrazů , tak redukujeme striktní strategií podvýraz . Pokud ani ten nelze, znamená to, že již nelze zjednodušit a celý výraz nahradíme pravou stranou jeho definice s dosazením hodnot výrazů za její parametry.¹⁾

Normální redukční strategie je taková, při které aplikaci upravujeme tak, že nejdříve redukujeme (pokud to jde) podvýraz použitím normální strategie, pokud to nejde, znamená to že M již nelze zjednodušit a celý výraz nahradíme pravou stranou její definice s dosazením výrazů za její parametry.²⁾

Jedná se o modifikovanou verzi normální redukční strategie, využívající faktu, že funkcionální jazyky jsou referenčně transparentní, tedy že jakýkoli výraz se ve stejném prostředí vyhodnotí vždy stejně, vyhýbá se tak opakovanému vyhodnocování stejných podvýrazů.
Líná redukční strategie je taková, při které aplikaci upravujeme tak, že nejdříve redukujeme, pokud to jde, podvýraz M použitím líné strategie. Když M redukovat nelze, znamená to, že M je funkce a celý výraz nahradíme pravou stranou její definice s dosazením výrazů za její parametry stejně jako u normální redukční strategie. Nyní si však při každém násobném dosazení zapamatujeme, které podvýrazy vzniklé dosazením za různé výskyty téže proměnné jsou stejné, a při jejich případném dalším vyhodnocování je redukujeme jen jednou, jakoby všechny naráz.⁴⁾

Striktní vyhodnocování bývá často v porovnání s normálním vyhodnocováním časově efektivnější, protože argumenty jsou vyhodnocovány jen jednou, zatímco v normálním vyhodnocování jsou argumenty vyhodnocovány tolikrát, kolikrát na to při výpočtu dojde.
Líné vyhodnocování je časově efektivní, protože se v něm každý argument vyhodnotí nejvýše jedenkrát (díky referenční transparentnosti funkcionálních jazyků).

Líné vyhodnocování nám umožňuje pracovat s funkcemi, které jsou definovány na nedefinovaných argumentech. Například máme-li funkci:

const x y = x 

Pak výraz const 1 (1 / 0) má dobře definovanou hodnotu 1, přestože hodnota podvýrazu (1 / 0) není definována. Tato nedefinovanost nevadí, protože podvýraz se vůbec nevyhodnotí. Nedefinovaná hodnota nemusí být způsobena jen dělením nulou, ale obvykle se považuje za význam cyklícího výpočtu.

Užitečným příkladem nedefinovaných podvýrazů jsou nekonečné datové struktury, zejména seznamy. Například předpis:

ones = 1 : ones 

definuje nekonečný seznam samých jedniček. Vyhodnocení výrazu ones se zacyklí a při každém kroku vytváří delší a delší seznam jedniček.

ones ~> 1 : ones ~> 1 : 1 : ones ~> 1 : 1 : 1 : ones ~> ... 

Avšak vyhodnocení výrazu take 2 ones probíhá díky línému vyhodnocování konstruktoru (:) takto

take 2 ones ~>  
1 : take (2 - 1) ones ~>  
1 : take 1 ones ~>  
1 : 1 : take (1 - 1) ones ~>  
1 : 1 : take 0 ones ~>  
1 : 1 : [] = [1, 1] 

Toto vyhodnocení interpretujeme jako extrakci dvouprvkového seznamu ze začátku nekonečného seznamu složeného ze samých jedniček.⁵⁾

Užitečnými funkcemi pro vytváření nekonečných seznamů jsou repeat, cycle a iterate⁶⁾

repeat x = s where s = x : s 

cycle t = s where s = t ++ s 

iterate f x = x : iterate f (f x) 

[x, f x, f (f x), f (f (f x))...] 

• FI:IB015 Úvod do funkcionálního programování (jaro), RNDr. Libor Škarvada

• RNDr. Libor Škarvada, Cvičení k předmětu
• RNDr. Libor Škarvada, Miniskripta -- zápisky z přednášek

Vhodné doplnění studia může být vyzkoušení příkladů ze cvičení prakticky v interpretu Haskellu Hugs.
Nebo třeba trošku populárněji psaný seriál o funkcionálním programování na Programujte.com.

Měli byste vědět, jak souvisí tabulka priorit operátorů s redukční strategií.

Winsik - ICQ: 215787520 mail: winsik.cz(zavinac)gmail.com

Otázku jsem připravil podle sebe a jsem si vědom toho, že někomu může něco chybět, nebo že se někomu nebude líbit struktura nebo grafické zpracování. Proto pokud chcete, můžete samozřejmě sami otázku upravit, doplnit co podle vás chybí, kontaktovat mne, a třeba připomínku vyjádřit v diskuzi, budu jen rád.

Otázku si přečetl pan RNDr. Libor Škarvada a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen rámcová, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.