🚀 go-pugleaf

In reply to:guttman@linus.mitre.org
>>   >In article <15421@dime.cs.umass.edu> yodaiken@freal.cs.umass.edu (victor yodaiken) writes:
>>   >   >This seems like an opportune time to put in a plug for the Primitive
>>   >   >Recursive arithmetic [1]. 
>>
>>   >But doesn't PRA have the intrinsic problem that it contains much too small a
>>   >set of functions?  
>>
>>   Too small for what? I have yet to see an example of a proposed or
>>   implemented digital computer that can actually compute an unbounded search,
>>   and do not understand why a programming language would need to be able to
>>   expressive functions that are not feasible.  
>
> ... 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.
There is an old result (Blum (?)) which
show that the complete text of a p.r. function definition is quite a bit
longer than the complete text of a partial recursive definition for a large
class of functions, but this is not a result with much meaning in this
context (any reasonable p.r. programming language will give the programmer
a collection of pre-defined p.r. fuctionals). 

If the programmer requires unbounded
search for a program to work correctly, than the program is undoubtedly
incorrect. If a programmer cannot bound the depth of a recursion by, say,
a k-exponential function, than it is hard to believe that the function can
be computed.