Re: Death by pointers. (Was: order of argument evaluation in C++, etc.)

johnston@imec.be (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
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.


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
> optimisers?


> 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.


--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html


--

Return to the comp.compilers page.
Search the comp.compilers archives again.