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 N, 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 ~> Q (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 M. Pokud ani ten nelze, znamená to, že M 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.1)

  • 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 M 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.2)

  • 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.3)

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 M 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.4)

  • 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.5)

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

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

Předměty

Použitá literatura

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.

1) , 2) miniskripta, kapitola 3, strana 12
3) 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.
4) miniskripta, kapitola 3, strana 13
5) ministkripta, kapitola 8, strana 36
6) ministkripta, kapitola 8, strana 37
7) miniskripta, kapitola 8, strana 36

Diskuze

, 2008/06/04 22:06

»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.

je to pravda? ja si myslim, ze se vyhodnoti prvni dvakrat a druhy jednou. Do prvniho x se musi dosadit. tj nejprve overime toto ( ( not False ) || ( not True ) ). Po tomto ale jste nevime, jakou bude mit celkovy vyraz hodnotu, proto musime udelat jetse ( not False ) && ( ( not False ) || ( not True ) ). Nebo se pletu?

, 2008/06/05 00:16

Já si myslím, že je to pravda.
Když si přečteš definici tak ta říká: když máš M N1…Nn tj.

                                             eat  (not False) (not True), tak první redukuješ výraz not True, pak redukuješ not False ,zůstane ti eat True False, z toho již nic redukovat nejde -> že eat je funkce a narhadíš ji pravou stranou definice funkce eat a za její parametry x dosadíš True a za y False. 
, 2008/06/05 00:17

Jaj, nevím, proč se mi ta odpověď tak divně zobrazila. snad se v tom vyznáš.

, 2008/06/05 16:44

Jj, vyznám dík. Teď jak jsi to napsal, tak je to jasné. Ani nechápu, jak jsem se k tomu mému číslu dobral….:( Ještě jednou díkes.

, 2008/06/04 22:23

jo, a u tech jednicek (ones) je jedno, zda jde o normalni ci line vyhodnocovani. Vzdy se to vyhodnoti. Jen u striktniho se zacyklim. Chapu spravne?
Dekuju

, 2008/06/05 00:45

pokud myslíš čistě ones, ne tu s tou funkcí take 2, tak to cyklí pořád, ať použiješ jakoukoli redukční strategii.

, 2008/06/05 16:43

myslím samozřejmě tu s tou take 2 ones. Sorry, jsem se spatne vyjadril

, 2008/06/16 15:53

Docela mi tu chybí ta první část otázky - pořadí vyhodnocování. Způsob redukce totiž přímo navazuje na pořadí vyhodnocování(() je před *, * je před + atd..) a bez toho se těžko vyřeší složitější příklady… Pěkně to tuším bylo v těch skriptech co byly psané rukou, zkusím je někde najít, pokud to někdo znáte, tak to sem prosím napište.

, 2008/06/18 15:29

hint –- slajd z prvnich nebo druhych cvik, ale bohuzel nemam cas jej hledat

, 2008/06/18 20:33

este stastie ze som ten slajd mal zalozeny v skriptach :)

, 2008/06/21 18:45

Doplnil jsem k normálnímu vyhodnocování informaci o efektu tzv. zkráceného vyhodnocování, protože by z toho jinak nemuselo být hned jasné, proč se druhý argument funkce eat nevyhodnotí ani jednou. Doufám, že jsem ten důvod toho správně pochopil.

, 2009/06/15 01:05

opravil jsem směr vyhodnocování logické konjunkce a disjunkce, ← to určitě být nemá (viz poznámka 3). u multiplikativních operátorů mám taky pochybnosti, proč je to ←, ale tuším, že třeba prolog to tak má, haskell jsem nikde nedohledal…

, 2009/06/23 11:57

přidána sekce Co byste ještě měli znát?

, 2009/06/23 12:16

V sekci s línou redukční strategií je možné pracovat s nekonečnými datovými strukturami. Neplatí to ale i pro normální red. strategii?

, 2009/06/23 12:31

To by me taky zajimalo…

, 2009/06/23 16:11

Platí. Líná redukční strategie je ale ovšem oproti normální někdy efektivnější, protože použivá mezivýsledky.

, 2010/01/11 11:23

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

jak to souvisí?:)

, 2010/01/20 21:09

Tipuji, že člověk, který to napsal, měl na mysli, že tabulka priorit operátorů určuje pořadí vyhodnocování.

You could leave a comment if you were logged in.
home/inf/ap7.txt · Poslední úprava: 2014/10/27 09:07 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0