Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site spuxll.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!ihnp4!houxm!whuxlm!spuxll!ech
From: ech@spuxll.UUCP (Ned Horvath)
Newsgroups: net.lang
Subject: Re: levelheight: automatic "nil pointer" handling
Message-ID: <611@spuxll.UUCP>
Date: Sun, 27-Jan-85 21:42:53 EST
Article-I.D.: spuxll.611
Posted: Sun Jan 27 21:42:53 1985
Date-Received: Tue, 29-Jan-85 05:54:46 EST
References: <6881@watdaisy.UUCP>
Organization: AT&T Information Systems, South Plainfield NJ
Lines: 21

It is most certainly NOT possible to statically (i.e. at compile time) check
for nil-pointer dereferencing.  To use a somewhat classical argument, suppose
I have a subroutine that emulates a turing machine for one step each time it
is called; if the TM halts, it sets a given pointer to a particular value,
otherwise it leaves it nil.

Obviously I could statically analyze a program containing such a subroutine
for nil-pointer dereferencing only if my compiler had the capability to solve
the halting problem.

Similar arguments (left as an exercise) can be advanced to demonstrate that
static array bounds checking is impossible in principle, or that one cannot
identify unreachable code.

To take a more mundane example, lest the TM Halting problem seem contrived,
imagine a program to search for local optima by relaxation methods.  Such
a program may or may not converge depending on its input -- which is 
presumably not available to the compiler.  A variable which is set when
convergence is reached has a value the compiler certainly cannot predict.

=Ned=