sen-material: comparison handouts/ho09.tex

equal deleted inserted replaced

-:3f0738fc8230
+:b46f86d95967
 complexity is really beside the point here. Furthermore, real
 machine code has many instructions for manipulating memory. We
 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
+real machine code, basic number formats have a range and might
-over-flow or under-flow from this range. Also the number of
+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
+memory in an actual computer, of course, is always limited. To
-somehow on any actual. To sum up, our language might look
+sum up, our language might look ridiculously simple, but it is
-ridiculously simple, but it is not far removed from
+not too far removed from practically relevant issues.
-practically relevant issues.
 \subsubsection*{An Interpreter}
 Designing a language is like playing god: you can say what
 \noindent In the first clause we just return the empty map for
 the program that does not contain any statement. In the second
 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
+snippets for the rest of the program (the otherwise clause).
-same, but also update the map so that $label$ now points to
+If yes, then we do the same, but also update the map so that
-the rest of the statements. There is one small problem we need
+$label$ now points to the rest of the statements (the if
-to overcome: our two programs shown so far have no label as
+clause). This looks all realtively straightforward, but there
-\emph{entry point}---that is where the execution is supposed
+is one small problem we need to overcome: our two programs
-to start. We usually assume that the first statement will be
+shown so far have no label as \emph{entry point}---that is
-run first. To make this the default, it is convenient if we
+where the execution is supposed to start. We usually assume
-add to all our programs a default label, say \pcode{""} (the
+that the first statement will be run first. To make this the
-empty string). With this we can define our pre-processing of
+default, it is convenient if we add to all our programs a
-programs as follows
+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)$
 \end{center}
 0 & \text{otherwise}
 \end{cases}$
 \end{tabular}
 \end{center}
-\noindent While this should look all relatively
+\noindent While this should look all rather intuitive`, still
-straightforward, still be very careful. There is a subtlety
+be very careful. There is a subtlety which can be easily
-which can be easily overlooked: The function
+overlooked: The function \textit{eval\_exp} takes an
-\textit{eval\_exp} takes an expression of our programming
+expression of our programming language as input and returns a
-language as input and returns a number as output. Therefore
+number as output. Therefore whenever we encounter a number in
-whenever we have a number in our program, we just return this
+our program, we just return this number---this is defined in
-number---this is defined in the first clause above. Whenever
+the first clause above. Whenever we encounter an addition,
-we encounter an addition, well then we first evaluate the
+well then we first evaluate the left-hand side
-left-hand side $\texttt{e}_\texttt{1}$ of the addition (this
+$\texttt{e}_\texttt{1}$ of the addition (this will give a
-will give a number), then evaluate the right-hand side
+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
 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
+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
+third clause and equality in the fourth clause.
-wrote at the beginning of this section about being god when
-designing a programming language. You can see this here: we
+Remember I wrote at the beginning of this section about being
-need to give meaning to symbols.
+god when designing a programming language. You can see this
+here: we need to give meaning to symbols. At the moment
-At the moment however, we are a poor fallible god. Look again
+however, we are a poor fallible god. Look again at the grammar
-at the grammar of our programming language and our definition.
+of our programming language and our definition. Clearly, an
-Clearly, an expression can contain variables. So far we have
+expression can contain variables. So far we have ignored them.
-ignored them. What should our interpreter do with variables?
+What should our interpreter do with variables? They might
-They might change during the evaluation of a program. For
+change during the evaluation of a program. For example the
-example the variable \pcode{n} in the factorial program counts
+variable \pcode{n} in the factorial program counts down from 5
-down from 5 up to 0. How can we improve our definition above
+down to 0. How can we improve our definition above to give also
-to give also an answer whenever our interpreter encounters a
+an answer whenever our interpreter encounters a variable in an
-variable in an expression? The solution is to add an
+expression? The solution is to add an \emph{environment},
-\emph{environment}, written $env$, as an additional input
+written $env$, as an additional input argument to our
-argument to our \textit{eval\_exp} function.
+\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}
 $\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 with their current values. For example
+associates variables with their current values. For example
-ß†after evaluating the first two lines in our factorial
+after evaluating the first two lines in our factorial
 program, such an environment might look as follows
 \begin{center}
 \begin{tabular}{ll}
 $\fbox{\texttt{a}} \mapsto \texttt{1}$ &
 \end{center}
 \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
+This is written $env(x)$---meaning we query this map with $x$
-obtain the corresponding number. You might ask what happens if
+we obtain the corresponding number. You might ask what happens
-an environment does not contain any value for, say, the
+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
 definition for evaluating expressions.
 \noindent The first clause is for the empty program, or when
 we arrived at the end of the program. In this case we just
 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
 programs and generated the snippets). The third clause is for
 variable assignments. Again we just evaluate the rest for the
 of the environment we first evaluate the expression
 $\texttt{e}$ using our evaluation function for expressions.
 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
+clause is for the unconditional jump to a label, called
-have to look up in our snippets map $sn$ what are the next
+\texttt{lbl}. That means we have to look up in our snippets
-statements for this label are. Therefore we will continue with
+map $sn$ what are the next statements for this label.
-evaluating, not with the rest of the program, but with the
+Therefore we will continue with evaluating, not with the rest
-statements stored in the snippets-map under the label
+of the program, but with the statements stored in the
-$\texttt{lbl}$. The fifth clause for conditional jumps is
+snippets-map under the label $\texttt{lbl}$. The fifth clause
-similar, but in order to make the jump we first need to
+for conditional jumps is similar, but to decide whether to
-evaluate the expression $\texttt{e}$ in order to find out
+make the jump we first need to evaluate the expression
-whether it is $1$. If yes, we jump, otherwise we just continue
+$\texttt{e}$ in order to find out whether it is $1$. If yes,
-with evaluating the rest of the program.
+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
 the evaluation function with the default entry point and the
 empty environment:
 $\fbox{\texttt{n}} \mapsto \texttt{0}$
 \end{tabular}
 \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
+implementations of interpreters. A good choice for a
-functional programming language is Scala. This is a
+functional programming language is Scala, a programming
-programming language that combines functional and
+language that combines functional and object-oriented
-object-oriented programming-styles. It has received in the
+programming-styles. It has received in the last five years or
-last five years or so quite a bit of attention. One reason for
+so quite a bit of attention. One reason for this attention is
-this attention is that, like the Java programming language,
+that, like the Java programming language, Scala compiles to
-Scala compiles to the Java Virtual Machine (JVM) and therefore
+the Java Virtual Machine (JVM) and therefore Scala programs
-Scala programs can run under MacOSX, Linux and
+can run under MacOSX, Linux and Windows.\footnote{There are
-Windows.\footnote{There are also experimental backends for
+also experimental backends for Android and JavaScript.} Unlike
-Android and JavaScript.} Unlike Java, however, Scala often
+Java, however, Scala often allows programmers to write very
-allows programmers to write very concise and elegant code.
+concise and elegant code. Some therefore say Scala is the much
-Some therefore say Scala is the much better Java. A number of
+better Java. A number of companies, The Guardian, Twitter,
-companies, The Guardian, Twitter, Coursera, FourSquare,
+Coursera, FourSquare, LinkedIn to name a few, either use Scala
-LinkedIn to name a few, either use Scala exclusively in
+exclusively in production code, or at least to some
-production code, or at least to some substantial degree. If
+substantial degree. If you want to try out Scala yourself, the
-you want to try out Scala yourself, the Scala compiler can be
+Scala compiler can be downloaded from
-downloaded from
 \begin{quote}
 \url{http://www.scala-lang.org}
 \end{quote}

changeset 368	b46f86d95967
parent 366	34a8f73b2c94
child 369	6c7996b6b471