> 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.
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.
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.
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.
> 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".
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.
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)
Note that on the last time through the loop you are doing a wipe() that was not actually necessary to accomplish your cleaning goal, and thus wasting some paper (unless you note that it came out white and set it aside to use on the first iteration the next time you need to clean, but I doubt anyone does that).
Some people were once trying to come up with the most useless possible superhero or supervillain, and I suggested "Exact Wipe Man", with the power to look at the result of a wipe of anything and know if that was the last wipe needed.
While on the subject of wiping one's derrière, I once read a question in an advice column where the questioner said that for some reason that subject came up among a group of people and someone asked what direction people wipe. It turned out that in that group of around 10 people 9 went one way and one went the other. That one wrote to ask if he was a freak or if he was normal and surrounded by freaks.
The columnist of course had no idea what the answer was, and asked around the office. She found that nearly everyone in the office went the same way as the questioner's friends, and informed him that he did appear to be unusual.
It turns out that I am also in the minority group. It had never even occurred to me that anyone might go the other way as it seems completely unnatural to me. Most people wipe in private with not even people they are in intimate physical relationships with watching and it is almost never a topic of discussion so you can be doing it completely different from everyone else and never find out.
This raises the question of what other things do we regularly do in private but might be doing in some way different from most other people? Maybe I'm flossing or brushing my teeth in some weird way, or maybe the way I turn on under the shower head always misses one particular spot and so I've got some section in the middle of my back that's never washed, or something like that?
I was tempted to subscribe to a month or two of one of those "voyeur" sites where they have a house with cameras in every room so you can see everything the residents do, to see how my flossing, showering, etc., compared, but never got around to doing so.
As far as I understand, women actually do teach each other explicitly (as in mother tells the daughter) to wipe in the direction away from the vagina, because it actually matters and they can give themselves a UTI going in the other direction. For men, it makes no difference and there is no reason for anyone to ever talk about it.
The flossing and teeth brushing thing, though, seriously? I don't know in principle if I'm doing it the same as other people, but I do remember quite well my parents teaching me to do it and I at least do it the same way they do. I didn't just figure out how to brush my teeth as a 3 year-old by trial and error. It was a topic of discussion at one point, at least with them, and that presumably means I do it the same way as my sisters.
> Note that on the last time through the loop you are doing a wipe() that was not actually necessary to accomplish your cleaning goal, and thus wasting some paper
True! Although I'd argue that's just part of the human condition. How do we check if any given condition obtains? Very often the simplest and most effective approach is just to perform some action which depends on that condition for its success, and we conclude from the fact that our action succeeded/failed that the condition does/doesn't obtain. How do we check if a closed door is locked? Technically we could use a see-through camera to observe the lock mechanism, but it's more straightforward to just try to push it open and see if we succeed/fail to do so. Ideally we may prefer structured decision-making like if-else and switch-case statements but in reality we tend to go for the quick and dirty (if less elegant, and sometimes wasteful) try-catches. :)
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.
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...
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)
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).
Recursion is just a species of iteration for a computing scientist. It's the kind of iteration with an implicit stack (that may be elided for tail calls). There is nothing special about "the stack" other than that pretty much all of our silicon is engineered to make it perform well. So in that sense it's pretty special, but mathematically not so much.
I would state that as an iterative procedure can be recursive or not. There are no recursive processes executed by any extant silicon that aren't iteration with a, potentially optional, stack.
And once you look at procedures that use two stacks, like this[1], then it becomes pretty apparent just how arbitrary the distinction is.
+1 This is why I initially asked, to me it is an implementation detail. I was never the best at theoretical computation, especially as it veered more toward math. Chriswarbo's comments helped me see the point of the blog post
Isn't it the other way around? That is isn't iteration a species of recursion?
I mean that anything iterative looks to me like a simple (linear) case of recursion. But I can imagine a series of calls that is recursive but not linearly iterative.
Your function `f` is performing a tail-call, and since it's not allocating any new values it should run happily forever in constant space. This is a common way to implement servers, e.g. 'serve = (request) => { respond(request); serve(next_request()); }'
Unfortunately some "poorly designed language implementations"[0] will fail to run such functions, with the "stack overflow" you mention.
The article is specifically talking about primitive-recursion versus non-primitive recursion. Primitive recursion is when we only recurse on a "smaller part" of our argument; e.g. the tail of a list, or subtracting 1 from a natural number, or the children of a tree node, etc. We cannot, say, recurse on the next state of a Turing Machine; since that's not a "smaller part" of the previous state.
Primitive recursion is equivalent to a 'for' loop with a pre-computed bound, e.g. 'for i in [0..X]: ...'.
Recursion that's "non-primitive" would include general recursion, which places no restriction on how we recurse; e.g. we could recurse on the next state of a Turing Machine. General recursion is equivalent to a 'while' loop which re-computes its condition after each iteration.
"Non-primitive" recursion can also include other restricted forms of recursion, which do not allow general computation, but cannot be represented by a primitive-recursive form; for example, the (usual definition of the) Ackermann function mentioned in the article takes two arguments, and its recursive calls can increase the second argument (so it's not primitive recursive). However, the pair of arguments always decrease according to (x, y) < (x, y+1) (if the first argument stays the same, the second argument must decrease) and (x, y) < (x+1, z) (if the first argument decreases, we can use anything for the second argument). The latter condition is so permissive that the Ackermann function is allowed to recurse with a second argument that is itself the result of another recursive call. This grows so fast that the number of loop iterations required to implement it cannot be computed by a primitive-recursive function (whatever function we try, there will eventually be an input that requires more iterations than that function returns).
If we're allowing unbounded (co)datastructures then a singly-linked list will do the trick.
Perhaps these examples don't count since they're not computable functions. Specifically, searching for an element in a bottomless tree/list that doesn't contain it will not halt, making this a partial function.
> 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.
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.
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
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.
45 comments
[ 3.6 ms ] story [ 70.7 ms ] threadYes. 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
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.
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.
> 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".
For example, wiping one's butt:
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)
Some people were once trying to come up with the most useless possible superhero or supervillain, and I suggested "Exact Wipe Man", with the power to look at the result of a wipe of anything and know if that was the last wipe needed.
While on the subject of wiping one's derrière, I once read a question in an advice column where the questioner said that for some reason that subject came up among a group of people and someone asked what direction people wipe. It turned out that in that group of around 10 people 9 went one way and one went the other. That one wrote to ask if he was a freak or if he was normal and surrounded by freaks.
The columnist of course had no idea what the answer was, and asked around the office. She found that nearly everyone in the office went the same way as the questioner's friends, and informed him that he did appear to be unusual.
It turns out that I am also in the minority group. It had never even occurred to me that anyone might go the other way as it seems completely unnatural to me. Most people wipe in private with not even people they are in intimate physical relationships with watching and it is almost never a topic of discussion so you can be doing it completely different from everyone else and never find out.
This raises the question of what other things do we regularly do in private but might be doing in some way different from most other people? Maybe I'm flossing or brushing my teeth in some weird way, or maybe the way I turn on under the shower head always misses one particular spot and so I've got some section in the middle of my back that's never washed, or something like that?
I was tempted to subscribe to a month or two of one of those "voyeur" sites where they have a house with cameras in every room so you can see everything the residents do, to see how my flossing, showering, etc., compared, but never got around to doing so.
The flossing and teeth brushing thing, though, seriously? I don't know in principle if I'm doing it the same as other people, but I do remember quite well my parents teaching me to do it and I at least do it the same way they do. I didn't just figure out how to brush my teeth as a 3 year-old by trial and error. It was a topic of discussion at one point, at least with them, and that presumably means I do it the same way as my sisters.
True! Although I'd argue that's just part of the human condition. How do we check if any given condition obtains? Very often the simplest and most effective approach is just to perform some action which depends on that condition for its success, and we conclude from the fact that our action succeeded/failed that the condition does/doesn't obtain. How do we check if a closed door is locked? Technically we could use a see-through camera to observe the lock mechanism, but it's more straightforward to just try to push it open and see if we succeed/fail to do so. Ideally we may prefer structured decision-making like if-else and switch-case statements but in reality we tend to go for the quick and dirty (if less elegant, and sometimes wasteful) try-catches. :)
``` function fWhile(q){ doSomethingWith(q.pop()) return !q.empty ? fWhile(q) : void }
fWhile(queue)
```
- 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)
F is recursive. While is iterative.
An iterative process can be recursive or not.
And once you look at procedures that use two stacks, like this[1], then it becomes pretty apparent just how arbitrary the distinction is.
[1] https://www.cs.utexas.edu/~EWD/MCReps/MR35.PDF
I mean that anything iterative looks to me like a simple (linear) case of recursion. But I can imagine a series of calls that is recursive but not linearly iterative.
Unfortunately some "poorly designed language implementations"[0] will fail to run such functions, with the "stack overflow" you mention.
[0] https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO
Primitive recursion is equivalent to a 'for' loop with a pre-computed bound, e.g. 'for i in [0..X]: ...'.
Recursion that's "non-primitive" would include general recursion, which places no restriction on how we recurse; e.g. we could recurse on the next state of a Turing Machine. General recursion is equivalent to a 'while' loop which re-computes its condition after each iteration.
"Non-primitive" recursion can also include other restricted forms of recursion, which do not allow general computation, but cannot be represented by a primitive-recursive form; for example, the (usual definition of the) Ackermann function mentioned in the article takes two arguments, and its recursive calls can increase the second argument (so it's not primitive recursive). However, the pair of arguments always decrease according to (x, y) < (x, y+1) (if the first argument stays the same, the second argument must decrease) and (x, y) < (x+1, z) (if the first argument decreases, we can use anything for the second argument). The latter condition is so permissive that the Ackermann function is allowed to recurse with a second argument that is itself the result of another recursive call. This grows so fast that the number of loop iterations required to implement it cannot be computed by a primitive-recursive function (whatever function we try, there will eventually be an input that requires more iterations than that function returns).
If we're allowing unbounded (co)datastructures then a singly-linked list will do the trick.
Perhaps these examples don't count since they're not computable functions. Specifically, searching for an element in a bottomless tree/list that doesn't contain it will not halt, making this a partial function.
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/2...). That's apparently equivalent to the class of multiply-recursive functions (https://dl.acm.org/doi/abs/10.5555/860256.860258)
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
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
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...
[2] https://agda.readthedocs.io/en/v2.6.4.1/language/coinduction...
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.