Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!camelback!volpe
From: volpe@camelback.crd.ge.com (Christopher R Volpe)
Newsgroups: comp.lang.c
Subject: Re: Can analysis detect undefined expressions?
Message-ID: <20574@crdgw1.crd.ge.com>
Date: 14 Jun 91 12:48:44 GMT
References: <1991Jun13.015548.24724@grebyn.com> <1991Jun13.231924.3711@ism.isc.com>
Sender: news@crdgw1.crd.ge.com
Reply-To: volpe@camelback.crd.ge.com (Christopher R Volpe)
Lines: 29

In article <1991Jun13.231924.3711@ism.isc.com>,
willcr@bud.sos.ivy.isc.com (Will Crowder) writes:
|>I'm not sure if it has been proven impossible, and indeed, trivial and
|>obvious violations like "i = i++ + i++" are easy to spot.  However,
|>how would you deal with the case of:
|>
|>   i = (*p)++ + (*q)++;
|>
|>I mean, this statement is perfectly legal and its value defined if
|>p != q.  However, if p == q, then you're once again in deep yogurt as you're
|>modifying the same object twice without an intervening sequence point.
|>
|>I don't know statistics well enough to put this as eloquently as I'd like,
|>but:
|>
|>Determining at compile time of p could ever be equal to q would require
|>exhaustive code path analysis, and this analysis has been shown to take
|>longer than the estimated remaining lifespan of the galaxy for anything
|>over a few lines.  (I can't remember that great quote I heard about it,
|>or I'd put it in my .sig.)

It's not just time consuming, it's theoretically impossible for an
arbitrary program. It's trivial to reduce the halting problem to
this problem, thus showing its undecidability. 
                                       
==================
Chris Volpe
G.E. Corporate R&D
volpecr@crd.ge.com