Page 1 of 1

Compiler options for endless loops and stack overflow

Posted: 8 Sep 2015 18:00
by Peter Muraya
Hi,
The Visual Prolog compiler has an array of warnings that point to potential flaws in the logic of a program -- an extremely useful feature indeed. Two other runtime conditions, Endless loops and Stack overflows, are pointers to some problem with the logic. Is it feasible for future versions of Prolog to detect and give warnings at compile time wherever this is likely to occur in the code?

Posted: 8 Sep 2015 23:24
by Paul Cerkez
very interesting question.

Thomas may have another answer but in my gut, I think you might have a bunch of frivolous warnings.

strictly playing devil's advocate here:

What about the case where you are monitoring an external input, would that not be an endless loop?
What about the case where the endless loop is caused by an error in the external data at run time?

If the data supplying your application is all external, how would an application know that it is causing a stack overflow? (yes there are some situations that improper code can cause a stack overflow and these could generate a compile time warning but is it worth the expense on the compiler developer side to implement the code?) The follow on is what about code that 'looks' like it will trip an overflow but actually won't. You then run into the problem of "the boy crying wolf." You see too many false alarms and you begin to ignore that particular alarm completely.

In some cases, I could see both of these being implemented in very narrow, limited situations, but trying to cover the potential expanse might be too daunting, leaving it better to trap and report it when it occurs.

just my musings :-)

P.

Posted: 9 Sep 2015 7:41
by Peter Muraya
Hello Paul,
I admit that the logic for detecting these situations is not trivial but it may be helped by addition of new keywords to assist the compiler weed out the potentially frivolous cases. Take the case of the repeat predicate below.

Code: Select all

predicates     repeat:() nondeterm. clauses     repeat.     repeat:-repeat.
I think there is enough information in this particular code for the compiler to detect this as an endless loop. So, it would throw the warning to that effect -- which would be frivolous because the intention is indeed for this predicate to be endless. In that case we would help the compiler by including the endless keyword, thus:-

Code: Select all

predicates     repeat:() nondeterm endless. clauses     repeat.     repeat:-repeat.

Posted: 9 Sep 2015 11:09
by Martin Meyer
The problem of determining from a program and an input, whether the program will finish running on that input or continue to run forever, is known as the halting problem.

The halting problem is (proven to be) undecidable in general for idealized computers.

Also undecidable in general are variations like "does a sub-routine fall in a loop for all possible inputs?" or "exists an input, for which it loops?". The halting problem is even undecidable for programs without input, because for any given pair of program and input, the input can be hard coded in the program, so that an equivalent program without input is obtained.

The relevant difference between idealized computers (i.e. mathematical models of computers, for example Turing machines) and real computers is, that idealized computers have an infinite memory.

However even though we are running our programs on real computers with finite memory, regarding the loop detection the compiler had to determine, whether program execution loops endlessly, when there is sufficient memory, thus whether it loops endlessly on an idealized computer.

So, in general, detection of all endless loops by the compiler is impossible. In special cases it would be possible of course, but would a solution for only some special cases help much?

Regards
Martin

Posted: 9 Sep 2015 12:43
by Paul Cerkez
Thanks Martin, I couldn't remember the name "Halting Problem" - (they say memory is the 2nd thing to go when you get old, I just wish I could remember the 1st! :wink: )

Posted: 9 Sep 2015 13:40
by Thomas Linder Puls
We will not attempt to make such analysis, first of all due to the undecidable nature of the problem.

A little extra comment: repeat is not "endless" (repeat(), ! will terminate), but it is easy to create an endless loop using repeat (e.g. repeat(), fail).

Posted: 9 Sep 2015 16:55
by Peter Muraya
Hi Martin,
Thanks for the link to the Halting Problem; I was not aware that this issue is as old as computers and that it has been classified as undecidable.

Posted: 9 Sep 2015 18:00
by Peter Muraya
Thomas,
You are right, repeat is not endless. I have changed my example to the following to illustrate what I meant by use of keyword to support warnings for endless loops; but I now appreciate that the problem is much bigger than I thought.

Code: Select all

predicates      test:() endless. clauses      test():-          foreach repeat() do               something()          end foreach.