What is a Global Stack Used For?

Appeared in Volume 7/3, August 1994

Keywords: implementation.


jjmccabe@unix1.tcd.ie 
James McCabe
12th March 1994

Can anyone please explain to me what a global stack is used for? In SICStus Prolog I am repeating a large operation over and over again, and the program finds it necessary to keep a long list of ancestors, but it is obviously not important in a loop situation for this to happen.

Are there any good ways for freeing memory, not just for a global stack but for all the stacks.


imi-kdsi@nic.cerf.net 
Peter Ludemann
14th March 1994

Usually, the global stack is used for newly created non-atomic terms. For example, if you're building up a list, each "cell" in the list is allocated on the global stack. The "global stack" is very similar to the "heap" in Lisp, except that under some circumstances, the global stack can be popped, so that garbage collection is not always needed.

Some Prologs require the pre-allocation of all local and global memory; others (such as Quintus) can allocate as needed and shift stacks around to minimize over-all memory use.

James McCabe writes:

the program finds it necessary to keep a long list of ancestors, but it is obviously not important in a loop situation for this to happen.

"Call" information usually goes onto the "local stack". If your Prolog has Tail Recursion Optimization (TRO), this stack shouldn't grow if you don't leave choice points hanging around. Ancestors are only kept if you're debugging or if choice points prevent pruning the local and global stacks.

He continues:

Are there any good ways for freeing memory, not just for a global stack but for all the stacks.

If you make sure that your predicates are in TRO form, both the global and local stacks will grow as little as possible (if you want to know more about this, read Ait-Kaci's tutorial on the Warren Abstract Machine). Richard O'Keefe's book has a discussion of TRO, as I recall.

If TRO et al don't work, there are desperation measures, such as repeat-fail loops. But these almost never need to be used.


ok@goanna.cs.rmit.oz.au 
Richard A. O'Keefe
16th March 1994

James McCabe writes:

Can anyone please explain to me what a global stack is used for?

Compound terms, mainly. In other languages this is usually called a "heap". One meg really isn't a lot: if a list cell costs 8 bytes (I don't know what it costs in SICStus, but that's a reasonable guess) that's just 1 048 576 bytes / 8 bytes/cons = 131 072 cons cells. Not really a lot of space if you are doing something serious. Prolog calls this area a "stack" because it is popped on failure. If you're running out, your code is building a lot of new data structures and not failing much. Consider redesigning your data structures to save space.