{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:06:54Z","timestamp":1761620814119,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2000,3]]},"abstract":"<jats:p>Studying independence of goals has proven very useful in the context of logic programming. In particular, it has provided a formal basis for powerful automatic parallelization tools, since independence ensures that two goals may be evaluated in parallel while preserving correctness and efficiency. We extend the concept of independence to constraint logic programs (CLP) and prove that it also ensures the correctness and efficiency of the parallel evaluation of independent goals. Independence for CLP languages is more complex than for logic programming as search space preservation is necessary but no longer sufficient for ensuring correctness and efficiency. Two additional issues arise. The first is that the cost of constraint solving may depend upon the order constraints are  encountered. The second is the need to handle dynamic scheduling. We clarify these issues by proposing various types of search independence and constraint solver independence, and show how they can be combined to allow different optimizations, from parallelism to intelligent backtracking. Suficient conditions for independence which can be evaluated \u201ca priori\u201d at run-time are also proposed. Our study also yields new insights into independence in logic programming languages. In particular, we show that search space preservation is not only a sufficient but also a necessary condition for ensuring correctness and efficiency of parallel execution.<\/jats:p>","DOI":"10.1145\/349214.349224","type":"journal-article","created":{"date-parts":[[2002,10,7]],"date-time":"2002-10-07T13:52:47Z","timestamp":1033998767000},"page":"296-339","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Independence in CLP languages"],"prefix":"10.1145","volume":"22","author":[{"given":"Mar\u00eda","family":"Garc\u00eda de la Banda","sequence":"first","affiliation":[{"name":"Monash Univ., Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Hermenegildo","sequence":"additional","affiliation":[{"name":"Technical Univ. of Madrid, Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim","family":"Marriott","sequence":"additional","affiliation":[{"name":"Monash Univ., Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2000,3]]},"reference":[{"volume-title":"Handbook of Theoretical Computer Science","author":"APT K.","unstructured":"APT , K. 1990. Introduction to Logic Programming . In Handbook of Theoretical Computer Science , J. van Leeuwen, Ed. Vol. B : Formal Model and Semantics. Elsevier, Amsterdam and The MIT Press , Cambridge, 495-574. APT, K. 1990. Introduction to Logic Programming. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed. Vol. B: Formal Model and Semantics. Elsevier, Amsterdam and The MIT Press, Cambridge, 495-574.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/322326.322339"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/197405.197406"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/0167-6423(89)90014-2"},{"key":"e_1_2_1_5_1","first-page":"194","article-title":"Deduction Revision by Intelligent Backtracking. In Implementations of Prolog, J. Campbell","author":"BRUYNOOGHE EIRA","year":"1984","unstructured":"BRUYNOOGHE , ~\/{. AND PER EIRA , g. 1984 . Deduction Revision by Intelligent Backtracking. In Implementations of Prolog, J. Campbell , Ed. Elliss Horwood , 194 - 205 . BRUYNOOGHE, ~\/{. AND PEREIRA, g. 1984. Deduction Revision by Intelligent Backtracking. In Implementations of Prolog, J. Campbell, Ed. Elliss Horwood, 194-205.","journal-title":"Ed. Elliss Horwood"},{"key":"e_1_2_1_6_1","first-page":"2","article-title":"Automatic Compile-time Parallelization of Logic Programs for Restricted, Goal-level","volume":"38","author":"BUENO F.","year":"1999","unstructured":"BUENO , F. , GARC fA DE LA B ANDA , M., HERMENEGILDO , M. , AND MUTHUKUMAR , I~. 1999 . Automatic Compile-time Parallelization of Logic Programs for Restricted, Goal-level , Independent And-parMlelism. J. Logic Program. 38 , 2 (February), 165-218. BUENO, F., GARCfA DE LA BANDA, M., HERMENEGILDO, M., AND MUTHUKUMAR, I~. 1999. Automatic Compile-time Parallelization of Logic Programs for Restricted, Goal-level, Independent And-parMlelism. J. Logic Program. 38, 2 (February), 165-218.","journal-title":"Independent And-parMlelism. J. Logic Program."},{"key":"e_1_2_1_7_1","first-page":"00007","volume-title":"Special CCP95 Workshop issue. 10","author":"BUENO F.","year":"1998","unstructured":"BUENO , F. , HERMENEGILDO , M. , MONTANARI , U. , AND ROSSI , F. 1998 . Partial Order and Contextual Net Semantics for Atomic and Locally Atomic CC Programs. Science of Computer Programmin9 30, 51-82 . Special CCP95 Workshop issue. 10 .1016\/S0167-6423(97) 00007 - 00005 BUENO, F., HERMENEGILDO, M., MONTANARI, U., AND ROSSI, F. 1998. Partial Order and Contextual Net Semantics for Atomic and Locally Atomic CC Programs. Science of Computer Programmin9 30, 51-82. Special CCP95 Workshop issue. 10.1016\/S0167-6423(97)00007-5"},{"volume-title":"Extracting Non-strict Independent And-parMlelism Using Sharing and Freeness Information. In 199J International Static Analysis Symposium. Number 864 in LNCS","author":"CABEZA D.","unstructured":"CABEZA , D. AND HERMENEGILDO , M. 1994. Extracting Non-strict Independent And-parMlelism Using Sharing and Freeness Information. In 199J International Static Analysis Symposium. Number 864 in LNCS . Springer-Verlag , Namur, Belgium , 297-313. CABEZA, D. AND HERMENEGILDO, M. 1994. Extracting Non-strict Independent And-parMlelism Using Sharing and Freeness Information. In 199J International Static Analysis Symposium. Number 864 in LNCS. Springer-Verlag, Namur, Belgium, 297-313.","key":"e_1_2_1_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/185403.185453"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/79204.79210"},{"key":"e_1_2_1_12_1","volume-title":"Binding Environments for Parallel Logic Programs in Nonshared Memory Multiprocessors. In Symposium on Logic Programming 457-467","author":"CONERY J. S.","year":"1987","unstructured":"CONERY , J. S. 1987 . Binding Environments for Parallel Logic Programs in Nonshared Memory Multiprocessors. In Symposium on Logic Programming 457-467 . CONERY, J. S. 1987. Binding Environments for Parallel Logic Programs in Nonshared Memory Multiprocessors. In Symposium on Logic Programming 457-467."},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1002\/spe.4380231204"},{"key":"e_1_2_1_14_1","first-page":"471","volume-title":"Restricted AND-Parallelism. In International Conference on 5th Generation Computer Systems","author":"DEGROOT D.","year":"1984","unstructured":"DEGROOT , D. 1984 . Restricted AND-Parallelism. In International Conference on 5th Generation Computer Systems . Tokyo , 471 - 478 . DEGROOT, D. 1984. Restricted AND-Parallelism. In International Conference on 5th Generation Computer Systems. Tokyo, 471-478."},{"unstructured":"FRANZEN T. 1992. Logical Aspects of the Andorra Kernel Language. Draft\/Personal communication.  FRANZEN T. 1992. Logical Aspects of the Andorra Kernel Language. Draft\/Personal communication.","key":"e_1_2_1_15_1"},{"volume-title":"Programming Languages: Implementation, Logics, and Programs. Number 1140 in LNCS","author":"GARC ANDA","unstructured":"GARC fA DE LA B ANDA , M., BUENO , F. , AND HERMENEGILDO , M. 1996. Towards Independent And-ParMlelism in CLP . In Programming Languages: Implementation, Logics, and Programs. Number 1140 in LNCS . Springer-Verlag , Aachen, Germany , 77-91. GARCfA DE LA BANDA, M., BUENO, F., AND HERMENEGILDO, M. 1996. Towards Independent And-ParMlelism in CLP. In Programming Languages: Implementation, Logics, and Programs. Number 1140 in LNCS. Springer-Verlag, Aachen, Germany, 77-91.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 7th International Conference on Logic Programming. MIT Press, 31-46","author":"HARIDI S.","year":"1990","unstructured":"HARIDI , S. AND JANSON , S. 1990 . Kernel Andorra Prolog and its Computation Model . In Proceedings of the 7th International Conference on Logic Programming. MIT Press, 31-46 . HARIDI, S. AND JANSON, S. 1990. Kernel Andorra Prolog and its Computation Model. In Proceedings of the 7th International Conference on Logic Programming. MIT Press, 31-46."},{"key":"e_1_2_1_18_1","first-page":"31","volume-title":"Proceedings of EUROPAR'97","volume":"1300","author":"HERMENEGILDO M.","year":"1997","unstructured":"HERMENEGILDO , M. 1997 . Automatic Parallelization of Irregular and Pointer-Based Computations: Perspectives from Logic and Constraint Programming . In Proceedings of EUROPAR'97 . LNCS, vol. 1300 . Springer-Verlag , 31 - 46 . (invited). HERMENEGILDO, M. 1997. Automatic Parallelization of Irregular and Pointer-Based Computations: Perspectives from Logic and Constraint Programming. In Proceedings of EUROPAR'97. LNCS, vol. 1300. Springer-Verlag, 31-46. (invited)."},{"key":"e_1_2_1_19_1","volume-title":"1990 International Conference on Logic Programming. MIT Press, 253- 268","author":"HERMENEGILDO M.","year":"1990","unstructured":"HERMENEGILDO , M. AND GREENE , K. 1990 . &amp;-Prolog and its Performance: Exploiting Independent And-ParMlelism . In 1990 International Conference on Logic Programming. MIT Press, 253- 268 . HERMENEGILDO, M. AND GREENE, K. 1990. &amp;-Prolog and its Performance: Exploiting Independent And-ParMlelism. In 1990 International Conference on Logic Programming. MIT Press, 253- 268."},{"issue":"1","key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0743-1066(93)00007-F","article-title":"Strict and Non-Strict Independent And-ParMlelism in Logic Programs: Correctness, Efficiency, and Compile-Time Conditions","volume":"22","author":"HERMENEGILDO M.","year":"1995","unstructured":"HERMENEGILDO , M. AND ROSSI , F. 1995 . Strict and Non-Strict Independent And-ParMlelism in Logic Programs: Correctness, Efficiency, and Compile-Time Conditions . J. Logic Program. 22 , 1 , 1 - 45 . HERMENEGILDO, M. AND ROSSI, F. 1995. Strict and Non-Strict Independent And-ParMlelism in Logic Programs: Correctness, Efficiency, and Compile-Time Conditions. J. Logic Program. 22, 1, 1-45.","journal-title":"J. Logic Program."},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/41625.41635"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/0743-1066(94)90033-7","article-title":"Constraint Logic Programming: A Survey","volume":"19","author":"JAFFAR J.","year":"1994","unstructured":"JAFFAR , J. AND MAHER , M. 1994 . Constraint Logic Programming: A Survey . J. Logic Program. 19\/20 , 503 - 581 . JAFFAR, J. AND MAHER, M. 1994. Constraint Logic Programming: A Survey. J. Logic Program. 19\/20, 503-581.","journal-title":"J. Logic Program."},{"key":"e_1_2_1_23_1","first-page":"196","volume-title":"4th International Conference on Logic Programming","author":"JAFFAR J.","year":"1987","unstructured":"JAFFAR , J. AND MICHAYLOV , S. 1987 . Methodology and Implementation of a CLP System . In 4th International Conference on Logic Programming . University of Melbourne , MIT Press, 196 - 219 . JAFFAR, J. AND MICHAYLOV, S. 1987. Methodology and Implementation of a CLP System. In 4th International Conference on Logic Programming. University of Melbourne, MIT Press, 196-219."},{"key":"e_1_2_1_24_1","volume-title":"Programming Paradigms of the Andorra Kernel Language. In 1991 International Logic Programming Symposium. MIT Press, 167-183","author":"JANSON S.","year":"1991","unstructured":"JANSON , S. AND HARIDI , S. 1991 . Programming Paradigms of the Andorra Kernel Language. In 1991 International Logic Programming Symposium. MIT Press, 167-183 . JANSON, S. AND HARIDI, S. 1991. Programming Paradigms of the Andorra Kernel Language. In 1991 International Logic Programming Symposium. MIT Press, 167-183."},{"key":"e_1_2_1_25_1","volume-title":"Completeness and Full Parallelism of Parallel Logic Programming Schemes. In 4th IEEE Symposium on Logic Programming. IEEE, 125-133","author":"KALE L. V.","year":"1987","unstructured":"KALE , L. V. 1987 . Completeness and Full Parallelism of Parallel Logic Programming Schemes. In 4th IEEE Symposium on Logic Programming. IEEE, 125-133 . KALE, L. V. 1987. Completeness and Full Parallelism of Parallel Logic Programming Schemes. In 4th IEEE Symposium on Logic Programming. IEEE, 125-133."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of Joint International Conference and Symposium on Logic Programming. MIT Press, 37-51","author":"KELLY A.","year":"1996","unstructured":"KELLY , A. , MACDONALD , A. , MARRIOTT , K. , STUCKEY , P. , AND YAP , R. 1996 . Effectiveness of optimizing compilation for CLP(R) . In Proceedings of Joint International Conference and Symposium on Logic Programming. MIT Press, 37-51 . KELLY, A., MACDONALD, A., MARRIOTT, K., STUCKEY, P., AND YAP, R. 1996. Effectiveness of optimizing compilation for CLP(R). In Proceedings of Joint International Conference and Symposium on Logic Programming. MIT Press, 37-51."},{"volume-title":"Logic Programming","author":"LLOYD J. W.","unstructured":"LLOYD , J. W. 1987. Logic Programming . Springer-Verlag . LLOYD, J. W. 1987. Logic Programming. Springer-Verlag.","key":"e_1_2_1_28_1"},{"volume-title":"Programming with Constraints: An Introduction","author":"MARRIOT K.","unstructured":"MARRIOT , K. AND STUCKEY , P. 1998. Programming with Constraints: An Introduction . The MIT Press . MARRIOT, K. AND STUCKEY, P. 1998. Programming with Constraints: An Introduction. The MIT Press.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","volume-title":"19th Annual A CM Conf. on Principles of Programming Languages. ACM, 334-344","author":"MARRIOTT K.","year":"1992","unstructured":"MARRIOTT , K. AND STUCKEY , P. 1992 . The 3 R's of Optimizing Constraint Logic Programs: Refinement, Removal, and Reordering . In 19th Annual A CM Conf. on Principles of Programming Languages. ACM, 334-344 . 10.1145\/158511.158685 MARRIOTT, K. AND STUCKEY, P. 1992. The 3 R's of Optimizing Constraint Logic Programs: Refinement, Removal, and Reordering. In 19th Annual A CM Conf. on Principles of Programming Languages. ACM, 334-344. 10.1145\/158511.158685"},{"key":"e_1_2_1_31_1","volume-title":"Approximating Interaction Between Linear Arithmetic Constraints. In 1994 International Symposium on Logic Programming. MIT Press, 571-585","author":"MARRIOTT K.","year":"1994","unstructured":"MARRIOTT , K. AND STUCKEY , P. 1994 . Approximating Interaction Between Linear Arithmetic Constraints. In 1994 International Symposium on Logic Programming. MIT Press, 571-585 . MARRIOTT, K. AND STUCKEY, P. 1994. Approximating Interaction Between Linear Arithmetic Constraints. In 1994 International Symposium on Logic Programming. MIT Press, 571-585."},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/357162.357169"},{"issue":"2","key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/0022-0000(78)90043-0","article-title":"Linear Unification","volume":"16","author":"PATERSON M. S.","year":"1978","unstructured":"PATERSON , M. S. AND WEGMAN , M. 1978 . Linear Unification . J. of Computer and System Sciences 16 , 2 , 158 - 167 . PATERSON, M. S. AND WEGMAN, M. 1978. Linear Unification. J. of Computer and System Sciences 16, 2, 158-167.","journal-title":"J. of Computer and System Sciences"},{"volume-title":"Logic Programming","author":"PEREIRA L. M.","unstructured":"PEREIRA , L. M. AND PORTO , A. 1982. Selective backtracking . In Logic Programming . Academic Press , 107-114. PEREIRA, L. M. AND PORTO, A. 1982. Selective backtracking. In Logic Programming. Academic Press, 107-114.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","first-page":"93","volume-title":"Optimization of Logic Programs with Dynamic Scheduling. In 1997 International Conference on Logic Programming. MIT Press","author":"PUEBLA G.","year":"1997","unstructured":"PUEBLA , G. , GARC fA DE LA B ANDA , M., MARRIOTT , K. , AND STUCKEY , P. 1997 . Optimization of Logic Programs with Dynamic Scheduling. In 1997 International Conference on Logic Programming. MIT Press , Cambridge, MA , 93 - 107 . PUEBLA, G., GARCfA DE LA BANDA, M., MARRIOTT, K., AND STUCKEY, P. 1997. Optimization of Logic Programs with Dynamic Scheduling. In 1997 International Conference on Logic Programming. MIT Press, Cambridge, MA, 93-107."},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/321250.321253"},{"volume-title":"Computer Science Department","author":"SW W, V","unstructured":"SaRa SW a W, V . 1987. Compiling CP () on top of Prolog. Tech. Rep. CMU-CS-87-174 , Computer Science Department , Carnegie-Mellon University , Pittsburgh . October. SaRaSWaW, V. 1987. Compiling CP() on top of Prolog. Tech. Rep. CMU-CS-87-174, Computer Science Department, Carnegie-Mellon University, Pittsburgh. October.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","first-page":"119","volume-title":"2nd International Symposium on Logic Programming. IEEE Press","author":"UEDA K.","year":"1985","unstructured":"UEDA , K. AND CHIKIYAMA , T. ( 1985 ). A compiler for concurrent prolog . In 2nd International Symposium on Logic Programming. IEEE Press , Boston , 119 - 126 . UEDA, K. AND CHIKIYAMA, T. (1985). A compiler for concurrent prolog. In 2nd International Symposium on Logic Programming. IEEE Press, Boston, 119-126."},{"key":"e_1_2_1_39_1","first-page":"3","article-title":"An Efficient, Easily Adaptable System For Interpreting Natural Language Queries","volume":"8","author":"WARREN D.","year":"1982","unstructured":"WARREN , D. AND PEREIRA , F. C. N. 1982 . An Efficient, Easily Adaptable System For Interpreting Natural Language Queries . American Journal of Computational Linguistics 8 , 3 - 4 , 110-122. WARREN, D. AND PEREIRA, F. C. N. 1982. An Efficient, Easily Adaptable System For Interpreting Natural Language Queries. American Journal of Computational Linguistics 8, 3-4, 110-122.","journal-title":"American Journal of Computational Linguistics"},{"key":"e_1_2_1_40_1","volume-title":"On the Practicality of Global Flow Analysis of Logic Programs. In 5th International Conference and Symposium on Logic Programming. MIT Press, 684-699","author":"WARREN R.","year":"1988","unstructured":"WARREN , R. , HERMENEGILDO , i V{. , AND DEBRAY , S. K. 1988 . On the Practicality of Global Flow Analysis of Logic Programs. In 5th International Conference and Symposium on Logic Programming. MIT Press, 684-699 . WARREN, R., HERMENEGILDO, iV{., AND DEBRAY, S. K. 1988. On the Practicality of Global Flow Analysis of Logic Programs. In 5th International Conference and Symposium on Logic Programming. MIT Press, 684-699."},{"key":"e_1_2_1_41_1","first-page":"749","volume-title":"5th International Conference and Symposium on Logic Programming","author":"WINSBOROUGH W.","year":"1988","unstructured":"WINSBOROUGH , W. AND WAERN , A. 1988 . Transparent And-Parallelism in the Presence of Shared Free variables . In 5th International Conference and Symposium on Logic Programming . Seattie,Washington , 749 - 764 . WINSBOROUGH, W. AND WAERN, A. 1988. Transparent And-Parallelism in the Presence of Shared Free variables. In 5th International Conference and Symposium on Logic Programming. Seattie,Washington, 749-764."}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/349214.349224","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/349214.349224","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:07Z","timestamp":1750188667000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/349214.349224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,3]]}},"alternative-id":["10.1145\/349214.349224"],"URL":"https:\/\/doi.org\/10.1145\/349214.349224","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2000,3]]},"assertion":[{"value":"2000-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}