1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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=52]{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.
|
