Abstract
Compile-time garbage collection (CTGC) is still a very uncommon feature within compilers. In previous work we have developed a compile-time structure reuse system for Mercury, a logic programming language. This system indicates which datastructures can safely be reused at run-time. As preliminary experiments were promising, we have continued this work and have now a working and well performing near-to-ship CTGC-system built into the Melbourne Mercury Compiler (MMC).
In this paper we present the multiple design decisions leading to this system, we report the results of using CTGC for a set of benchmarks, including a real-world program, and finally we discuss further possible improvements. Benchmarks show substantial memory savings and a noticeable reduction in execution time.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Y. Bekkers and P. Tarau. Monadic constructs for logic programming. In J. Lloyd, editor, Proceedings of the International Symposium on Logic Programming, pages 51–65, Cambridge, Dec. 4–7 1995. MIT Press.
M. Bruynooghe. A practical framework for the abstract interpretation of logic programs. Journal of Logic Programming, 10(2):91–124, Feb. 1991.
M. Bruynooghe, G. Janssens, and A. Kågedal. Live-structure analysis for logic programming languages with declarations. In L. Naish, editor, Proceedings of the Fourteenth International Conference on Logic Programming (ICLP’97), pages 33–47, Leuven, Belgium, 1997. MIT Press.
F. Bueno, D. Cabeza, M. Hermenegildo, and G. Puebla. Global Analysis of Standard Prolog Programs. In European Symposium on Programming, number 1058 in LNCS, pages 108–124, Sweden, April 1996. Springer-Verlag.
F. Bueno, M. García de la Banda, M. Hermenegildo, K. Marriott, G. Puebla, and P. J. Stuckey. A model for inter-module analysis and optimizing compilation. In Tenth International Workshop on Logic-based Program Synthesis and Transformation, London, UK, 2000. to appear.
P. Cousot and R. Cousot. Comparing the Galois connection and widening/ narrowing approaches to abstract interpretation. In M. Bruynooghe and M. Wirsing, editors, Proceedings of the Fourth International Symposium on Programming Language Implementation and Logic Programming, pages 269–295, Leuven, Belgium, 1992. LNCS 631, Springer-Verlag.
S. K. Debray. On copy avoidance in single assignment languages. In D. S. Warren, editor, Proceedings of the Tenth International Conference on Logic Programming, pages 393–407, Budapest, Hungary, 1993. The MIT Press.
B. Demoen, M. García de la Banda, W. Harvey, K. Marriott, and P. J. Stuckey. An overview of HAL. In Proceedings of the International Conference on Principles and Practice of Constraint Programming, pages 174–188, Virginia, USA, October 1999. Springer Verlag.
T. Dowd, Z. Somogyi, F. Henderson, T. Conway, and D. Jeffery. Run Time Type Information in Mercury. In Principles and Practice of Declarative Programming, pages 224–243, 1999.
G. Gudjónsson and W. H. Winsborough. Compile-time memory reuse in logic programming languages through update in place. ACM Transactions on Programming Languages and Systems, 21(3):430–501, May 1999.
F. Henderson, T. Conway, Z. Somogyi, and D. Jeffery. The Mercury language reference manual. Technical Report 96/10, Dept. of Computer Science, University of Melbourne, February 1996.
M. Hermenegildo, F. Bueno, G. Puebla, and P. López. Program Analysis, Debugging and Optimization Using the Ciao System Preprocessor. In D. D. Schreye, editor, 1999 International Conference on Logic Programming, pages 52–66, Cambridge, MA, December 1999. MIT Press.
A. Kågedal and S. Debray. A practical approach to structure reuse of arrays in single assignment languages. In L. Naish, editor, Proceedings of the 14th International Conference on Logic Programming, pages 18–32, Cambridge, July 8–11 1997. MIT Press.
F. Kluźniak. Compile-time garbage collection for ground Prolog. In R. A. Kowalski and K. A. Bowen, editors, Proceedings of the Fifth International Conference and Symposium on Logic Programming, pages 1490–1505, Seattle, 1988. MIT Press, Cambridge.
N. Mazur, G. Janssens, and M. Bruynooghe. A module based analysis for memory reuse in Mercury. In J. Lloyd, V. Dahl, U. Furbach, M. Kerber, K.-K. Lau, C. Palamidessi, L. Moniz Pereira, Y. Sagiv, and P. J. Stuckey, editors, Computational Logic-CL 2000, First International Conference, London, UK, July 2000, Proceedings, volume 1861 of Lecture Notes in Artificial Intelligence, pages 1255–1269. Springer-Verlag, 2000.
M. Mohnen. Optimising the Memory Management of Higher-Order Functional Programs. Technical Report AIB-97-13, RWTHAac hen, 1997. PhD Thesis.
G. Morrisett and J. Reppy. The third annual ICFP programming contest. In Conjunction with the 2000 International Conference on Functional Programming, http://www.cs.cornell.edu/icfp/, 2000.
A. Mulkers, W. Winsborough, and M. Bruynooghe. Live-structure dataow analysis for Prolog. ACM Transactions on Programming Languages and Systems, 16(2):205–258, Mar. 1994.
Z. Somogyi, F. Henderson, and T. Conway. The execution algorithm of Mercury, an efficient purely declarative logic programming language. The Journal of Logic Programming, 29(1–3):17–64, October-December 1996.
M. Tofte and J.-P. Talpin. Region-based memory management. Information and Computation, 132(2):109–176, 1997.
P. Wadler. The essence of functional programming. In Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACTSymp osium on Principles of Programming Languages, pages 1–14, Albequerque, New Mexico, Jan. 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mazur, N., Ross, P., Janssens, G., Bruynooghe, M. (2001). Practical Aspects for a Working Compile Time Garbage Collection System for Mercury. In: Codognet, P. (eds) Logic Programming. ICLP 2001. Lecture Notes in Computer Science, vol 2237. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45635-X_15
Download citation
DOI: https://doi.org/10.1007/3-540-45635-X_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42935-7
Online ISBN: 978-3-540-45635-3
eBook Packages: Springer Book Archive