e-x-a.org » NPRG005 Neprocedurální programování 2016/17

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

  • ČAS: LS 2016/17, každé úterý ve 14:00 v S8, MS MFF
  • KONTAKT: exa.exa@gmail.com, do předmětu napište něco jako [NEPROC], ať se odlišíte od šedé mezivrstvy skorospamu.

Materiály ke čtení

Kde sehnat vývojové prostředí?

Oficiální seznam.

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

  • SWI prolog na příklady, GNU prolog na některé ošklivé triky
  • Racket scheme
  • standardní GHC/GHCi

Za co bude zápočet?

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

  • splnit pár domácích úkolů (aspoň jeden z prologu a aspoň jeden z haskellu, ve vlasntním zájmu ale oba, + 1 bonus ze scheme)
  • na cvičeních občas vypadat aktivně zúčastněně (nedostatek aktivitních bodů bude možné nahradit nadprodukcí bodů za domácí úkoly)
  • 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íme 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 neprocedurálního přístupu. 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é psát cokoliv co využije jednoduché zpracování nepravidelných datových struktur a/nebo lazy vyhodnocování.
  • 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). Transpilery vítány.
  • Moje velice oblíbená skupina problémů: parsery, miniaturní kompilátory, 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, ...
  • 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: 31. 3. 2017 23:59:59
  • Odevzdání včetně připomínkování nebo prezentace: poslední cvičení (bude celé věnované odevzdávání a prezentacím zápočťáků)

(Pozor, přes červen většinou nebudu k dispozici, pokud chcete zápočet už v červnu, velmi silně doporučuju zápočťák stihnout do posledního cvičení.)

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 = úkol A-E.
  • A+ = pěkný úkol
  • A! = úkol nevypadal, že funguje, jak má (doporučení k odevzdání dalšího úkolu)

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

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

Úkol A, termín 20. 3. 2017

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 předvyhodnocenou programátorem) a program, který z nich odvodí řešení.

Příklad jak může vypadat výsledek: prolog na dotaz reseni_worfova_problemu(PohlaviDitete,PohlaviRodice1,DiteLhalo) odpoví PohlaviDitete=holka, PohlaviRodice1=kluk, ...

Úkol B, termín 10. 4. 2017

Vyřešte Loydovo puzzle velikosti 4×4. Řešení nemusí být optimální, ale mělo by být spočítané rychle, takže použijte nějakou heuristiku (skládání “postupně” apod.). Zajistěte, že na neřešitelných případech program nebude zkoušet všechny kombinace možností (ideálně to zařiďte řezem).

Program by měl přijmout počáteční permutaci čísel a mezery (např. seznam velikosti 16 nebo nějakou šestnáctici) a vrátit seznam obsahující nějakou formu návodu jak puzzle vyřešit, například postupně všechny “operace”, nebo postupně všechny stavy na cestě k řešení.

DODATEK: “spočítané rychle” nepřehánějte, řešení do 5 sekund je skvělé a do minuty úplně stačí.

Úkol C, termín 30. 4. 2017

Ve scheme naprogramujte násobení matic libovolné (i obdélníkové) velikosti. Matice obsahují jen normální čísla, a jsou reprezentované jako seznamy seznamů po řádkových vektorech, tj. identitní matice 3×3 je reprezentovaná '((1 0 0)(0 1 0)(0 0 1)).

Snažte se o nejkratší a nejhezčí kód (ne nutně nejrychlejší nebo nejodolnější) a co nejlepší využití funkcí (map), (zip) a (foldl), hodí se i předdefinovaný (andmap).

Úkol D, termín 9. 5. 2017

Napište v Haskellu matchování jednoduchých regulárních výrazů. Stačí podporovat následující featury:

  • kulaté závorky
  • tečku
  • or
  • Kleeneho hvězdičku

Escapování neřešte, kulaté závorky, svislítko, tečku ani hvězdičku prostě matchovat nebudeme. Stejně tak neřešte časovou složitost matchování (samozřejmě to jde lineárně převodem na DKA, ale tak co).

Naopak řešte čistotu, přehlednost a potenciální rozšiřitelnost kódu. Vhodné je si string s patternem nejdřív rozparsovat na nějakou hezkou vlastní reprezentaci (na cvičení budeme podobně matchovat globy), pak se s tím pracuje podstatně líp.

Program by měl zvládnout potvrdit např. že výrazu (a|b|c)*C.A*C odpovídá slovo abcbaCXAAAC ale neodpovídá mu slovo ccCC.

Doporučený interface je asi takovýhle:

> :t regexMatch
regexMatch :: String -> String -> Bool   -- pattern, word, result
> regexMatch ".*aabaa.*" "nazdarbazar"
False
> regexMatch ".*aabaa.*" "nazdaabaazar"
True
Úkol E, termín 23. 5. 2017

V Haskellu vyřešte Worfův problém z úkolu A. Samozřejmě to jde tradičně hrubou silou, ale zkuste to udělat nějak elegantně, ideálně tak, aby výsledný program vypadal sémanticky, tj. jako “přeložené zadání” podobně jako u dobrých řešení v prologu.

Hint: List comprehension se chová trochu jako prolog, nešlo by to tak? Případně si z monád můžete vyrobit vlastní podobný (vhodnější) “skoro prolog”, list comprehension je totiž taky jen úplně obyčejná monádová konstrukce. Budu to předvádět na cvičeních 9.5. a 16.5.

Průběh cvičení

21. 2. 2017

Úvod, předběžnosti. K čemu je procedurální kód fajn a k čemu je podivný. Knowledge databáze v prologu.

Na hodině se nám skoro povedlo vyrobit vyhodnocovač logických formulí: prolog ohodnotí program vyhodnot(nebo(a(ano,ne),ano), X). dosazením X=ano. Zdroják z hodiny zde .

DÚ:

  1. napište mi mail (viz nahoře), ať na vás mám kontakt.
  2. na příště se zamyslete:
    • jaký je rozdíl mezi negativní odpovědí na vyhodnot(a(ano,neg(kocka)),X). a na vyhodnot(a(ano,neg(ano)), X).
    • se proč se zacyklí dotaz vyhodnot(X,kocka).
    • jak donutit prolog, aby vyhodnot(F,ne). postupně vypsalo všechny formule, které se vyhodnotí na ne, a nezacyklil se na neg(neg(neg(neg(.....)))).

28. 2. 2017

Lepší generování/vyhodnocování formulí, aritmetika.

DÚ:

  • Pokud jste mi ještě nenapsali mail, napište mi ho.
  • Na rozmyšlení (a proměnu na body příště):
    • převod z normálních čísel do množinově logické aritmetiky a zpět. num(5,X) doplní X=s(s(s(s(s(n))))) apod.
    • jak a proč selže nebo neselže plus(X,s(n),X) (tj. rovnice x=1+x)?

7. 3. 2017

Seznamy, transpozice matice, logická hádanka.

14. 3. 2017

Krutý trik na append v O(1), nějaké seznamové zbytky.

21. 3. 2017

Stromy, negace.

Pozor, nahoře je zadání DÚ B. Moje řešení úkolu A je k nalezení v bonusech.

28. 3. 2017

Prohledávání grafu, začátek parsování.

4. 4. 2017

Parsery a nějaké velmi drobné prologove zbytky (na I/O není moc co řešit). Scheme primer.

11. 4. 2017

Scheme, ocasní (tail) rekurze.

18. 4. 2017

Plynulý přechod k potřebě typových systémů. Úvod do haskellu.

25. 4. 2017

Haskell, seznamy, parsování. Vlastní datové typy.

2. 5. 2017

Haskell, nekonečné seznamy a nekonečné stromy. List comprehension.

Algoritmus na typovou inferenci.

9. 5. 2017

Letmé dokončení typové inference. I/O, do notation, overloading v typových třídách, nasměrování na monády.

Ve zdrojáku z hodiny je (prakticky naprosto nepoužitelná ale přesto demonstrativní) instance Applicative Tree a OpCounter.

16. 5. 2017

Maybe jako monáda, seznam jako monáda, stav jako monáda, IO a skutečný svět.

23. 5. 2017

Jak z haskellu udělat prolog a/nebo scheme. Dořešování zápočťáků, rozdávání zápočtů.

Bonusy

Prolog, scheme a haskell co jsme napsali na hodinách.