Path: utzoo!utgpu!watserv1!watmath!att!att!emory!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!haven!adm!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Answers, Chapter 1: TeX
Message-ID: <4349@lanl.gov>
Date: 30 Oct 90 02:35:37 GMT
References: <1990Oct29.191321.3202@maths.nott.ac.uk>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 82

From article <1990Oct29.191321.3202@maths.nott.ac.uk>, by anw@maths.nott.ac.uk (Dr A. N. Walker):
> [...]
> 	Yes, but one trouble is that one of the commonest cases in
> practice is where a variable is aliassed with itself, as in a[i] v. a[j].

Well, it is one of the common forms of aliasing.  However, it is clearly
marked as such: both are references to 'a'.  Further, it is a very rare
problem compared to array processing with 'a[j]' vs. 'b[j]' - here it
is _very_ important that we _know_ 'a' to be disjoint from 'b'.

> [...]
> It gets worse when you are worried about a[j] v. b[j] where a, b and j
> are parameters to some procedure -- you plainly need to be sure that
> a != b [...]

That has been my point.  If 'a' and 'b' aren't declared together in
the same 'aliased' declaration, they _can't_ be aliased.  Not at all.
Ever.

This requires that the loader check procedure arguments against
alias status and guarantee that the caller doesn't pass aliased
arguments to a subroutine that doesn't also declare them aliased.
Since all the tests are done at compile- and load-time, there is
no run-time penalty.  The price to be paid for this is that any
case that is still ambiguous at load-time must be assumed aliased.

> [...]  [and it gets worse in languages that allow slicing and other
> subsetting of arrays], [...]

Exactly the reason for wanting to get explicit compile-time and
load-time checkable constraints into the language.  This permits
the compiler to generate efficient code for those things (the majority)
which are _known_ not to be aliased.

> [...]                  which again involves arbitrarily messy checks if
> a and b are potentially inherited from further procedures and you insist
> that the checks be carried out by compiler and loader.  [...]

It is because of this problem of inheriting data through several levels
of the call chain that the test in the loader is most important.  The
loader _can_ perform this test reliably and quickly.  This permits
efficient code to be generated while maintaining confidence that
the no-alias assumptions won't be violated.

> [...]                                                   The problems
> will only be exacerbated if you deprive programmers of natural ways of
> using pointers, so that they find themselves [through brute force or
> ignorance] emulating proper data structures by indexing into arrays.

I don't know any natural ways of using pointers.  Pointers are one of
the most unnatural data structuring tools that I've ever encountered.
Further, in the context of the data structuring tools I've recommended,
I see no reason to use arrays to simulate any data structure other than
arrays.   Linked lists, graphs, trees, etc. should all be implemented
as recursive data structures (aliased or not as teh need arises).
Where's the need for arrays?

> 
> 	You are right that in many cases pointerless code can help
> the compiler by making certain aliasses impossible;  on the other
> hand, in most if not all of the cases where this matters, the
> compiler can make the same deductions given a program which is
> properly divided into modules and in which scope rules are enforced.

You yourself have pointed out many specific cases where a compiler
CANNOT make such deductions.  The case of arrays 'a' and 'b'
being passed to the same function as arguments is a case in point:

real function :: example(real::a(:),b(:))
   do while (some_condition)
      SOME CODE INVOLVING BOTH a AND b
   end do
end function

Since 'a' and 'b' aren't declared with the 'aliased' attribute, then
they _must_ not be aliased.  The loader can and _should_ determine
that this constraint is obeyed.  Using the language features I've
been recommending, the compiler can optimize the loop all it wants.
Without the constraints I advocate, such optimizations are eather
unsafe or not applied at all.

J. Giles