Obsah

AP7, IN7 Vyhodnocování výrazů
Předměty
Použitá literatura
Kam dál
Co byste ještě měli znát?
Vypracoval
Diskuze

AP7, IN7 Vyhodnocování výrazů

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

Pořadí vyhodnocování

Směr	Priorita	Operátor	Popis
←	9	.	skládání funkcí
→	9	!!	indexování prvku seznamu
←	8	^	umocňování
→	7	* / 'div' 'mod'	multiplikativní aritmetické operátory
→	6	+ -	aditivní aritmetické operátory
←	5	: ++	přidání prvku, spojení seznamů
-	4	== /= < <= > >= 'elem' 'notElem'	relační operátory
←	3	&&	logická konjunkce
←	2	\|\|	logická disjunkce

Redukční krok

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

Mějme funkci
$f x_{1} ... x_{n} = N$ A výraz tvaru
$f M_{1} ... M_{n}$

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ě $x_{i}$ nahradí odpovídajícím výrazem $M_{i}$ . 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).

Redukční strategie

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

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

Při striktní redukční strategii postupujeme zevnitř.
Při použití striktní redukční strategie vyhodnocujeme argumenty funkcí právě jednou.
Striktní redukční strategii se zejména v imperativních jazycích říká volání hodnotou.
Striktní redukční strategie se používá v jazycích, které nejsou čistě funkcionální, je výhodnější v menší spotřebě paměti při vyhodnocování. V jazycích s vedlejšími efekty by bylo líné vyhodnocování nepřehledné – to je další důvod, kdy je vhodné používat striktní redukční strategii.

Příklady

Mějme funkci sq definovanou:

sq x = x * x

Výraz sq(sq 3) se při použití striktní redukční strategie bude vyhodnocovat:

sq (sq 3) ~> sq (3 * 3) ~> sq 9 ~> 9 * 9 ~> 81

Mějme funkce f, const definované předpisy:

f x = f x 
const x y = x

Ve výrazu const 3 (f 1) se bude podvýraz f 1 při použití striktní redukční strategie vyhodnocovat nekonečně dlouho, tedy výpočet se zacyklí a k výsledku nedojdeme nikdy:

const 3 (f 1) ~> const 3 (f 1) ~> const 3 (f 1) ~> ...

Mějme funkci eat definovanou :

eat x y = x && (x || y)

Redukujeme-li výraz eat (not False) (not True) striktně, vyhodnotí se každý z argumentů jednou.

Normální redukční strategie

Normální redukční strategie je taková, při které aplikaci $M N_{1} ... N_{n}$ 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 $M N_{1} ... N_{n}$ nahradíme pravou stranou její definice s dosazením výrazů $N_{i}$ za její parametry.²⁾

Pokud je možné výraz M redukovat nějakou redukční strategií na výslednou hodnotu, dospějeme k ní použitím normální redukční strategie po konečném počtu kroků – tedy normální redukční strategie je efektivně normalizující, výpočet se nezacyklí, pokud nemusí.
Při normální strategii postupujeme z vnějšku.
Normální redukční strategie nemusí vést k nejkratšímu výpočtu.
Normální redukční strategie bývá nazývána zejména v imperativních jazycích volání jménem.
Při normální redukční strategii vyhodnocujeme argumenty tolikrát, kolikrát na to při výpočtu dojde.

Příklady

Mějme funkci:

sq x = x * x

Výraz sq(sq 3) se při použití normální redukční strategie bude vyhodnocovat:

sq (sq 3) ~> sq 3 * sq 3 ~> (3 * 3) * sq 3 ~> 9 * sq 3 ~> 9 * (3 * 3) ~> 9 * 9 ~> 81

Mějme funkce f, const definované předpisy:

f x = f x 
const x y = x

Výraz const 3 (f 1) se při použití normální redukční strategie bude vyhodnocovat:

const 3 (f 1) ~> 3

Mějme funkci eat definovanou :

eat x y = x && (x || y)

Redukujeme li výraz eat ( not False) ( not True) normálně, vyhodnotí se první argument dvakrát a druhý se nevyhodnotí ani jednou.³⁾

Líná redukční strategie

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 $M N_{1} ... N_{n}$ 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 $M N_{1} ... N_{n}$ nahradíme pravou stranou její definice s dosazením výrazů $N_{i}$ 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.⁴⁾

Platí obdobné tvrzení jako u normální strategie, pokud má výraz nějakou výslednou formu, dospěje se k ní po konečném počtu kroků líné redukční strategie.
Při líné redukční strategii vyhodnocujeme každý argument nejvýše jedenkrát.
Díky líné redukční strategii je možné pracovat i s nekonečnými datovými strukturami.

Příklady

Mějme funkci eat definovanou:

eat x y = x && (x || y)

Redukujeme li výraz eat (not False) (not True) líně, vyhodnotí se první argument jednou a druhý ani jednou.

Efektivita

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ů).

Nekonečné datové struktury

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

repeat :: a → [a]

repeat x = s where s = x : s

funkce repeat vytváří seznam, do kterého do nekonečna přidává prvek z argumentu x.

cycle

cycle :: [a] → [a]

cycle t = s where s = t ++ s

funkce cycle vytváří seznam, do kterého do nekonečna připojuje seznam z argumentu t.

iterate

iterate :: (a → a) → a → [a]

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

funkce iterate vytváří z funkce f a prvku x seznam:

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

V líných jazycích můžeme pracovat s nekonečnými seznamy. Konstruktor (:) nevyhodnocuje své argumenty, když nemusí. Proto se při výpočtu vyhodnotí z nekonečného seznamu vždy jen tolik, kolik je potřeba.

Příklady nekonečných datových struktur

Seznam všech čísel od 0 do nekonečna

[0..]
Zápis označuje nekonečný seznam [0, 1, 2, 3…]

Seznam všech druhých mocnin

Je možné vyjádřit například pomocí funkce map, která aplikuje zadanou funkci na prvky zadaného seznamu:

map square [0..]

Případně také intenzionálním zápisem:

[x^2 | x <- [0..]]

Nekonečný seznam seznamů čísel reprezentující tabulku všech mocnin

[ [x^n | x ← [0..]] | n ← [0..] ]

Seznam Fibonacciho čísel

Definován rekurzivně pomocí funkce zipWith

fib = 1 : 1 : zipWith (+) fib (tail fib)

Funkce zipWith aplikuje zadanou operaci na odpovídající prvky dvou zadaných seznamů a z výsledků těchto aplikací vytvoří seznam.

Například zipWith (*) [1, 2, 3] [1, 4, 9] *~> [1, 8, 27]⁷⁾

Předměty

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

Použitá literatura

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

Kam dál

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.

Co byste ještě měli znát?

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

Vypracoval

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.

¹⁾ , ²⁾

miniskripta, kapitola 3, strana 12

³⁾

Počítá se s tzv. zkráceným vyhodnocováním u operátoru ||, součástí jehož definice je následující předpis: True || _ = True … proto se druhý argument nevyhodnotí ani jednou.

⁴⁾

miniskripta, kapitola 3, strana 13

⁵⁾

ministkripta, kapitola 8, strana 36

⁶⁾

ministkripta, kapitola 8, strana 37

⁷⁾

miniskripta, kapitola 8, strana 36