diff -r 5a6e8b7d20f7 -r efad8155513f handouts/ho09.tex --- 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