Garbarge collection for Prolog based on WAM

ABSTRACT

The Warren abstract machine (WAM) has become a generally accepted standard Prolog implementation technique. Garbage collection is an important aspect in the implementation of any Prolog system. A synopsis of the WAM is presented and then marking and compaction algorithms are shown that take advantage of WAM's unique use of the data areas. Marking and compaction are performed on both the heap and the trail; both use pointer reversal techniques, which obviate the need for extra stack space. However, two bits for every pointer on the heap are reserved for the garbage collection algorithm. The algorithm can work on segments of the heap, which may lead to a significant reduction of the total garbage collection time. The time of the algorithms are linear in the size of the areas.

REFERENCES

• 1: Barklund, J., and Millroth, H. Garbage cut for garbage collection of iterative Prolog programs. In Proceedings of the 1986 Symposium on Logic Programming (Salt Lake City, Utah).
• 2: Bekkers, Y., Caner, B., Ridoux, O., and Ungaro. L. A short note on garbage collection in Prolog interpreters. Logic Programming Newsletter, no. 5 (Winter 83/84).
• 3: Bruynooghe, M. A note on garbage collection in Prolog interpreters. In Proceedings of the First International Logic Programming Conference, 1982, pp. 52-55.
• 4: Bruynooghe, M. Garbage collection in Prolog interpreters. In J. Campbell (Ed.), Implementations of PROLOG, Ellis Horwood, Chichester, England 1984, pp. 259-267.
• 5: Bruynooghe, M. The memory management of Prolog implementations. In K.L. Clark and S-A T~irnlund (Eds.), Logic Programming. Academic Press, New York, 1982, pp. 82-98.
• 6: Carlsson, M. Compilation for Tricia and its abstract machine. Tech. Rep. 35, 1986, UPMAIL, Uppsata University.
• 7: Gabriel. J., Lindholm, T., Lusk, E.L., and Overbeek, R.A. Tutorial on the Warren abstract machine for computational logic. Tech. Rep. ANL-84-84, Argonne National Lab., Argonne, Ill.
• 8: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 9: F. Lockwood Morris, A time- and space-efficient garbage compaction algorithm, Communications of the ACM, v.21 n.8, p.662-665, Aug. 1978 [doi>10.1145/359576.359583]
• 10: Sahlin, D. Garbage collection using the reset information and making tests deterministic using the rese! information. SICS working document. SICS, Kista, Sweden, Mar. 1986.
• 11: Sahtin, D. Making the garbage collection independent of the amount of garbage. Res. Rep. R87008, SICS, Kista, Sweden, ISSN 0283-3638.
• 12: Thorelli, L-E. Marking algorithms. BIT 12, 4 (1972), 555-568.
• 13: Pittomvils, E., Bruynooghe, M., Willems, Y.D. Towards a real time garbage collector for Prolog. In Proceedings of the Symposium on Logic Programming, 1985, pp. 185-198.
• 14: Warren, D.H.D. An abstract Prolog instruction set. Tech. Note 309, SRI International, Menlo Park, Calif., Oct. 1983.
• 15: Warren, D.H.D. Implementing Prolog--Compiling predicate logic programs. Rep. 39 and 40, University of Edinburgh, Department of Artificial Intelligence, Edinburgh, Scotland, May 1977.
• 16: Warren, D.S. The runtime environment for a Prolog compiler using a copy algorithm. Tech. Rep. 83/052, SUNY at Stony Brook, N.Y., 1983. Major revision. March 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Prolog

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Design, Languages, Performance, Theory