🚀 go-pugleaf

In article <15548@dime.cs.umass.edu> you write:
>In reply to:guttman@linus.mitre.org
>> ... But I think a more
>>valuable point is that there are programming language idioms that (in the ideal
>>sense) allow many non-PR algorithms to be expressed, and which are too useful
>>to do without.  That is, to replace them by a PR expression that would do the
>>same computation in the cases of practical interest would require an impossibly
>>fine analysis of which cases will be of practical interest, and what
>>termination-guaranteeing conditions will be true in those cases.  
>>
>>	Josh
>>
>
>This is a common argument, but I'd like to see something a little more
>concrete. What's an example of a function that is of real interest
>to a programmer, and that cannot be  expressed cleanly as a p.r. function.
>It is oft stated that p.r. function definitions will be far
>more cumbersome than those of more general frameworks, but I have yet
>to see any real evidence of this.

Since there is still `term rewriting' in the subject: take the
Knuth-Bendix algorithm for transforming rewrite rule systems into a
canonical form. It is a straightforward algorithm if you write it with
a while-loop or with recursion. You'll have trouble writing it with PR
constructs since no general bound is known.

Another example is the Groebner basis algorithm for transforming a set
of polynomials into standard form. As soon as you have this standard
form (`Groebner basis') you can decide membership of the ideal
generated by the set of polynomials, which you can't with the original
set -- so the algorithm is of practical use.

This Groebner basis algorithm has a similar structure as the
Knuth-Bendix algorithm (Knuth-Bendix can be simulated by Groebner
basis algorithm, probably vice versa). The Groebner basis algorithm
runs in doubly exponential time (double exp. in the degree of the
polynomials and exponential in the number of polys or so) and still it
is useful (at least many mathematicians are using it). The algorithm
is around since 1967, it took some 10 years until a bound was
discovered for the case of polys of degree at most 2. There is still
no bound known for the general case. Without a bound for the running
time you cannot program this algorithm using PR constructs.

A more practical example: the Roider algorithm for collision detection
(of a robot with an obstacle). It has a simple structure (with a
while loop) and it's fast. I don't know whether a bound is known. If
there is it must be quite pessimistic, since the running time depends
on the form of the obstacle and the robot (input data) and on the
starting point for the iteration (arbitrary).

Especially, in mathematical or technical software you often have
algorithms that are naturally expressed with non-PR constructs and
where no bound is known or where the bound is extremely pessimistic.
So better keep recursion and/or while loop in the language.

Even partial recursive functions might be useful, for example for
writing an automatic theorem prover.

Gerald

--
Gerald Baumgartner
Dept. of Computer Sciences, Purdue University, W. Lafayette, IN 47907
Internet: gb@cs.purdue.edu  UUCP: ...!{decwrl,gatech,ucbvax}!purdue!gb