1 files changed, 66 insertions, 0 deletions
diff --git a/paper/eval.tex b/paper/eval.tex
new file mode 100644
index 0000000..14246f8
--- /dev/null
+++ b/paper/eval.tex
@@ -0,0 +1,66 @@
+\section{Evaluation}
+\label{sec:eval}
+
+The \CI{Either} type that we use both in the \CI{State} and in the result of
+\CI{eval} implements the \CI{Monad} class. Monads provide an convenient way to
+simulate effects found in other language, as has been argued by \cite{monads}.
+In this case, we want to simulate exception handling: the evaluation of an
+arithmetic may fail, for example in the case of an undefined variable or when
+we try to divide by zero. These errors may occur in different places: the first
+occurs in the \CI{State} function, while the latter will occur in the \CI{eval}
+implementation of \CI{AExpr}. Using monads, we can easily pass through errors.
+An example will clarify:
+
+\lstinputlisting[firstline=40,lastline=55]{While/WhileCommon.icl}
+
+Recall that the second argument to \CI{eval}, here \CI{st}, is of type
+\CI{State}. That is, it is a function that yields an \CI{Either Error Int}. In
+the first alternative of \CI{eval}, for variables, we implicitly use this: if
+looking up the variable in the state fails, a \CI{Left Error} will be returned.
+
+The last case is more interesting, however. Here, we use bind (\CI{>>=}) to
+simulate exception handling: the two evaluations of \CI{a1} and \CI{a2} may
+fail, as may the application of the operator to its two arguments. Even though
+we don't know at this point \emph{why} or \emph{where} the evaluation failed,
+\CI{>>=} will conveniently pass through any errors.
+
+The abstraction of monad binding allows us to work with data or errors, without
+knowing if we still have data to work with. This gives a very basic and
+readable evaluator.
+
+\medskip
+The \CI{eval} instance for \CI{BExpr} is not very different from the one for
+\CI{AExpr} and is omitted here for brevity.
+
+\subsection{Using a lookup table as state}
+\label{sec:eval:lookup}
+We have defined our \CI{State} as a function. Another solution, that may seem
+more straightforward for people coming from the imperative paradigm, would be
+to model it as a lookup table:
+
+\begin{lstlisting}
+:: State :== [(Var, Int)]
+\end{lstlisting}
+
+While possible, this has several drawbacks. First of all, we would need a
+separate function to look up a variable in this store. We could implement that
+function as follows:
+
+\begin{lstlisting}
+lookup :: Var State -> Either Error Int
+lookup _ []   = Left (Runtime "Undefined")
+lookup v [(w:i):st]
+	| v == w    = pure i
+	| otherwise = lookup v st
+\end{lstlisting}
+
+We did not get a rid of a function: a lookup table forces us to write an extra
+function to look up values. Higher order functions provide a more natural way
+to reason about something which, in the end, really is a function. Functional
+programming allows us to work intuitively with higher order functions, which
+lets us stay closer to the specification.
+
+This brings us at the second drawback. Implementing the state as a lookup table
+distances us from the specification, making it more difficult to verify that
+the implementation is correct. In a functional style it is trivial to check
+that an implementation matches the specification.