e-x-a.org » NPRG005 Neprocedurální programování 2017/18

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

  • ČAS: každé úterý 10:40 v SW2
  • KONTAKT: kratochvil@ksi.mff.cuni.cz, do předmětu napište něco jako [NEPROC]

Materiály ke čtení

  • Stránka Tomáše Dvořáka obsahuje všechno potřebné o průběhu semestru.
  • Learn prolog now!
  • Skvělé učebnice Haskellu:
    • Learn You a Haskell — kratší, trochu teoretičtější, autor očekává, že už umíte programovat a obecně “víte co chcete”.
    • Real World Haskell — podstatně praktičtější ukázka univerzálního nasazení Haskellu v prostředí běžně vyhrazeném Pythonu, Perlu, PHP a C/C++.
  • Scheme se tento semestr vyhneme, ale jako případný materiál pro doplnění znalostí můžete použít Teach yourself Scheme in fixnum days — pokud vám scheme přijde primitivní, doporučuju aspoň kapitolu s (amb), popisuje pěknou souvislost mezi lazy funkcionálním zpracováním a prologem.
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:

  • odevzdat pár domácích úkolů (Domácích úkolů bude 5, očekává se odevzdání všech úkolů. Narozdíl od jiných předmětů se řešení DÚ většinou vejdou na několik řádků. Z odevzdaných řešení by aspoň 50% mělo fungovat správně.)
  • na cvičeních občas vypadat aktivně zúčastněně (za aktivní účast budou aktivitní body, neměli byste jich mít míň než 6)
  • vyrobit zápočťák

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:

  • V Prologu je vhodné programovat umělé, logicky smýšlející inteligence a řešítka problémů s velkým stupněm volnosti
  • V Haskellu je vhodné všechno ostatní, kromě low-level věcí na které je typicky trochu vhondější C/C++.
  • Scheme je někde na “půlce cesty” — typy jsou dynamické, (map) užitečný, a navíc je velmi jednoduché generovat další schemový kód (protože všechna data jsou seznamy a seznamy jsou kód). Velice vhodné jako skriptovací jazyk do větších prostředí.

Konkrétní nápady:

  • Vezměte svůj zápočťák z programování 1 a přepište ho do Haskellu.
  • Moje oblíbená skupina problémů: parsery, miniaturní jazyky, typecheckery (co třeba Hindley-Milnerův typový systém “skoro zadarmo” v prologu?), odvozovače informací o kódu (statická analýza), maličké interpretery, pidi virtuální stroje, transpilery, (pře)formátovače, ...
  • Cokoliv co souvisí s nějakým jiným studentským projektem (např. ročníkovým).
  • Dost nápadů na témata můžete najít u Jána Hrice a Rudolfa Kryla anebo taky třeba tady ale obecně i jinde a dost na googlu.
Termíny
  • Domluvení a odsouhlasení tématu včetně zapsání do SISu: 10. 5. 2018 23:59:59
  • Odevzdání včetně připomínkování nebo prezentace: konec zápočtového týdne

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:

  • Číslo N = aktivita na N-tém cvičení
  • ABCDE = splněný úkol A-E
  • A? = úkol A asi funguje, ale ze zdrojáku vůbec není poznat proč (a bude potřeba to dovysvětlit a/nebo dokomentovat) — zkuste odevzdat vylepšené řešení nebo mi napište, ať máte feedback
  • A! = úkol A vypadá že funguje jak má a je uznaný, ale v kódu je něco hodně divného nebo neefektivního nebo výsledek není úplně správně — můžete si napsat o feedback
  • A+ = pěkný úkol A — hlasitě se pochvalte
  • Z = odevzdaný zápočťák

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

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

Můžete se těšit na:

  • Programovací jazyk z roku 1952 1930
  • SVG obrázky
  • Abstrahovaného Worfa na steroidech — to asi radši vyřešíme na posledním cvičení

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é:

  • Postupně doplňovat řádky, sloupce nebo jednotlivé kostičky, jakmile jsou doplněné správně, už na ně nesahat (a zahodit všechny možnosti backtrackování).
  • První zkoušet tahy, které vypadají blíž řešení (např. celková sečtená manhattanská (nebo jiná) vzdálenost všech kostiček od jejich cílového místa je co nejmenší)

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

  • Matice vyrobené ze dvou spojových seznamů v sobě jsou celkem pomalé. Dost výkonu můžete ušetřit pomocí (trochu) vhodnější reprezentace: Matici reprezentujte jako jeden dlouhý seznam (třeba po řádcích), rozdělený v místě, kde je volné políčko, a bokem si pamatujte souřadnice. Například matice [[1,3,2], [ ,5,8], [7,6,4]] jde reprezentovat jako stav(0,1, [2,3,1], [5,8,7,6,4]). Přesuny doleva/doprava pak jen přehodí jeden prvek mezi seznamy, operace nahoru/dolu jich přehodí celý řádek.
  • Heuristiku se vzdáleností nemusíte pro každý tah počítat celou znova, stačí si ji uložit do stavu, a při změnách se podívat, která kostička se kam posunula. Za dodržení určitých podmínek dokonce není nikdy potřeba heuristiku spočítat celou.
  • Heuristiku je vhodné počítat jen pro kostičky, které se zrovna pokoušíte někam dostat (ostatní vás zajímat nemusí).
  • Pro opravdu velká puzzle se hodí mít i heuristiku na pozici díry (tu potřebujete dostat co nejblíž kostičkám, se kterýmí chcete pohnout). Alternativně pozici díry můžete upravit “manuálně” bez prohledávání.
  • Zhruba polovinu zadání nejde vyřešit. Váš program by v takovém případě neměl zkoumat všechny možnosti, ale skončit podstatně dřív pomocí vhodně zakázaného/zahozeného backtrackování.
Ú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:

  • Proměnnou "x" by parser měl naparsovat jako var(x).
  • Abstrakci λx.A, ve stringu jako "/x.A", by měl naparsovat jako lam(x,A). λ budeme pro jednoduchost psát jako obyčejné lomítko. Tělo abstrakce (A) za tečkou pokračuje až do konce výrazu nebo odpovídající závorky. Zkrácenou syntaxi (tj. psaní λabc.a místo λa.λb.λc.a) neřešte.
  • Aplikaci funkce A na parametr B, ve stringu "AB", by měl naparsovat jako app(A,B). Aplikace se závorkují zleva, tj. v abc je neviditelná závorka (ab)c.
  • Výrazy v závorkách by parser měl zpracovat běžným způsobem.

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:

  • Funkci parseGlob :: String -> Maybe Glob, která string převede na Glob (pokud to jde). Typ Glob vyrobte jako alias (pomocí type) seznamu globových prvků, které vypadají např. nějak takhle: data GlobElem = GlobStar | GlobAny | GlobExactChar Char. Příklad vadného globu je asd*\ nebo \asd*, naproti tomu \\asd\* je OK.
  • Funkci optimizeGlob :: Glob -> Glob, která z globových výrazů vyřadí blbosti, jako např. ***, a optimalizuje relativní pozice otazníků a hvězdiček (?* je lepší než *? nebo *?* — obecně skupiny hvězdiček a otazníků je nejlepší předělat na skupinu otazníků následovaných jednou hvězdičkou). Může se vám hodit: groupBy (z Data.List), filter, null a concat.
  • Funkci matchGlob :: Glob -> String -> Bool, která zjistí, jestli string vyhovuje dodanému (optimalizovanému) vzoru.
  • Funkci matchSubGlob :: Glob -> String -> Bool, která zjistí, jesti ve stringu není aspoň nějaký globu vyhovující podstring. Hodí se použít any, inits a tails (z Data.List), případně můžete trochu poupravit vstupní Glob.

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:

  • [1,2] <> [2,3] <> mempty vrátí [1,2,2,3]
  • mempty je porovnatelné s Nothing
  • mempty je taky porovnatelné s []
  • nebo Just [3] <> Nothing <> Just [1,5] vrátí Just [3,1,5] (což je zajímavá metoda jak se vyhnout ošetřování případů s Nothing).

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 instanci Ord [a] pomocí zipWith a mconcat. Na případy, kdy jeden seznam je přesný prefix druhého, použijte length a možná jedno <> navíc.

Průběh cvičení

1 (20. 2. 2018)
  • Knowledge databáze v prologu
  • Vyhodnocování a formule jiného jazyka v prologu

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ě:

  • Co se stane, když nechám vyhodnotit nekonečnou strukturu? Třeba s kódem z hodiny: X=ne(X), vyhodnot(X,Bool).
  • Jiná nekonečná formule typu False && (False && (False && (False && ...))) je očividně False, ale kód z hodiny ji nevyhodnotí. Nešel by vyhodnocovací kód modifikovat tak, aby zvládnul dokázat, že X=a(ne,X), vyhodnot(X,ne). ?

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)
  • Rekurze a “imperativní” programování prologem
  • Číselné konstanty v prologu
  • Seznamy
3 (6. 3. 2018)
4 (13. 3. 2018)
  • Krutý trik na append v O(1).
  • Seznamové zbytky: reverse s akumulátorem, transpozice matice, mergesort
5 (20. 3. 2018)
  • Gramatiky a parsování Prologem (závorky, čísla, JSON).
6 (27. 3. 2018)
  • Lambda kalkulus a typy.

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)
  • Rychloúvod do Haskellu, základní práce s čísly a seznamy, drobný komentář o Haskellových typech.
  • Lazy vyhodnocování umožňuje jednoduchou práci s nekonečnými datovými strukturami.
8 (10. 4. 2018)
  • Trochu pokročilejší haskell, zábava s first-class funkcemi
  • ukázka pár ručně definovaných datových typů
  • Maybe
9 (17. 4. 2018)
  • Overloading pomocí typových tříd
10 (24. 4. 2018)
  • Aplikativní monoid je monáda!
  • Opravdové Imperativní Programování
  • Maybe, Either, List jako monády
  • IO, RealWorld
Plán (věci ve frontě)
  • Nedeterminismus a parsování (Haskell jako Prolog)
    • Worf na steroidech!
  • Do očí bijící souvislost lambda kalkulu s přirozenou logikou
    • Pár příkladů jak použít Either — flatten, or, chyby.

Bonusy

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

....