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!
  • 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 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). 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.
  • 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 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”.

Původně plánované rezervační oddělení ubytovací kanceláře jsem zrušil, protože bylo ohavné.

Ú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, ...

Úkol B, termín 13. 4. 2018

Vyřešte prologovým programem Loydovo puzzle (alias 15ku alias kostičky alias …, viz wiki) libovolné velikosti. Řešení nemusí být optimální (tj. nejkratší), ale je potřeba ho spočítat v rozumném čase (ideálně ne úplně exponenciálním).

Na dostatečně rychlé řešení velkých puzzle potřebujete kvalitní heuristiku. Vymyslete si libovolnou, ale tyhle jsou osvědčené:

  • Postupně doplňovat řádky, sloupce nebo jednotlivé kostičky, jakmile jsou doplněné správně, už na ně nesahat (a zahodit všechny možnosti backtrackování).
  • První zkoušet tahy, které vypadají blíž řešení (např. celková sečtená manhattanská (nebo jiná) vzdálenost všech kostiček od jejich cílového místa je co nejmenší)

Aby vaše řešení bylo rychlé (a nezbláznili jste se programováním), rozmyslete si následující:

  • Matice vyrobené ze dvou spojových seznamů v sobě jsou celkem pomalé. Dost výkonu můžete ušetřit pomocí (trochu) vhodnější reprezentace: Matici reprezentujte jako jeden dlouhý seznam (třeba po řádcích), rozdělený v místě, kde je volné políčko, a bokem si pamatujte souřadnice. Například matice [[1,3,2], [ ,5,8], [7,6,4]] jde reprezentovat jako stav(0,1, [2,3,1], [5,8,7,6,4]). Přesuny doleva/doprava pak jen přehodí jeden prvek mezi seznamy, operace nahoru/dolu jich přehodí celý řádek.
  • Heuristiku se vzdáleností nemusíte pro každý tah počítat celou znova, stačí si ji uložit do stavu, a při změnách se podívat, která kostička se kam posunula. Za dodržení určitých podmínek dokonce není nikdy potřeba heuristiku spočítat celou.
  • Heuristiku je vhodné počítat jen pro kostičky, které se zrovna pokoušíte někam dostat (ostatní vás zajímat nemusí).
  • Pro opravdu velká puzzle se hodí mít i heuristiku na pozici díry (tu potřebujete dostat co nejblíž kostičkám, se kterýmí chcete pohnout). Alternativně pozici díry můžete upravit “manuálně” bez prohledávání.
  • Zhruba polovinu zadání nejde vyřešit. Váš program by v takovém případě neměl zkoumat všechny možnosti, ale skončit podstatně dřív pomocí vhodně zakázaného/zahozeného backtrackování.
Úkol C, termín 15. 5. 2018

Podobně jako na cvičení 5 vyrobte pomocí prologových gramatik parser lambda kalkulu zadaného ve stringu:

  • Proměnnou "x" by parser měl naparsovat jako var(x).
  • Abstrakci λx.A, ve stringu jako "/x.A", by měl naparsovat jako lam(x,A). λ budeme pro jednoduchost psát jako obyčejné lomítko. Tělo abstrakce (A) za tečkou pokračuje až do konce výrazu nebo odpovídající závorky. Zkrácenou syntaxi (tj. psaní λabc.a místo λa.λb.λc.a) neřešte.
  • Aplikaci funkce A na parametr B, ve stringu "AB", by měl naparsovat jako app(A,B). Aplikace se závorkují zleva, tj. v abc je neviditelná závorka (ab)c.
  • Výrazy v závorkách by parser měl zpracovat běžným způsobem.

Například výraz (λx.λy.yxy) se zapíše a naparsuje takhle: parse_lambda("/x./y.yxy", lam(x, lam(y, app(app(var(y), var(x)), var(y)))) )..

Jinak uzávorkovaný výraz (λx.λy.y(xy)): parse_lambda("/x./y.y(xy)", lam(x, lam(y, app(var(y), app(var(x), var(y)))) ))..

Protože substituce je základ pro vyhodnocování lambda kalkulu (a mnoha jiných jazyků), naimplementujte predikát subst(Vstup, Promenna, Nahrada, Vystup), který ve výrazu Vstup nahradí všechny volné výskyty proměnné náhradou. Kolize proměnných při substituci neřešte (viz. níže).

Příklad: subst(app(var(x), lam(x, var(x))), x, lam(z, var(z)), app(lam(z, var(z)), lam(x, var(x)))).

Podobně, protože jména proměnných mohou v programu poměrně nepříjemně kolidovat, vyrobte funkci, která všechny zachycené proměnné ve výrazu přejmenuje na unikátní názvy: např. 0, 1, 2, atd.

Příklad: (λx.(λx.x)x) je totéž jako (λx.(λy.y)x), po přečíslování (λ0.(λ1.1)0). Odpovídající kód: uniquify_vars(lam(x, app(lam(x,var(x)), var(x))), lam(0, app(lam(1,var(1)), var(0)))).

Pro řešení si stáhněte šablonu, ve které je zároveň i testovací kód, ukázka přejmenování proměnných a nějaké věci navíc (vyhodnocování a typování λ-výrazů) včetně bonusu. Vaším úkolem je nahradit volání todo tak, aby oba testy fungovaly správně.

Úkol D, termín 15. 5. 2018

Běžně známým hvězdičkovým patternům z příkazové řádky se říká Glob. Viz. man 3 glob.

Globový výraz je obyčejný string se speciálními znaky * a ?, kde hvězdička namatchuje nula až nekonečno libovolných písmen, a otazník namatchuje přesně 1 libovolné písmeno. Všechny ostatní znaky ve výrazu matchují samy sebe.

Pokud chcete namatchovat hvězdičku (nebo otazník), musíte ji escapovat zpětným lomítkem. Totéž platí i pro samotné zpětné lomítko.

V Haskellu vyrobte:

  • Funkci parseGlob :: String -> Maybe Glob, která string převede na Glob (pokud to jde). Typ Glob vyrobte jako alias (pomocí type) seznamu globových prvků, které vypadají např. nějak takhle: data GlobElem = GlobStar | GlobAny | GlobExactChar Char. Příklad vadného globu je asd*\ nebo \asd*, naproti tomu \\asd\* je OK.
  • Funkci optimizeGlob :: Glob -> Glob, která z globových výrazů vyřadí blbosti, jako např. ***, a optimalizuje relativní pozice otazníků a hvězdiček (?* je lepší než *? nebo *?* — obecně skupiny hvězdiček a otazníků je nejlepší předělat na skupinu otazníků následovaných jednou hvězdičkou). Může se vám hodit: groupBy (z Data.List), filter, null a concat.
  • Funkci matchGlob :: Glob -> String -> Bool, která zjistí, jestli string vyhovuje dodanému (optimalizovanému) vzoru.
  • Funkci matchSubGlob :: Glob -> String -> Bool, která zjistí, jesti ve stringu není aspoň nějaký globu vyhovující podstring. Hodí se použít any, inits a tails (z Data.List), případně můžete trochu poupravit vstupní Glob.

Nepovinný bonus — Typová třída na slepované věci

Monoidy jsou struktury s asociativní binární operací, ve kterých vůči této operaci existuje neutrální prvek. Výhoda monoidů je, že jsou všude: Např. přirozená čísla s plus a nulou jsou monoid; přirozená čísla s násobením a jedničkou jsou jiný monoid, matice s násobením jsou monoid, permutace se skládáním jsou monoid, množiny se sjednocením jsou monoid, systém podmnožin nějaké množiny s průnikem tvoří monoid, I7 z hodiny tvoří několik různých monoidů, a obecně hodně dalších věcí je taky monoid. V Haskellu jsou monoidy např. seznamy s operací slepení (++) a prázným seznamem (viz. instance Monoid [a] — schválně si zkontrolujte, že (++) je asociativní a přilepením prázdného seznamu se nic nestane). Zobecněný operátor monoidní operace se značí <> (importujte si Data.Monoid), zobecněná prázdná hodnota se jmenuje mempty. Takže třeba:

  • [1,2] <> [2,3] <> mempty vrátí [1,2,2,3]
  • mempty je porovnatelné s Nothing
  • mempty je taky porovnatelné s []
  • nebo Just [3] <> Nothing <> Just [1,5] vrátí Just [3,1,5] (což je zajímavá metoda jak se vyhnout ošetřování případů s Nothing).
  • mconcat je funkce na slepení seznamu slepitelných věcí: mconcat ["ahoj"," ","Dřindřichu"] vrátí "ahoj Dřindřichu".

Nikoho teď už asi nepřekvapí, že Ordering (výsledek operace compare z typové třídy Ord) je taky monoid, s poměrně specifickým lexikálním účelem. Bonusový úkol: Reimplementujte porovnávání seznamů pomocí zipWith a mconcat (bez použití instance Ord [a]). Na případy, kdy jeden seznam je přesný prefix druhého, použijte buď length (což je ale nudné a nefunguje to pro nekonečné seznamy) nebo si seznamy trochu upravte (hint: datové typy můžete zadarmo obohatit o plus/mínus nekonečno a zachovat porovnatelnost).

Výsledná funkce by měla mít typ zhruba cmpLists :: Ord a => [a] -> [a] -> Ordering.

(Splněný bonusový úkol se bude brát jako výrazná úleva při hodnocení zápočťáku. Řešení přilepte do souboru s úkolem D.)

Úkol E, termín konec semestru (s řešením počkejte na cvičení 15.5.)

Vyrobte Haskellový toolkit pro “kreslení” “obrázků” “tužkou”. Stav kreslení jde reprezentovat jako pokreslený papír (na něm jsou čáry, což jsou nějaké dvojice 2D bodů) a pozice a stav tužky (tužka má 2D pozici a dotýká/nedotýká se papíru).

Pomocí State (můžete použít buď State ze cvičení, nebo standardní Control.Monad.State) implementujte následující:

  • ze State odvoďte typ Drawing, jako stavovou monádu na kreslící operace. Doporučená implementace je: type Drawing a = State DrawState a. Typ DrawState definujte jako vlastní stav kreslení.
  • pomocí runState vyrobte funkci runDrawing :: Drawing a -> DrawState, která spustí kreslící program a vrátí výsledný stav papíru a tužky.
  • pomocí setState a getState (v Control.Monad.State se tyhle funkce jmenují put a get) vyrobte funkce:
    • pencilUp :: Drawing () — zvedne tužku (tj. přestane kreslit)
    • pencilDown :: Drawing () — dá tužku na papír (tj. začne kreslit)
    • pencilMove :: Point2D -> Drawing () — posune tužku o relativní souřadnice. Čára se na papír nakreslí podle toho, jestli je tužka zrovna na papíře nebo nad papírem.

Pozn.: Nepište vlastní implementaci stavových funkcí (na cvičení 13 jsme to dělali jen proto, že jsme State vyráběli od nuly), použijte do-notation a put a get.

Základ pro vyrobení úkolu (s demo kódem který by nakonec měl vyrobit pěkné SVG se čtverečky) najdete tady.

Nepovinný bonus — Worf na steroidech

List comprehension je vytváření seznamu pomocí hezké syntaxe, například [ x*3+y | x <- [1..10], y<-[1..10], x < 2*y ]. Na přednášce se o něm už mluvilo, my ho procvičíme a rozebereme na předposledním cvičení.

Zajímavý poznatek o list comprehensionu je, že jde použít jako Prolog: Výpočet vrátí všechny validní možnosti, které projdou podmínkami (není problém si pak pomocí head vytáhnout tu první co by vrátil Prolog a zbytek líně zahodit). Místo prologového fail jde použít x <- [] nebo jen [] (tj. “žádné možnosti”), místo true se dá stejně použít [()] (tj. “jedna nezajímavá možnost”), místo prologové čárky se používá list-comprehensionová čárka, a místo or se použije ++ (tj. sjednocení všech možností). Unifikace bohužel nefunguje (aspoň ne takhle jednoduše v list comprehensionech) — pokud potřebujete z podvýpočtu nějaká data, musíte je vrátit. Jiné zajímavé zjištění je, že comprehensionová syntax je vlastně úplně normální monáda: např. [ a+b | a <-[1..3], b<-[1..3], a/=b] se přepíše na do {a<-[1..3]; b<-[1..3]; guard (a/=b); return (a+b)}, takže comprehensiony jde psát rovnou jako normální “prologovitě imperativní” programy.

Plot twist: Worf z prvního domácího úkolu ztratil interpret Prologu!

Implementujte řešení jeho problému v Haskellu, na nederminismus použijte list comprehension. Opět platí zákaz ručního “pomáhání” a předpřipravování dat, snažte se tvrzení domorodců reprezentovat co nejvíc sémanticky v Haskellu. Hint: Predikát rika jde pomocí předchozího návodu poměrně jednoduše přeložit na zpracování seznamů možností. Seznamy pravdivostí tvrzení z něj vracejte jako [Bool] (tj. všechny možné výsledky jako [[Bool]]).

(Pozn.: guard je definovaný v Data.List jako guard True = [()]; guard False = [].)

(Splněný bonusový úkol se bude brát jako výrazná úleva při hodnocení zápočťáku. Řešení přilepte do souboru s úkolem E.)

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)
  • Rekurze a “imperativní” programování prologem
  • Číselné konstanty v prologu
  • Seznamy
3 (6. 3. 2018)
4 (13. 3. 2018)
  • Krutý trik na append v O(1).
  • Seznamové zbytky: reverse s akumulátorem, transpozice matice, mergesort
5 (20. 3. 2018)
  • Gramatiky a parsování Prologem (závorky, čísla, JSON).
6 (27. 3. 2018)
  • Lambda kalkulus a typy.

Cokoliv ze cvičení si můžete zopakovat třeba tady. Účelem mírného procvičení lambda kalkulu bylo ukázat teoretický základ pro Haskell. Jestli si z toho chcete něco užitečného odnést, odneste si lambda-kalkulovou metodu výroby víceparametrových funkcí z jednoparametrových, a zapamatujte si, že typ funkcí se reprezentuje šipkou. Např. C-style funkce bool f(int, float) má λ-style typ int -> float -> bool.

Na cvičení jsem trochu nestihl zaimplementovat odvození typů lambda kalkulu v prologu, proto prologovou implementaci typového systému obdržíte zadarmo k úkolu C.

Slibované líné vyhodnocování odsouvám k procvičení v Haskellu.

Do očí bijící souvislost lambda kalkulu s přirozenou logikou jsem prozatím taky odsunul. Zájemci si můžou vygooglit Curry-Howardův izomorfismus.

Řešení domácího úkolu A je k dispozici.

7 (3. 4. 2018)
  • Rychloúvod do Haskellu, základní práce s čísly a seznamy, drobný komentář o Haskellových typech.
  • Lazy vyhodnocování umožňuje jednoduchou práci s nekonečnými datovými strukturami.
8 (10. 4. 2018)
  • Trochu pokročilejší haskell, zábava s first-class funkcemi
  • ukázka pár ručně definovaných datových typů
  • Maybe
9 (17. 4. 2018)
  • Overloading pomocí typových tříd
10 (24. 4. 2018)
  • Aplikativní monoid je monáda!
  • Maybe, Either jako monády
  • použití IO
  • Opravdové Imperativní Programování, State

State jsme tradičně nestihli. Další cvičení je až za 3 týdny, pokud se na něj chcete připravit, zkuste si doma dodělat monádovou instanci State s a pár souvisejících věcí:

  • Typ stavové “andThen” operace by měl být: (>>=) :: State s a -> (a -> State s b) -> State s b (porovnejte s andThen pro Maybe). Fungování by mělo být následující: Spustit první stavovou operaci, výsledek použit pro vyrobení druhé stavové operace z druhého argumentu, tu spustit na updatovaný stav a vrátit výsledek výsledek.
  • Vyrobte getState :: State s s, stavovou operaci která stav vrátí i jako nový stav, i jako výsledek výpočtu
  • Vyrobte setState :: s -> State s (), stavovou operaci která nastaví stav a jako výsledek výpočtu nevrátí níc
  • Vyrobte funkci runState :: s -> State s a -> (s, a), která spustí stavový výpočet s počátečním stavem a vrátí konečný stav a výsledek výpočtu.

Bonus: Proč se monády jmenujou tak blbě: je to monoid (všimněte si že je jedno, jestli v Cčku stavové výpočty uzávorkujete jako a;b;c nebo {a;b};c nebo a;{b;c}, výpočty co nic neudělají můžete generovat třeba jako pure id) a navíc je aplikativní. A “monap” zní ještě hůř.

13 (15. 5. 2018)

Dodělaný State, aplikace na stavové výpočty. Trochu IO. List comprehension rozdělaný na monády.

14 (22. 5. 2018)

Aplikace monád na rozumné věci: Velmi Jednoduché Extrémně Účinné Parsování (TM). Zcela zdarma připomínka Prologového backtrackingu. Stáhněte si miniaturní variantu haskellové parsovací knihovny Parsec, se kterou budeme pracovat na cvičení: vzhledem k velikosti a stylu se jmenuje pidiparsec.

Když zbyde čas, budeme se bavit teoretickým dopadem existence typových systémů (typy jsou věty, programy vyrábějí věty, a typy typů jsou druhy).

Parser z hodiny bylo nakonec celkem jednoduché opravit, stačilo si uvědomit co udělá return [] <|> ... (nic moc…).

Plán (věci ve frontě)
  • Nedeterminismus a parsování (Haskell jako Prolog)
  • Do očí bijící souvislost lambda kalkulu s přirozenou logikou

Bonusy

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

...

Typing the technical interview.