4.10.1 Overview

SICStus Prolog uses five data areas: program space, global stack, local stack, choice stack, and trail stack. Each of these areas is automatically expanded if it overflows.

The local stack contains all the control information and variable bindings needed in a Prolog execution. Space on the local stack is reclaimed on determinate success of predicates and by tail recursion optimization, as well as on backtracking.

The choice stack contains data representing outstanding choices for some goals or disjunctions. Space on the choice stack is reclaimed on backtracking.

The global stack contains all the data structures constructed in an execution of the program. This area grows with forward execution and shrinks on backtracking.

The trail stack contains references to all the variables that need to be reset when backtracking occurs. This area grows with forward execution and shrinks on backtracking.

The program space contains compiled and interpreted code, recorded terms, and atoms. The space occupied by compiled code, interpreted code, and recorded terms is recovered when it is no longer needed; the space occupied by atoms that are no longer in use can be recovered by atom garbage collection described in ref-mgc-ago.

These fluctuations in memory usage of the above areas can be monitored by statistics/[0,2].

SICStus Prolog uses the global stack to construct compound terms, including lists. Global Stack space is used as Prolog execution moves forward. When Prolog backtracks, it automatically reclaims space on the global stack. However, if a program uses a large amount of space before failure and backtracking occur, then this type of reclamation may be inadequate.

Without garbage collection, the Prolog system must attempt to expand the global stack whenever a global stack overflow occurs. To do this, it first requests additional space from the operating system. If no more space is available, then the Prolog system attempts to allocate unused space from the other Prolog data areas. If additional space cannot be found, then a resource error is raised.

Global stack expansion and abnormal termination of execution due to lack of stack space can occur even if there are structures on the global stack that are no longer accessible to the computation (these structures are what is meant by “garbage”). The proportion of garbage to non-garbage terms varies during execution and with the Prolog code being executed. The global stack may contain no garbage at all, or may be nearly all garbage.

The garbage collector periodically reclaims inaccessible global stack space, reducing the need for global stack expansion and lessening the likelihood of running out of global stack. When the garbage collector is enabled (as it is by default), the system makes fewer requests to the operating system for additional space. The fact that less space is required from the operating system can produce a substantial savings in the time taken to run a program, because paging overhead can be much less.

For example, without garbage collection, compiling a file containing the sequence

p(_) :- p([a]).
:- p(_).

causes the global stack to expand until the Prolog process eventually runs out of space. With garbage collection enabled, the above sequence continues indefinitely. The list built on the global stack by each recursive call is inaccessible to future calls (since p/1 ignores its argument) and can be reclaimed by the garbage collector.

Garbage collection does not guarantee freedom from out-of-space errors, however. Compiling a file containing the sequence

p(X) :- p([X]).
:- p(a).

expands the global stack until the Prolog process eventually runs out of space. This happens in spite of the garbage collector, because all the terms built on the global stack are accessible to future computation and cannot be reclaimed.