long/long.tex

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