kean@grads.cs.ubc.ca (Alex Kean) (11/17/88)
I was attempting to run a Quintus Prolog program that potentially generates
exponential number of clauses on the inputs. In my case, my set of clauses
are roughly 200 where each clause is about 5 literals. They are represented
by a list of lists. Unfortunately I ran into [segmentation fault] on a Sun4,
SunOS 3.2. I suspected there is some problem with the memory management. I
decided to test the memory by writing the following simple program:
(1) an outer "loop" that run for "N" times;
(2) an inner loop that mutiply a list of 10 chars ['1234567890']
for 18 times and never returns the list.
By calling "loop(300)" on the Sun4, the program crash and exits Quintus Prolog.
Questions: (a) Which stack has overflowed ?
(b) In general, what are the factors to observe when writing
prolog programs that takes up lots of memory.
-------------------------------------------------------------------------
pair(0,_).
pair(N,X) :-
append(X,X,Z1),
N1 is N - 1,
pair(N1,Z1).
loop(0).
loop(N) :-
pair(18,['0123456789']),
!, garbage_collect,
J is N -1,
loop(J).
-------------------------------------------------------------------------
Thanks.
Alex Kean
Department of Computer Science
University of British Columbia
Vancouver, British Columbia,
Canada.ok@quintus.uucp (Richard A. O'Keefe) (11/18/88)
In article <3@ubc-cs.UUCP> kean@grads.cs.ubc.ca (Alex Kean) writes: >I was attempting to run a Quintus Prolog program ... >Unfortunately I ran into [segmentation fault] on a Sun4, SunOS 3.2. ***PLEASE***, will people who have problems with Quintus Prolog SEND BUG REPORTS TO QUINTUS. It's not as if it was hard, or anything. All you do is send electronic mail to ...!sun!quintus!hotline If you get a segmentation fault from plain Prolog code, and still more if the system exits unexpectedly, that is certainly a bug. I am currently running some tests to see whether the problem still exists: it is possible that this may be an instance of a mistake which was fixed before the current release. (Don't forget to include the version number in a bug report.) >Questions: (a) Which stack has overflowed ? This question is meaningless in Quintus Prolog, where the memory areas do not have fixed sizes but expand and contract as needed. Given that each iteration of loop/1 in Kean's example constructs about 1Mbyte on the heap, it's probably the heap which overflows most of the time, but it may grab space from one of the other stacks and cause that to overflow. > (b) In general, what are the factors to observe when writing > prolog programs that takes up lots of memory. Start by reading appendix I in the Quintus Prolog Reference Manual. (a) Good data structure design. Don't over-use lists; don't use wrappers; don't copy things when the original will do. (b) Be careful to make your programs as determinate as possible; this is automatic when good coding practice meets good data structure design. I'll illustrate (b) with Kean's example. >pair(0,_). >pair(N,X) :- > append(X,X,Z1), > N1 is N - 1, > pair(N1,Z1). There is *NOTHING* in this to say that the second clause should not be tried once the first clause has succeeded. Any Prolog system will therefore be obliged to retain a choice-point for in this case. Code this either as pair(0, _) :- !. pair(N, X) :- append(X, X, XX), M is N-1, pair(M, XX). or as pair(N, X) :- ( N =:= 0 -> true ; append(X, X, XX), M is N-1, pair(M, XX) ). (See the section on "counters" in chapter 1 of my tutorial.) >loop(0). >loop(N) :- > pair(18,['0123456789']), > !, garbage_collect, > J is N -1, > loop(J). Once again, there is nothing in this to say that the second clause should not be tried once the first clause has succeeded. Code it as loop(0) :- !. loop(N) :- pair(18, [atom]), % which is now determinate garbage_collect, M is N-1, loop(M). or as loop(N) :- ( N =:= 0 -> true ; pair(18, [atom]), garbage_collect, M is N-1, loop(M) ). If you have choice points lying around, the arguments saved in them may be hanging on to things you think are garbage. (c) The old hack: when you have a determinate query which isn't supposed to bind any variables, fail back over it. loop(N) :- ( N =:= 0 -> true ; \+ \+ pair(18, [atom]), % det. test, reclaim space M is N-1, loop(M) ). If you do this, it is better to move the failing back into the definition of the called predicate. One Quintus-specific point (described in section 7-5 of the Quintus Prolog System-Dependent Features manual) is that | ?- prolog_flag(gc_trace, _, on). will make the garbage collector print out a summary of what it has done, which can be quite illuminating.
lang@macbeth.PRC.Unisys.COM (Francois-Michel Lang) (11/22/88)
Send, abort, edit, or list? l
In article <3@ubc-cs.UUCP> kean@grads.cs.ubc.ca (Alex Kean) writes:
++ I was attempting to run a Quintus Prolog program that potentially generates
++ exponential number of clauses on the inputs.
...
++ I decided to test the memory by writing the following simple program:
++ (1) an outer "loop" that run for "N" times;
++ (2) an inner loop that mutiply a list of 10 chars ['1234567890']
++ for 18 times and never returns the list.
++ By calling "loop(300)" on the Sun4, the program crash and exits Quintus Prolog.
++
++ Questions: (a) Which stack has overflowed ?
++ (b) In general, what are the factors to observe when writing
++ prolog programs that takes up lots of memory.
++
++ -------------------------------------------------------------------------
++ pair(0,_).
++ pair(N,X) :-
++ append(X,X,Z1),
++ N1 is N - 1,
++ pair(N1,Z1).
++
++ loop(0).
++ loop(N) :-
++ pair(18,['0123456789']),
++ !, garbage_collect,
++ J is N -1,
++ loop(J).
++ -------------------------------------------------------------------------
Well, one thing that will help right of the top is to add a couple of cuts
in the base cases of pair/2 and loop/1. Without those cuts, you carry around
lots of superfluous choice points, and, what's worse, if you ever backtrack
into pair/2 or loop/1, you're going to be in trouble.
Also, if you add those cuts, the cut currently in the definition of loop/1
becomes unnecessary (I'm not too sure what it was doing in there in the first place).
I'll let Richard answer (a) and (b).
I also don't understand is the use of '0123456789',
and the claim that the program multiplies a list of 10 chars.
It looks to me that calling pair(N, L) will construct a list
consisting of 2^N copies of L appended together.
----------------------------------------------------------------------------
Francois-Michel Lang
Paoli Research Center, Unisys Corporation lang@prc.unisys.com (215) 648-7256
Dept of Comp & Info Science, U of PA lang@cis.upenn.edu (215) 898-9511