{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:02:12Z","timestamp":1740135732703,"version":"3.37.3"},"reference-count":65,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2018,7,27]],"date-time":"2018-07-27T00:00:00Z","timestamp":1532649600000},"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":[[2018,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>One of the main advantages of Prolog is its potential for the<jats:italic>implicit exploitation of parallelism<\/jats:italic>and, as a high-level language, Prolog is also often used as a means to<jats:italic>explicitly control concurrent tasks<\/jats:italic>. Tabling is a powerful implementation technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant sub-computations. Given these advantages, the question that arises is if tabling has also the potential for the exploitation of concurrency\/parallelism. On one hand, tabling still exploits a search space as traditional Prolog but, on the other hand, the concurrent model of tabling is necessarily far more complex, since it also introduces concurrency on the access to the tables. In this paper, we summarize Yap's main contributions to concurrent tabled evaluation and we describe the design and implementation challenges of several alternative table space designs for implicit and explicit concurrent tabled evaluation that represent different trade-offs between concurrency and memory usage. We also motivate for the advantages of using<jats:italic>fixed-size<\/jats:italic>and<jats:italic>lock-free<\/jats:italic>data structures, elaborate on the key role that the engine's<jats:italic>memory allocator<\/jats:italic>plays on such environments, and discuss how Yap's mode-directed tabling support can be extended to concurrent evaluation. Finally, we present our future perspectives toward an efficient and novel concurrent framework which integrates both implicit and explicit concurrent tabled evaluation in a single Prolog engine.<\/jats:p>","DOI":"10.1017\/s147106841800039x","type":"journal-article","created":{"date-parts":[[2018,7,27]],"date-time":"2018-07-27T07:43:30Z","timestamp":1532677410000},"page":"950-992","source":"Crossref","is-referenced-by-count":0,"title":["Table space designs for implicit and explicit concurrent tabled evaluation"],"prefix":"10.1017","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1589-3174","authenticated-orcid":false,"given":"MIGUEL","family":"AREIAS","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4502-8835","authenticated-orcid":false,"given":"RICARDO","family":"ROCHA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,7,27]]},"reference":[{"unstructured":"Freire J. , Swift T. and Warren D. S. 1996. Beyond depth-first: Improving tabled logic programs through alternative scheduling strategies. In Proc. of International Symposium on Programming Language Implementation and Logic Programming, LNCS, vol. 1140. Springer, 243\u2013258.","key":"S147106841800039X_ref24"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref22","DOI":"10.1007\/s10994-008-5094-2"},{"unstructured":"Shen K. 1992. Exploiting dependent and-parallelism in prolog: The dynamic dependent and-parallel scheme (DDAS). In Proc. of Joint International Conference and Symposium on Logic Programming. The MIT Press, 717\u2013731.","key":"S147106841800039X_ref59"},{"doi-asserted-by":"crossref","unstructured":"Marques R. and Swift T. 2008. Concurrent and local evaluation of normal programs. In Proc. of International Conference on Logic Programming, LNCS, vol. 5366. Springer, 206\u2013222.","key":"S147106841800039X_ref41","DOI":"10.1007\/978-3-540-89982-2_24"},{"doi-asserted-by":"crossref","unstructured":"Areias M. and Rocha R. 2014. On the correctness and efficiency of lock-free expandable tries for tabled logic programs. In Proc. of International Symposium on Practical Aspects of Declarative Languages, M. Flatt and H.-F. Guo , Ed. LNCS, vol. 8324. Springer, San Diego, California, USA, 168\u2013183.","key":"S147106841800039X_ref7","DOI":"10.1007\/978-3-319-04132-2_12"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref2","DOI":"10.1007\/BF01407834"},{"doi-asserted-by":"crossref","unstructured":"Johnson E. , Ramakrishnan C. R. , Ramakrishnan I. V. and Rao P. 1999. A space efficient engine for subsumption-based tabled evaluation of logic programs. In Proc. of Fuji International Symposium on Functional and Logic Programming, LNCS, vol. 1722. Springer, 284\u2013300.","key":"S147106841800039X_ref34","DOI":"10.1007\/10705424_19"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref13","DOI":"10.1145\/209937.209958"},{"volume-title":"Introduction to Parallel Computing: Design and Analysis of Algorithms","year":"1994","author":"Kumar","key":"S147106841800039X_ref37"},{"volume-title":"Intel Threading Building Blocks","year":"2007","author":"Reinders","key":"S147106841800039X_ref50"},{"unstructured":"Ghemawat S. and Menage P. TCMalloc: Thread-Caching Malloc. Accessed 10 November 2014. URL: http:\/\/goog-perftools.sourceforge.net\/doc\/tcmalloc.html [online].","key":"S147106841800039X_ref25"},{"volume-title":"Data Structures Using C","year":"1990","author":"Tenenbaum","key":"S147106841800039X_ref63"},{"unstructured":"Gupta G. and Pontelli E. 1999. Stack splitting: A simple technique for implementing or-parallelism on distributed machines. In Proc. of International Conference on Logic Programming. The MIT Press, 290\u2013304.","key":"S147106841800039X_ref29"},{"volume-title":"Knapsack Problems: Algorithms and Computer Implementations","year":"1990","author":"Martello","key":"S147106841800039X_ref43"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref62","DOI":"10.1017\/S1471068411000500"},{"unstructured":"Somogyi Z. and Sagonas K. 2006. Tabling in mercury: Design and implementation. In Proc. of International Symposium on Practical Aspects of Declarative Languages, LNCS, vol. 3819. Springer, 150\u2013167.","key":"S147106841800039X_ref60"},{"doi-asserted-by":"crossref","unstructured":"Liang S. , Fodor P. , Wan H. and Kifer M. 2009. OpenRuleBench: An analysis of the performance of rule engines. In Proc. of International World Wide Web Conference. ACM, 601\u2013610.","key":"S147106841800039X_ref38","DOI":"10.1145\/1526709.1526790"},{"key":"S147106841800039X_ref4","first-page":"636","volume-title":"International Conference on Parallel and Distributed Systems","author":"Areias","year":"2012"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref3","DOI":"10.1017\/S147106841100024X"},{"volume-title":"Using OpenMP: Portable Shared Memory Parallel Programming","year":"2008","author":"Chapman","key":"S147106841800039X_ref15"},{"doi-asserted-by":"crossref","unstructured":"Areias M. and Rocha R. 2015. Batched evaluation of full-sharing multithreaded tabling. In Proc. of Post-Proceedings of the 4th Symposium on Languages, Applications and Technologies. CCIS, vol. 563. Springer, 113\u2013124.","key":"S147106841800039X_ref8","DOI":"10.1007\/978-3-319-27653-3_11"},{"unstructured":"Chico P. , Carro M. , Hermenegildo M. V. , Silva C. and Rocha R. 2008. An improved continuation call-based implementation of tabling. In Proc. of International Symposium on Practical Aspects of Declarative Languages, LNCS, vol. 4902. Springer, 197\u2013213.","key":"S147106841800039X_ref17"},{"unstructured":"Santos Costa, V. , Warren D. H. D. and Yang R. 1991. Andorra-I: A parallel prolog system that transparently exploits both and- and or-parallelism. In Proc. of ACM Symposium on Principles and Practice of Parallel Programming. ACM, 83\u201393.","key":"S147106841800039X_ref58"},{"unstructured":"Alba E. , Almeida F. , Blesa M. J. , Cabeza J. , Cotta C. , D\u00ed-az M. , Dorta I. , Gabarr\u00f3 J. , Le\u00f3n C. , Luna J. , Moreno L. M. , Pablos C. , Petit J. , Rojas A. , and Xhafa F. 2002. MALLBA: A library of skeletons for combinatorial optimisation (research note). In Proc. of International Euro-Par Conference, LNCS, vol. 2400. Springer, 927\u2013932.","key":"S147106841800039X_ref1"},{"unstructured":"Bagwell P. 2001. Ideal Hash Trees. Technical report.","key":"S147106841800039X_ref11"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref32","DOI":"10.1007\/BF03037164"},{"doi-asserted-by":"crossref","unstructured":"Herlihy M. and Wing J. M. 1987. Axioms for concurrent objects. In Proc. ACM Symposium on Principles of Programming Languages. ACM, 13\u201326.","key":"S147106841800039X_ref31","DOI":"10.21236\/ADA200584"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref9","DOI":"10.1007\/s10766-014-0346-1"},{"unstructured":"Gloger W. Ptmalloc. Accessed 15 November 2014. URL: http:\/\/www.malloc.de\/en\/.","key":"S147106841800039X_ref27"},{"doi-asserted-by":"crossref","unstructured":"Masmano M. , Ripoll I. and Crespo A. 2006. A comparison of memory allocators for real-time applications. In Proc. of the 4th International Workshop on Java Technologies for Real-time and Embedded Systems, JTRES '06. ACM, 68\u201376.","key":"S147106841800039X_ref44","DOI":"10.1145\/1167999.1168012"},{"unstructured":"Pel\u00e1ez I. , Almeida F. and Su\u00e1rez F. 2007. DPSKEL: A skeleton based tool for parallel dynamic programming. In Proc. of International Conference on Parallel Processing and Applied Mathematics, LNCS, vol. 4967. Springer, 1104\u20131113.","key":"S147106841800039X_ref46"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref23","DOI":"10.1145\/367390.367400"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref30","DOI":"10.1145\/504083.504085"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref65","DOI":"10.1007\/978-3-319-25883-6"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref39","DOI":"10.1017\/S0956796805005526"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref5","DOI":"10.1017\/S1471068412000117"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref12","DOI":"10.1145\/356989.357000"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref16","DOI":"10.1145\/227595.227597"},{"doi-asserted-by":"crossref","unstructured":"Cruz F. and Rocha R. 2010. Retroactive subsumption-based tabled evaluation of logic programs. In Proc. of European Conference on Logics in Artificial Intelligence, LNAI, vol. 6341. Springer, 130\u2013142>.","key":"S147106841800039X_ref19","DOI":"10.1007\/978-3-642-15675-5_13"},{"doi-asserted-by":"crossref","unstructured":"Costa J. , Raimundo J. and Rocha R. 2009. A term-based global trie for tabled logic programs. In Proc. of International Conference on Logic Programming. LNCS, vol. 5649. Springer, 205\u2013219.","key":"S147106841800039X_ref18","DOI":"10.1007\/978-3-642-02846-5_20"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref10","DOI":"10.1016\/j.jss.2016.06.060"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref33","DOI":"10.1142\/S0129626400000238"},{"volume-title":"The Art of Computer Programming, volume 3: (2nd ed.) Sorting and Searching","year":"1998","author":"Knuth","key":"S147106841800039X_ref35"},{"doi-asserted-by":"crossref","unstructured":"Santos J. and Rocha R. 2013. On the efficient implementation of mode-directed tabling. In Proc. of International Symposium on Practical Aspects of Declarative Languages, LNCS, vol. 7752. Springer, 141\u2013156.","key":"S147106841800039X_ref56","DOI":"10.1007\/978-3-642-45284-0_10"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref61","DOI":"10.1016\/j.jpdc.2010.01.004"},{"key":"S147106841800039X_ref57","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1017\/S1471068411000512","article-title":"The YAP prolog system","volume":"12","author":"Santos","year":"2012","journal-title":"Journal of Theory and Practice of Logic Programming"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref53","DOI":"10.1017\/S1471068404002030"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref54","DOI":"10.1145\/291889.291897"},{"key":"S147106841800039X_ref6","first-page":"1775","article-title":"Batched evaluation of linear tabled logic programs","volume":"10","author":"Areias","year":"2013","journal-title":"Journal of Computer Science and Information Systems, Special Issue on Advances in Model Driven Engineering, Languages and Agents"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref26","DOI":"10.1007\/s00453-008-9268-x"},{"doi-asserted-by":"crossref","unstructured":"Saha D. 2006. Incremental Evaluation of Tabled Logic Programs. Ph.D. thesis, Department of Computer Science, State University of New York.","key":"S147106841800039X_ref55","DOI":"10.1007\/11799573_7"},{"unstructured":"Moura P. 2008. ISO\/IEC DTR 13211\u20135:2007 Prolog Multi-threading Predicates.","key":"S147106841800039X_ref45"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref20","DOI":"10.1017\/S1471068415000137"},{"unstructured":"Lusk E. , Butler R. , Disz T. , Olson R. , Overbeek R. , Stevens R. , Warren D. H. D. , Calderwood A. , Szeredi P. , Haridi S. , Brand P. , Carlsson M. , Ciepielewski A. and Hausman B. 1988. The aurora Or-parallel prolog system. In Proc. of International Conference on 5th Generation Computer Systems. Institute for New Generation Computer Technology, 819\u2013830.","key":"S147106841800039X_ref40"},{"doi-asserted-by":"crossref","unstructured":"Guo H.-F. and Gupta G. 2001. A simple scheme for implementing tabled logic programming systems based on dynamic reordering of alternatives. In Proc. of International Conference on Logic Programming. LNCS, vol. 2237. Springer, 181\u2013196.","key":"S147106841800039X_ref28","DOI":"10.1007\/3-540-45635-X_20"},{"volume-title":"Introduction to Parallel Computing","year":"2002","author":"Kumar","key":"S147106841800039X_ref36"},{"unstructured":"Evans J. 2006. A scalable concurrent malloc(3) implementation for FreeBSD. In Proc. of the Technical BSD Conference.","key":"S147106841800039X_ref21"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref64","DOI":"10.1017\/S1471068411000445"},{"unstructured":"Rocha R. , Silva F. and Santos Costa, V. 1999. Or-parallelism within tabling. In Proc. of International Workshop on Practical Aspects of Declarative Languages. LNCS, vol. 1551. Springer, 137\u2013151.","key":"S147106841800039X_ref51"},{"doi-asserted-by":"crossref","unstructured":"Marques R. , Swift T. and Cunha J. C. 2010. A simple and efficient implementation of concurrent local tabling. In Proc. of International Symposium on Practical Aspects of Declarative Languages, LNCS, vol. 5937. Springer, 264\u2013278.","key":"S147106841800039X_ref42","DOI":"10.1007\/978-3-642-11503-5_22"},{"unstructured":"Pontelli E. and Gupta G. 1997. Implementation mechanisms for dependent and-parallelism. In Proc. of International Conference on Logic Programming. The MIT Press, 123\u2013137.","key":"S147106841800039X_ref47"},{"unstructured":"Carro M. and Hermenegildo M. V. 1999. Concurrency in prolog using threads and a shared database. In Proc. of International Conference on Logic Programming. The MIT Press, 320\u2013334.","key":"S147106841800039X_ref14"},{"doi-asserted-by":"publisher","key":"S147106841800039X_ref48","DOI":"10.1016\/S0743-1066(98)10013-4"},{"unstructured":"Rao P. , Ramakrishnan C. R. and Ramakrishnan I. V. 1996. A thread in time saves tabling time. In Proc. of Joint International Conference and Symposium on Logic Programming. The MIT Press, 112\u2013126.","key":"S147106841800039X_ref49"},{"doi-asserted-by":"crossref","unstructured":"Rocha R. , Silva F. and Santos Costa, V. 2001. On a tabling engine that can exploit or-parallelism. In Proc. of International Conference on Logic Programming, LNCS, vol. 2237. Springer, 43\u201358.","key":"S147106841800039X_ref52","DOI":"10.1007\/3-540-45635-X_11"}],"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\/S147106841800039X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,21]],"date-time":"2019-10-21T06:49:03Z","timestamp":1571640543000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106841800039X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,27]]},"references-count":65,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["S147106841800039X"],"URL":"https:\/\/doi.org\/10.1017\/s147106841800039x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2018,7,27]]}}}