3 ms·
Loops that depend on some graph (say, mutated in place) to reach a fixed point can present a challenge here. You have to reason about the algorithm that changes
by kazinator 5y ago
Loops that depend on some graph (say, mutated in place) to reach a fixed point can present a challenge here. You have to reason about the algorithm that changes the values at the graph nodes, and whether it guarantees forward progress toward a fixed point.
Floating point convergence is another risky thing in this category. If you're iterating to convergence, the test has to nail it, and if there is any risk of it going sideways, there has to be some exit strategy baked in.
I think more than once in the past I've added a maximum count to some loop that might not otherwise terminate, more than generous enough not to trigger as a false positive.
I seem to recall that Donald Knuth's TeX famously has some infinite looping detection in some of its formatting code. I can't find any references to this via web searching, though.
Another category are mutually tail-recursive functions. The termination of a tail-recursive network of functions could be as hard to prove as a goto graph.
Introducing a maximum iteration count could mean adding a count parameter to many of the functions, passing count -1 and checking for dropping to or below zero in more than one place.
- LorenPechtel 5y agoYeah, more than once I've coded suicide counters into indeterminate loops to catch corrupted graphs. And recently I had a fairly simple user-created graph that I forgot to put a suicide counter on. Of course I found out the omission the hard way. What did you expect it to do when you said A waits on B, B waits on C, C waits on D and D waits on A??? (Actually, the main part worked so it didn't immediately smack him in the face. However, there was a routine to find the completion time, if an item didn't exist use the completion time of it's parent(s).)