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í.
  • moje velice oblíbená skupina problémů: parsery, miniaturní kompilátory, typecheckery, odvozovače informací o kódu, maličké interpretery, pidi virtuální stroje, transpilery, přeformátovače, ...
  • dost nápadů na témata můžete najít u Jána Hrice a Rudolfa Kryla anebo taky třeba tady a 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: 31. 5. 2017 23:59:59 (odevzdávání a prezentacím zápočťáků věnujeme poslední 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í.

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.

Bonusy

Prolog co jsme napsali na hodinách.