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!
  • 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.
  • 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++.
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). Transpilery vítány.

Konkrétní nápady:

  • 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 hodnocení 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 nevypadal, že funguje, jak má — příště se víc snažte
  • 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:

  • Rezervační oddělení ubytovací kanceláře
  • Programovací jazyk z roku 1952
  • SVG obrázky
  • Abstrahovaného Worfa na steroidech
Ú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, ...

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)
Plán (věci ve frontě)
  • Matice a složitější seznamy
  • Negace v přirozené logice je podivná!
  • Neúplné struktury (rozdílové seznamy)
  • Parsování v prologu je to samé jako vypisování
  • Lambda kalkulus a typy (v prologu), do očí bijící souvislost lambda kalkulu s přirozenou logikou
  • Haskell, nekonečně líné struktury
  • Haskellové datové typy
  • Polymorfismus a overloading v haskellu. Vlastnosti dat:
    • Show-ovatelnost
    • Číselnost
    • Porovnatelnost
    • Foldovatelnost
    • Monoidnost
  • Funktory (obalování jako vlastnost dat), aplikativa a monády (slepovatelné obaly)
  • IO v jazycích bez vedlejších efektů. Bonusové zjištění, že celý skutečný svět se dá celý pohodlně uložit přesně do 0 bitů.
  • Nedeterminismus (Haskell jako Prolog)
  • Parsování v Haskellu

Bonusy

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

....