# Zkouška 15.1.2019 - "Všechno je funkce"

<{ForumPost(poster="mnaukal", timestamp=2019-01-15 17:25:56)}>
Zadával Robert Husák a sám říkal, že zadání nejspíš bylo těžší než obvykle. Většina lidí ho nestihla odevzdat v časovém limitu 4 hodin, nicméně i za částečné řešení může člověk dostat nějaké body.

 > **Hlavní myšlenka**  
 >   
 > Cílem úlohy je vytvořit interpreter jednoduchého funkcionálního jazyka. Pro naši potřebu si funkci můžeme představit jako objekt, kterému můžeme předat jiné funkce jako argumenty a on nám vrátí novou funkci jako výsledek. Celočíselná konstanta je pak speciálním případem funkce bez argumentů. V úloze budeme pracovat se dvěma typy funkcí:  
 >   
 >     Základní funkce pracují přímo s číselnými konstantami typu *int*:  
 >         *add(x, y) := x + y  
 >         sub(x, y) := x - y  
 >         mul(x, y) := x * y  
 >         div(x, y) := x / y*  
 >   
 >     Funkce vyššího řádu dostanou jako argumenty jiné funkce a vracejí novou funkci z nich vytvořenou (notace *(arg1, ..., argn) → expr* značí novou bezejmennou funkci):  
 >         *bind1(f, x) := (y) → f(x, y)  
 >         bind2(f, y) := (x) → f(x, y)  
 >         dupl(f) := (x) → f(x, x)  
 >         join(f, g) := (x, y) → f(g (x, y))*  
 >   
 >     Příklady použití pro složení nových funkcí:  
 >         Unární minus: *bind1(sub, 0) = (x) → (0 - x)*  
 >         Polovina: *bind2(div, 2) = (x) → (x / 2)*  
 >         Druhá mocnina: *dupl(mul) = (x) → (x * x)*  
 >         Průměr: *join(bind2(div, 2), add) = (x, y) → (x + y) / 2*  
 >   
 > Samotná interpretace spočívá v postupné aplikaci těchto funkcí vzájemně na sebe i na číselné konstanty. V každém kroku budete buď výsledek ukládat do proměnné, nebo jej vypíšete na výstup.  
 >   
 > Interpreter má v sobě tabulku proměnných, která mapuje každou proměnnou z jejího názvu na funkci, která do ní byla naposledy přiřazena. Před interpretací dané sekvence příkazů jsou v tabulce těmto jménům přiřazeny příslušné funkce (viz výše): *add, sub, mul, div, bind1, bind2, dupl, join*. Přiřazením do proměnné nasměrujete (příp. přesměrujete) její jméno v tabulce na nově vytvořenou funkci.  
 >   
 > **Vstup**  
 >   
 > Argumenty programu  
 >   
 > Program je možné volat s libovolným počtem argumentů. Pokud není zadán žádný argument, načtěte příkazy ze standardního vstupu. V opačném případě zpracujte příkazy ze souborů, jejichž cesty byly zadány jako argumenty. Interpretace každého souboru musí začínat s čistým stavem, tj. proměnné přiřazené v jednom souboru se nepřenášejí do dalšího.  
 >   
 > Formát souboru s příkazy  
 >   
 > Každý příkaz se nachází na samostatném řádku. Prázdné řádky a řádky, které obsahují jen bílé znaky, ignorujte. Existují dva možné příkazy:  
 >   
 >     **Přiřazení**: formát je následující:  
 >   
 >     *let \[promenna] = \[fce] \[arg1] \[arg2] ... \[argn]*  
 >   
 >     Vyhodnoťte funkci \[fce] se zadanými argumenty *\[arg1], \[arg2], ..., \[argn]* a výslednou funkci zapište do proměnné \[promenna].  
 >   
 >     **Vyhodnocení a výpis:**  
 >   
 >     *\[fce] \[arg1] \[arg2] ... \[argn]*  
 >   
 >     Vyhodnoťte funkci \[fce] se zadanými argumenty *\[arg1], \[arg2], ..., \[argn]* a výsledek vypište na standardní výstup. Formát je následující:  
 >         Pokud je výsledná funkce celočíselná konstanta, vypište její hodnotu.  
 >         V opačném případě vypište řetězec *fun(n)*, kde *n* je počet argumentů.  
 >   
 > Jednotlivé tokeny v příkazech mohou být oddělené libovolným počtem bílých znaků. Zjištění hodnot funkce \[fce] a argumentů \[arg1], ..., \[argn] probíhá následovně:  
 >   
 >     Pokud token obsahuje jen číslice a na začátku volitelně znak '-', jedná se o číselnou konstantu.  
 >     V opačném případě se jedná o funkci, kterou vyhledáte v aktuální tabulce proměnných. Pokud se tam nenachází, vypište chybu |Unknown function| (včetně svislítek).  
 >   
 > Nezapomeňte, že číselná konstanta je také speciálním případem funkce, která neočekává žádné argumenty a vrací sebe sama. Takže například pro vstup  
 >   
 > *let val = 42  
 > val  
 > -43*  
 >   
 > Bude výstup *42 -43*.  
 >   
 > V případě nesprávné syntaxe příkazu přiřazení vypište chybu |Syntax error| (včetně svislítek). Pokud je funkce volaná s nesprávným počtem argumentů (i kdekoliv v zanoření), vypište chybu |Invalid argument count|. Při dělení nulou vypište chybu |Division by zero|. Při libovolné z chyb příkaz ignorujte a pokračujte dalším.  
 >   
 > **Výstup**  
 >   
 > Před interpretací každého zadaného souboru vypište na první řádek jeho cestu s dvojtečkou na konci (při načítání příkazů ze standardního vstupu tento řádek nevypisujte). Následující řádek bude obsahovat všechny výstupy z příkazů v souboru oddělené mezerami (za posledním výstupem může být mezera také), poté bude následovat prázdný řádek.  
 >   
 > **Příklad**  
 >   
 > sample.in  
 > 
 > 
 > 
 > 
 > 
 >     add 42 5
 >     let var = add 42 5
 >     var
 >     
 >     let square = dupl mul
 >     square 4
 >     
 >     let squareDist = join square sub
 >     squareDist 5 9
 >     
 >     let mul2 = bind1 mul 2
 >     mul2 3
 > 
 > 
 > 
 > 
 > Zavolání programu  
 >   
 > *Program.exe sample.in*  
 >   
 > Výstup  
 > 
 > 
 > 
 > 
 > 
 >     sample.in:
 >     47 47 16 16 6
 > 
 > 
 > 
 > 
 > **Testovací vstupy**  
 >   
 >  *basic.in  
 >     combined.in  
 >     catches.in*  
 >   
 > Výstup  
 > 
 > 
 > 
 > 
 > 
 >     basic.in:
 >     1 2 3 4 5 6 7
 >     
 >     combined.in:
 >     fun(1) 2 fun(1) 3 fun(1) 4 fun(2) 5 16 fun(2) 8 fun(1) fun(2) 8 8
 >     
 >     catches.in:
 >     1 |Invalid argument count| |Unknown function| |Unknown function| |Unknown function| |Invalid argument count| |Invalid argument count| |Invalid argument count| |Syntax error| |Syntax error| 2 3 |Division by zero| fun(1) 4 5 |Division by zero|


*Attachments:*

- *[combined.in.txt](/Forum%20archiv/Attachments/7137_306676b6a9d21306cb01e40a98fcece9)*
- *[catches.in.txt](/Forum%20archiv/Attachments/7137_a50374a4891581d63de074e469e83fb1)*
- *[basic.in.txt](/Forum%20archiv/Attachments/7137_f51a24ffe2f17ef1d24c516bda4e8772)*

<{/ForumPost}>

<{ForumPost(poster="mnaukal", timestamp=2019-01-15 17:37:25)}>
Ještě přidám svoje řešení: [https://gist.github.com/Mnaukal/49be0f2 ... 0bd2db1296](https://gist.github.com/Mnaukal/49be0f286899568d88c6410bd2db1296) Nemyslím si o něm, že je nějak ideální a šlo to udělat o něco jednodušeji, ale funkční je a na splnění zkoušky stačilo.  
  
Vzorové řešení bylo také založené na polymorfismu a třídách pro jednotlivé typy funkcí. Ale mělo třeba jednodušeji vyřešené předávání parametrů do funkcí, které bylo udělané předáním vectoru funkcí.
<{/ForumPost}>