Re: Death by pointers. (Was: order of argument evaluation in C++, etc.) (Henry Baker)
Tue, 5 Sep 1995 01:40:00 GMT

          From comp.compilers

Related articles
Order of argument evaluation in C++, etc. (1995-07-08)
Re: Order of argument evaluation in C++, etc. (1995-08-25)
Death by pointers. (Was: order of argument evaluation in C++, etc.) (1995-08-30)
Re: Death by pointers. (Was: order of argument evaluation in C++, etc. (1995-09-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Henry Baker)
Keywords: analysis, optimize
Organization: nil organization
References: 95-07-068 95-08-195 95-09-030
Date: Tue, 5 Sep 1995 01:40:00 GMT (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 (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:


Post a followup to this message

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