{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T14:23:47Z","timestamp":1649168627774},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2012,5,29]],"date-time":"2012-05-29T00:00:00Z","timestamp":1338249600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Region-based memory management (RBMM) is a form of compile time memory management, well-known from the world of functional programming. In this paper we describe our work on implementing RBMM for the logic programming language Mercury. One interesting point about Mercury is that it is designed with strong type, mode, and determinism systems. These systems not only provide Mercury programmers with several direct software engineering benefits, such as self-documenting code and clear program logic, but also give language implementors a large amount of information that is useful for program analyses. In this work, we make use of this information to develop program analyses that determine the distribution of data into regions and transform Mercury programs by inserting into them the necessary region operations. We prove the correctness of our program analyses and transformation. To execute annotated programs, we have implemented runtime support that tackles the two main challenges posed by backtracking. First, backtracking can require regions removed during forward execution to be \u201cresurrected\u201d; and second, any memory allocated during computation that has been backtracked over must be recovered promptly without waiting for the regions involved to come to the end of their life. We describe in detail our solution of both these problems. We study in detail how our RBMM system performs on a selection of benchmark programs, including some well-known difficult cases for RBMM. Even with these difficult cases, our RBMM-enabled Mercury system obtains clearly faster runtimes for 15 out of 18 benchmarks compared to the base Mercury system with its Boehm runtime garbage collector, with an average runtime speedup of 24%, and an average reduction in memory requirements of 95%. In fact, our system achieves optimal memory consumption in some programs.<\/jats:p>","DOI":"10.1017\/s1471068412000075","type":"journal-article","created":{"date-parts":[[2012,5,29]],"date-time":"2012-05-29T13:36:20Z","timestamp":1338298580000},"page":"959-1024","source":"Crossref","is-referenced-by-count":1,"title":["Region-based memory management for Mercury programs"],"prefix":"10.1017","volume":"13","author":[{"given":"QUAN","family":"PHAN","sequence":"first","affiliation":[]},{"given":"GERDA","family":"JANSSENS","sequence":"additional","affiliation":[]},{"given":"ZOLTAN","family":"SOMOGYI","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2012,5,29]]},"reference":[{"key":"S1471068412000075_ref31","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2613"},{"key":"S1471068412000075_ref30","unstructured":"Tofte M. , Birkedal L. , Elsman M. , Hallenberg N. , Olesen T. and Sestoft P. 2006. Programming with Regions in the MLKit. Accessed 3 December 2009. URL: http:\/\/www.it.edu\/research\/mlkit\/dist\/mlkit-4.3.0.pdf."},{"key":"S1471068412000075_ref29","doi-asserted-by":"publisher","DOI":"10.1023\/B:LISP.0000029446.78563.a4"},{"key":"S1471068412000075_ref28","first-page":"32","volume-title":"Proceedings of the 23rd ACM SIGPLAN Symposium on Principles of Programming Languages","author":"Steensgaard","year":"1996"},{"key":"S1471068412000075_ref27","first-page":"150","volume-title":"Proceedings of the Eighth International Symposium on Practical Aspects of Declarative languages","author":"Somogyi","year":"2006"},{"key":"S1471068412000075_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(96)00068-4"},{"key":"S1471068412000075_ref23","first-page":"317","volume-title":"Proceedings of the 23rd International Conference on Logic Programming","author":"Phan","year":"2007"},{"key":"S1471068412000075_ref18","unstructured":"Mazur N. 2004. Compile-time Garbage Collection for the Declarative Language Mercury. PhD thesis, Department of Computer Science, Katholieke Universiteit Leuven, Belgium."},{"key":"S1471068412000075_ref16","doi-asserted-by":"crossref","unstructured":"Makholm H. 2000b. Region-Based Memory Management in Prolog. MS thesis, University of Copenhagen, Copenhagen, Denmark.","DOI":"10.1145\/362422.362434"},{"key":"S1471068412000075_ref24","first-page":"161","volume-title":"Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming","author":"Phan","year":"2009"},{"key":"S1471068412000075_ref15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/362422.362434","volume-title":"Proceedings of the Second International Symposium on Memory Management","author":"Makholm","year":"2000"},{"key":"S1471068412000075_ref14","first-page":"175","volume-title":"Proceedings of the Symposium on Principles and Practice of Declarative Programming","author":"Henglein","year":"2001"},{"key":"S1471068412000075_ref13","first-page":"150","volume-title":"Proceedings of the Third International Symposium on Memory Management","author":"Henderson","year":"2002"},{"key":"S1471068412000075_ref12","first-page":"141","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Hallenberg","year":"2002"},{"key":"S1471068412000075_ref11","first-page":"282","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Grossman","year":"2002"},{"key":"S1471068412000075_ref10","first-page":"313","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Gay","year":"1998"},{"key":"S1471068412000075_ref4","first-page":"171","volume-title":"Proceedings of the 23rd ACM SIGPLAN Symposium on Principles of Programming Languages","author":"Birkedal","year":"1996"},{"key":"S1471068412000075_ref25","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/1375634.1375644","volume-title":"Proceedings of the Seventh International Symposium on Memory Management","author":"Phan","year":"2008"},{"key":"S1471068412000075_ref17","first-page":"163","volume-title":"Proceedings of the 18th International Conference on Logic Programming","author":"Makholm","year":"2002"},{"key":"S1471068412000075_ref19","first-page":"1255","volume-title":"Proceedings of First International Conference on Computational Logic","author":"Mazur","year":"2000"},{"key":"S1471068412000075_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796807006399"},{"key":"S1471068412000075_ref7","first-page":"296","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Chase","year":"1990"},{"key":"S1471068412000075_ref21","unstructured":"Mercury team 2009. The Mercury Programming Language Reference Manual. Accessed 3 December 2009. URL: http:\/\/www.cs.mu.oz.au\/research\/mercury\/information\/doc-latest\/mercury_ref."},{"key":"S1471068412000075_ref20","first-page":"105","volume-title":"Proceedings of the 17th International Conference on Logic Programming","author":"Mazur","year":"2001"},{"key":"S1471068412000075_ref1","first-page":"174","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Aiken","year":"1995"},{"key":"S1471068412000075_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03811-6"},{"key":"S1471068412000075_ref3","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/91556.91652","volume-title":"Proceedings of the ACM Conference on LISP and Functional Programming","author":"Baker","year":"1990"},{"key":"S1471068412000075_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380180902"},{"key":"S1471068412000075_ref8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1145\/1029873.1029884","volume-title":"Proceedings of the Fourth International Symposium on Memory Management","author":"Cherem","year":"2004"},{"key":"S1471068412000075_ref9","first-page":"243","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Chin","year":"2004"},{"key":"S1471068412000075_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45142-0_6"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068412000075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,16]],"date-time":"2022-01-16T12:15:14Z","timestamp":1642335314000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068412000075\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,29]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["S1471068412000075"],"URL":"https:\/\/doi.org\/10.1017\/s1471068412000075","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,29]]}}}