# HG changeset patch # User Christian Urban # Date 1418917879 0 # Node ID e1e0f78baa705362c1b901cd4338b0222cb12605 # Parent 619073c376494aa6a0e1a624dacf593422d7b236 updated diff -r 619073c37649 -r e1e0f78baa70 handouts/ho09.pdf Binary file handouts/ho09.pdf has changed 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: