Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!ncar!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <27546@megaron.cs.arizona.edu>
Date: 16 Nov 90 00:14:22 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 80

In article  <6045:Nov1519:34:2290@kramden.acf.nyu.edu> Dan Bernstein writes:
]Well, I can't remember ever debugging a non-terminating program that
]*didn't* have a rather simple infinite loop, and I remember debugging
]lots of programs where the loop was simple. Does your experience differ?

The word "simple" here is ambiguous.  If you mean that the loop was
fairly small, I guess most of them are.  If you mean that the number
of states traversed in a cycle is small, then yes, my experience
differs.  It seems to me that there is almost always at least some
monotonic action going on in a loop (which is the reason for having
the loop), and this action will create very long state cycles.

]I'd be interested in seeing your example.

Here's the simplest form: you accidentally use the wrong exit
condition:

  for (i = start; i != -1; i++) ...

If "start" begins as a non-negative number, you've got a long wait
ahead of you.

]Not long ago in this thread I remarked that the halting problem is
]solvable in practice. The response I got---from a computer scientist---
]was religious disbelief.

Oh, well.  If I'd known you had such a huge sample space, I would
never have had the nerve to question you.  I guess if I have
enountered one beligerant mathematician I can just assume this is
typical of the field.

And furthermore, you have _not_ solved it.  If your proposal were
implemented there would still be programs that would never --for all
practical purposes-- terminate.  How has life changed?  All you have
done is decreased the likelihood of such an eventuallity, by some
unknown amount that --in the absence of further evidence-- reasonable
people can disagree on.

] It doesn't take much thought to apply theory to
]practice and put some reasonable bounds on the resources necessary to
]discover a loop---but computer scientists *don't do it*.

There are a lot of things that should be done that no one has time
for.  There is so much _real_ research involved in designing and
implementing programming languages, that this just hasn't recieved
much attention.  It is far from being the most important thing that
has been neglected in the field.  Many of us would even go so far as
to say that this is not a matter of research, but of engineering, and
therefore outside the realm of computer science.

]Just undecidability.

Hmm.  Are you claiming here that if something is undecideable in
theory that there is necessarily no practical approximation?  Weren't
you just bashing an anonymous computer scientist for such an opinion?

] Of course, if you were to believe some of the
]people who argued with me in this group, you'd believe that sorting is
]not linear in the number of bytes being sorted

Depends on your model.  Assertions about the complexity of sorting
rely by necessity on the underlying model.  I can produce a model
where sorting time is a constant.  As to whether your model is better
than others, that is a matter of opinion.  Personally, I happen to
agree with you on this one, but I wouldn't go about insulting people
because they disagree with me.

] that finding the optimal
]pointer version of array code is decidable

Again, a matter of the model in use.  Everyone else in the world was
assuming a model where the weights of the paths was given as part of
the input (or assumed to be uniform).  After you finally clued us in
about how your model differed, the argument degenerated to opinions on
models.
-- 
					David Gudeman
Department of Computer Science
The University of Arizona        gudeman@cs.arizona.edu
Tucson, AZ 85721                 noao!arizona!gudeman