
diff -r 619073c37649 -r e1e0f78baa70 handouts/ho09.tex
--- 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: 




