Real-time memory management for Prolog | SpringerLink
Skip to main content
Springer Nature Link
Log in

Real-time memory management for Prolog

  • Conference paper
  • First Online:
Logic Programming

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 592))

  • 155 Accesses

Abstract

This paper relates a long experiment on implementing real time garbage collectors for Prolog. First, the main peculiarities of Prolog memory management are briefly reviewed. The relation between non-determinism and garbage collection are explained. Early-reset and variable shunting are presented. Attributed variables, a new type of data for implementing Prolog extensions and realizing a value trail mechanism is introduced. Then, a realtime garbage collection algorithm, taking these aspects into account, is entirely presented. The synchronizing problems, including those linked to non-determinism, are discussed in details. Finally, two concrete implementations are described.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Appleby, K., Carlsson, M., Haridi, S., and Sahlin, D. Garbage collection for Prolog Based on the WAM. Communications of the ACM 31, 6 (June 1988), pp. 719–741.

    Article  Google Scholar 

  2. Baker, H.G. List processing in real time on a serial computer. Communications of the ACM 21, 4 (April 1978), pp. 280–294.

    Article  Google Scholar 

  3. Barklund, J. A Garbage collection Algorithm for Tricia. Tech. Rept. 37B, UPMAIL, Uppsala University, Sweeden, December, 1987.

    Google Scholar 

  4. Barklund, J. and Millroth, H. Hash Tables in Logic Programming. In Proceedings of the International conference on Logic Programming, ICLP87, Lassez, J.L., Melbourne, Austria, MIT Press, May 1987, pp. 411–427.

    Google Scholar 

  5. Bekkers, Y., Canet, B., Ridoux, O., and Ungaro, L. A short note on garbage collection in Prolog interpreters. Logic Programming News letters, 5 (1984).

    Google Scholar 

  6. Bekkers, Y., Canet, B., Ridoux, O., and Ungaro, L. A memory management machine for Prolog Interpreters. In Proceedings of the second international Logic Programming conference, Uppsala, Sweden, July 1984, pp. 343–353.

    Google Scholar 

  7. Bekkers, Y., Canet, B., Ridoux, O., and Ungaro, L. A memory with a real-time garbage collector for implementing logic programming languages. In Proceedings of the second International symposium on Logic programming, IEEE, Salt-Lake City, Utah, 1986, pp. 258–265.

    Google Scholar 

  8. Bekkers, Y., Canet, B., Ridoux, O., and Ungaro, L. Mali, A memory for implementing logic programming languages. In Programming of future generation computers, Fuchi, M.N., Tokyo, Japan, Elsevier Sciences Publishers BV North Holland, 1988, pp. 25–34.

    Google Scholar 

  9. Brisset, P. and Ridoux, O. Naive reverse can be linear. In Proceedings of the international conference on Logic programming, Paris, France, June 1991.

    Google Scholar 

  10. Bruynooghe, M. Garbage collection in prolog interpreters. In Implementations of Prolog, J. Campbell, E.H., 1984, pp. 259–267.

    Google Scholar 

  11. Carlsson, M. Freeze, Indexing and other Implementation Issues in the WAM. In Proceedinings of the 4th International Conference on Logic Programming, ICLP87, Lassez, J.L., Melbourne, Australia, MIT Press, May 1987, pp. 40–58.

    Google Scholar 

  12. Cheney, C.J. A nonrecursive list compacting Algorithm. Communications of the ACM 13, 11 (November 1970), pp. 677–678.

    Article  Google Scholar 

  13. Colmerauer, A. Prologll: Manuel de référence et modèle théorique. Tech. Rept. GIA, Université d'Aix-Marseille II, 1982.

    Google Scholar 

  14. le Huitouze, S. Mise en œuvre de Prologll/Mali, Ph.D. dissertation, Université de Rennes I, Décembre 1988.

    Google Scholar 

  15. le Huitouze, S. A new data structure for implementing Extensions to Prolog. In Proceeding PLILP'90, LNCS 456, 1990, pp. 136–150.

    Google Scholar 

  16. Lieberman, H. and Hewitt, C. A real-time garbage collector based on the lifetimes of Objects. Communications of the ACM 26, 6 (June 1983), pp. 419–429.

    Article  Google Scholar 

  17. Neumerkel, U. Extensible Unification by Metastructures. In Proceeding of META90, Leuven, Belgium, May 1990, pp. 352–363.

    Google Scholar 

  18. Pittomvils, E., Bruynooghe, M., and Willems, Y.D. Towards a real time garbage collector for Prolog. In Proceedings of the IEEE Symposium on Logic Programming, Boston, MA, July 1985, pp. 185–198.

    Google Scholar 

  19. Schimpf, J. Garbage collection for Prolog based on twin Cells. In Proceedings of the 2nd NACLP workshop on Logic Programming architecture and implementations, Austin, Texas, November 1990.

    Google Scholar 

  20. Touraïvane, M. La récupération de mémoire dans les machines non déterministes, Ph.D. dissertation, Université Aix-Marseille II, Faculté des Sciences de Luminy, Marseille, France, November 1988.

    Google Scholar 

  21. Turk, A.K. Compiler Optimisations for the WAM. In Proceedinings of the 3rd International Conference on Logic Programming, ICLP86, London, UK, July 1986, pp. 657–662.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INRIA / IRISA, Av. du Général Leclerc, 35042, Rennes-Cedex, France

    Yves Bekkers & Lucien Ungaro

Authors
  1. Yves Bekkers
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lucien Ungaro
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

A. Voronkov

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bekkers, Y., Ungaro, L. (1992). Real-time memory management for Prolog. In: Voronkov, A. (eds) Logic Programming. Lecture Notes in Computer Science, vol 592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55460-2_1

Download citation

  • DOI: https://doi.org/10.1007/3-540-55460-2_1

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-55460-8

  • Online ISBN: 978-3-540-47083-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation