Funkcionální programování (NAIL097)
Tomáš Křen (záskok za Petra Pudláka, http://petr.pudlak.name/fp/)Vyučováno v zimním semestru 2014/15 - Zk 2/0.
Slidy
Přednáší se hlavně podle slidu Petra Pudláka, které jsou zde. Probrali jsme slidy 1-6.Plus tyhle moje o kategoriích.
Domácí ukoly
První domácí úkol
První domací úkol je navrhnout si datovou strukturu pro vnitřní reprezentaci lambda termu a k ní implementovat dvě funkce, jednu pro načtení lamda termu ze stringu do teto reprezentace, druha pro výpis teto struktury zpět do stringu. Pokud možno v Haskellu, ale klidne i v jinem jazyce.
showTerm :: Term -> String readTerm :: String -> Term
Nápověda: Pro vnitřní reprezentaci termu můžem použít například následující reprezentaci:
data Term = Var String | App Term Term | Lam String Term
Všiměte si, že tato reprezentace kopíruje formální definici lambda termu (kde místo V použijeme String):
Druhý domácí úkol
Implementujte vyhodnocení termů pro různé redukční strategie, tzn. alespoň pro "línou" (redukuje nejlevější redex, tj. ten na který narazíme při preorder procházení jako na první) a "aplikativní" (redukuje nejvnitřnější nejlevější redex, tj. ten na který narazíme při postorder procházení jako na první) redukční strategii. (viz 2. slidy)
Můžete použít například následující mustr:
-- jeden krok redukční strategie (vrací Nothing pro term v NF) type Strategy = Term -> Maybe Term lazy :: Strategy lazy t = ... eager :: Strategy eager t = ... -- Spočítá normální formu danou redukční strategií za maximálně n kroků -- (vrací Nothing, pokud se nepovedlo redukovat za daný počet kroků) toNormalForm :: Strategy -> Int -> Term -> Maybe Term toNormalForm s n t = ...