--- a/handouts/ho09.tex Wed Dec 31 16:43:22 2014 +0000
+++ b/handouts/ho09.tex Thu Jan 01 11:41:48 2015 +0000
@@ -181,13 +181,12 @@
do not have this at all. This is actually a more serious
simplification because we assume numbers to be arbitrary small
or large, which is not the case with real machine code. In
-real code basic number formats have a range and might
-over-flow or under-flow from this range. Also the number of
+real machine code, basic number formats have a range and might
+over-flow or under-flow this range. Also the number of
variables in our programs is potentially unlimited, while
-memory in an actual computer, of course, is always limited
-somehow on any actual. To sum up, our language might look
-ridiculously simple, but it is not far removed from
-practically relevant issues.
+memory in an actual computer, of course, is always limited. To
+sum up, our language might look ridiculously simple, but it is
+not too far removed from practically relevant issues.
\subsubsection*{An Interpreter}
@@ -265,16 +264,17 @@
clause, we have to distinguish the case where the first
statement is a label or not. As said before, if not, then we
just ``throw away'' the label and recursively calculate the
-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 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
+snippets for the rest of the program (the otherwise clause).
+If yes, then we do the same, but also update the map so that
+$label$ now points to the rest of the statements (the if
+clause). This looks all realtively straightforward, but there
+is one small problem we need 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)$
@@ -365,16 +365,16 @@
\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
+\noindent While this should look all rather intuitive`, 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 encounter 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
@@ -389,25 +389,25 @@
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
+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.
+third clause and equality in the fourth clause.
-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 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}, written $env$, as an additional input
-argument to our \textit{eval\_exp} function.
+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 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
+down 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},
+written $env$, as an additional input argument to our
+\textit{eval\_exp} function.
\begin{center}
\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
@@ -435,8 +435,8 @@
\end{center}
\noindent This environment $env$ also acts like a map: it
-associates variable with their current values. For example
-߆after evaluating the first two lines in our factorial
+associates variables with their current values. For example
+after evaluating the first two lines in our factorial
program, such an environment might look as follows
\begin{center}
@@ -449,14 +449,14 @@
\noindent Again I highlighted 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
+This is written $env(x)$---meaning 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
more precisely 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 done this. In a
-real programming language we would of course try a bit harder
+real programming language, we would of course try a bit harder
and for example give an error at compile time, or design our
language in such a way that this can never happen. With the
second version of \textit{eval\_exp} we completed our
@@ -492,7 +492,7 @@
return the environment. The second clause is for when the next
statement is a label. That means the program is of the form
$\texttt{label:}\;rest$ where the label is some string and
-$rest$ stands for all following statement. This case is easy,
+$rest$ stands for all following statements. This case is easy,
because our evaluation function just discards the label and
evaluates the rest of the statements (we already extracted all
important information about labels when we pre-processed our
@@ -506,16 +506,17 @@
This gives us a number. Then we assign this number to the
variable $x$ in the environment. This modified environment
will be used to evaluate the rest of the program. The fourth
-clause is for the unconditional jump to a label. That means we
-have to look up in our snippets map $sn$ what are the next
-statements for this label are. Therefore we will continue with
-evaluating, not with the rest of the program, but with the
-statements stored in the snippets-map under the label
-$\texttt{lbl}$. The fifth clause for conditional jumps is
-similar, but in order to make the jump we first need to
-evaluate the expression $\texttt{e}$ in order to find out
-whether it is $1$. If yes, we jump, otherwise we just continue
-with evaluating the rest of the program.
+clause is for the unconditional jump to a label, called
+\texttt{lbl}. That means we have to look up in our snippets
+map $sn$ what are the next statements for this label.
+Therefore we will continue with evaluating, not with the rest
+of the program, but with the statements stored in the
+snippets-map under the label $\texttt{lbl}$. The fifth clause
+for conditional jumps is similar, but to decide whether to
+make the jump we first need to evaluate the expression
+$\texttt{e}$ in order to find out whether it is $1$. If yes,
+we jump, otherwise we just continue with evaluating the rest
+of the program.
Our interpreter works in two stages: First we pre-process our
program generating the snippets map $sn$, say. Second we call
@@ -544,30 +545,29 @@
\end{center}
\noindent While the discussion above should have illustrated
-the ideas, in order to do some serious calculation we clearly
+the ideas, in order to do some serious calculations, we clearly
need to implement the interpreter.
-\subsubsection*{Code of the Interpreter}
+\subsubsection*{Scala Code for the Interpreter}
Functional programming languages are very convenient for
-implementations of interpreters. A convenient choice for a
-functional programming language is Scala. This is a
-programming language that combines functional and
-object-oriented programming-styles. It has received in the
-last five years or so quite a bit of attention. One reason for
-this attention is that, like the Java programming language,
-Scala compiles to the Java Virtual Machine (JVM) and therefore
-Scala programs can run under MacOSX, Linux and
-Windows.\footnote{There are also experimental backends for
-Android and JavaScript.} Unlike Java, however, Scala often
-allows programmers to write very concise and elegant code.
-Some therefore say Scala is the much better Java. A number of
-companies, The Guardian, Twitter, Coursera, FourSquare,
-LinkedIn to name a few, either use Scala exclusively in
-production code, or at least to some substantial degree. If
-you want to try out Scala yourself, the Scala compiler can be
-downloaded from
+implementations of interpreters. A good choice for a
+functional programming language is Scala, a programming
+language that combines functional and object-oriented
+programming-styles. It has received in the last five years or
+so quite a bit of attention. One reason for this attention is
+that, like the Java programming language, Scala compiles to
+the Java Virtual Machine (JVM) and therefore Scala programs
+can run under MacOSX, Linux and Windows.\footnote{There are
+also experimental backends for Android and JavaScript.} Unlike
+Java, however, Scala often allows programmers to write very
+concise and elegant code. Some therefore say Scala is the much
+better Java. A number of companies, The Guardian, Twitter,
+Coursera, FourSquare, LinkedIn to name a few, either use Scala
+exclusively in production code, or at least to some
+substantial degree. If you want to try out Scala yourself, the
+Scala compiler can be downloaded from
\begin{quote}
\url{http://www.scala-lang.org}