eric%vax.nr.uninett@TOR.NTA.NO (Eric Monteiro) (01/25/88)
Hello,
I have a problem with Xerox Quintus Prolog :
I cannot do DEEP recursion.
I've partitioned the disk such that I have maximum space - 65000 pages,
but cannot do deeper than 5-10000 levels of recursion on a clean
sysout. This is interpreted code, compiled code is of
magnitude 10 better. (The twoliner test program is :
addone(I, Max) :- I<Max, J is I+1, addone(J,Max).
addone(_,_).
?- addone(1, 10000). )
IS THIS A REASONABLE RESULT ?! (or are there ways around).
Grateful for any advice,
Eric Monteiro
eric@vax.nr.uninett
or
Norwegian Computing Center
Forskningsvn. 1B,
Boks 114 Blindern,
N-0314 Oslo 3,
Norway
ok@quintus.UUCP (Richard A. O'Keefe) (01/27/88)
In article <101*eric@vax.nr.uninett>, eric%vax.nr.uninett@TOR.NTA.NO (Eric Monteiro) writes: > I have a problem with Xerox Quintus Prolog : > I cannot do DEEP recursion. > I've partitioned the disk such that I have maximum space - 65000 pages, > but cannot do deeper than 5-10000 levels of recursion on a clean > sysout. This is interpreted code, compiled code is of > magnitude 10 better. (The twoliner test program is : > addone(I, Max) :- I<Max, J is I+1, addone(J,Max). > addone(_,_). > > ?- addone(1, 10000). ) > > IS THIS A REASONABLE RESULT ?! (or are there ways around). > There are several points. (1) Try writing a recursive function in interpreted Lisp, and see how far you get. (2) In Xerox Quintus Prolog, the interpreter is best regarded as a debugging aid. The recommended approach is to develop code with the compiler, falling back on the interpreter when things go wrong. (You can set spy-points on compiled code, so you should be able to isolate the problem moderately well before switching over to interpreted code.) (3) Repartitioning the disc isn't going to buy you anything. Basically, Lisp and Prolog both want to rule the world. The compromise which was reached is that when you load Prolog it grabs 4 Mbytes from Lisp. When this happens you see a message in the Prompt Window that looks something like "Grabbing 4Mb from Lisp, this will take a while". It does. (4) Of the 4Mb, the first release allocated 1Mb permanently to stack frames, and 3Mb to heap and trail. I am not sure what the 2.0 release does. Compiled and interpreted clauses and so on are held as normal Lisp objects. (5) Most interpreters take several stack frames for each interpreted procedure call, and the Prolog interpreter is no exception. Now a stack frame is going to take a minimum of 12 bytes (never mind why), so if the overhead is N stack frames per interpreted goal, the absolute maximum interpreted depth would be about 88,000/N. So a ceiling of 10,000 levels of interpreted execution is not all that far from the theoretical bound. (6) Note that the addone/2 predicate is a very very strange one. It is not determinate: *each* invocation of it forces the creation of a choice point and the retention of a stack frame. If instead one wrote addone(I, Max) :- I >= Max. addone(I, Max) :- I < Max, J is I+1, addone(J, Max). one would find *no* recursion limit in compiled code because this version is tail recursive. There are three things going on here: - Prolog specific: addone/2 is so written that it MUST use up stack space rapidly in ANY Prolog system. - Quintus specific: we chose to allocate a fixed 1Mbyte stack in the 1.5 release (Lisp has a 128kbyte stack). - Xerox integration: the problem of integrating another paradigm into an open operating system. For example, we couldn't keep on grabbing pages from Lisp, for two reasons: we want to have them contiguous, and we don't want to wipe out Lisp. I think what we came up with was a reasonable engineering compromise. The coding style can make an immense difference to the efficiency of Prolog programs. I have often found that rewriting a Prolog program to make it more beautiful and better structured can produce ten-fold speed-ups and large space savings. The Prolog Digest might perhaps be a better forum for questions about Prolog coding style.