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 by P.\ Wadler
   9 in \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 for lists, arrays and recursive descent parsers. While these examples
 167 strengthen the proposed solution they do not necessarily provide extra or
 168 stronger proof and are thus not treated here.
 169
 170 Especially for input/output the monadic pattern is useful. If one wants to
 171 capture side-effects, instead of reimplementing every function for the
 172 particular side effects you can just write the monadic operations and let the
 173 monads handle the rest.
 174
 175 Even after more than 20 years the monadic pattern has proven to be very useful.
 176 For example in the programming language \emph{Haskell} all the input and output
 177 are handled using a specialized monadic structure. Monadic constructions are
 178 also incorporated in the standard library/prelude of pure functional languages
 179 such as \emph{Haskell} and \emph{Clean}. Even in impure languages the
 180 constructions turns out to be useful and thus monadic structures are available
 181 as library options or extensions in languages such as \emph{Scheme},
 182 \emph{Perl}, \emph{Python}, \emph{Scala} and many more.
 183
 184 \section{Analysis}
 185 \subsection{Writing style}
 186 The paper/lecture notes has been written for (under)-graduate students and thus
 187 it is extremely readable. Even with no particular domain knowledge in the paper
 188 is very clear. There is a gradual buildup in complexity which results in an
 189 easy read for the reader.
 190
 191 To make the point clear the author tackles the expression problem, arrays as a
 192 state and parsers which all are classical problems in the functional
 193 programming field. Even when the reader has little knowledge of functional
 194 programming those problems are likely to be familiar and are become effective
 195 in illustrating the power of monads.
 196
 197 \subsection{Discussion}
 198 Within the time frame and setting in which the paper is published this is a
 199 very good publication. However in hindsight there are some things that could be
 200 improved upon.
 201
 202 The language used is sometimes a bit informal and possibly even fluffy.
 203 However, the fact that these were originally lecture notes for a summer school
 204 clear this issue up.
 205
 206 Secondly, the section about parsers is quite big and could very well be a paper
 207 on its own. The approach and definitions in the parser example are significantly
 208 different than in the previous examples and therefore.
 209
 210 \end{document}