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

Základní kurs objektově orientovaného programování v C++. Třídy a objekty, zapouzdření, metody, plymorfismus. Abstraktní datové typy, přetěžování. Kontejnery, iterátory, algoritmy. Šablony, generické programování, kompilační polymorfismus. Výjimky. Bezpečné a přenositelné programování, vazby na OS.
mnaukal
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"

Příspěvek od mnaukal »

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

Kó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
Zavolání programu

Program.exe sample.in

Výstup

Kód: Vybrat vše

sample.in:
47 47 16 16 6
Testovací vstupy

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|
Přílohy
basic.in.txt
(119 bajtů) Staženo 225 x
combined.in.txt
(522 bajtů) Staženo 234 x
catches.in.txt
(475 bajtů) Staženo 231 x
mnaukal
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"

Příspěvek od mnaukal »

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í.
Odpovědět

Zpět na „NPRG041 Programování v C++“