handouts/ho09.tex
changeset 357 5b91f5ad2772
parent 356 e1e0f78baa70
child 359 c90f803dc7ea
--- 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