Funkcionális Nyelvek 2 (MSc)

Funkcionális Nyelvek 2 (MSc) Páli Gábor János [email protected] Eötvös Loránd Tudományegyetem Informatikai Kar Programozási Nyelvek és Fordítóprogramok Tanszék

Tematika

A (tervezett) tematika rövid összefoglalása http://people.inf.elte.hu/pgj/fny2_msc/ I

Monádok, monádtípusok, ezek kombinációja

I

Tulajdonságalapú tesztelés

I

Konkurens és párhuzamos programozás (tisztán funkcionális nyelvben)

I

Perzisztens (tisztán funkcionális) adatszerkezetek

I

Hatékonyság funkcionális nyelvekben

I

Beágyazott nyelvek

I

Interaktív funkcionális programok

[3..30]

Monádok

Programozás monádokkal – bevezetés

https://byorgey.wordpress.com/2009/01/12/ abstraction-intuition-and-the-monad-tutorial-fallacy/ [5..30]

Programozás burritokkal

[6..30]

Programozás burritokkal

[7..30]

Programozás burritokkal

[8..30]

Programozás burritokkal

[9..30]

Programozás burritokkal

[10..30]

Programozás burritokkal

[11..30]

Programozás burritokkal

[12..30]

Mi nem a monád? A következo˝ állítások mindegyike hamis: I

A monádok nem tisztán funkcionálisak.

I

A monádok programbeli hatásokat modelleznek.

I

A monádok az állapotról szólnak.

I

˝ A monádok utasítások sorbarendezését teszik lehetové.

I

A monádok az I/O-t modellezik.

I

A monádok muködéséhez ˝ szükséges a lusta kiértékelés.

I

A monádok segítségével lehet trükkösen mellékhatásokat használni.

I

A monádok egy beágyazott nyelv a Haskelleben belül.

I

A monádokat csak matematikusok érthetik meg.

[13..30]

A monád fogalmának megértése 8 egyszeru˝ lépésben 1. Ne olvassuk tutorialokat! 2. Ne olvassuk tutorialokat! 3. Tanuljunk a Haskell típusairól (→ „Nyelvek típusrendszere” tárgy)! 4. Tanuljuk meg a típusosztályokat (→ „Funkcionális nyelvek” tárgy)! 5. Tanulmányozzuk a Typeclassopediát∗ ! 6. Tanulmányozzuk a monádok definícióját! 7. Programozzunk monádokkal (→ beadandók)! 8. Ne írjunk tutorialokat! ∗

http://www.cs.tufts.edu/comp/150FP/archive/

brent-yorgey/tc.pdf

[14..30]

Programozás monádokkal – programstruktúrálás Tegyük fel, hogy meg szeretnénk írni egy tisztán funkcionális nyelven az alábbi algoritmussal rendelkezo˝ programot: I

˝ Írjuk ki a képernyore, hogy "Provide me a word> ".

I

Olvassuk be a felhasználó által begépelt szót. ˝ ˝ Az adott szótól függoen tegyük a következot:

I

I

I

˝ Ha palindróma, akkor írjuk ki a képernyore, hogy "Palindrome." ˝ Ha nem palindróma, akkor írjuk ki a képernyore, hogy "Not a palindrome."

Adottak: putStr :: String -> World -> World getLine :: World -> (String, World)

[15..30]

Programozás monádokkal – programstruktúrálás

($) :: (a -> b) -> a -> b f $ x = f x program :: World -> World program w = (\(s, w) -> if (s == reverse s) then putStr "A palindrome." w else putStr "Not a palindrome." w) $ getLine $ putStr "Provide me a word> " $ w

[16..30]

Programozás monádokkal – programstruktúrálás

(|>) :: a -> (a -> b) -> b x |> f = f x program’ :: World -> World program’ w = w |> putStr "Provide me a word> " |> getLine |> \(s, w) -> if (s == reverse s) then putStr "A palindrome." w else putStr "Not a palindrome." w

[17..30]

Programozás monádokkal – programstruktúrálás type IO a = World -> (a, World) -- putStr :: String -> IO () -- getLine :: IO String (>>=) :: IO a -> (a -> IO b) -> IO b (f >>= g) w = (g x) w’ where (x, w’) = f w (>>) :: IO a -> IO b -> IO b f >> g = f >>= \_ -> g program’’ :: IO () program’’ = putStr "Provide me a word> " >> getLine >>= \s -> if (s == reverse s) then putStr "A palindrome." else putStr "Not a palindrome." [18..30]

Programozás monádokkal – programstruktúrálás

main :: IO () main = do putStr "Provide me a word> " s <- getLine if (s == reverse s) then putStr "A palindrome." else putStr "Not a palindrome."

[19..30]

Programozás monádokkal – a Monad típusosztály -- Control.Monad class Monad (m :: * -> *) where return :: a -> m a (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b x >> f = x >>= \_ -> f fail :: String -> m a fail s = error s (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c) f >=> g = \x -> f x >>= g return >=> f f >=> return (f >=> g) >=> h

=== === ===

f f f >=> (g >=> h)

+ „run” függvény [20..30]

Programozás monádokkal – a do szintaktika Átírási szabályok: do { e1; e2 }

-->

e1 >> do { e2 }

do { p <- e1; e2 }

-->

e1 >>= \x -> case x of p -> do { e2 } _ -> fail "error"

do { let p = e1; e2 }

-->

let p = e1 in do { e2 }

do { e }

-->

e

Például: do { do x <- f; x <- f y <- g; y <- g z <- h; --> z <- h --> let t = (x,y,z); let t = (x,y,z) return t return t }

[21..30]

f >>= \x -> g >>= \y -> h >>= \z -> let t = (x,y,z) in return t

Milyen monádok léteznek? data IO a = ? Az IO monáddal tetszöleges mellékhatást tudunk modellezni, ez a "jolly joker". Például: I

putStrLn: írás a szabványos kimenetre

I

getLine: olvasás a szabványos bemenetröl

I

IORef: módosítható hivatkozások, „mutatók”

I

IOError: kivétel(kezelés)

I

IOArray: hatékony, felülírható elemeket tartalmazó tömb

I

forkIO: (konkurens) szálak létrehozása

„run” függvény: a futtató rendszer, unsafePerformIO [22..30]

Ilyen monádok léteznek? data [a] = [] | a:[a] instance Monad [] where return x = [x] xs >>= f = concat [ f x | x <- xs ] fail _ = [] multiplyToNM :: (Num a, Eq a, Enum a) => a -> [(a,a)] multiplyToNM n = do x <- [1..n] y <- [x..n] if (x * y == n) then return (x,y) else fail "Not applicable." multiplyToN n = [ (x,y) | x <- [1..n], y <- [x..n], x * y == n ]

[23..30]

Az Identity monád

type Identity a = a -a -> (a -> b) -> b (>>=) :: Identity a -> (a -> Identity b) -> Identity b x >>= f = f x -a -> a return :: a -> Identity a return x = x -a -> a runIdentity :: Identity a -> a runIdentity x = x

[24..30]

Az Identity monád

-- Control.Monad.Identity data Identity a = I a runIdentity :: Identity a -> a runIdentity (I x) = x instance Monad Identity where return x = I x x >>= f = f (runIdentity x)

[25..30]

Az Identity monád (példa) m :: Int -> Identity Int m x = return (x * x) m’ :: Int -> Identity Int m’ x = do return (x * x) return (x * 2) return (x * 3) m’’ m’’ x y m

:: Int -> Identity Int n = do <- m’ n <- return (x * n) y

y = runIdentity (m’’ 4) [26..30]

A Maybe monád data Maybe a = Just a | Nothing (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b (Just x) >>= f = f x Nothing >>= f = Nothing return :: a -> Maybe a return x = Just x testMaybe :: Maybe Int testMaybe = Just 3 >>= \x -> Just 4 >>= \y -> return (x + y)

[27..30]

A Reader monád type Reader e a = e -> a -(e -> a) -> (a -> (e -> b)) -> (e -> b) (>>=) :: Reader e a -> (a -> Reader e b) -> Reader e b (x >>= f) e = f (x e) e -a -> (e -> a) return :: a -> Reader e a return x = \e -> x -e -> e ask :: Reader e e (ask) e = e -(e -> a) -> e -> a runReader :: Reader e a -> e -> a runReader f x = f x

[28..30]

A Reader monád -- Control.Monad.Reader data Reader e a = R (e -> a) runReader :: Reader e a -> e -> a runReader (R f) x = f x instance Monad (Reader e) where return x = R (\e -> x) x >>= f = R (\e -> let x’ = runReader x e in runReader (f x’) e) ask :: Reader e e ask = R (\e -> e)

[29..30]

A Reader monád (példa) type Identifier = String type Bindings a = Data.Map.Map Identifier a valueOf :: Identifier -> Bindings a -> a valueOf name binds = maybe (error "Not found") id (Data.Map.lookup name binds) bindings :: [(Identifier, a)] -> Bindings a bindings = Data.Map.fromList -- getValuesM :: [Identifier] -> Bindings a -> [a] getValuesM :: [Identifier] -> Reader (Bindings a) [a] getValuesM ids = do binds <- ask return [ valueOf id binds | id <- ids ] getValues :: [Identifier] -> Bindings a -> [a] getValues ids names = runReader (getValuesM ids) names

[30..30]