Navigation
Page categories
Outline:
Last modification
2025-09-04
This is smol web. If you don't like it, fix your browser.

Informační stránka o cvičení z neprocedurálního programování.

Materiály ke čtení#

Kde sehnat vývojové prostředí?#

Na cvičeních budu používat:

Všechna prostředí jsou dostupná v labu. Na vlastní počítač s UNIXem/Linuxem si je můžete nainstalovat pomocí prakticky libovolného balíčkovacího systému. Instalační balíky pro Windows jsou dostupné z odkazů.

Za co bude zápočet?#

Za splnění následujících podmínek:

Na zkoušku je potřeba zápočet, proto je fajn mít všechno vyřešené do konce května.

Pokud v Haskellu i Prologu už programovat umíte a myslíte si, že požadavky pro vás budou triviální, dejte mi vědět mailem nebo na první hodině, ať se zbytečně nenudíte docházkou.

Zápočťáky#

Narozdíl od zápočťáků z “tradičních” programování není potřeba, aby zápočtový program byl nějak extrémně obsáhlý, ale je nutné jím demonstrovat, že umíte správně zneužít výhody logického/funkcionálního programování. Téma je libovolné (kromě úplně triviálních úloh dostupných v desítkách kopií na celém internetu), ale doporučuje se neodbíhat od témat, pro která byly neprocedurální jazyky stvořeny:

Konkrétní nápady:

Termíny#

Upozornění: Pokud chcete zápočťák odevzdávat v červnu nebo později, může se stát, že nebudu k dispozici. Počítejte s nepředvídatelným zpožděním zápočtu o 0 až 3 týdny.

Mezivýsledky#

Jsou k vidění v SISu ve studijních mezivýsledcích. Vysvětlivky:

Zadání domácích úkolů#

Řešení DÚ vkládejte do SISu pomocí rozhraní “studijní mezivýsledky”.

Původně plánované rezervační oddělení ubytovací kanceláře jsem zrušil, protože bylo ohavné.

Úkol A, termín 20. 3. 2018#

V džungli žije kmen domorodců, jejichž vyjadřování vykazuje mimořádnou (občas nepříjemnou) výstřednost: Muži vždycky říkají pravdu; ženy nikdy neřeknou dvě nepravdivé věty za sebou, ani dvě pravdivé věty za sebou. Nepříjemnější je, že muži i ženy se oblékají a vypadají obecně stejně, takže s rozeznáváním pravdy to je občas složité.

Antropolog (říkejme mu Worf) se domorodce pokouší studovat, jenže ještě pořádně neumí domorodčí jazyk. Takže když jednoho dne potká rodinu a zeptá se dítěte, jestli je chlapec, Worf odpovědi nerozumí. Proto se obrátí na rodiče, z nichž Worfovi jeden řekne “Dítě řeklo, že je chlapec” a druhý doplní “Dítě je holka. Dítě lhalo.”

Worf by pro pokračování ve výzkumu lokálních tradic potřeboval vědět, jak dítě odpovědělo (případně jestli lhalo) a určit pohlaví dítěte a obou rodičů.

Úkol: Napište prologový program, který problém z dodaných faktů vyřeší. Zdrojový kód by měl dokumentovat a prokazovat správnost řešení, tj. měl by obsahovat přehlednou prologovou reprezentaci všech vstupních faktů (ideálně ne částečně vyhodnocenou programátorem) a program, který z nich odvodí řešení.

Při řešení se vyhněte vlastní definici pravdivosti, použijte jen tu prologovou. (Tzn. vaše řešení by nemělo pracovat s termy podobnými ano a ne jako na prvním cvičení.) Doporučený postup je nadefinovat si rika(+Pohlavi, +SeznamTvrzeni, -SeznamPravdivychTvrzeni). Vyjádření prvního rodiče pak jde pěkně vyjádřit např. jako rika(Rodic1, [rika(Dite, [Dite=muz], X)], _). Zkoumáním X pak můžete jednoduše poznat, jestli dítě lhalo.

Příklad, jak může vypadat interface (výsledek není správně): Prolog na dotaz reseni_worfova_problemu(PohlaviDitete,PohlaviRodice1,PohlaviRodice2) odpoví PohlaviDitete=holka, PohlaviRodice1=kluk, ...

Úkol B, termín 13. 4. 2018#

Vyřešte prologovým programem Loydovo puzzle (alias 15ku alias kostičky alias …, viz wiki) libovolné velikosti. Řešení nemusí být optimální (tj. nejkratší), ale je potřeba ho spočítat v rozumném čase (ideálně ne úplně exponenciálním).

Na dostatečně rychlé řešení velkých puzzle potřebujete kvalitní heuristiku. Vymyslete si libovolnou, ale tyhle jsou osvědčené:

Aby vaše řešení bylo rychlé (a nezbláznili jste se programováním), rozmyslete si následující:

Úkol C, termín 15. 5. 2018#

Podobně jako na cvičení 5 vyrobte pomocí prologových gramatik parser lambda kalkulu zadaného ve stringu:

Například výraz (λx.λy.yxy) se zapíše a naparsuje takhle: parse_lambda("/x./y.yxy", lam(x, lam(y, app(app(var(y), var(x)), var(y)))) )..

Jinak uzávorkovaný výraz (λx.λy.y(xy)): parse_lambda("/x./y.y(xy)", lam(x, lam(y, app(var(y), app(var(x), var(y)))) ))..

Protože substituce je základ pro vyhodnocování lambda kalkulu (a mnoha jiných jazyků), naimplementujte predikát subst(Vstup, Promenna, Nahrada, Vystup), který ve výrazu Vstup nahradí všechny volné výskyty proměnné náhradou. Kolize proměnných při substituci neřešte (viz. níže).

Příklad: subst(app(var(x), lam(x, var(x))), x, lam(z, var(z)), app(lam(z, var(z)), lam(x, var(x)))).

Podobně, protože jména proměnných mohou v programu poměrně nepříjemně kolidovat, vyrobte funkci, která všechny zachycené proměnné ve výrazu přejmenuje na unikátní názvy: např. 0, 1, 2, atd.

Příklad: (λx.(λx.x)x) je totéž jako (λx.(λy.y)x), po přečíslování (λ0.(λ1.1)0). Odpovídající kód: uniquify_vars(lam(x, app(lam(x,var(x)), var(x))), lam(0, app(lam(1,var(1)), var(0)))).

Pro řešení si stáhněte šablonu, ve které je zároveň i testovací kód, ukázka přejmenování proměnných a nějaké věci navíc (vyhodnocování a typování λ-výrazů) včetně bonusu. Vaším úkolem je nahradit volání todo tak, aby oba testy fungovaly správně.

Úkol D, termín 15. 5. 2018#

Běžně známým hvězdičkovým patternům z příkazové řádky se říká Glob. Viz. man 3 glob.

Globový výraz je obyčejný string se speciálními znaky * a ?, kde hvězdička namatchuje nula až nekonečno libovolných písmen, a otazník namatchuje přesně 1 libovolné písmeno. Všechny ostatní znaky ve výrazu matchují samy sebe.

Pokud chcete namatchovat hvězdičku (nebo otazník), musíte ji escapovat zpětným lomítkem. Totéž platí i pro samotné zpětné lomítko.

V Haskellu vyrobte:

Nepovinný bonus — Typová třída na slepované věci#

Monoidy jsou struktury s asociativní binární operací, ve kterých vůči této operaci existuje neutrální prvek. Výhoda monoidů je, že jsou všude: Např. přirozená čísla s plus a nulou jsou monoid; přirozená čísla s násobením a jedničkou jsou jiný monoid, matice s násobením jsou monoid, permutace se skládáním jsou monoid, množiny se sjednocením jsou monoid, systém podmnožin nějaké množiny s průnikem tvoří monoid, I7 z hodiny tvoří několik různých monoidů, a obecně hodně dalších věcí je taky monoid. V Haskellu jsou monoidy např. seznamy s operací slepení (++) a prázným seznamem (viz. instance Monoid [a] — schválně si zkontrolujte, že (++) je asociativní a přilepením prázdného seznamu se nic nestane). Zobecněný operátor monoidní operace se značí <> (importujte si Data.Monoid), zobecněná prázdná hodnota se jmenuje mempty. Takže třeba:

Nikoho teď už asi nepřekvapí, že Ordering (výsledek operace compare z typové třídy Ord) je taky monoid, s poměrně specifickým lexikálním účelem. Bonusový úkol: Reimplementujte porovnávání seznamů pomocí zipWith a mconcat (bez použití instance Ord [a]). Na případy, kdy jeden seznam je přesný prefix druhého, použijte buď length (což je ale nudné a nefunguje to pro nekonečné seznamy) nebo si seznamy trochu upravte (hint: datové typy můžete zadarmo obohatit o plus/mínus nekonečno a zachovat porovnatelnost).

Výsledná funkce by měla mít typ zhruba cmpLists :: Ord a => [a] -> [a] -> Ordering.

(Splněný bonusový úkol se bude brát jako výrazná úleva při hodnocení zápočťáku. Řešení přilepte do souboru s úkolem D.)

Úkol E, termín konec semestru (s řešením počkejte na cvičení 15.5.)#

Vyrobte Haskellový toolkit pro “kreslení” “obrázků” “tužkou”. Stav kreslení jde reprezentovat jako pokreslený papír (na něm jsou čáry, což jsou nějaké dvojice 2D bodů) a pozice a stav tužky (tužka má 2D pozici a dotýká/nedotýká se papíru).

Pomocí State (můžete použít buď State ze cvičení, nebo standardní Control.Monad.State) implementujte následující:

Pozn.: Nepište vlastní implementaci stavových funkcí (na cvičení 13 jsme to dělali jen proto, že jsme State vyráběli od nuly), použijte do-notation a put a get.

Základ pro vyrobení úkolu (s demo kódem který by nakonec měl vyrobit pěkné SVG se čtverečky) najdete tady.

Nepovinný bonus — Worf na steroidech#

List comprehension je vytváření seznamu pomocí hezké syntaxe, například [ x*3+y | x <- [1..10], y<-[1..10], x < 2*y ]. Na přednášce se o něm už mluvilo, my ho procvičíme a rozebereme na předposledním cvičení.

Zajímavý poznatek o list comprehensionu je, že jde použít jako Prolog: Výpočet vrátí všechny validní možnosti, které projdou podmínkami (není problém si pak pomocí head vytáhnout tu první co by vrátil Prolog a zbytek líně zahodit). Místo prologového fail jde použít x <- [] nebo jen [] (tj. “žádné možnosti”), místo true se dá stejně použít [()] (tj. “jedna nezajímavá možnost”), místo prologové čárky se používá list-comprehensionová čárka, a místo or se použije ++ (tj. sjednocení všech možností). Unifikace bohužel nefunguje (aspoň ne takhle jednoduše v list comprehensionech) — pokud potřebujete z podvýpočtu nějaká data, musíte je vrátit. Jiné zajímavé zjištění je, že comprehensionová syntax je vlastně úplně normální monáda: např. [ a+b | a <-[1..3], b<-[1..3], a/=b] se přepíše na do {a<-[1..3]; b<-[1..3]; guard (a/=b); return (a+b)}, takže comprehensiony jde psát rovnou jako normální “prologovitě imperativní” programy.

Plot twist: Worf z prvního domácího úkolu ztratil interpret Prologu!

Implementujte řešení jeho problému v Haskellu, na nederminismus použijte list comprehension. Opět platí zákaz ručního “pomáhání” a předpřipravování dat, snažte se tvrzení domorodců reprezentovat co nejvíc sémanticky v Haskellu. Hint: Predikát rika jde pomocí předchozího návodu poměrně jednoduše přeložit na zpracování seznamů možností. Seznamy pravdivostí tvrzení z něj vracejte jako [Bool] (tj. všechny možné výsledky jako [[Bool]]).

(Pozn.: guard je definovaný v Data.List jako guard True = [()]; guard False = [].)

(Splněný bonusový úkol se bude brát jako výrazná úleva při hodnocení zápočťáku. Řešení přilepte do souboru s úkolem E.)

Průběh cvičení#

1 (20. 2. 2018)#

Na hodině jsem chtěl ukázat fixpoint (větu o pevném bodě, stejně jako z analýzy) ale Prolog mě přelstil, protože výsledek X=f(X) mu přišel dostačující. V případě použití se výraz samozřejmě chová jako X=f(f(f(f(f(......))))).

K zamyšlení na příště:

Zveřejnil jsem zadání úkolu A. K řešení budete potřebovat pár věcí ze cvičení 2 a 3 (takže vklidu počkejte).

2 (27. 2. 2018)#
3 (6. 3. 2018)#
4 (13. 3. 2018)#
5 (20. 3. 2018)#
6 (27. 3. 2018)#

Cokoliv ze cvičení si můžete zopakovat třeba tady. Účelem mírného procvičení lambda kalkulu bylo ukázat teoretický základ pro Haskell. Jestli si z toho chcete něco užitečného odnést, odneste si lambda-kalkulovou metodu výroby víceparametrových funkcí z jednoparametrových, a zapamatujte si, že typ funkcí se reprezentuje šipkou. Např. C-style funkce bool f(int, float) má λ-style typ int -> float -> bool.

Na cvičení jsem trochu nestihl zaimplementovat odvození typů lambda kalkulu v prologu, proto prologovou implementaci typového systému obdržíte zadarmo k úkolu C.

Slibované líné vyhodnocování odsouvám k procvičení v Haskellu.

Do očí bijící souvislost lambda kalkulu s přirozenou logikou jsem prozatím taky odsunul. Zájemci si můžou vygooglit Curry-Howardův izomorfismus.

Řešení domácího úkolu A je k dispozici.

7 (3. 4. 2018)#
8 (10. 4. 2018)#
9 (17. 4. 2018)#
10 (24. 4. 2018)#

State jsme tradičně nestihli. Další cvičení je až za 3 týdny, pokud se na něj chcete připravit, zkuste si doma dodělat monádovou instanci State s a pár souvisejících věcí:

Bonus: Proč se monády jmenujou tak blbě: je to monoid (všimněte si že je jedno, jestli v Cčku stavové výpočty uzávorkujete jako a;b;c nebo {a;b};c nebo a;{b;c}, výpočty co nic neudělají můžete generovat třeba jako pure id) a navíc je aplikativní. A “monap” zní ještě hůř.

13 (15. 5. 2018)#

Dodělaný State, aplikace na stavové výpočty. Trochu IO. List comprehension rozdělaný na monády.

14 (22. 5. 2018)#

Aplikace monád na rozumné věci: Velmi Jednoduché Extrémně Účinné Parsování ™. Zcela zdarma připomínka Prologového backtrackingu. Stáhněte si miniaturní variantu haskellové parsovací knihovny Parsec, se kterou budeme pracovat na cvičení: vzhledem k velikosti a stylu se jmenuje pidiparsec.

Když zbyde čas, budeme se bavit teoretickým dopadem existence typových systémů (typy jsou věty, programy vyrábějí věty, a typy typů jsou druhy).

Parser z hodiny bylo nakonec celkem jednoduché opravit, stačilo si uvědomit co udělá return [] <|> ... (nic moc…).

Plán (věci ve frontě)#

Bonusy#

Věci co jsme napsali na hodinách budou k dispozici tady

…

Typing the technical interview.