--- a/handouts/ho09.tex Thu Dec 18 12:00:44 2014 +0000
+++ b/handouts/ho09.tex Thu Dec 18 15:51:19 2014 +0000
@@ -324,29 +324,156 @@
\end{center}
\noindent I highlighted the \emph{keys} in this map. Since
-there are three labels in the factorial program, there are
-three keys. When running the factorial program and
-encountering a jump, then we only have to consult this map, in
-order to find out what the next instruction should be.
+there are three labels in the factorial program (remember we
+added \pcode{""}), there are three keys. When running the
+factorial program and encountering a jump, then we only have
+to consult this snippets-map in order to find out what the
+next instruction should be.
We should now be in the position to define how a program
-should be run. This ``running'' of programs is often called
-\emph{evaluation}. Let us start with the definition for
-how expressions are evaluated. A first attempt is the
-following recursive function:
+should be run. In the context of interpreters, this
+``running'' of programs is often called \emph{evaluation}. Let
+us start with the definition of how expressions are evaluated.
+A first attempt might be the following recursive function:
\begin{center}
\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$\textit{snippets}([])$ & $\dn$ & $\varnothing$\\
-$\textit{snippets}(stmt\;\; rest)$ & $\dn$ &
-$\begin{cases}
- \textit{snippets}(rest)[label := rest] & \text{if}\;stmt = \textit{label:}\\
- \textit{snippets}(rest) & \text{otherwise}
-\end{cases}$
+$\textit{eval\_exp}(\texttt{n})$ & $\dn$ & $n$
+ \qquad\text{if}\; \texttt{n}\; \text{is a number like}
+ \ldots \pcode{-2}, \pcode{-1}, \pcode{0}, \pcode{1},
+\pcode{2}\ldots{}\\
+$\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{+}\,
+ \texttt{e}_\texttt{2})$ &
+ $\dn$ & $\textit{eval\_exp}(\texttt{e}_\texttt{1}) +
+ \textit{eval\_exp}(\texttt{e}_\texttt{2})$\\
+$\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{*}\,
+ \texttt{e}_\texttt{2})$ &
+ $\dn$ & $\textit{eval\_exp}(\texttt{e}_\texttt{1}) *
+ \textit{eval\_exp}(\texttt{e}_\texttt{2})$\\
+$\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{=}\,
+ \texttt{e}_\texttt{2})$ &
+ $\dn$ & $\begin{cases}
+ 1 & \text{if}\;\textit{eval\_exp}(\texttt{e}_\texttt{1}) =
+ \textit{eval\_exp}(\texttt{e}_\texttt{2})\\
+ 0 & \text{otherwise}
+ \end{cases}$
+\end{tabular}
+\end{center}
+
+\noindent While this should look all relatively
+straightforward, still be very careful. There is a subtlety
+which can be easily overlooked: The function
+\textit{eval\_exp} takes an expression of our programming
+language as input and returns a number as output. Therefore
+whenever we have a number in our program, we just return this
+number---this is defined in the first clause above. Whenever
+we encounter an addition, well then we first evaluate the
+left-hand side, $\texttt{e}_\texttt{1}$ of the addition (this
+will give a number), then evaluate the right-hand side
+$\texttt{e}_\texttt{2}$ (this gives another number), and
+finally add both numbers together. Here is the subtlety: on
+the left-hand side of the $\dn$ we have a \texttt{+} (in the
+teletype font) which is the symbol for addition in our
+programming language. On the right-hand side we have $+$ which
+stands for the arithmetic operation from ``mathematics'' of
+adding two numbers. These are rather different concepts---one
+is a symbol (which we made up), and the other a mathematical
+operation. When we will have a look at an actual
+implementation of our interpreter, the mathematical operation
+will be the function for addition from the programming
+language in which we \underline{\smash{implement}} our
+interpreter. While the \texttt{+} is just a symbol that is
+used in our programming language. Clearly we have to use a
+symbol that is a good mnemonic for addition otherwise we will
+confuse the programmers working with our language. Therefore
+we use $\texttt{+}$. A similar choice is made for times in the
+third clause and equality in the fourth clause. Remember I
+wrote at the beginning of this section about being god when
+designing a programming language. You can see this here: we
+need to give meaning to symbols.
+
+At the moment however, we are a poor fallible god. Look again
+at the grammar of our programming language and our definition.
+Clearly, an expression can contain variables. So far we we
+ignored them. What should our interpreter do with variables?
+They might change during the evaluation of a program. For
+example the variable \pcode{n} in the factorial program counts
+down from 5 up to 0. How can we improve our definition above
+to give also an answer whenever our interpreter encounters a
+variable in an expression? The solution is to add an
+\emph{environment}, $env$ as an additional input argument to
+our \textit{eval\_exp} function.
+
+\begin{center}
+\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+$\textit{eval\_exp}(\texttt{n}, env)$ & $\dn$ & $n$
+ \qquad\text{if}\; \texttt{n}\; \text{is a number like}
+ \ldots \pcode{-2}, \pcode{-1}, \pcode{0}, \pcode{1},
+\pcode{2}\ldots{}\\
+$\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{+}\,
+ \texttt{e}_\texttt{2}, env)$ &
+ $\dn$ & $\textit{eval\_exp}(\texttt{e}_\texttt{1}, env) +
+ \textit{eval\_exp}(\texttt{e}_\texttt{2}, env)$\\
+$\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{*}\,
+ \texttt{e}_\texttt{2}, env)$ &
+ $\dn$ & $\textit{eval\_exp}(\texttt{e}_\texttt{1}, env) *
+ \textit{eval\_exp}(\texttt{e}_\texttt{2}, env)$\\
+$\textit{eval\_exp}(\texttt{e}_\texttt{1} \,\texttt{=}\,
+ \texttt{e}_\texttt{2}, env)$ &
+ $\dn$ & $\begin{cases}
+ 1 & \text{if}\;\textit{eval\_exp}(\texttt{e}_\texttt{1}, env) =
+ \textit{eval\_exp}(\texttt{e}_\texttt{2}, env)\\
+ 0 & \text{otherwise}
+ \end{cases}$\\
+$\textit{eval\_exp}(\texttt{x}, env)$ & $\dn$ & $env(x)$
+\end{tabular}
+\end{center}
+
+\noindent This environment $env$ also acts like a map: it
+associates variable names with the current value. In the
+clause for variables, we therefore consult this environment
+and return whatever value is currently stored for this
+variable. This is written $env(x)$ indicating that the
+environment acts like a function. If we call the function with
+$x$ we obtain the corresponding number. What happens if an
+environment does not contain any value for, say, the variable
+$x$. Well, then our interpreter just crashes, or will raise an
+exception. In this case we had a ``bad'' program that tried to
+use a variable before it was initialised. With the second
+version of \textit{eval\_exp} we completed our definition for
+evaluating expressions.
+
+Next comes the evaluation function for statements. We define
+this function in such a way that we evaluate a whole sequence
+of statements. Assume a program $p$ and its preprocessed
+snippets $sn$. Then we define:
+
+\begin{center}
+\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+$\textit{eval\_stmts}([], env)$ & $\dn$ & $env$\\
+$\textit{eval\_stmts}(\texttt{label:}\;rest, env)$ &
+ $\dn$ & $\textit{eval\_stmts}(rest, env)$ \\
+$\textit{eval\_stmts}(\texttt{x\,:=\,e}\;rest, env)$ &
+ $\dn$ & $\textit{eval\_stmts}(rest,
+ env[x := \textit{eval\_exp}(\texttt{e}, env)])$\\
+$\textit{eval\_stmts}(\texttt{jmp?\,e\,lbl}\;rest, env)$
+ & $\dn$ & $\begin{cases}\begin{array}{@{}l@{\hspace{-12mm}}r@{}}
+ \textit{eval\_stmts}(sn(\texttt{lbl}), env)\\
+ & \text{if}\;\textit{eval\_exp}(\texttt{e}, env) = 1\\
+ \textit{eval\_stmts}(rest, env) & \text{otherwise}\\
+ \end{array}\end{cases}$\\
+$\textit{eval\_stmts}(\texttt{goto\,lbl}\;rest, env)$
+ & $\dn$ & $\textit{eval\_stmts}(sn(\texttt{lbl}), env)$
\end{tabular}
\end{center}
+
+
+
+
+
+
\end{document}
%%% Local Variables: