[HN Gopher] Where do non-primitive recursive functions come up n...
___________________________________________________________________
Where do non-primitive recursive functions come up naturally?
Author : furcyd
Score : 46 points
Date : 2023-12-04 02:31 UTC (20 hours ago)
(HTM) web link (blog.computationalcomplexity.org)
(TXT) w3m dump (blog.computationalcomplexity.org)
| 082349872349872 wrote:
| > _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 wrote:
| 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.
| valenterry wrote:
| 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 wrote:
| It just means "while A, _do_ B ". The do is implicit, just
| like with if, for, etc.
| xnorswap wrote:
| The Do is explicit in some languages like Visual Basic:
| 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 wrote:
| I confess various Basics all dying out feels more and
| more like the result of snobbishness as I get older.
| saghm wrote:
| > 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".
| karatinversion wrote:
| I always write a negative "is empty" check as "size > 0"
| for this reason
| magicalhippo wrote:
| 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.
| aragonite wrote:
| 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 wrote:
| I think this code would be nicer if the wipe() function
| returned the color ;)
| dmichulke wrote:
| You should not use "white" but the initial color_of_tp()
| Vvector wrote:
| And brown TP causes your program to be stuck in endless
| loop
| misja111 wrote:
| I would definitely stop wiping if the color turned to red.
| culi wrote:
| i recommend witch hazel
| pixel8account wrote:
| 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 wrote:
| 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 derriere, 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.
| jaktet wrote:
| Well what direction was the unusual way?
| nh23423fefe wrote:
| the correct way is obviously away from genitals not
| towards.
| nonameiguess wrote:
| 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.
| aragonite wrote:
| > 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. :)
| btreecat wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| But aren't recursive functions capable of this ?
|
| ``` function fWhile(q){ doSomethingWith(q.pop()) return
| !q.empty ? fWhile(q) : void }
|
| fWhile(queue)
|
| ```
| betenoire wrote:
| 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 wrote:
| 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 wrote:
| 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.
| d-lisp wrote:
| Well, if recursion is a species of iteration; then
| recursion and iteration are not the same thing.
|
| An iterative process can be recursive or not.
| chriswarbo wrote:
| 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.
|
| [0]
| https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO
| d-lisp wrote:
| Is TCO still rejected by V8 ?
| chriswarbo wrote:
| 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).
| chriswarbo wrote:
| > a tree that may have no bottom
|
| 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.
| betenoire wrote:
| thank you, this helped me understand it
| pkhuong wrote:
| > 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/2...).
| That's apparently equivalent to the class of multiply-recursive
| functions (https://dl.acm.org/doi/abs/10.5555/860256.860258)
| tromp wrote:
| The best known non-primitive recursive function is Ackermann's
| function which grows at rate f_o 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
| tromp wrote:
| > 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
___________________________________________________________________
(page generated 2023-12-04 23:01 UTC)