Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Optimizing
Message-ID: <14281:Nov1605:03:5490@kramden.acf.nyu.edu>
Date: 16 Nov 90 05:03:54 GMT
References: <8515:Nov1522:16:1490@kramden.acf.nyu.edu> <6083@lanl.gov>
Organization: IR
Lines: 52

In article <6083@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> From article <8515:Nov1522:16:1490@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> > [...]        In the ``array references cannot be made optimal'' thread I
> > gave something that might stand for a proof of my assertions. Jim admits
> > that I'm right too.
> False.  But read the thread yourself.  The are _optimizations_ that
> the compiler can't do.  They must, therefore, be expressed by the
> human programmer.  Pointers are _not_ inherently superior to
> arrays for expressing these improvements.

Again, you must be defining ``pointers'' and ``arrays'' differently from
the rest of the world.

You have admitted my point that no algorithm can determine the optimal
choice of whether to store &(x[0]) or &(x[1]), because no algorithm can
determine for all programs which pointer will be used more. I'll even
quote the article for you if you want.

This is just a special case of the assertion that no algorithm can solve
the addition chain problem in a general computation. More precisely, the
fundamental difference between pointers and arrays is that the former
can find &(x[a]) given &(x[b]), while without pointers this can only be
done for &(x[0]) (and in fact &(x[b]) can only be stored for b = 0). No
algorithm can convert an optimal pointer-free program into an optimal
pointer version. Do you agree with that assertion?

To put it differently, it is impossible to optimize array references
unless there's some way to express array shifts (pointer arithmetic).
Do you agree with that assertion?

Now Fortran, Pascal, and Ada have arrays. They can't express array
shifts. Agreed? C can express array shifts. Agreed?

Therefore arrays cannot be optimized as well as pointers in some
programs. Agreed?

You have said the opposite of the above statement. Agreed? (I'll quote
it for you if you want.) I can think of two reasons why: 1. When you
said ``array'' you didn't mean array as in Fortran, or Pascal, or Ada.
2. You simply didn't think enough to realize that optimizing array
references is equivalent to solving the halting problem.

Now I'm tempted to believe #2, since in several articles before I posted
the outline of my proof and the proof itself, you challenged my
assertion that optimizing array references is equivalent to solving the
halting problem. (I'll quote it for you if you want.)

But I'll be charitable. I'm perfectly willing to believe that you have
simply been using a different definition of ``array'' from the rest of
the world (except people who use the new Fortran). So which is it?

---Dan