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í#

• Stránka Tomáše Dvořáka obsahuje všechno potřebné o průběhu semestru.
• Learn prolog now!
• 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.
• Learn you a haskell

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 4x4. Ř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 3x3 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.