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í?
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Ú:
- napište mi mail (viz nahoře), ať na vás mám kontakt.
- na příště se zamyslete:
- jaký je rozdíl mezi negativní odpovědí na
vyhodnot(a(ano,neg(kocka)),X).
a navyhodnot(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í nane
, a nezacyklil se naneg(neg(neg(neg(.....))))
.
- jaký je rozdíl mezi negativní odpovědí na
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)?
- převod z normálních čísel do množinově logické aritmetiky a zpět.
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ů.