[DanWaterworth]

You make some good points. Especially that a GR function may be able to work more efficiently than a PR function; do you have an example or can you cite a reference for this?

As for optimization, I believe that it may be possible to more effectively automatically parallelize a PR function than a GR one.

[cpressey]

Unfortunately, it's hearsay to me; it came up in conversation (about computability and complexity) with a professor, and I took his word for it at the time; I've been meaning to ask him for a reference ever since, but never got around to it.

But at least one thing I can see is that in PR, you need to fix the upper bounds of the loops (/recursion depth) ahead of time, not "on the fly". If you're doing some kind of iterative approximation, you probably don't know what those bounds "should" be, because you're going to terminate on some other condition, like, the change in the value has become negligible. Your upper bound will be a worst-case estimate -- which you have to do extra work to compute -- and I don't see how it differs much, in practice, from a timeout, which has the advantage (again from a systems perspective) of being measured in clock time rather than cycles.

Not sure about parallelization. PR doesn't suggest any advantages to me for that offhand, but then, I haven't thought about it.

[DanWaterworth]

W.r.t parallelism, I'll copy here something I wrote elsewhere in this thread:

"I don't know for sure that this is possible yet, but I believe that the processor would be able to estimate the amount of work required to evaluate an expression. Using this ability, it would be able to automatically parallelize the evaluation of an expression by splitting it up into pieces of approximately equal size and then distributing them to sub processors."