Compiler options for endless loops and stack overflow

Discussions related to Visual Prolog
Peter Muraya
VIP Member
Posts: 146
Joined: 5 Dec 2012 7:29

Compiler options for endless loops and stack overflow

Unread post by Peter Muraya » 8 Sep 2015 18:00

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?
Mutall Data Management Technical Support

Paul Cerkez
VIP Member
Posts: 202
Joined: 6 Mar 2000 0:01

Unread post by Paul Cerkez » 8 Sep 2015 23:24

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.
AI Rules!
P.

Peter Muraya
VIP Member
Posts: 146
Joined: 5 Dec 2012 7:29

Unread post by Peter Muraya » 9 Sep 2015 7:41

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.
Mutall Data Management Technical Support

Martin Meyer
VIP Member
Posts: 289
Joined: 14 Nov 2002 0:01

Unread post by Martin Meyer » 9 Sep 2015 11:09

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

Paul Cerkez
VIP Member
Posts: 202
Joined: 6 Mar 2000 0:01

Unread post by Paul Cerkez » 9 Sep 2015 12:43

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: )
AI Rules!
P.

User avatar
Thomas Linder Puls
VIP Member
Posts: 1622
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls » 9 Sep 2015 13:40

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).
Regards Thomas Linder Puls
PDC

Peter Muraya
VIP Member
Posts: 146
Joined: 5 Dec 2012 7:29

Unread post by Peter Muraya » 9 Sep 2015 16:55

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.
Mutall Data Management Technical Support

Peter Muraya
VIP Member
Posts: 146
Joined: 5 Dec 2012 7:29

Unread post by Peter Muraya » 9 Sep 2015 18:00

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.
Mutall Data Management Technical Support

Post Reply