Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site sdcrdcf.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!godot!harvard!talcott!panda!genrad!decvax!ittvax!dcdwest!sdcsvax!sdcrdcf!markb
From: markb@sdcrdcf.UUCP (Mark Biggar)
Newsgroups: net.lang
Subject: Re: levelheight: automatic "nil pointer" handling
Message-ID: <1721@sdcrdcf.UUCP>
Date: Tue, 29-Jan-85 12:27:14 EST
Article-I.D.: sdcrdcf.1721
Posted: Tue Jan 29 12:27:14 1985
Date-Received: Sat, 2-Feb-85 09:04:49 EST
References: <2340@hplabsc.UUCP> <4948@utzoo.UUCP> <6292@boring.UUCP> <536@mako.UUCP> <6881@watdaisy.UUCP>
Reply-To: markb@sdcrdcf.UUCP (Mark Biggar)
Distribution: net
Organization: System Development Corp. R+D, Santa Monica
Lines: 19
Summary: nil pointers, static checking

The problem of statically determining if a program will ever try to
dereference a nil pointer is exactly equivalent to the Turing
halting problem.  In general any problem of the form "Does a program
ever do X" (except for trivial things like "Does the program execute
its first statement") is unsolvable.

In the case of nil pointer deferencing this can be shown as follows:

Assume you have a program T that that will statically check that a given
input program will never dereference a nil pointer.  Now, modify any
program X which passes the test T in the following way:  at each possible
point in program X where X could halt (just before the end of main, before
and exit or abort, etc.) add a dereference to a nil pointer making a new
program X'.  X' now has the property that if it passes test T it never halts
and if it fails test T it does halt.  Thus, T can be used to solve the Turing
halting problem.  As this is impossible, no such program T can exist.

Mark Biggar
{allegra,burdvax,cbosgd,hplabs,ihnp4,akgua,sdcsvax}!sdcrdcf!markb