49 \emph{yes} and \emph{no}, but also \emph{don't know}. With |
49 \emph{yes} and \emph{no}, but also \emph{don't know}. With |
50 this ``trick'' even the halting problem becomes |
50 this ``trick'' even the halting problem becomes |
51 decidable\ldots{}for example we could always say \emph{don't |
51 decidable\ldots{}for example we could always say \emph{don't |
52 know}. Of course this would be silly. The point is that we |
52 know}. Of course this would be silly. The point is that we |
53 should be striving for a method that answers as often as |
53 should be striving for a method that answers as often as |
54 possible \emph{yes} or \emph{no}---just in cases when it is |
54 possible either \emph{yes} or \emph{no}---just in cases when |
55 too difficult we fall back on the \emph{don't-know}-answer. |
55 it is too difficult we fall back on the |
56 This might sound all like abstract nonsense. Therefore let us |
56 \emph{don't-know}-answer. This might sound all like abstract |
57 look at a concrete example. |
57 nonsense. Therefore let us look at a concrete example. |
58 |
58 |
59 |
59 |
60 \subsubsection*{A Simple, Idealised Programming Language} |
60 \subsubsection*{A Simple, Idealised Programming Language} |
61 |
61 |
62 Our starting point is a small, idealised programming language. |
62 Our starting point is a small, idealised programming language. |
63 This language contains variables holding integers. We want to |
63 This language contains variables holding integers. We want to |
64 find out what the sign of these integers will be when the |
64 find out what the sign of these integers will be when the |
65 program runs. This seems like a very simple problem, but it |
65 program runs. This seems like a very simple problem, but it |
66 will turn out even such a simple analysis is in general |
66 will turn out even such a simple analysis if approached |
67 undecidable, just like Turing's halting problem. Is it an |
67 naively is in general undecidable, just like Turing's halting |
68 interesting problem? Well, yes---if a compiler can find out |
68 problem. I let you think why? |
69 that for example a variable will never be negative and this |
69 |
70 variable is used as an index for an array, then the compiler |
70 |
71 does not need to generate code for an underflow-test. Remember |
71 Is sign-analysis of variables an interesting problem? Well, |
72 some languages are immune to buffer-overflow attacks because |
72 yes---if a compiler can find out that for example a variable |
73 they add bound checks everywhere. This could potentially |
73 will never be negative and this variable is used as an index |
74 drastically speed up the generated code. |
74 for an array, then the compiler does not need to generate code |
|
75 for an underflow-test. Remember some languages are immune to |
|
76 buffer-overflow attacks because they add bound checks |
|
77 everywhere. This could potentially drastically speed up the |
|
78 generated code. |
75 |
79 |
76 Since we want to |
80 Since we want to |
77 |
81 |
78 \begin{multicols}{2} |
82 \begin{multicols}{2} |
79 \begin{plstx}[rhs style=,one per line,left margin=9mm] |
83 \begin{plstx}[rhs style=,one per line,left margin=9mm] |