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!
  • Hodí se projít si vestavěné predikáty SWI Prologu
• 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:

• SWI prolog na příklady, GNU prolog na některé ošklivé triky
• standardní GHC/GHCi
• Pokud chcete používat Scheme, docela fajn prostředí je Racket scheme

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.