🚀 go-pugleaf

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.