Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-14T01:19:46.340Z Has data issue: false hasContentIssue false
  • English
  • Français

Incremental copying garbage collection for WAM-based Prolog systems

Published online by Cambridge University Press:  01 September 2007

RUBEN VANDEGINSTE  and
BART DEMOEN
RUBEN VANDEGINSTE
Affiliation:
Department of Computer Science, K.U.Leuven, Belgium (e-mail: ruben@cs.kuleuven.ac.be, bmd@cs.kuleuven.ac.be)
BART DEMOEN
Affiliation:
Department of Computer Science, K.U.Leuven, Belgium (e-mail: ruben@cs.kuleuven.ac.be, bmd@cs.kuleuven.ac.be)
Get access Rights & Permissions [Opens in a new window]

Abstract

The design and implementation of an incremental copying heap garbage collector for WAM-based Prolog systems is presented. Its heap layout consists of a number of equal-sized blocks. Other changes to the standard WAM allow these blocks to be garbage collected independently. The independent collection of heap blocks forms the basis of an incremental collecting algorithm which employs copying without marking (contrary to the more frequently used mark© or mark&slide algorithms in the context of Prolog). Compared to standard semi-space copying collectors, this approach to heap garbage collection lowers in many cases the memory usage and reduces pause times. The algorithm also allows for a wide variety of garbage collection policies including generational ones. The algorithm is implemented and evaluated in the context of hProlog.

Keywords

memory management of logic programming languagesincremental copying garbage collectionWAM based Prolog implementation
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 7 , Issue 5 , September 2007 , pp. 505 - 536
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aït-Kaci, H. 1990. The WAM: a (real) tutorial. Tech. Rep. 5, DEC Paris Research Report.Google Scholar
Appleby, K., Carlsson, M., Haridi, S. and Sahlin, D. 1988. Garbage collection for Prolog based on WAM. Communications of the ACM 31, 6 (June), 719–741.CrossRefGoogle Scholar
Bekkers, Y., Ridoux, O. and Ungaro, L. 1992. Dynamic Memory Management for Sequential Logic Programming Languages. In Proceedings of IWMM'92: International Workshop on Memory Management, Bekkers, Y. and Cohen, J., Eds. Number 637 in Lecture Notes in Computer Science. Springer-Verlag, 82–102.Google Scholar
Bevemyr, J. and Lindgren, T. 1994. A simple and efficient copying Garbage Collector for Prolog. In Proceedings of the Sixth International Symposium on Programming Language Implementation and Logic Programming, Hermenegildo, M. and Penjam, J., Eds. Number 844 in Lecture Notes in Computer Science. Springer-Verlag, 88–101.CrossRefGoogle Scholar
Blackburn, S. M., Jones, R. E., McKinley, K. S. and Moss, J. E. B. 2002. Beltway: Getting around garbage collection gridlock. In Proceedings of SIGPLAN 2002 Conference on Programming Languages Design and Implementation, PLDI'02, Berlin, June, 2002. ACM SIGPLAN Notices, vol. 37(5). ACM Press.Google Scholar
Blackburn, S. M. and McKinley, K. S. 2002. In or out?: putting write barriers in their place. In Proceedings of the third international symposium on Memory management. ACM Press, 175–184.Google Scholar
Bruynooghe, M. 1984. Garbage collection in prolog interpreters. In Implementations of Prolog, Campbell, J., Ed. Horwood, Ellis, 259–267.Google Scholar
Castro, L. F. and Costa, V. S. 2001. Understanding Memory Management in Prolog Systems. In Proceedings of the 17th International Conference on Logic Programming, ICLP'2001, Codognet, P., Ed. Number 2237 in Lecture Notes in Computer Science. Springer-Verlag, 11–26.Google Scholar
Demoen, B., Engels, G. and Tarau, P. 1996. Segment order preserving copying Garbage Collection for WAM based Prolog. In Proceedings of the 1996 ACM Symposium on Applied Computing. ACM Press, 380–386.CrossRefGoogle Scholar
Demoen, B., García de la Banda, M., Harvey, W., Mariott, K. and Stuckey, P. 1999. An overview of HAL. In Proceedings of the International Conference on Principles and Practice of Constraint Programming, Jaffar, J., Ed. LNCS, vol. 1713. Springer, 174–188.Google Scholar
Demoen, B. and Nguyen, P.-L. 2000. So many WAM variations, so little time. In Computational Logic – CL2000, First International Conference, London, UK, July 2000, Proceedings, Lloyd, J., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Palamidessi, C., Pereira, L. M., Sagiv, Y., and Stuckey, P. J., Eds. Lecture Notes in Artificial Intelligence, vol. 1861. ALP, Springer, 1240–1254.Google Scholar
Demoen, B., Nguyen, P.-L. and Vandeginste, R. 2002. Copying garbage collection for the WAM: to mark or not to mark? In Proceedings of ICLP2002 – International Conference on Logic Programming, Stuckey, P., Ed. Number 2401 in Lecture Notes in Computer Science. ALP, Springer-Verlag, Copenhagen, 194–208.CrossRefGoogle Scholar
Hudson, R. L. and Moss, J. E.B.. 1992. Incremental collection of mature objects. In Proc. Int. Workshop on Memory Management. Number 637. Springer-Verlag, Saint-Malo (France), 388–403.CrossRefGoogle Scholar
Jones, R. and Lins, R. 1996. Garbage Collection: Algorithms for automatic memory management. John Wiley. See also http://www.cs.ukc.ac.uk/people/staff/rej/gcbook/gcbook.html.Google Scholar
Li, X. 2000. Efficient Memory Management in a merged Heap/Stack Prolog Machine. In Proceedings of the 2nd ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'00). ACM Press, 245–256.Google Scholar
Mehl, M. 1999. The oz virtual machine – records, transients, and deep guards. Ph.D. thesis, Technische Fakultät der Universität des Saarlandes.Google Scholar
Nethercote, N. 2004. Dynamic binary analysis and instrumentation. Ph.D. thesis, Computer Laboratory, University of Cambridge, United Kingdom.Google Scholar
Nethercote, N. and Seward, J. 2003. Valgrind: A program supervision framework. In Proceedings of the Third Workshop on Runtime Verification (RV'03). Boulder, Colorado, USA.Google Scholar
Pittomvils, E., Bruynooghe, M. and Willems, Y. D. 1985. Towards a real time garbage collector for PROLOG. In Proc. 1985 Logic Programming Symposium. IEEE, IEEE Computer Society Press, 185–198.Google Scholar
Quintus. 1989. Personal Communication from Richard O'Keefe and Mats Carlsson.Google Scholar
Scheidhauer, R. 1998. Design, implementierung und evaluierung einer virtuellen maschine für Oz. PhD thesis, Universität des Saarlandes, Fachbereich Informatik, Saarbrücken, Germany.Google Scholar
Seward, J., Nethercote, N., Fitzhardinge, J. et al. Valgrind. http://www.valgrind.org.Google Scholar
Touati, H. and Hama, T. 1988. A light-weight Prolog garbage collector. In Proceedings of the International Conference on Fifth Generation Computer Systems (FGCS'88). OHMSHA Ltd. Tokyo and Springer-Verlag, 922–930.Google Scholar
Warren, D. H. D. 1983. An Abstract Prolog Instruction Set. Tech. Rep. 309, SRI.Google Scholar
Wilson, P. R. 1992. Uniprocessor garbage collection techniques. In Proc. Int. Workshop on Memory Management. Number 637. Springer-Verlag, Saint-Malo (France).Google Scholar