--- a/handouts/ho09.tex Wed Dec 10 23:50:35 2014 +0000
+++ b/handouts/ho09.tex Thu Dec 11 23:51:08 2014 +0000
@@ -11,7 +11,7 @@
If we want to improve the safety and security of our programs,
we need a more principled approach to programming. Testing is
-good, but as Dijkstra famously said:
+good, but as Dijkstra famously wrote:
\begin{quote}\it
``Program testing can be a very effective way to show the
@@ -41,7 +41,7 @@
Static analysis is a technique that checks properties of a
program without actually running the program. This should
raise alarm bells with you---because almost all interesting
-properties about programs are equivalent to the halting
+properties about programs are equivalent to the halting
problem, which we know is undecidable. For example estimating
the memory consumption of programs is in general undecidable,
just like the halting problem. Static analysis circumvents
@@ -60,9 +60,11 @@
\subsubsection*{A Simple, Idealised Programming Language}
Our starting point is a small, idealised programming language.
-This language, amongst other things, contains variables
-holding integers. We want to find out what the sign of these
-integers will be when the program runs. This sign-analysis
+It is idealised because we cut several corners in comparison
+with real programming languages. The language we will study
+contains, amongst other things, variables holding integers. We
+want to find out what the sign of these integers (positive or
+negative) will be when the program runs. This sign-analysis
seems like a very simple problem, but it will turn out even
such simple problems, if approached naively, are in general
undecidable, just like Turing's halting problem. I let you
@@ -74,7 +76,7 @@
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
-buffer-overflow attacks because they add underflow and
+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.
@@ -134,7 +136,9 @@
marked with the label \pcode{done}. If \pcode{n} is not zero,
we multiply the content of \pcode{a} by \pcode{n}, decrease
\pcode{n} by one and jump back to the beginning of the loop,
-marked with the label \pcode{top}.
+marked with the label \pcode{top}. Another program in our
+language is shown in Figure~\ref{fib}. I let you think what it
+calculates.
\begin{figure}[t]
\begin{lstlisting}[numbers=none,
@@ -151,23 +155,38 @@
goto top
done:
\end{lstlisting}
-\label{A mystery program in our idealised programming language.}
+\caption{A mystery program in our idealised programming language.
+Try to find out what it calculates! \label{fib}}
\end{figure}
Even if our language is rather small, it is still Turing
-complete---so rather powerful. However, discussing this more
-would lead us to far astray.
+complete---meaning quite powerful. However, discussing this
+fact in more detail would lead us too far astray. Clearly, our
+programming is rather low-level and not very comfortable for
+writing programs. It is inspired by machine code, which is the
+code that is actually executed by a CPU. So a more interesting
+question is what is missing in comparison with real machine
+code? Well, not much\ldots{}in principle. Real machine code,
+of course, contains many more arithmetic instructions (not
+just addition and multiplication) and many more conditional
+jumps. We could add these to our language if we wanted, but
+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
+precision, 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 numbers of
+variables in our programs is unlimited, while memory, of
+course, is always limited somehow on any actual machine. To
+sum up, our language might look very simple, but it is not
+completely removed from practically relevant issues.
-What would be missing in comparison with real
-(low-level machine) code? Well, the numbers we assume to be
-arbitrary precision, which is not the case in real code. There
-basic number formats have a rang and might over-run or
-under-run from this range. Our assumption about variables,
-does not correspond to actual registers, which are only
-limited on real hardware. Obviously, real code has richer
-operations than just addition, multiplication and equality.
-But this are not really essential limitations of our simple
-examples.
+
+\subsubsection*{An Interpreter}
+
+Designing a language is like being god: you can say what
+each part of the program should mean.
\end{document}