Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!asuvax!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: C strongly typed?
Message-ID: <18885@megaron.cs.arizona.edu>
Date: 12 Mar 90 23:08:47 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 39

In article  <0501@sheol.UUCP> throopw@sheol.UUCP (Wayne Throop) writes:
>> From: steven@cwi.nl (Steven Pemberton)
>
>> Examples of operations that could be reduced to compile-time type
>> errors are: dereferencing nil, array indexing errors and sub-range
>> errors in general.
>
>Well, since dereferencing nil is a sort of range check, I suppose
>that it could be checked for at compile time as easily as the others.
>But it seems to me that all of these can be reduced to solving
>the halting problem.  Even if I'm wrong about that, the problem
>is quite a bit beyond the current state of the art of static
>flow-of-control analysis, is it not?

I didn't reply to the original because I expected several other people
to reply.  In fact, dereferencing nil and range checks _can_ be
reduced to the halting problem.  The trick is to insert a
nil-dereference/range violation at each exit point.  More obviously,
how do you check the following?

	i := read_integer(input_file);
	x := a[i];

The answer is that you can't.  You have to know what the input to the
program is going to be.

However, you _can_ do such an analysis making worst-case or best-case
assumptions, getting an approximation to the answer.  That is, there
are a lot of cases where you can statically analyse a program and say
at a given place that (worst-case) ``there are some inputs for which
this may be an error'', or that (best-case) ``for all inputs this
will be an error''.  What you cannot do is say that ``there are some
inputs for which this will be an error'', and guarantee that you have
found all points in the program at which this is true.
-- 
					David Gudeman
Department of Computer Science
The University of Arizona        gudeman@cs.arizona.edu
Tucson, AZ 85721                 noao!arizona!gudeman