Mechanism to ensure a loop ends

Question

When I was in college we had a guest lecture from David Parnas. In it he mentioned a mechanism that is used to guarantee that a loop (while loop, for loop, etc.) exits safely at some point. He scoffed at the fact that nobody knew what it was....the sad thing is that years later I dont know either. Does anyone know what this mechanism is called?

Answer 1

This question seems illogical.

There is no one gaurantee to ensure a loop exits other than create a post condition that you know will be hit, i.e. increment a counter, don't touch the counter inside the loop and have a maximum for it to hit.

You could also create a timer or another structure to check if the loop is taking too long.

What was Parnas implying here? A universal exit to any loop that doesn't interfere with the logic or simply designing proper post conditions?

Answer 2

There are many ways to guarantee that a loop exits safely:

1. Don't write it to be infinite
2. The others are left as an excercise

Seriously, the best way is to keep it simple, and to have a stable and fully tested termination condition (ie. the code that checks whether it should run another iteration or exit).

What you have described could very well be translated into the halting problem, which is a well known problem with no solution.

Also, a google search reveals that David Parnas works at the University of Limerick, you could call them up and ask to talk to him. I'm sure he would be pleased you're still trying to learn from what he taught you back then :)

Answer 3

Your guest lecturer might have been referring to Cycle Detection, a method of detecting infinite loops.

This blog post describes the detection of infinite loops in a linked list. Interestingly, it uses the same terminology as the Wikipedia article.

Answer 4

Judging by his area of expertise (which includes formal proofs of correctness), I think he meant the loop variant, which is a general technique used to prove loop termination.