Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!jarthur!uunet!mcsun!ukc!warwick!nott-cs!piaggio!anw
From: anw@maths.nott.ac.uk (Dr A. N. Walker)
Newsgroups: comp.lang.misc
Subject: Re: Answers, Chapter 1: TeX
Message-ID: <1990Nov2.183359.6761@maths.nott.ac.uk>
Date: 2 Nov 90 18:33:59 GMT
References: <1990Oct29.191321.3202@maths.nott.ac.uk> <4349@lanl.gov>
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Maths Dept., Nott'm Univ., UK.
Lines: 90

In article <4349@lanl.gov> jlg@lanl.gov (Jim Giles) writes:

	[Quite a lot, but I think we've reached a stage where we can
say what the situation is, and then agree to differ.]

	Suppose we have a procedure with two arrays as parameters.  In
a call of the procedure, the actual parameters may be arbitrarily messily
derived from other parameters in the call chain, may be slices or other
subsets [not in all languages, of course] perhaps of the same array.
There is a spiffy optimisation available (say, a block move, or a clever
vectorisation) that sometimes doesn't work if the parameters (call them
A and B) are not sufficiently different.  Call the optimised version of
the code ALPHA, and the unoptimised version BETA.  In real life, though
not on the machines available to impoverished Maths departments, ALPHA
may run (say) 30 times faster than BETA.

	Then Fortran should compile the code somewhat like

		IF interfere (A, B) THEN undefined ELSE ALPHA

As ALPHA is a perfectly good value of "undefined", this is usually optimised
to just ALPHA.  We would all agree, I hope, that this is less than ideal,
and can give rise to difficult-to-uncover bugs.

	C should compile the code to something like

		IF interfere (A, B) THEN BETA ELSE ALPHA

In practice, to economise on code size, unless "interfere" can be determined
very easily at compile time to be FALSE, it will compile to BETA.  This
is clearly slower ("less efficient") than the Fortran.

	JLG would like us to declare whether or not A and B can interfere.
If we *do* so declare, then it compiles to BETA, otherwise the code is

		IF interfere (A, B) THEN ERROR ELSE ALPHA

where, we hope, "interfere" can usually, if not always, be decided
statically by the compiler and loader, giving another optimisation.

	JLG's solution is obviously better than the Fortran.  Further,
it satisfies the rule that optimisation must not break code that, prima
facie, works, so it is a "correct" solution.  Further, it is clearly no
slower than the C, and perhaps much faster.  He therefore has a tenable
case.

	The counter argument is that it puts the burden in the wrong
place.  JLG is asking the *programmer* to assert something that may
not be assertable.  Some of the procedures in the call chain may be
library procedures, or may involve global variables from other modules,
for example.  How do *I* know what aliassing may occur?  Further,
in languages which (very usefully) allow dynamic array slicing, the
presence or absence of aliassing may often only be determinable at
run time, so either I program "defensively" and declare the alias
(so having a program which always runs slowly), or I take pot luck
and have a program which may fail at run time.

	In fact, the *real* situation, is that if the compiler and
loader can determine whether or not aliassing can occur, then the
"alias" declaration is unnecessary, and if they can't, then a run-time
check is needed anyway.  Hints to compilers, if thought desirable,
could be given in all sorts of other ways.

>I don't know any natural ways of using pointers.

	Well, we've been round this before.  *I* find them useful;
why do you want me to change my natural images and pictures of what
my programs do?  No-one is forcing *you* to use them.

	If you insist on thinking of pointers merely as ways of
storing machine addresses in a half-hearted attempt to avoid the
(assumed) overheads of array indexing, then of course you find
them unnatural.  On the other hand, if you have (say) a graph,
and at some point in your program you discover a node with an
interesting property, how *do* you naturally refer later to that
same node *other than* by explicitly or implicitly keeping a
pointer to that node?

>	   Linked lists, graphs, trees, etc. should all be implemented
>as recursive data structures (aliased or not as teh need arises).

	Even if you implement the graph itself as a recursive structure
(implied:  without pointers [and I am by no means convinced that that
is desirable, even if it is possible]), you may still find yourself
wanting to keep fingers on particular nodes.  A finger by any other
name is still a pointer.

-- 
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk