====== 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.((miniskripta, kapitola 3, strana 12)) * 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.((miniskripta, kapitola 3, strana 12)) * 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.((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.)) ==== 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.((miniskripta, kapitola 3, strana 13)) * 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.((ministkripta, kapitola 8, strana 36)) Užitečnými funkcemi pro vytváření nekonečných seznamů jsou **repeat**, **cycle** a **iterate**((ministkripta, kapitola 8, strana 37)) 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 :: [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 :: (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 === [0..] Zápis označuje nekonečný seznam **[0, 1, 2, 3...]** 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..]] [ [x^n | x <- [0..]] | n <- [0..] ] 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]**((miniskripta, kapitola 8, strana 36)) ====== Předměty ====== * [[https://is.muni.cz/auth/predmety/predmet.pl?kod=IB015;fakulta=1433;obdobi=|FI:IB015]] Úvod do funkcionálního programování (jaro), [[https://is.muni.cz/auth/lide/?searchid=%C5%A1karvada&Hledat=Hledat&zpet=.%2F&zpet_text=Zp%C4%9Bt+na+hled%C3%A1n%C3%AD+osob|RNDr. Libor Škarvada]] ====== Použitá literatura ====== * RNDr. Libor Škarvada, [[http://www.fi.muni.cz/%7Elibor/vyuka/IB015/cviceni/index.html|Cvičení k předmětu]] * RNDr. Libor Škarvada, [[http://www.fi.muni.cz/%7Elibor/vyuka/IB015/zapisky.pdf|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** [[http://www.haskell.org/hugs/|Hugs]]. Nebo třeba trošku populárněji psaný seriál o funkcionálním programování na [[http://programujte.com/index.php?rubrika=26-programovani&sekce=165-funkcionalni-programovani&kategorie=166-serial-funkc-progr-|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. ~~DISCUSSION~~