{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T18:46:34Z","timestamp":1648925194784},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2010,1,18]],"date-time":"2010-01-18T00:00:00Z","timestamp":1263772800000},"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":[[2011,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The most successful <jats:italic>unfolding rules<\/jats:italic> used nowadays in the partial evaluation of logic programs are based on <jats:italic>well quasi orders<\/jats:italic> (wqo) applied over (covering) <jats:italic>ancestors<\/jats:italic>, i.e., a subsequence of the atoms selected during a derivation. Ancestor (sub)sequences are used to increase the specialization power of unfolding while still guaranteeing termination and also to reduce the number of atoms for which the wqo has to be checked. Unfortunately, maintaining the structure of the ancestor relation during unfolding introduces significant overhead. We propose an efficient, practical <jats:italic>local<\/jats:italic> unfolding rule based on the notion of covering ancestors which can be used in combination with a wqo and allows a stack-based implementation without losing any opportunities for specialization. Using our technique, certain nonleftmost unfoldings are allowed as long as local unfolding is performed, i.e., we cover depth-first strategies. To deal with practical programs, we propose assertion-based techniques which allow our approach to treat programs that include (Prolog) built-ins and external predicates in a very extensible manner, for the case of leftmost unfolding. Finally, we report on our implementation of these techniques embedded in a practical partial evaluator, which shows that our techniques, in addition to dealing with practical programs, are also significantly more efficient in time and somewhat more efficient in memory than traditional tree-based implementations.<\/jats:p>","DOI":"10.1017\/s1471068409990263","type":"journal-article","created":{"date-parts":[[2010,1,18]],"date-time":"2010-01-18T08:58:45Z","timestamp":1263805125000},"page":"1-32","source":"Crossref","is-referenced-by-count":0,"title":["Efficient local unfolding with ancestor stacks"],"prefix":"10.1017","volume":"11","author":[{"given":"GERM\u00c1N","family":"PUEBLA","sequence":"first","affiliation":[]},{"given":"ELVIRA","family":"ALBERT","sequence":"additional","affiliation":[]},{"given":"MANUEL","family":"HERMENEGILDO","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2010,1,18]]},"reference":[{"key":"S1471068409990263_ref7","unstructured":"Bueno F. , Cabeza D. , Carro M. , Hermenegildo M. , L\u00f3pez-Garc\u00eda P. and Puebla G. (Eds.) 2009. The Ciao System. Reference Manual. Vol. 1.13. Technical report URL: http:\/\/www.ciaohome.org."},{"key":"S1471068409990263_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(95)00149-2"},{"key":"S1471068409990263_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037142"},{"key":"S1471068409990263_ref29","first-page":"465","volume-title":"Proc. of ILPS'95","author":"S\u00f8rensen","year":"1995"},{"key":"S1471068409990263_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF03038271"},{"key":"S1471068409990263_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-83189-8"},{"key":"S1471068409990263_ref19","first-page":"230","volume-title":"Proceedings of SAS'98","author":"Leuschel","year":"1998"},{"key":"S1471068409990263_ref23","first-page":"139","article-title":"Offline specialisation in prolog using a hand-written compiler generator","volume":"4","author":"Leuschel","year":"2004","journal-title":"TPLP"},{"key":"S1471068409990263_ref6","volume-title":"The Ciao System. Reference Manual","author":"Bueno","year":"2004"},{"key":"S1471068409990263_ref1","volume-title":"Compilers \u2013 Principles, Techniques and Tools","author":"Aho","year":"1986"},{"key":"S1471068409990263_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)90027-M"},{"key":"S1471068409990263_ref12","first-page":"88","volume-title":"Proc. of PEPM'93, the ACM Sigplan Symposium on Partial Evaluation and Semantics-Based Program Manipulation","author":"Gallagher","year":"1993"},{"key":"S1471068409990263_ref17","first-page":"122","volume-title":"Proc. of LOPSTR'94 and META'94","author":"Leuschel","year":"1994"},{"key":"S1471068409990263_ref2","first-page":"1","article-title":"A practical partial evaluation scheme for multi-paradigm declarative languages","volume":"2002","author":"Albert","year":"2002","journal-title":"Journal of Functional and Logic Programming"},{"key":"S1471068409990263_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S147106840200145X"},{"key":"S1471068409990263_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2005.02.006"},{"key":"S1471068409990263_ref15","first-page":"210","article-title":"Well-quasi-ordering, the tree theorem, and vazsonyi's conjecture","volume":"95","author":"Kruskal","year":"1960","journal-title":"Transactions of the American Mathematical Society"},{"key":"S1471068409990263_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/963778.963784"},{"key":"S1471068409990263_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037527"},{"key":"S1471068409990263_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-25951-0_11"},{"key":"S1471068409990263_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)80001-T"},{"key":"S1471068409990263_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00030-8"},{"key":"S1471068409990263_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/258993.259014"},{"key":"S1471068409990263_ref3","first-page":"115","volume-title":"Fiftheenth International Symposium on Logic-based Program Synthesis and Transformation (LOPSTR'05)","author":"Albert","year":"2006"},{"key":"S1471068409990263_ref14","volume-title":"Partial Evaluation and Automatic Program Generation","author":"Jones","year":"1993"},{"key":"S1471068409990263_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068402001114"},{"key":"S1471068409990263_ref18","unstructured":"Leuschel M. 1996\u20132002a. The ecce partial deduction system and the dppd library of benchmarks. Obtainable via URL: http:\/\/www.ecs.soton.ac.uk\/~mal."},{"key":"S1471068409990263_ref9","first-page":"53","volume-title":"LOPSTR","author":"Craig","year":"2005"},{"key":"S1471068409990263_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/10722311_2"},{"key":"S1471068409990263_ref20","first-page":"379","volume-title":"The Essence of Computation \u2013 Essays Dedicated to Neil Jones","author":"Leuschel","year":"2002"}],"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\/S1471068409990263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T20:08:36Z","timestamp":1556395716000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068409990263\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,18]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["S1471068409990263"],"URL":"https:\/\/doi.org\/10.1017\/s1471068409990263","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1,18]]}}}