long/long.tex

   1 %&long
   2 \begin{document}
   3 \frame{\titlepage}
   4
   5 \section{Introduction}
   6 \begin{frame}
   7         \frametitle{Scientific Impact}
   8         \begin{block}{Metrics}
   9                 \begin{itemize}[<+->]
  10                         \item Cited $676$ times in $23$ years
  11                         \item $\pm 30$ cites per year
  12                         \item Cited as de-facto monad introducing paper
  13                         \item Monads in computer science: Moggi et al.\ in $1989$
  14                 \end{itemize}
  15         \end{block}
  16 \end{frame}
  17
  18 \begin{frame}
  19         \frametitle{Objective \& Current state}
  20         \begin{block}{Objective}
  21                 \begin{itemize}
  22                         \item First introduction to monads
  23                         \item Layman's terms
  24                 \end{itemize}
  25         \end{block}
  26
  27         \pause%
  28         \begin{block}{Current state of the art}
  29                 \begin{itemize}[<+->]
  30                         \item $2016$: $2$ papers citing Wadler
  31                         \item $2015$: $24$ papers citing Wadler
  32                         \item Ranging from
  33                                 \begin{itemize}[<+->]
  34                                         \item Introducing new monad types
  35                                         \item Generic programming
  36                                         \item Designing modular DSL's
  37                                         \item Concurrency frameworks in functional languages
  38                                         \item\ldots
  39                                 \end{itemize}
  40                 \end{itemize}
  41         \end{block}
  42 \end{frame}
  43
  44 \section{Contents}
  45 \subsection{Introduction}
  46 \begin{frame}
  47         \frametitle{Introduction}
  48         \begin{itemize}
  49                 \item Monads (Moggi et al.)
  50                 \item Integrate the impure in the pure
  51                 \item Wadler shows \textsc{Haskell} examples
  52                 \item Following samples are in \textsc{Clean}
  53         \end{itemize}
  54 \end{frame}
  55
  56 \subsection{Naive approach}
  57 \begin{frame}[fragile]
  58         \frametitle{Case study (1)}
  59         \framesubtitle{Evaluator}
  60         \begin{CleanCode}
  61 :: Term = Con Int | Div Term Term
  62
  63 eval :: Term -> Int
  64 eval (Con a) = a
  65 eval (Div t u) = eval t / eval u
  66
  67 //Examples
  68 answer :: Term
  69 answer = (Div (Div (Con 1972) (Con 2)) (Con 23))
  70
  71 error :: Term
  72 error = (Div (Con 1) (Con 0))
  73         \end{CleanCode}
  74 \end{frame}
  75
  76 \begin{frame}[fragile]
  77         \frametitle{Case study (2)}
  78         \framesubtitle{Exceptions}
  79         \begin{CleanCode}
  80 :: M a = Raise Exception | Return a
  81 :: Exception :== String
  82
  83 eval :: Term -> M Int
  84 eval (Con a) = Return a
  85 eval (Div t u) = case eval t of
  86         Raise e = Raise e
  87         Return a = case eval u of
  88                 Raise e = Raise e
  89                 Return b = if (b == 0)
  90                         (Raise "Divide by zero")
  91                         (Return (a / b))
  92         \end{CleanCode}
  93 \end{frame}
  94
  95 \begin{frame}[fragile]
  96         \frametitle{Case study (3)}
  97         \framesubtitle{State, count divisions}
  98         \begin{CleanCode}
  99 :: M a :== State -> (a, State)
 100 :: State :== Int
 101
 102 eval :: Term -> M Int
 103 eval (Con a) x = (a, x)
 104 eval (Div t u)
 105 # (a, y) = eval t x
 106 # (b, z) = eval u y
 107 = (a/b, z+1)
 108         \end{CleanCode}
 109 \end{frame}
 110
 111 \subsection{Monadic approach}
 112 \begin{frame}[fragile]
 113         \frametitle{Monadic (1)}
 114         Monad is a triple: $(M, unit, \star)$
 115         \pause%
 116         \begin{block}{Signatures}
 117                 \begin{CleanCode}
 118 :: M a = ...
 119 unit :: a -> M a
 120 ((#$\star$#)) :: (M a) (a -> M b) -> M b
 121                 \end{CleanCode}
 122         \end{block}
 123         \pause%
 124         \begin{block}{Evaluator (Identity monad)}
 125                 \begin{CleanCode}
 126 :: M a :== a
 127 unit :: a -> I a
 128 unit a = a
 129 ((#$\star$#)) :: (M a) (a -> M b) -> M b
 130 ((#$\star$#)) a k = k a
 131                 \end{CleanCode}
 132         \end{block}
 133 \end{frame}
 134
 135 \begin{frame}[fragile]
 136         \frametitle{Monadic (2)}
 137         \framesubtitle{Exceptions}
 138         \pause%
 139         \begin{CleanCode}
 140 :: M a = Raise Exception | Return a
 141 :: Exception :== String
 142         \end{CleanCode}
 143         \pause%
 144         \begin{CleanCode}
 145 unit :: a -> M a
 146 unit a = Return a
 147
 148 ((#$\star$#)) :: (M a) (a -> M b) -> M b
 149 ((#$\star$#)) m k = case m of
 150         Raise e = Raise e
 151         Return a = k a
 152         \end{CleanCode}
 153         \pause%
 154         \begin{CleanCode}
 155 raise :: Exception -> M a
 156 raise e = Raise e
 157         \end{CleanCode}
 158 \end{frame}
 159
 160 \begin{frame}[fragile]
 161         \frametitle{Monadic (3)}
 162         \framesubtitle{State}
 163         \pause%
 164         \begin{CleanCode}
 165 :: M a = State -> (a, State)
 166 :: State :== Int
 167         \end{CleanCode}
 168         \pause%
 169         \begin{CleanCode}
 170 unit :: a -> M a
 171 unit a = \x.(a, x)
 172
 173 ((#$\star$#)) :: (M a) (a -> M b) -> M b
 174 ((#$\star$#)) m k = \x.let (a, y) = m x in
 175         let (b, z) = k a y in
 176         (b, z)
 177         \end{CleanCode}
 178         \pause%
 179         \begin{CleanCode}
 180 tick :: M Void
 181 tick = \x.(Void, x + 1)
 182         \end{CleanCode}
 183 \end{frame}
 184
 185 \subsection{Laws}
 186 \begin{frame}[fragile]
 187         \frametitle{Laws}
 188         \begin{block}{Monoid}
 189                 \begin{itemize}
 190                         \item Left unit:
 191                                 \begin{CleanCode}
 192 unit a (#$\star$#) \b.n = n[a/b]
 193                                 \end{CleanCode}
 194                         \item Right unit
 195                                 \begin{CleanCode}
 196 m (#$\star$#) \a.unit a = m
 197                                 \end{CleanCode}
 198                         \item Associativity
 199                                 \begin{CleanCode}
 200 m (#$\star$#) (\a.n (#$\star$#) \b.o) = (m (#$\star$#) \a.n) (#$\star$#) \b.o
 201                                 \end{CleanCode}
 202                 \end{itemize}
 203         \end{block}
 204 \end{frame}
 205
 206 \subsection{Further evidence}
 207 \begin{frame}[fragile]
 208         \frametitle{Different approach}
 209         \framesubtitle{Parsers (1)}
 210         \begin{CleanCode}
 211 :: M a = State -> [(a, State)]
 212 :: State :== [Char]
 213
 214 unit :: a -> M a
 215 unit a = \x.[(a, x)]
 216
 217 ((#$\star$#)) :: (M a) (a -> M b) -> M b
 218 ((#$\star$#)) m k = \x.[(b, z) \\ (a, y) <- m x, (b, z) <- k a y]
 219         \end{CleanCode}
 220 \end{frame}
 221
 222 \begin{frame}[fragile]
 223         \frametitle{Different approach}
 224         \framesubtitle{Parsers (2)}
 225         \begin{CleanCode}
 226 zero :: M a
 227 zero = \x.[]
 228
 229 ((#$\oplus$#)) :: (M a) (M a) -> M a
 230 ((#$\oplus$#)) m n = \x.m x ++ n x
 231
 232 ((#$\triangleright$#)) :: (M a) (a -> Bool) -> M a
 233 ((#$\triangleright$#)) m p = m (#$\star$#) \a.if (p a) (unit a) zero
 234
 235 item :: M Char
 236 item [] = []
 237 item [a:x] = [(a, x)]
 238         \end{CleanCode}
 239 \end{frame}
 240
 241 \begin{frame}[fragile]
 242         \frametitle{Different approach}
 243         \framesubtitle{Parsers (3)}
 244         \begin{CleanCode}
 245 iterate :: M a -> M [a]
 246 iterate m = (m (#$\star$#) \a.iterate m (#$\star$#) \x.unit [a:x]) (#$\oplus$#) unit []
 247
 248 iterate (item (#$\triangleright$#) isDigit) "23 and more"
 249 [([2,3], " and more"), ([2], "3 and more"), ([], "23 and more")]
 250         \end{CleanCode}
 251         \pause
 252         \begin{CleanCode}
 253 ((#$\oslash$#)) :: (M a) (M a) -> M a
 254 ((#$\oslash$#)) m n = \x.if (m x <> []) (m x) (n x)
 255         \end{CleanCode}
 256 \end{frame}
 257
 258 \section{Discussion}
 259 \begin{frame}
 260         \begin{block}{Writing style}
 261                 \begin{itemize}[<+->]
 262                         \item Pleasure to read
 263                         \item Classical problems
 264                         \item Fancy words
 265                 \end{itemize}
 266         \end{block}
 267         \pause
 268         \begin{block}{Discussion queries}
 269                 \begin{itemize}[<+->]
 270                         \item Toy implementations, bigger?
 271                         \item Would the last section about parsers be a paper on its own?
 272                 \end{itemize}
 273         \end{block}
 274 \end{frame}
 275
 276 \begin{frame}
 277         \frametitle{Questions or discussion points?}
 278 \end{frame}
 279
 280 \end{document}