e-x-a.org » NPRG005 Neprocedurální programování 2018/19

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

  • ČAS: každou středu 10:40 v SU2
  • 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!
  • 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++.
    • Pokud něco programujete v haskellu, hodí se prohledavač balíků Hoogle
  • Scheme se tento semestr vyhneme, ale jako případný materiál pro doplnění znalostí můžete použít 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.
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 vhodně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). Velice vhodné jako skriptovací jazyk do větších prostředí.

Konkrétní nápady:

  • Vezměte svůj zápočťák z programování 1 a přepište ho do Haskellu.
  • Neprocedurální programování umožňuje vyjadřovat hrozně složité myšlenky extrémně kompaktním způsobem. Zkrácení 1000-řádkového programu v C#/Javě na 5 až 10 řádek Haskellu nebo Prologu je skvělý zápočťák.
  • 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.

Zápočťáky je vhodné nenatahovat — 100 řádků dostatečně “ostrého” kódu který nejúčinnějším způsobem řeší zadaný problém je úplně OK.

Termíny
  • Zapsání zápočťáku do SISu: 12. 5. 2019 23:59:59. Téma si studenti vymyslí a zapíšou sami do studijních mezivýsledků. Komentář budu přidávat tamtéž. Odpovídající políčko se 12.5. magicky zamkne a nebudou možné další změny. Pokud si nejste jistí a téma chcete prodiskutovat, napište mi mail.
  • Odevzdání včetně připomínkování nebo prezentace: konec zápočtového týdne (zdrojový kód nahrajte do odpovídajícího políčka do SISu)

Upozornění: Pokud chcete zápočťák odevzdávat v červnu nebo později, může se stát, že nebudu k dispozici. Proto, pokud odevzdáváte pozdě a chcete stihnout termín nějaké zkoušky, předem počítejte s nepředvídatelným zpožděním zápočtu 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 asi funguje, ale ze zdrojáku vůbec není poznat proč (a bude potřeba to dovysvětlit a/nebo dokomentovat) — zkuste odevzdat vylepšené řešení nebo mi napište, ať máte feedback
  • A! = úkol A vypadá že funguje jak má a je uznaný, ale v kódu je něco hodně divného nebo neefektivního nebo výsledek není úplně správně — můžete si napsat o feedback
  • 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”.

  • Úkol A (Worf) — Termín: páté cvičení (20.3.2019, 10:39:59.999). S řešením chcete pravděpodobně počkat až po třetím cvičení
  • Úkol B (SMILES) — Termín: sedmé cvičení, korekce/zlepšení můžete odevzdávat i po termínu (cca do víkendu). Metodiku vhodnou k vyřešení budeme dělat na pátém cvičení
  • Úkol C (((mult-mtx))) — Termín: večer po osmém cvičení.
  • Úkol D (bankovní záznamy) — Termín: večer po desátém cvičení.
  • Úkol E (výpočty s logem) — Termín: večer po třináctém (posledním) cvičení.
  • Úkol F (STLC) — bonusový úkol (vhodný jako teoretická příprava na zkoušku, případně jako záplata za jiné chybějící úkoly)

Průběh cvičení

20. 2. 2019

Úplný základ Prologu, atomy, klauzule, Skolemovské použití predikátů jako funkcí, vyhodnocování logické formule.

K zamyšlení: Zkuste vyhodnocovadlem logických formulí z cvičení vyřešit nějakou malou instanci SATu.

27. 2. 2019

Imperativní konstrukce v Prologu, problém s konstruktivistickou sémantikou negace.

Seznamy a běžné funkce na zpracování seznamů: head vs. tail, běžné seznamoviny (append, reverse).

Stihli jsme i logickou hádanku.

6. 3. 2019

Předávání predikátů jako proměnných, funkce vyšších řádů (filter, map).

Slovo o tail rekurzi, reverse s akumulátorem.

Pokročilá zábava se seznamy, čísla, třídění, matice.

13. 3. 2019

Doděláme násobení matic. Otočení matice o 90 stupňů. Zip a fold. Stromy.

20. 3. 2019

Deadline prvního úkolu!

Krutý trik na append/3 fungující v O(1).

Parsování prologem, generativní gramatiky.

Na cvičení se to trochu nestihlo udělat formálně, takže přidávám drobný přehled: Gramatická pravidla se v Prologu zapisují šipkou -->; pravidlo se převede na obdobu normálního pravidla (definovaného pomocí :-) ve kterém si jednotlivá pod-pravidla automaticky předávají seznam k naparsování a vrací “zbytek”. To jsou 2 parametry navíc, které se automaticky přidají ke každému termu (tj. gramatický term s N parametry se převede na normální term s N+2 parametry). Navíc jde vynutit vybrání několika termů “ručně” pomocí [hranatých závorek] a spuštění negramatického kódu (který nedostane seznam a zbytek) se provede pomocí {složených závorek}.

Například:

a --> b.
a(I) --> b(I), c.
a(I) --> b, [I], c.
a --> [X], {isdigit(X)}.

se přeloží na:

a(Z1, Z2) :- b(Z1, Z2).
a(I, Z1, Z3) :- b(I, Z1, Z2), c(Z2, Z3).
a(I, Z1, Z4) :- b(Z1,Z2), Z2=[I|Z3], c(Z3,Z4).
a(Z1,Z2) :- Z1=[X|Z2], isdigit(X).

Pro kompletnost přidávám demonstrační parser aritmetických výrazů (někteří si podobný program můžou pamatovat jako 300řádkovou zrůdnost v C++, nebo možná ještě horší v C#).

27. 3. 2019

Pro úplnost naparsujeme JSOŇ.

Úvod do funkcionálního programování (ve scheme), lambdy.

3. 4. 2019

Úvod do Haskellu, práce se seznamy a jednoduchými typy. Vracet funkce je fajn.

10. 4. 2019

Typy, Curry-style funkce. Lambdy. Stromy a nekonečné datové struktury.

Poslední příklad jsem přepsal z if na guard syntax (což je jen trochu hezčí metoda jak napsat hromadu ifů za sebou).

17. 4. 2019

Ještě trochu zábavy se stromy. Typové třídy a instance.

23.4. 2019 dopoledne

Ještě nějaká zábava se stromy. Typové třídy Eq, Functor a Foldable.

Vyskytla se otázka, proč některé typové třídy existují s typovým parametrem (např. instance Eq (Strom a) a jiné s typovým parametrem definovat nejde, např. instance Functor (Strom a).

Technický důvod: Eq má kind * -> Constraint, proto akceptuje věci s druhem *, tj. např. Int, Maybe Int nebo Strom Float. Obecně instance říká, že je schopná porovnávat konkrétní objekty jednoho typu. Všimněte si že např. objekty typu Maybe (Int->Int) nijak rozumně porovnávat nejde. Naproti tomu, Functor má kind (* -> *) -> Constraint, takže akceptuje jen jednoparametrové typové konstruktory, což je např. Strom, nebo Maybe nebo IO.

Praktický důvod: Třídy Functor, Foldable (a další, např. Applicative, Traversable a Monad) mají podstatně silnější požadavky na svoje instance:

Například pokud o Strom chcete tvrdit, že je Functor (tj. “kontejner”), musí to nutně být “kontejner” generický, tj. schopný obsahovat jak Int, tak String, tak Strom->[(Float,Float)], tak i jakýkoliv jiný typ. Toto chování vynucuje typ funkce fmap :: Functor f => (a->b) -> f a -> f b — kdybyste např. na Strom Int aplikovali fmap s funkcí typu Int->NecoNoveho, naprosto jasně očekáváte Strom NecoNoveho, bez ohledu na to jestli někdo dodefinoval konkrétní instanci pro Strom NecoNoveho.

Jinak řečeno, absence typového parametru v definici instance znemožňuje reagovat na konkrétní typ obsažený v kontejneru, čímž nepřímo vynucuje, že kontejner bude zcela generický pro všechny typy.

Pro Foldable to platí podobně — svůj kontejner musíte být schopní “seskládat” pomocí foldr vždycky stejně, zcela bez ohledu na to, co obsahuje. Některé funkce z Foldable které v kontejneru potřebují rozumně zpracovatelné hodnoty (např. elem, minimum nebo sum) toto dospecifikovávají extra požadavkem na typovou třídu vnitřního typu, např. elem :: (Foldable t, Eq a) => a -> t a -> Bool nebo sum :: (Foldable t, Num a) => t a -> a.

23.4. 2019 odpoledne

Jak poměrně přirozeně dojít k monádám.

Pokud jste cvičení nestihli, zhruba podobný obsah mám ve slajdech z Haskellu dostupných odsud (aktuálně na stránkách cca 60 až 76).

Bonus: Pohled na ukrutnou pravdu o IO.

15. 5. 2019

Applicative/Monad hierarchie. Použití State a celá ukrutná pravda o IO. Zmínku o Reader/Write jsme nestihli, ale Writer je víceméně tosamé, jako Commented z DÚ E.

22. 5. 2019 (bude)

Monadické parsování (což je řekněme “killer app” celého Haskellu).

Můžete si stáhnout jednoduchou implementaci kterou budeme používat na cvičení.

Bonusy

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

...

Typing the technical interview.