10 ms·

Where do non-primitive recursive functions come up naturally?

53 points by furcyd 3y ago

082349872349872 3y ago
> 0) Are there problems for which writing a WHILE loop is the way to go even though they are not needed? Yes. Often one can (after much thought and code) write something that explicitly reduces a problem in just* the right order, but it is quicker and simpler to repeatedly apply a set of rewrites WHILE any changes have been made. * see Knuth on Tarjan's SCC
- zmgsabst 3y ago
  Even nested while loops: while not stream.closed: symbols = [] current_symbol = None while not current_symbol == END: current_symbol = stream.read() symbols.append(current_symbol) # Do stuff with symbols. I’d argue that “while” is natural any time you have co-inductive types, and want to traverse until deconstruction stops.
  - magicalhippo 3y ago
    I also find "while" natural whenever I have some precondition. For example if I need to take a lock before checking for the terminating condition while holding the lock.
  - valenterry 3y ago
    Sorry, but it's not natural for me at all. In fact, when I learned programming, that was one of the harder things to wrap my head around. In English, when you say while A, B" it means "as long as condition A is fulfilled, condition B is also fulfilled". Like "while the window is open, the room is getting colder". But then in programming, that's not how it works. "while the stream is not closed..." what? A variable called symbols is being assigned. That's an action - so how often does it happen? Once or multiple times? Can the code after the while run in parallel or only sequential? And don't even get me started with forgetting to close the stream. Etc. etc. Intuitively it would be: "1.) open a stream. 2.) If there is nothing more to read, close the stream, otherwise read one symbol and add it to the list of symbols. Repeat 3.) repeat step 2". So for me at least, the recursive version is much more intuitive. it's how I think about it and how I would think about it if it were a real-world problem too.
    - Scarblac 3y ago
      It just means "while A, do B". The do is implicit, just like with if, for, etc.
      - xnorswap 3y ago
        The Do is explicit in some languages like Visual Basic: https://learn.microsoft.com/en-us/dotnet/visual-basic/language-reference/statements/do-loop-statement https://learn.microsoft.com/en-us/dotnet/visual-basic/langua... Now it's a bit confusing if you're used to other languages, because you might think "while" is a test-at-start and "Until" is test-at-end, but actually while and until can both be tested either at the start or the end, and While and Until are just testing the negation of each other. It can also be extra confusing, because there is a separate While.. End loop without the Do that can be used instead. There's a reason Visual Basic died out, and it isn't just the snobbishness of seeing C# as more of a "real" language.
        taeric 3y ago
        I confess various Basics all dying out feels more and more like the result of snobbishness as I get older.
    - saghm 3y ago
      > In English, when you say while A, B" it means "as long as condition A is fulfilled, condition B is also fulfilled". Like "while the window is open, the room is getting colder". > But then in programming, that's not how it works. "while the stream is not closed..." what? A variable called symbols is being assigned. That's an action - so how often does it happen? Once or multiple times? Can the code be after the while run in parallel or only sequential? And don't even get me started with forgetting to close the stream Ruby has the "until" keyword as an alternative to "while not" (similar to but not as commonly needed as "unless" for "if not"). I've honestly always kind of liked Ruby's willingness to go out of its way to try to make things like this more natural, but sadly I think I'm in the minority on this one. The one that always feels the most funky to me is whenever I have to invert `is_empty` in some way; I wish that languages would standardize having a method that means the opposite purely for aesthetic reasons, which I suspect would be wildly unpopular with everyone else besides me due to being seen as "redundant".
- aragonite 3y ago
  Lots of mundane human activities are most naturally represented as while (or do-while) loops. For example, wiping one's butt: do { wipe() } while { color_of_tp() !== "white" } Or anything that falls under cleaning, really. Although I'd argue while loops belong most at home in imperative code. (Cleaning for example is like the impure function par excellence, done only for side effect)
  - ape4 3y ago
    I think this code would be nicer if the wipe() function returned the color ;)
  - deleted 3y ago
    [deleted]
  - dmichulke 3y ago
    You should not use "white" but the initial color_of_tp()
    - Vvector 3y ago
      And brown TP causes your program to be stuck in endless loop
  - misja111 3y ago
    I would definitely stop wiping if the color turned to red.
    - culi 3y ago
      i recommend witch hazel
  - pixel8account 3y ago
    Ironically this one may actually be better represented by a for loop, because after 20 times or so you might want to reconsider your situation.
  - tzs 3y ago
btreecat 3y ago
I really struggled gaining much from that presentation format. It was confusing to follow for me, and possibly due to my lack of XP in the domain but I don't think I left feeling like the title question was answered.
betenoire 3y ago
I feel out of my depth here.. you need while loops to do a breadth first traversal of a tree that may have no bottom. (while !q.empty ...)
- davidgay 3y ago
  I'm no expert, but note that finite loops were allowed. In the case of any tree or graph traversal, you could replace it by a loop bounded by the tree/graph size plus an if...
- d-lisp 3y ago
  But aren't recursive functions capable of this ? ``` function fWhile(q){ doSomethingWith(q.pop()) return !q.empty ? fWhile(q) : void } fWhile(queue) ```
  - betenoire 3y ago
    Admittedly, it's been several decades since I took theory of comp. I left the comment hoping someone would teach me. My understanding is that recursion and non recursion (implementations) are equivalent, but my feeling from the article is that they are not. I vaguely recall having assignments of rewrite the two in the other forms. - edit I think I see what you are saying, I must not really understand the concept of primitive recursion (or non-, not sure which I don't understand)
    - d-lisp 3y ago
      There is a difference between while(true){ } and f=()=>f() In the sense that f will at one point call a function in a function in ... and in some languages this will cause an error (maximum call stack). Also I think in some languages: in memory is stored some context that allows us to know how to "get out" of the function f, and within each recursive call of f, memory usage grows (I am no expert). F is recursive. While is iterative.
      - User23 3y ago
pkhuong 3y ago
> 2) QUESTION: Are there simple programming languages so that HALT restricted to them is decidable but not primitive recursive? I suspect one could contrive such a language so I ask for both natural and contrived examples. I like the lexicographic descent criterion as a not too contrived example of a class of programs larger than primitive recursion, and yet for which it's easy to prove termination (e.g., https://goto.ucsd.edu/~gridaphobe/liquid/haskell/blog/blog/2013/12/15/lexicographic-termination.lhs/ https://goto.ucsd.edu/~gridaphobe/liquid/haskell/blog/blog/2...). That's apparently equivalent to the class of multiply-recursive functions (https://dl.acm.org/doi/abs/10.5555/860256.860258 https://dl.acm.org/doi/abs/10.5555/860256.860258)
tromp 3y ago
The best known non-primitive recursive function is Ackermann's function which grows at rate f_ω in the Fast Growing Hierarchy [1]. Any computable function whose running time grows slower than that, i.e. bounded by some f_k for finite k, should be primitive recursive, since one can just add f_k(n) upper bounds to any unbounded loop without affecting the result. I think functions growing as fast as Ackermann's don't come up naturally, except on a Googology forum. > 6) QUESTION: We know that GO and CHESS have very high complexity, but are still prim recursive. > 7) Tarjan's UNION-FIND data structure has amortized complexity roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's function. This is also a lower bound. See Wikipedia entry on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data structure actually used? I've used the union-find data structure for keeping track of groups of connected stones in Go. And also for keeping track of connected cells for generating random mazes. [1] https://en.wikipedia.org/wiki/Fast-growing_hierarchy https://en.wikipedia.org/wiki/Fast-growing_hierarchy
- tromp 3y ago
  > I think functions growing as fast as Ackermann's don't come up naturally, except on a Googology forum. Apparently I spoke too soon. One problem where Ackermann naturally comes up is the Vector Addition Systems [1] just discussed today. [1] https://news.ycombinator.com/item?id=38519944 https://news.ycombinator.com/item?id=38519944
gnulinux 3y ago
The simplest example [0] (other than Ackerman function et al (i.e. structural recursion) which come up less in practice) is coinduction which can be used to construct infinitely large objects on which you can apply operations that will prove to halt. For example given an infinitely large stream of integers 0, 2, 4, 6, 8, ..., 2*i (i in N) it's trivial to write a halting algorithm that'll sum first N elements of the stream. In short, we need to a way to express that the computation will be bounded by N. Agda programming language (which requires halting, and therefore is not Turing-Complete) has a robust coinduction support. E.g. in this [1] tutorial you can see it being used to construct decidable languages. A more traditional tutorial to coinduction could be found here [2]. [0] if we count primitive corecursion as "non-primitive recursive" here [1] https://agda.readthedocs.io/en/v2.6.4.1/language/sized-types.html https://agda.readthedocs.io/en/v2.6.4.1/language/sized-types... [2] https://agda.readthedocs.io/en/v2.6.4.1/language/coinduction.html https://agda.readthedocs.io/en/v2.6.4.1/language/coinduction...
nayuki 3y ago
On the other side of things, I show by construction how many well-known functions can be implemented as primitive recursive functions: https://www.nayuki.io/page/primitive-recursive-functions https://www.nayuki.io/page/primitive-recursive-functions One challenge I found is that I have to set the upper bounds conservatively. For example for sqrt(n), the loop actually counts all the way up to n, because in the worst case, sqrt(1) = 1. As another example, to find the nth prime number, I search up to 2^n, because a conservative lower bound is that there is at least one prime number between 2 and 4, between 4 and 8, between 8 and 16, etc.

53 points by furcyd 3y ago

> 0) Are there problems for which writing a WHILE loop is the way to go even though they are not needed? Yes. Often one can (after much thought and code) write something that explicitly reduces a problem in just* the right order, but it is quicker and simpler to repeatedly apply a set of rewrites WHILE any changes have been made. * see Knuth on Tarjan's SCC

zmgsabst 3y ago
Even nested while loops: while not stream.closed: symbols = [] current_symbol = None while not current_symbol == END: current_symbol = stream.read() symbols.append(current_symbol) # Do stuff with symbols. I’d argue that “while” is natural any time you have co-inductive types, and want to traverse until deconstruction stops.
- magicalhippo 3y ago
  I also find "while" natural whenever I have some precondition. For example if I need to take a lock before checking for the terminating condition while holding the lock.
- valenterry 3y ago
  Sorry, but it's not natural for me at all. In fact, when I learned programming, that was one of the harder things to wrap my head around. In English, when you say while A, B" it means "as long as condition A is fulfilled, condition B is also fulfilled". Like "while the window is open, the room is getting colder". But then in programming, that's not how it works. "while the stream is not closed..." what? A variable called symbols is being assigned. That's an action - so how often does it happen? Once or multiple times? Can the code after the while run in parallel or only sequential? And don't even get me started with forgetting to close the stream. Etc. etc. Intuitively it would be: "1.) open a stream. 2.) If there is nothing more to read, close the stream, otherwise read one symbol and add it to the list of symbols. Repeat 3.) repeat step 2". So for me at least, the recursive version is much more intuitive. it's how I think about it and how I would think about it if it were a real-world problem too.
  - Scarblac 3y ago
    It just means "while A, do B". The do is implicit, just like with if, for, etc.
    - xnorswap 3y ago
      The Do is explicit in some languages like Visual Basic: https://learn.microsoft.com/en-us/dotnet/visual-basic/language-reference/statements/do-loop-statement https://learn.microsoft.com/en-us/dotnet/visual-basic/langua... Now it's a bit confusing if you're used to other languages, because you might think "while" is a test-at-start and "Until" is test-at-end, but actually while and until can both be tested either at the start or the end, and While and Until are just testing the negation of each other. It can also be extra confusing, because there is a separate While.. End loop without the Do that can be used instead. There's a reason Visual Basic died out, and it isn't just the snobbishness of seeing C# as more of a "real" language.
      - taeric 3y ago
        I confess various Basics all dying out feels more and more like the result of snobbishness as I get older.
  - saghm 3y ago
    > In English, when you say while A, B" it means "as long as condition A is fulfilled, condition B is also fulfilled". Like "while the window is open, the room is getting colder". > But then in programming, that's not how it works. "while the stream is not closed..." what? A variable called symbols is being assigned. That's an action - so how often does it happen? Once or multiple times? Can the code be after the while run in parallel or only sequential? And don't even get me started with forgetting to close the stream Ruby has the "until" keyword as an alternative to "while not" (similar to but not as commonly needed as "unless" for "if not"). I've honestly always kind of liked Ruby's willingness to go out of its way to try to make things like this more natural, but sadly I think I'm in the minority on this one. The one that always feels the most funky to me is whenever I have to invert `is_empty` in some way; I wish that languages would standardize having a method that means the opposite purely for aesthetic reasons, which I suspect would be wildly unpopular with everyone else besides me due to being seen as "redundant".
aragonite 3y ago
Lots of mundane human activities are most naturally represented as while (or do-while) loops. For example, wiping one's butt: do { wipe() } while { color_of_tp() !== "white" } Or anything that falls under cleaning, really. Although I'd argue while loops belong most at home in imperative code. (Cleaning for example is like the impure function par excellence, done only for side effect)
- ape4 3y ago
  I think this code would be nicer if the wipe() function returned the color ;)
- deleted 3y ago
  [deleted]
- dmichulke 3y ago
  You should not use "white" but the initial color_of_tp()
  - Vvector 3y ago
    And brown TP causes your program to be stuck in endless loop
- misja111 3y ago
  I would definitely stop wiping if the color turned to red.
  - culi 3y ago
    i recommend witch hazel
- pixel8account 3y ago
  Ironically this one may actually be better represented by a for loop, because after 20 times or so you might want to reconsider your situation.
- tzs 3y ago

btreecat 3y ago

I really struggled gaining much from that presentation format. It was confusing to follow for me, and possibly due to my lack of XP in the domain but I don't think I left feeling like the title question was answered.

betenoire 3y ago

I feel out of my depth here.. you need while loops to do a breadth first traversal of a tree that may have no bottom. (while !q.empty ...)

davidgay 3y ago
I'm no expert, but note that finite loops were allowed. In the case of any tree or graph traversal, you could replace it by a loop bounded by the tree/graph size plus an if...
d-lisp 3y ago
But aren't recursive functions capable of this ? ``` function fWhile(q){ doSomethingWith(q.pop()) return !q.empty ? fWhile(q) : void } fWhile(queue) ```
- betenoire 3y ago
  Admittedly, it's been several decades since I took theory of comp. I left the comment hoping someone would teach me. My understanding is that recursion and non recursion (implementations) are equivalent, but my feeling from the article is that they are not. I vaguely recall having assignments of rewrite the two in the other forms. - edit I think I see what you are saying, I must not really understand the concept of primitive recursion (or non-, not sure which I don't understand)
  - d-lisp 3y ago
    There is a difference between while(true){ } and f=()=>f() In the sense that f will at one point call a function in a function in ... and in some languages this will cause an error (maximum call stack). Also I think in some languages: in memory is stored some context that allows us to know how to "get out" of the function f, and within each recursive call of f, memory usage grows (I am no expert). F is recursive. While is iterative.
    - User23 3y ago

pkhuong 3y ago

> 2) QUESTION: Are there simple programming languages so that HALT restricted to them is decidable but not primitive recursive? I suspect one could contrive such a language so I ask for both natural and contrived examples. I like the lexicographic descent criterion as a not too contrived example of a class of programs larger than primitive recursion, and yet for which it's easy to prove termination (e.g., https://goto.ucsd.edu/~gridaphobe/liquid/haskell/blog/blog/2013/12/15/lexicographic-termination.lhs/ https://goto.ucsd.edu/~gridaphobe/liquid/haskell/blog/blog/2...). That's apparently equivalent to the class of multiply-recursive functions (https://dl.acm.org/doi/abs/10.5555/860256.860258 https://dl.acm.org/doi/abs/10.5555/860256.860258)

tromp 3y ago

The best known non-primitive recursive function is Ackermann's function which grows at rate f_ω in the Fast Growing Hierarchy [1]. Any computable function whose running time grows slower than that, i.e. bounded by some f_k for finite k, should be primitive recursive, since one can just add f_k(n) upper bounds to any unbounded loop without affecting the result. I think functions growing as fast as Ackermann's don't come up naturally, except on a Googology forum. > 6) QUESTION: We know that GO and CHESS have very high complexity, but are still prim recursive. > 7) Tarjan's UNION-FIND data structure has amortized complexity roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's function. This is also a lower bound. See Wikipedia entry on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data structure actually used? I've used the union-find data structure for keeping track of groups of connected stones in Go. And also for keeping track of connected cells for generating random mazes. [1] https://en.wikipedia.org/wiki/Fast-growing_hierarchy https://en.wikipedia.org/wiki/Fast-growing_hierarchy

tromp 3y ago
> I think functions growing as fast as Ackermann's don't come up naturally, except on a Googology forum. Apparently I spoke too soon. One problem where Ackermann naturally comes up is the Vector Addition Systems [1] just discussed today. [1] https://news.ycombinator.com/item?id=38519944 https://news.ycombinator.com/item?id=38519944

gnulinux 3y ago

The simplest example [0] (other than Ackerman function et al (i.e. structural recursion) which come up less in practice) is coinduction which can be used to construct infinitely large objects on which you can apply operations that will prove to halt. For example given an infinitely large stream of integers 0, 2, 4, 6, 8, ..., 2*i (i in N) it's trivial to write a halting algorithm that'll sum first N elements of the stream. In short, we need to a way to express that the computation will be bounded by N. Agda programming language (which requires halting, and therefore is not Turing-Complete) has a robust coinduction support. E.g. in this [1] tutorial you can see it being used to construct decidable languages. A more traditional tutorial to coinduction could be found here [2]. [0] if we count primitive corecursion as "non-primitive recursive" here [1] https://agda.readthedocs.io/en/v2.6.4.1/language/sized-types.html https://agda.readthedocs.io/en/v2.6.4.1/language/sized-types... [2] https://agda.readthedocs.io/en/v2.6.4.1/language/coinduction.html https://agda.readthedocs.io/en/v2.6.4.1/language/coinduction...

nayuki 3y ago

On the other side of things, I show by construction how many well-known functions can be implemented as primitive recursive functions: https://www.nayuki.io/page/primitive-recursive-functions https://www.nayuki.io/page/primitive-recursive-functions One challenge I found is that I have to set the upper bounds conservatively. For example for sqrt(n), the loop actually counts all the way up to n, because in the worst case, sqrt(1) = 1. As another example, to find the nth prime number, I search up to 2^n, because a conservative lower bound is that there is at least one prime number between 2 and 4, between 4 and 8, between 8 and 16, etc.