|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. (Was: order of argument evaluation in C++, etc. firstname.lastname@example.org (1995-09-05)|
|From:||email@example.com (Henry Baker)|
|References:||95-07-068 95-08-195 95-09-030|
|Date:||Tue, 5 Sep 1995 01:40:00 GMT|
firstname.lastname@example.org (Adrian Johnstone) 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
> : 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.
Alias detection should be at least as hard as ML type inference, which
is provably exponential, worst case -- i.e., _harder_ than NP-complete.
Alias detection can be performed by a variant of ML type inference
ftp://ftp.netcom.com/pub/hb/hbaker/Share-Unify.html (also .ps.Z)
> The thing that makes C a nightmare for optimisation is the
> all-pervading nature of pointers along with the widespread use of void
> pointers which can implicitly cast all over the place.
He that is without Scheme, let him cast the first pointer...
> In the not so distant future, all common computers will use
> superscalar processors of one form or another, and I predict that the
> detailed dataflow analysis required to get the best out of these
> machines will mandate a move towards languages which are easier to
> analyse, that is with restricted use of pointers and possibly a
> complete lack of side effects.
> The time has surely now come when we need to apply the same process to
> data access. After all, what is a pointer but a goto within a data
> structure? Actually programming with side effect reduced languages is
> not so hard, so why on earth are we making things so difficult for our
> The most pressing question, of course, is what the new, side-effect
> reduced, language should be called.
It is currently called 'ML', short for 'Muzzled Lisp' ;-).
You might also check on the latest work by Phil Wadler on integrating
linear types into type inference, and into the language 'Clean', which
also provides for linear types.
Return to the
Search the comp.compilers archives again.