Prolog programs use memory in two ways:
This memory must be managed, i.e., allocated when required and freed for use when no longer required. To a certain degree this is performed automatically by the Prolog system, but the Prolog programmer must be aware of how memory is used by Prolog.
Memory used by Prolog is partitioned into a number of different areas:
Code Space is memory used to store compiled Prolog clauses. It will vary in size over the execution-life of a Prolog program.
Stack Space contains a number of fixed size areas called stacks. The size of these areas may be set when alis or an application is invoked, but once set they cannot be changed. Most problems with memory usage arise in the use of these stacks. The stack sizes can be controlled by an configuration (.cfg) file
Dynamic Space is memory used to store dynamic database items as well as internal Prolog requirements. Atom names and strings are also stored here.
Table Space is a fixed-size piece of memory containing tables required by Prolog. The sizes of some of these tables can be controlled by an configuration (.cfg) file.
Code space and dynamic space are allocated as needed from memory left over in the computer after Prolog has loaded. As objects in one or the other space are "freed" the memory is returned to general use, so it is possible for the same piece of memory to contain a piece of compiled code and a string or an atom name over the course of execution of a program.
Stack space is divided into four areas.
Heap Stack is used to hold terms constructed at run time. For example during the execution of "foo(1,2,3) =.. X," X will be bound to a list which did not exist previously. This list is built on the heap.
The heap expands as programs execute and contracts only on backtracking. An automatic facility called garbage collection will try to clear the heap stack of unwanted items but it cannot always succeed (see below). Thus this stack is often one of the first data areas to become filled.
Local Stack is used to store variables used in clauses. This stack is not likely to overflow its maximum permissible size.
Control Stack is used to store information required to restore backtrack points in the execution and to store information about the choice of clauses in a proof.
The control stack shrinks both on backtracking and on successfully proving goals which cannot be backtracked into.
Trail Stack contains addresses of variables which need to be unbound on backtracking. This stack does not usually overflow its default size.
The built-in predicates pro_heap, pro_control, pro_local and pro_trail return the maximum size of each resource as well as the current usage level when the pro_xxx predicate was called.
One of the major productivity benefits of a language such as Prolog, is that you do not have to allocate and free memory for various program data structures. By simply referring to something, you cause Prolog to automatically manage the memory needed for that thing.
During the course of execution, items are left in memory that are no longer used. Occupied memory which could, in theory, be reused is called garbage. Amzi! Prolog employs a technique known as garbage collection which attempts to return this space to general use.
In Prolog, the two areas where 'garbage' accumulates are the dynamic database, where asserts and retracts take place and where strings, constants and consulted code are stored, and the heap, which is the workhorse data structure on which Prolog unification takes place.
The dynamic database does immediate retracts of many clauses, but some clauses, due to bindings it might have, cannot be immediately retracted. These clauses accumulate in the dynamic database. You can now optionally cause these clauses to be garbage collected whenever the Prolog engine decides it needs to allocate another chunk of memory for the dynamic database. The garbage collection might avoid the allocation of the new chunk. The downside is programs might run a little slower.
To turn on this option, use the .cfg parameter 'dbgc = [on|off]'. Like other .cfg parameters, it can be set from the original LSAPI call to lsInit2().
(If you use pro_db/2 to see the effects of asserts and retracts, the information is confused by the fact that an initial assert allocates additional data structures beyond just the clause, and the interpreter also makes use of the dynamic database. However, the query:
pro_db(A, U), assert(foo), pro_db(A2, U2), retract(foo), pro_db(A3, U3)
will show U and U3 to be the same after the first time you try it.)
During the execution of a Prolog program it is possible for heap space to be used and then never needed again. An example of this would be when a program creates a structure on the heap stack (using "=.." say), refers to it once, and then never again in the course of execution. Unless the program backtracks past the code that created the structure, it will remain on the heap stack until the program terminates. Since heap space is a rare commodity, we would like to be able to reclaim this space for further use by the program.
Garbage collection usually occurs automatically if needed. If, for example, the heap stack becomes full before a program terminates then the garbage collector will be invoked on the heap stack. If it can free enough heap stack to continue execution of the program then execution will continue, and all you will notice is a temporary pause (typically less than a second) as the garbage collector does its work. If the garbage collector cannot free enough stack then a fatal error occurs (see below) and the program is aborted.
Like many symbolic programming languages, Prolog has an appetite for memory. This is particularly apparent on personal computers which have rather limited memory. In these cases it may well be necessary to fine tune the size of the stacks in order for the program to run to completion. Even then there may be cases where programs cause one or more stacks to overflow as they execute. The following points may help restructure a program so that it runs in available memory:
Iteration is sometimes preferred over recursion from the point of view of stack usage. For example, suppose that we wished to write a program which simply reads some user input and processes it ad infinitum. One approach would be recursive (i.e., a clause which "calls itself'):
doit :- read(X), process(X), doit.
This is fine Prolog code but it may be expensive in memory requirements. Provided there are no choice points in process(X) then Amzi! Prolog will consume no control stack space when it comes to prove the final doit. Further the garbage collector will try to collect heap cells that it may have been left by process(X) (since X is not passed down through doit there is no way that heap cells created by process(X) can be referenced by the recursive call of doit).
Nonetheless, it is possible that eventually you will run out of memory if doit is allowed to run for too long. An equivalent way of performing the same task is to use failure rather then recursion:
doit :- repeat, read(X), process(X), fail.
Try to reduce the number of backtrack points. Recall that if a clause contains no backtrack points, and the goal the clause proves is not itself a backtrack point, then space is reclaimed from the local and control stacks when the clause completes successfully. If you know that the program will never backtrack into a certain goal because of the logic of the program, then a well placed cut at the end of each clause proving the goal can help free up space. This often occurs when multiple clauses are used as a kind of "case statement" but it is known that only one clause will ever be tried. Consider the following example:
goal(<head1>) :- g1, g2. goal(<head2>) :- h1, h2. goal(<head3>) :- i1, i2.
where the terms <head1>, <head2> and <head3> are mutually exclusive. If the goals in the bodies of the clauses have no choice points, or we know we will never wish to backtrack into them, then the above code can be replaced by the following, which is logically and procedurally the same, but will consume less control and local stack space:
goal(<head1>) :- g1, g2, !. goal(<head2>) :- h1, h2, !. goal(<head3>) :- i1, i2, !.
Copyright ©1987-2000 Amzi! inc. All Rights Reserved.