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
Zavolání programuKód: Vybrat vše
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
Program.exe sample.in
Výstup
Testovací vstupyKód: Vybrat vše
sample.in: 47 47 16 16 6
basic.in
combined.in
catches.in
Výstup
Kód: Vybrat vše
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|
Zkouška 15.1.2019 - "Všechno je funkce"
-
- Matfyz(ák|ačka) level I
- Příspěvky: 12
- Registrován: 30. 1. 2018 15:28
- Typ studia: Informatika Mgr.
Zkouška 15.1.2019 - "Všechno je funkce"
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.
- Přílohy
-
- basic.in.txt
- (119 bajtů) Staženo 229 x
-
- combined.in.txt
- (522 bajtů) Staženo 239 x
-
- catches.in.txt
- (475 bajtů) Staženo 236 x
-
- Matfyz(ák|ačka) level I
- Příspěvky: 12
- Registrován: 30. 1. 2018 15:28
- Typ studia: Informatika Mgr.
Re: Zkouška 15.1.2019 - "Všechno je funkce"
Ještě přidám svoje řešení: https://gist.github.com/Mnaukal/49be0f2 ... 0bd2db1296 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í.
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í.