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
|
\section{Preliminary definitions}
\label{sec:predefs}
A number of types will turn out to be useful in general. We define:
\lstinputlisting[firstline=25,lastline=28]{While/Common.dcl}
The \CI{Error} type distinguishes between different kinds of errors, that can
be further identified with a descriptive string. We could add more information
to these types, like the position (file, line and column) of the input token
that causes the error. The implementation thereof is straightforward and will
for the sake of brevity be omitted here.
We can model the partial state function as a function that yields an \CI{Either
Error Int}. Whenever a variable is not defined, a \CI{Left (Runtime
"Undefined")} will be returned. Otherwise, a \CI{Right n} is returned. The
initial state, which maps any variable to a \CI{Left} result, is implemented as
an instance of the \CI{zero} class.
\lstinputlisting[firstline=9,lastline=10]{While/WhileCommon.dcl}
\lstinputlisting[firstline=12,lastline=13]{While/WhileCommon.icl}
In order to build up our interpreter modularly, we wouldn't want to fix the
type of the AST just yet. Rather, we want it to be possible to implement
different kinds of abstract syntax trees: for example, it may be interesting to
implement a While program as a list of statements (making composition
implicit), while the straightforward AST would use a compositional constructor.
To allow for different ASTs, we make the \CI{run} function, that will interpret
a While program in some state, overloaded:
\lstinputlisting[firstline=35,lastline=35]{While/WhileCommon.dcl}
Similarly, we want to be able to use the same terminology of \emph{evaluation}
for both arithmetic and boolean expressions. This can be done using overloading
as well:
\lstinputlisting[firstline=37,lastline=39]{While/WhileCommon.dcl}
The \CI{eval} function may yield an error, for example when an undefined
variable is used. It makes sense to separate evaluation and interpretation,
because evaluation does not depend on the type for statements. Any AST using
\CI{AExpr} may now use this \CI{eval} function (while it is also possible to
create an AST that uses a different representation of arithmetic expressions).
Although all these functions are presented in an overloaded fashion, we will
only consider one implementation, the AST from \autoref{sec:ast} below. Other
models do not introduce additional problems that would be interesting for the
purposes of this paper.
|
