🚀 go-pugleaf

In article <15484@dime.cs.umass.edu> yodaiken@freal.cs.umass.edu (victor yodaiken) writes:
>   In article <GUTTMAN.90Jun12105623@darjeeling.mitre.org> guttman@mitre.org (Joshua D. Guttman) writes:
>   >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.  

An example too cheap to put much weight on is the non-terminating function 

(lambda (x)
  (let loop ((x x))
    (if #T
	(loop x)
	2)))

which is non PR simply because PR functions are total.  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