Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!psuvax1!rutgers!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Answers, Chapter 1: TeX
Message-ID: <4569@lanl.gov>
Date: 31 Oct 90 22:22:06 GMT
References: <27028@megaron.cs.arizona.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 131

From article <27028@megaron.cs.arizona.edu>, by gudeman@cs.arizona.edu (David Gudeman):
> [...]
> You are still comparing apples and oranges.  You are comparing
> "arrays, assumed not to be aliased" with "pointers, assumed to be
> aliased".

Oh, I'm sorry.  I have given this information before, but perhaps you
missed it.  An array is a mapping from one or more bounded index sets
to values of an underlying type.  Each array is assumed distinct from
all others unless _explicitly_ declared otherwise.

Note: such explicit declaration of aliasing must be locally visible
to the compiler at compile time and any attempt to cheat must be
intercepted be load-time checks.

> [...]
> ]Now _with_ the 'aliased' attribute:
> ]   (like the one I'm recommending), then pointers don't give you any
> ]   capability you don't already have _without_ them.  Pointers in such
> ]   a language are neither more powerful, more legible,...
> 
> This, of course, is a matter of opinion.  [...]

The 'soft' words (like 'legible') might be considered opinion, the
statement that pointers provide no more power is a statement of _fact_.

> [...]                                     Maybe to clarify things, you
> could post your definition of "pointer".  [...]

I've done this before too.  Perhaps you missed it.

My definition of pointer is a variable whose value is an address and
has the following operations defined on it:

   Dereferencing to some predefined (for each pointer) type object.
   Comparing to other pointers (of the same underlying type) for equality.
   Assigning to/from other pointers (of the same underlying type)
   Being initialized to some address by an allocation mechanism

This is essentially the definition of Pascal pointers.  In addition,
other operations are defined by some languages:

   Comparing for relative order
   Scaled differences between two pointers
   Scaled sums of a pointer with an integer
   Casting to some other underlying type
   ...

> [...]                                     In particular, I'm
> curious about how you think passing a pointer (C-style) is different
> from passing an array.

I've posted this before too.  A C style pointer (because C has the
capability of scaled address addition) is similar (but not identical
to) the passing of a one dimensional array which is indexed by
integers.  But, the array differs by requiring its bounds to be
passed and by its ability to be multidimensional and by the fact
that it is _not_ aliased or overlapping with any other argument or
global variable without explicit _local_ declaration of the fact.

In fact, my definition of arrays differs from the Fortran definition
only in the fact that I allow array args to be aliased if explicitly
declared so, and Fortran _never_ allows them to be.  Also, I would
recommend that the array bounds be passed implicitly rather than
requiring the user to do it.

> [...]
> ]   ...  Using pointers to simulate these data types
> ]   (sequences for example) deprives the compiler of information which
> ]   _could_ be used to improve the performance of the code.
> 
> I'd also like to know what information this is.  Presumably a complete
> definition of what you mean by "pointer" and "array" will make this
> obvious.

I gave an example of this before too.  Consider the Fortran loop:

      do 10 i=1,N
	 x(1,i) = x(2,i)
  10  continue

It is easy for the compiler to see that the second column is being
copied to the first and the source and destinations don't overlap.
So, the code can easily be vectorized, pipelined, or unrolled for
faster execution.  Even the IBM PC can benefit from this knowledge
(and issue a block move instruction).

The corresponding C code is:

      p = &x;
      q = p + N;
      for (i=0;i<N;i++) *p++ = *q++;

I've taken the obvious step of making array 'x' be row-wise to make
the C version the same as the Fortran.  Note that it's not as easy
for either the user or the compiler to tell that the move is safe
from dependencies.  It's possible: 'q' starts out 'N' ahead of 'p'
and the loop only takes 'N' steps.  But the test is clearly more
complicated than the array version required.

Suppose that you have to do the assignment 'against the grain' of
the array.  That is, the elements to be moved aren't the consecutive
ones.  The Fortran version is:

      do 10 i=1,M
	 x(i,1) = x(i,2)
   10 continue

The compiler can again _easily_ see that there are no dependencies.
The C version is:

      p = &x;
      q = p + 1;
      for (i=0;i<M;i++,p+=M,q+=M) *p = *q;

Here, the determination that there is no overlap requires the
compiler to see that the 'M'-parity of 'p' is always zero and
the 'M'-parity of 'q' is always one (both based on the base of
'x').  Few C compilers can even do the first example.  I don't
know any that can see this last.

Note:  I picked Fortran as the counter-example but I could just as
easily have used Pascal, Modula, Ada, Algol, etc..  In all of these,
the compiler can take advantage of the information which is lost if
the operation done using pointers.  Even in C, in those few contexts
where multidimensional arrays are actually recognized, it is better
to use the array notation so the compiler has more complete
information (if you can find a C compiler capable of making use
of such information).

J. Giles