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?
-
- VIP Member
- Posts: 147
- Joined: 5 Dec 2012 7:29
Compiler options for endless loops and stack overflow
Mutall Data Management Technical Support
-
- VIP Member
- Posts: 106
- Joined: 6 Mar 2000 0:01
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.
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.
P.
-
- VIP Member
- Posts: 147
- Joined: 5 Dec 2012 7:29
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.
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:-
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.
Code: Select all
predicates
repeat:() nondeterm endless.
clauses
repeat.
repeat:-repeat.
Mutall Data Management Technical Support
-
- VIP Member
- Posts: 331
- Joined: 14 Nov 2002 0:01
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
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
-
- VIP Member
- Posts: 106
- Joined: 6 Mar 2000 0:01
- Thomas Linder Puls
- VIP Member
- Posts: 1424
- Joined: 28 Feb 2000 0:01
-
- VIP Member
- Posts: 147
- Joined: 5 Dec 2012 7:29
-
- VIP Member
- Posts: 147
- Joined: 5 Dec 2012 7:29
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.
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