long/long.tex

   1 %&long
   2 \begin{document}
   3
   4 \maketitle
   5
   6 \tableofcontents
   7
   8 \section{Introduction}
   9 \subsection{Setting and objective}
  10 \emph{Monads for functional programming} was initially published in
  11 \emph{Program Design Calculi} which was a collection of lecture notes
  12 accompanying the \emph{Marktoberdorf} summer school in 1992. Later it was
  13 reissued in \emph{Springer}s \emph{Advanced Functional Programming} book which
  14 presents the tutorials from a spring school in Sweden in 1995.
  15
  16 The notes were written to introduce the reader to the idea of a Monad usable in
  17 a functional programming context. Where monads are already defined and studied
  18 in category theory in the early fifties. Moggi et al.\ were the first in 1988
  19 to see the usefulness in computer science and in particular functional
  20 programming. At the time of writing this paper was introducing state of the art
  21 research which later became the preferred way of dealing with side-effects in a
  22 pure language. The paper familiarized readers with the concepts while only
  23 requiring basic knowledge in functional programming.
  24
  25 \subsection{Impact}
  26 While Wadler had already published a lot about monads this turned out to be one
  27 of the most accessible and readable papers concerning the topic. A lot of the
  28 references in the paper cite his own work, but this is logical since he was
  29 part of the small group of researchers that kick-started the use of monads in
  30 functional programming.
  31
  32 The paper has been cited over $676$ times over the past $23$ years resulting in
  33 a $\pm 30$ cites per year. It is cited as the de-facto monad introducing paper.
  34 In 2015 and 2016 the paper has already been cited numerous times in topics
  35 including but not limited to: Introducing new monad types, generic programming,
  36 designing modular design specific languages, concurrency frameworks in
  37 functional languages and probabilistic computing.
  38
  39 \section{Proposal and evidence}
  40 \subsection{Proposal}
  41 Wadler proposes to capture side-effects in monads. A monad is a structure
  42 containing a monad type:
  43 \CI{:: M a}\\
  44 Secondly a monad contains a function to lift a value to the monadic domain:
  45 \CI{unit :: a -> M a}\\
  46 Lastly a monad contains the function that transforms \CI{a} into \CI{b} while
  47 capturing the possible side-effects in \CI{M}:
  48 \CI{(>>=) infixl 1 :: (M a) (a -> M b) -> M b}
  49
  50 When this structure adheres certain laws they are very useful in capturing
  51 side-effects that would otherwise be difficult to handle in an impure language.
  52 Wadler shows this by tackling several classical problems arising in the pure
  53 functional programming world.
  54
  55 \subsection{\emph{Expression problem}}
  56 In this review we will show one of the examples given to illustrate the meaning
  57 and usage the monadic pattern. The code snippets in the original paper
  58 supposedly are \emph{haskell} however they are not all valid. Thus the
  59 following snippets have been translated to valid
  60 \emph{Clean}~\footnote{\url{http://clean.cs.ru.nl}}
  61
  62 \paragraph{Simple evaluator}
  63 Say we have a simple evaluator where an expression is either an integer or a
  64 division between two expressions. Writing a simple evaluator is very straight
  65 forward.
  66 \begin{CleanCode}
  67 :: Term = Con Int | Div Term Term
  68
  69 eval :: Term -> Int
  70 eval (Con a) = a
  71 eval (Div t u) = eval t / eval u
  72
  73 answer :: Term
  74 answer = Div (Div (Con 1972) (Con 2)) (Con 23)
  75
  76 error :: Term
  77 error = (Div (Con 1) (Con 0))
  78 \end{CleanCode}
  79
  80 \paragraph{Exceptions}
  81 When we evaluate \CI{eval error} we get a runtime exception since dividing by
  82 zero is illegal. If we want to add exceptions things get a little more frisky.
  83 We extend the type with an exception type that either contains an exception
  84 or a return value. The following code will catch exceptions nicely.
  85 \begin{CleanCode}
  86 :: M a = Raise Exception | Return a
  87 :: Exception :== String
  88
  89 eval :: Term -> M Int
  90 eval (Con a) = return a
  91 eval (Div t u) = case eval t of
  92         Raise e = Raise e
  93         Return a = case eval u of
  94                 Raise e = Raise e
  95                 Return b = if (b == 0) (Raise "Divide by zero") (Return (a/b))
  96 \end{CleanCode}
  97
  98 \paragraph{State}
  99 Say we want to add state to the evaluator. Now we have to redo the entire
 100 evaluation part again. Say we have single integer as a state which counts the
 101 number of divisions taken. Then we get the following code which counts the
 102 number of divisions.
 103 \begin{CleanCode}
 104 :: M a :== State -> (a, State)
 105 :: State :== Int
 106
 107 eval :: Term -> M Int
 108 eval (Con a) = \x.(a, x)
 109 eval (Div t u) =
 110         \x.let (a, y) = eval t x in
 111         let (b, z) = eval u y in
 112         (a/b, z+1)
 113 \end{CleanCode}
 114
 115 \subsection{A monadic approach to the \emph{Expression problem}}
 116 \paragraph{Exceptions}
 117 The example for exceptions can be implemented using monads as follows:
 118 \begin{CleanCode}
 119 :: M a = Raise Exception | Return a
 120 :: Exception :== String
 121
 122 unit :: a -> M a
 123 unit a = Return a
 124
 125 (>>=) infixl 1 :: (M a) (a -> M b) -> M b
 126 (>>=) m k = case m of
 127         Raise e = Raise e
 128         Return a = k a
 129
 130 raise :: Exception -> M a
 131 raise e = Raise e
 132
 133 eval :: Term -> M Int
 134 eval (Con a) = unit a
 135 eval (Div t u) = eval t >>= \a->eval u >>= \b->case b of
 136         0 = Raise "Divide by zero"
 137         b = unit (a/b)
 138 \end{CleanCode}
 139
 140 \paragraph{State}
 141 The example for states can be implemented using monads as follows:
 142 \begin{CleanCode}
 143 :: Void = Void
 144 :: M a :== State -> (a, State)
 145 :: State :== Int
 146
 147 unit :: a -> M a
 148 unit a = \x->(a, x)
 149
 150 (>>=) infixl 1 :: (M a) (a -> M b) -> M b
 151 (>>=) m k = \x->let (a, y) = m x in
 152         let (b, z) = k a y in
 153         (b, z)
 154
 155 tick :: M Void
 156 tick = \x->(Void, x+1)
 157
 158 eval :: Term -> M Int
 159 eval (Con a) = unit a
 160 eval (Div t u) = eval t >>= \a->eval u >>= \b->tick >>= \_->unit (a/b)
 161 \end{CleanCode}
 162
 163 \subsection{Evidence}
 164 Besides the example shown above Wadler shows also shows the usefulness of
 165 monads in a setting where you use lists, arrays and recursive descent parsers.
 166 These examples show the flexibility and ease that monads bring. Especially for
 167 input/output the monadic pattern is useful. If one wants to capture
 168 side-effects, instead of reimplementing every function for the particular side
 169 effects you can just write the monadic operations and let the monads handle the
 170 rest.
 171
 172 Even after more than 20 years the monadic pattern is used throughout the
 173 functional programming world and is incorporated in all the functional
 174 programming languages used by the academic and by everyday programmers such as
 175 \emph{Haskell} and \emph{Clean}.
 176
 177 \section{Analysis}
 178 \subsection{Writing style}
 179 The paper has been written for (under)-graduate students and thus it is
 180 extremely readable. Even with no particular domain knowledge the paper is very
 181 clear. The author tackles the expression problem, arrays as a state and parsers
 182 which are classical problems in the functional programming field. Even when the
 183 reader has little knowledge of functional programming those problems are
 184 familiar and are effective in illustrating the power of monads.
 185
 186 \subsection{Discussion}
 187 Within the time frame of publishing these are near perfect publication, however
 188 in hindsight there are some things that could be improved upon.
 189
 190 The language use is sometimes a bit informal and possibly even fluffy. However,
 191 the fact that these were originally lecture notes for a summer school clear
 192 this issue up.
 193
 194 Secondly the section about parsers is quite big and not might not be necessary
 195 for illustrating the power of monads. The contents of this section could very
 196 well be a paper on its own.
 197
 198 \end{document}