|Order of argument evaluation in C++, etc. email@example.com (1995-07-08)|
|Re: Order of argument evaluation in C++, etc. firstname.lastname@example.org (1995-08-25)|
|Death by pointers. (Was: order of argument evaluation in C++, etc.) email@example.com (1995-08-30)|
|Re: Death by pointers. firstname.lastname@example.org (1995-09-05)|
|Re: Death by pointers. email@example.com (1995-09-05)|
|Re: Death by pointers. firstname.lastname@example.org (1995-09-06)|
|Re: Death by pointers. email@example.com (1995-09-11)|
|Re: Death by pointers. firstname.lastname@example.org (1995-09-12)|
|Re: Death by pointers. email@example.com (1995-09-12)|
|Re: Death by pointers. firstname.lastname@example.org (1995-09-13)|
|Re: Death by pointers. ECE@dwaf-hri.pwv.gov.za (John Carter) (1995-09-23)|
|[1 later articles]|
|From:||email@example.com (David Whitten)|
|Organization:||NETCOM On-line Communication Services (408 261-4700 guest)|
|References:||95-07-068 95-08-195 95-09-030|
|Date:||Tue, 5 Sep 1995 15:48:38 GMT|
Adrian Johnstone (firstname.lastname@example.org) wrote:
: On the sub-issue of alias detection as a problem in argument evaluation:
: : Unless I'm very much mistaken, alias identification is an insoluble
: : problem, and flagging order dependencies in expressions runs straight into
: : that wall.
: : Well, I guess it's insoluble in general (no my area of expertise), but it is
: : certainly possible and useful. It's clear that this is really what we're
: : talking about.
: In the C language, alias detection in the presecence of recursive data
: structures (i.e. linked lists and up) is an NP-complete problem, which
: certainly meets my definition of insoluble ;-). I'm not at home right
: now so I can't find the reference but it's derived in someone's PhD
: theis. Actually it's not at all surprising if you think about it. I
: would rather suppose that this result is true in any pointer-using
: language, including Pascal et al.
So the NP-Complete problem only occurs with languages that define
recursive data structures? What about a language where the only
aliasing that can occur is when parameter passing exists? (and
no variables may store explicit addresses?)
In this language, assume you can pass components of bundle/record/struct's
as parameters, and that you can pass store the NAME of a variable as the
value of a variable (and lookup a variable's value using its name later).
I'm sure the storage of Names and lookup of a name is very similar to
pointers, but doesn't have the same implications as real address pointers
in terms of garbage collection, but the only aliasing happening through
parameter passing seems to limit the alias detection problem to me.
I'm posting because I expect someone who actually has read these
results might be able to elaborate whether this limits the alias detection
problem sufficiently to make it solvable.
David (Whitten@netcom.com) (214) 437-5255
[Seems to me it'd be easy enough to construct alias problems which reduce to
the halting problem. -John]
Return to the
Search the comp.compilers archives again.