--- a/handouts/ho09.tex Mon Dec 08 07:14:28 2014 +0000
+++ b/handouts/ho09.tex Mon Dec 08 11:14:33 2014 +0000
@@ -51,10 +51,10 @@
decidable\ldots{}for example we could always say \emph{don't
know}. Of course this would be silly. The point is that we
should be striving for a method that answers as often as
-possible \emph{yes} or \emph{no}---just in cases when it is
-too difficult we fall back on the \emph{don't-know}-answer.
-This might sound all like abstract nonsense. Therefore let us
-look at a concrete example.
+possible either \emph{yes} or \emph{no}---just in cases when
+it is too difficult we fall back on the
+\emph{don't-know}-answer. This might sound all like abstract
+nonsense. Therefore let us look at a concrete example.
\subsubsection*{A Simple, Idealised Programming Language}
@@ -63,15 +63,19 @@
This language contains variables holding integers. We want to
find out what the sign of these integers will be when the
program runs. This seems like a very simple problem, but it
-will turn out even such a simple analysis is in general
-undecidable, just like Turing's halting problem. Is it an
-interesting problem? Well, 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 buffer-overflow attacks because
-they add bound checks everywhere. This could potentially
-drastically speed up the generated code.
+will turn out even such a simple analysis if approached
+naively is in general undecidable, just like Turing's halting
+problem. I let you think why?
+
+
+Is sign-analysis of variables an interesting problem? Well,
+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
+buffer-overflow attacks because they add bound checks
+everywhere. This could potentially drastically speed up the
+generated code.
Since we want to