328 there are three labels in the factorial program, there are

   328 there are three labels in the factorial program (remember we

   329 three keys. When running the factorial program and

   329 added \pcode{""}), there are three keys. When running the

   330 encountering a jump, then we only have to consult this map, in

   330 factorial program and encountering a jump, then we only have

   331 order to find out what the next instruction should be.

   331 to consult this snippets-map in order to find out what the

   332 next instruction should be.

   334 should be run. This ``running'' of programs is often called 

   335 should be run. In the context of interpreters, this

   335 \emph{evaluation}. Let us start with the definition for

   336 ``running'' of programs is often called \emph{evaluation}. Let

   336 how expressions are evaluated. A first attempt is the 

   337 us start with the definition of how expressions are evaluated.

   337 following recursive function:

   338 A first attempt might be the following recursive function:

   341 $\textit{snippets}([])$ & $\dn$ & $\varnothing$\\

   342 $\textit{eval\_exp}(\texttt{n})$ & $\dn$ & $n$

   342 $\textit{snippets}(stmt\;\; rest)$ & $\dn$ &

   343   \qquad\text{if}\; \texttt{n}\; \text{is a number like} 

   343 $\begin{cases}

   344   \ldots \pcode{-2}, \pcode{-1}, \pcode{0}, \pcode{1},

   344    \textit{snippets}(rest)[label := rest] & \text{if}\;stmt = \textit{label:}\\

   345 \pcode{2}\ldots{}\\

   345    \textit{snippets}(rest)                & \text{otherwise}

   346 $\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{+}\, 

   346 \end{cases}$   

   347                     \texttt{e}_\texttt{2})$ & 

   348   $\dn$ & $\textit{eval\_exp}(\texttt{e}_\texttt{1}) + 

   349            \textit{eval\_exp}(\texttt{e}_\texttt{2})$\\

   350 $\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{*}\, 

   351                     \texttt{e}_\texttt{2})$ & 

   352   $\dn$ & $\textit{eval\_exp}(\texttt{e}_\texttt{1}) * 

   353            \textit{eval\_exp}(\texttt{e}_\texttt{2})$\\

   354 $\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{=}\, 

   355                     \texttt{e}_\texttt{2})$ & 

   356   $\dn$ & $\begin{cases}

   357   1 & \text{if}\;\textit{eval\_exp}(\texttt{e}_\texttt{1}) =

   358                  \textit{eval\_exp}(\texttt{e}_\texttt{2})\\

   359   0 & \text{otherwise}

   360   \end{cases}$          

   350 

   364 \noindent While this should look all relatively

   365 straightforward, still be very careful. There is a subtlety

   366 which can be easily overlooked: The function

   367 \textit{eval\_exp} takes an expression of our programming

   368 language as input and returns a number as output. Therefore

   369 whenever we have a number in our program, we just return this

   370 number---this is defined in the first clause above. Whenever

   371 we encounter an addition, well then we first evaluate the

   372 left-hand side, $\texttt{e}_\texttt{1}$ of the addition (this

   373 will give a number), then evaluate the right-hand side

   374 $\texttt{e}_\texttt{2}$ (this gives another number), and

   375 finally add both numbers together. Here is the subtlety: on

   376 the left-hand side of the $\dn$ we have a \texttt{+} (in the

   377 teletype font) which is the symbol for addition in our

   378 programming language. On the right-hand side we have $+$ which

   379 stands for the arithmetic operation from ``mathematics'' of

   380 adding two numbers. These are rather different concepts---one

   381 is a symbol (which we made up), and the other a mathematical

   382 operation. When we will have a look at an actual

   383 implementation of our interpreter, the mathematical operation

   384 will be the function for addition from the programming

   385 language in which we \underline{\smash{implement}} our

   386 interpreter. While the \texttt{+} is just a symbol that is

   387 used in our programming language. Clearly we have to use a

   388 symbol that is a good mnemonic for addition otherwise we will

   389 confuse the programmers working with our language. Therefore

   390 we use $\texttt{+}$. A similar choice is made for times in the

   391 third clause and equality in the fourth clause. Remember I

   392 wrote at the beginning of this section about being god when

   393 designing a programming language. You can see this here: we

   394 need to give meaning to symbols. 

   395 

   396 At the moment however, we are a poor fallible god. Look again

   397 at the grammar of our programming language and our definition.

   398 Clearly, an expression can contain variables. So far we we

   399 ignored them. What should our interpreter do with variables?

   400 They might change during the evaluation of a program. For

   401 example the variable \pcode{n} in the factorial program counts

   402 down from 5 up to 0. How can we improve our definition above

   403 to give also an answer whenever our interpreter encounters a

   404 variable in an expression? The solution is to add an

   405 \emph{environment}, $env$ as an additional input argument to

   406 our \textit{eval\_exp} function.

   407  

   408 \begin{center}

   409 \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}

   410 $\textit{eval\_exp}(\texttt{n}, env)$ & $\dn$ & $n$

   411   \qquad\text{if}\; \texttt{n}\; \text{is a number like} 

   412   \ldots \pcode{-2}, \pcode{-1}, \pcode{0}, \pcode{1},

   413 \pcode{2}\ldots{}\\

   414 $\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{+}\, 

   415                     \texttt{e}_\texttt{2}, env)$ & 

   416   $\dn$ & $\textit{eval\_exp}(\texttt{e}_\texttt{1}, env) + 

   417            \textit{eval\_exp}(\texttt{e}_\texttt{2}, env)$\\

   418 $\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{*}\, 

   419                     \texttt{e}_\texttt{2}, env)$ & 

   420   $\dn$ & $\textit{eval\_exp}(\texttt{e}_\texttt{1}, env) * 

   421            \textit{eval\_exp}(\texttt{e}_\texttt{2}, env)$\\

   422 $\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{=}\, 

   423                     \texttt{e}_\texttt{2}, env)$ & 

   424   $\dn$ & $\begin{cases}

   425   1 & \text{if}\;\textit{eval\_exp}(\texttt{e}_\texttt{1}, env) =

   426                  \textit{eval\_exp}(\texttt{e}_\texttt{2}, env)\\

   427   0 & \text{otherwise}

   428   \end{cases}$\\

   429 $\textit{eval\_exp}(\texttt{x}, env)$ & $\dn$ & $env(x)$      

   430 \end{tabular}

   431 \end{center}

   432  

   433 \noindent This environment $env$ also acts like a map: it

   434 associates variable names with the current value. In the

   435 clause for variables, we therefore consult this environment

   436 and return whatever value is currently stored for this

   437 variable. This is written $env(x)$ indicating that the

   438 environment acts like a function. If we call the function with

   439 $x$ we obtain the corresponding number. What happens if an

   440 environment does not contain any value for, say, the variable

   441 $x$. Well, then our interpreter just crashes, or will raise an

   442 exception. In this case we had a ``bad'' program that tried to

   443 use a variable before it was initialised. With the second

   444 version of \textit{eval\_exp} we completed our definition for

   445 evaluating expressions.

   446  

   447 Next comes the evaluation function for statements. We define

   448 this function in such a way that we evaluate a whole sequence

   449 of statements. Assume a program $p$ and its preprocessed 

   450 snippets $sn$. Then we define:

   451 

   452 \begin{center}

   453 \begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}

   454 $\textit{eval\_stmts}([], env)$ & $\dn$ & $env$\\

   455 $\textit{eval\_stmts}(\texttt{label:}\;rest, env)$ &

   456   $\dn$ & $\textit{eval\_stmts}(rest, env)$ \\ 

   457 $\textit{eval\_stmts}(\texttt{x\,:=\,e}\;rest, env)$ & 

   458   $\dn$ & $\textit{eval\_stmts}(rest, 

   459            env[x := \textit{eval\_exp}(\texttt{e}, env)])$\\  

   460 $\textit{eval\_stmts}(\texttt{jmp?\,e\,lbl}\;rest, env)$ 

   461  & $\dn$ & $\begin{cases}\begin{array}{@{}l@{\hspace{-12mm}}r@{}}

   462  \textit{eval\_stmts}(sn(\texttt{lbl}), env)\\ 

   463  & \text{if}\;\textit{eval\_exp}(\texttt{e}, env) = 1\\

   464  \textit{eval\_stmts}(rest, env) & \text{otherwise}\\

   465  \end{array}\end{cases}$\\

   466 $\textit{eval\_stmts}(\texttt{goto\,lbl}\;rest, env)$ 

   467  & $\dn$ & $\textit{eval\_stmts}(sn(\texttt{lbl}), env)$            

   468 \end{tabular}

   469 \end{center}

   470 

   471 

   472 

   473 

   474 

   475 

   476 

   477