--- a/handouts/ho09.tex Thu Dec 18 15:51:19 2014 +0000
+++ b/handouts/ho09.tex Fri Dec 19 23:24:37 2014 +0000
@@ -75,14 +75,14 @@
yes---if a compiler can find out that for example a variable
will never be negative and this variable is used as an index
for an array, then the compiler does not need to generate code
-for an underflow-test. Remember some languages are immune to
+for an underflow-check. Remember some languages are immune to
buffer-overflow attacks, but they need to add underflow and
-overflow checks everywhere. If the compiler can omit the
-underflow test, for example, then this can potentially
-drastically speed up the generated code. According to the John
-Regehr, an expert in the field of compilers, overflow checks
-can cause 5-10\% slowdown, and in some languages even 100\%
-for tight loops.\footnote{\url{http://blog.regehr.org/archives/1154}}
+overflow checks everywhere. According to Regehr, an expert in
+the field of compilers, overflow checks can cause 5-10\%
+slowdown, and in some languages even 100\% for tight
+loops.\footnote{\url{http://blog.regehr.org/archives/1154}} If
+the compiler can omit the underflow check, for example, then
+this can potentially drastically speed up the generated code.
What do programs in our simple programming language look like?
The following grammar gives a first specification:
@@ -264,12 +264,13 @@
snippets for the rest of the program. If yes, then we do the
same, but also update the map so that $label$ now points to
the rest of the statements. There is one small problem we need
-to overcome: our two programs have no label as \emph{entry
-point}---that is where the execution starts. We usually assume
-that the first statement will be run first. To make this the
-default, it is convenient if we add to all our programs a
-default label, say \pcode{""} (the empty string). With this we
-can define our pre-processing of programs as follows
+to overcome: our two programs shown so far have no label as
+\emph{entry point}---that is where the execution is supposed
+to start. We usually assume that the first statement will be
+run first. To make this the default, it is convenient if we
+add to all our programs a default label, say \pcode{""} (the
+empty string). With this we can define our pre-processing of
+programs as follows
\begin{center}
$\textit{preproc}(prog) \dn \textit{snippets}(\pcode{"":}\;\; prog)$
@@ -368,7 +369,7 @@
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
+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
@@ -394,15 +395,15 @@
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
+Clearly, an expression can contain variables. So far we have
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.
+\emph{environment}, written $env$, as an additional input
+argument to our \textit{eval\_exp} function.
\begin{center}
\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
@@ -430,17 +431,27 @@
\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
+associates variable with their current values. For example
+such an environment might look as follows
+
+\begin{center}
+\begin{tabular}{ll}
+$\fbox{\texttt{a}} \mapsto \texttt{1}$ &
+$\fbox{\texttt{n}} \mapsto \texttt{5}$
+\end{tabular}
+\end{center}
+
+\noindent Again I hilighted the keys. In the clause for
+variables, we can therefore consult this environment and
+return whatever value is currently stored for this variable.
+This is written $env(x)$. If we query this map with $x$ we
+obtain the corresponding number. You might ask 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 have a ``bad'' program
+that tried to use a variable before it was initialised. The
+programmer should not have don this. With the second version
+of \textit{eval\_exp} we completed our definition for
evaluating expressions.
Next comes the evaluation function for statements. We define