%&long
\begin{document}
\maketitle
\tableofcontents

\section{Introduction}
\subsection{Setting and objective}
\emph{Monads for functional programming} was initially published by P.\ Wadler
in \emph{Program Design Calculi} which was a collection of lecture notes
accompanying the \emph{Marktoberdorf} summer school in 1992. Later it was
reissued in \emph{Springer}s \emph{Advanced Functional Programming} book which
presents the tutorials from a spring school situated in Sweden in 1995. 

The notes were written to introduce the reader to the monadic design pattern in
functional programming. Monads were already defined and studied
in category theory in the early 1950s but only in the 1988 it was first linked
to computer science. Moggi et al.\ were the first to see the usefulness in
computer science and in particular functional programming. At the time of
writing this paper was introducing state of the art research which later became
the preferred way of dealing with side-effects in a pure language. The paper
familiarized readers with the concepts while only requiring basic knowledge in
functional programming.
 
\subsection{Impact}
While Wadler had already published a lot about monads this turned out to be one
of the most accessible and readable papers concerning the topic. A lot of the
references in the paper cite his own work, but this is logical since he was
part of the small group of researchers that kick-started the use of monads in
functional programming.

The paper has been cited over $676$ times over the past $23$ years resulting in
a around cites per year. It is cited as the de-facto monad introducing paper.
In 2015 and 2016 the paper has already been cited numerous times in topics
including but not limited to: Introducing new monad types, generic programming,
designing modular design specific languages, concurrency frameworks in
functional languages and probabilistic computing.

\section{Proposal and evidence}
\subsection{Proposal}
Wadler proposes to capture side-effects in monads. A monad is a structure
containing three components. The first component is the type itself called
\CI{:: M a}

The second component is a function that lifts a certain value to the monadic
domain and is defined as \CI{unit :: a -> M a}

Lastly the structure contains a function which transforms a certain \CI{a} into
a certain \CI{b} while capturing the possible side-effects in \CI{M} and is
defined as: \CI{(>>=) infixl 1 :: (M a) (a -> M b) -> M b}

When this structure adheres certain laws they are very useful in capturing
side-effects that would otherwise be difficult to handle in an impure language.
Wadler shows this by tackling several classical problems arising in the pure
functional programming world.

\subsection{\emph{Expression problem}}
In this review we will show one of the examples given to illustrate the meaning
and usage the monadic pattern. The code snippets in the original paper
supposedly are \emph{Haskell} however they are not all valid. Thus the
following snippets have been translated to valid
\emph{Clean}~\footnote{\url{http://clean.cs.ru.nl}}.

\paragraph{Simple evaluator}
Say we have a simple evaluator where an expression is either an integer or a
division between two expressions. Writing a simple evaluator is very straight
forward.
\begin{CleanCode}
:: Term = Con Int | Div Term Term

eval :: Term -> Int
eval (Con a) = a
eval (Div t u) = eval t / eval u

answer :: Term
answer = Div (Div (Con 1972) (Con 2)) (Con 23)

error :: Term
error = (Div (Con 1) (Con 0))
\end{CleanCode}

\paragraph{Exceptions}
When we evaluate \CI{eval error} we get a runtime exception since dividing by
zero is illegal. If we want to add exceptions things get a little more frisky.
We extend the type with an exception type that either contains an exception
or a return value. The following code will catch exceptions nicely.
\begin{CleanCode}
:: M a = Raise Exception | Return a
:: Exception :== String

eval :: Term -> M Int
eval (Con a) = return a
eval (Div t u) = case eval t of
	Raise e = Raise e
	Return a = case eval u of
		Raise e = Raise e
		Return b = if (b == 0) (Raise "Divide by zero") (Return (a/b))
\end{CleanCode}

\paragraph{State}
Say we want to add state to the evaluator. Now we have to redo the entire
evaluation part again. Say we have single integer as a state which counts the
number of divisions taken. Then we get the following code which counts the
number of divisions.
\begin{CleanCode}
:: M a :== State -> (a, State)
:: State :== Int

eval :: Term -> M Int
eval (Con a) = \x.(a, x)
eval (Div t u) = 
	\x.let (a, y) = eval t x in
	let (b, z) = eval u y in
	(a/b, z+1)
\end{CleanCode}

\subsection{A monadic approach to the \emph{Expression problem}}
\paragraph{Exceptions}
The example for exceptions can be implemented using monads as follows:
\begin{CleanCode}
:: M a = Raise Exception | Return a
:: Exception :== String

unit :: a -> M a
unit a = Return a

(>>=) infixl 1 :: (M a) (a -> M b) -> M b
(>>=) m k = case m of
	Raise e = Raise e
	Return a = k a

raise :: Exception -> M a
raise e = Raise e

eval :: Term -> M Int
eval (Con a) = unit a
eval (Div t u) = eval t >>= \a->eval u >>= \b->case b of
	0 = Raise "Divide by zero"
	b = unit (a/b)
\end{CleanCode}

\paragraph{State}
The example for states can be implemented using monads as follows:
\begin{CleanCode}
:: Void = Void
:: M a :== State -> (a, State)
:: State :== Int

unit :: a -> M a
unit a = \x->(a, x)

(>>=) infixl 1 :: (M a) (a -> M b) -> M b
(>>=) m k = \x->let (a, y) = m x in
	let (b, z) = k a y in
	(b, z)

tick :: M Void
tick = \x->(Void, x+1)

eval :: Term -> M Int
eval (Con a) = unit a
eval (Div t u) = eval t >>= \a->eval u >>= \b->tick >>= \_->unit (a/b)
\end{CleanCode}

\subsection{Evidence}
Besides the example shown above, Wadler shows also shows the usefulness of
monads for lists, arrays and recursive descent parsers. While these examples
strengthen the proposed solution they do not necessarily provide extra or
stronger proof and are thus not treated here.

Especially for input/output the monadic pattern is useful. If one wants to
capture side-effects, instead of reimplementing every function for the
particular side effects you can just write the monadic operations and let the
monads handle the rest.

Even after more than 20 years the monadic pattern has proven to be very useful.
For example in the programming language \emph{Haskell} all the input and output
are handled using a specialized monadic structure. Monadic constructions are
also incorporated in the standard library/prelude of pure functional languages
such as \emph{Haskell} and \emph{Clean}. Even in impure languages the
constructions turns out to be useful and thus monadic structures are available
as library options or extensions in languages such as \emph{Scheme},
\emph{Perl}, \emph{Python}, \emph{Scala} and many more.

\section{Analysis}
\subsection{Writing style}
The paper/lecture notes has been written for (under)-graduate students and thus
it is extremely readable. Even with no particular domain knowledge in the paper
is very clear. There is a gradual buildup in complexity which results in an
easy read for the reader.

To make the point clear the author tackles the expression problem, arrays as a
state and parsers which all are classical problems in the functional
programming field. Even when the reader has little knowledge of functional
programming those problems are likely to be familiar and are become effective
in illustrating the power of monads.

\subsection{Discussion}
Within the time frame and setting in which the paper is published this is a
very good publication. However in hindsight there are some things that could be
improved upon.

The language used is sometimes a bit informal and possibly even fluffy.
However, the fact that these were originally lecture notes for a summer school
clear this issue up.

Secondly, the section about parsers is quite big and could very well be a paper
on its own. The approach and definitions in the parser example are significantly
different than in the previous examples and therefore.

\end{document}
