Access Restriction

Author Sawhlin, D. ♦ Carllson, M. ♦ Appleby, K. ♦ Haridi, S.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
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.
Description Affiliation: IBM Thomas J. Watson Research Center, Yorktown Heights, NY (Appleby, K.) || SICS, P.O. Box 1263, S-164 28 Kista, Sweden (Carllson, M.; Haridi, S.; Sawhlin, D.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 31
Issue Number 6
Page Count 23
Starting Page 719
Ending Page 741

Open content in new tab

   Open content in new tab
Source: ACM Digital Library