Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-30T19:03:30.641Z Has data issue: false hasContentIssue false
  • English
  • Français

Transforming floundering into success

Published online by Cambridge University Press:  30 October 2012

LEE NAISH
LEE NAISH*
Affiliation:
Department of Computing and Information Systems, Melbourne School of Engineering University of Melbourne, Melbourne 3010, Australia (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We show how logic programs with “delays” can be transformed to programs without delays in a way that preserves information concerning floundering (also known as deadlock). This allows a declarative (model-theoretic), bottom-up or goal-independent approach to be used for analysis and debugging of properties related to floundering. We rely on some previously introduced restrictions on delay primitives and a key observation which allows properties such as groundness to be analysed by approximating the (ground) success set.

Keywords

flounderingdelayscoroutiningprogram analysisabstract interpretationprogram transformationdeclarative debugging
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Issue 2 , March 2014 , pp. 215 - 238
Copyright
Copyright © Cambridge University Press 2012 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Apt, K. R. and van Emden, M. H. 1982. Contributions to the Theory of Logic Programming. Journal of ACM 29, 3, 841–862.Google Scholar
Apt, K. R. 1996. From Logic Programming to Prolog. Prentice-Hall, Upper Saddle River, NJ, USA.Google Scholar
Boye, J. and Maluszynski, J. 1995. Two aspects of directional types. In Proceedings of the Twelfth International Conference on Logic Programming, Sterling, L., Ed. Kanagawa, Japan, 747–761.Google Scholar
Codish, M., Falaschi, M. and Marriott, K. 1994. Suspension analysis for concurrent logic programs. ACM Toplas 16, 3, 649–686.Google Scholar
Codish, M., Falaschi, M., Marriott, K. and Winsborough, W. 1997. A confluent semantic basis for the analysis of concurrent constraint logic programs. Journal of Logic Programming 30, 1, 649–686.Google Scholar
Codognet, C., Codognet, P. and Corsini, M.-M. 1990. Abstract interpretation for concurrent logic languages. In Proceedings of the North American Conference on Logic Programming, Debray, S. and Hermenegildo, M., Eds. The MIT Press, Austin, TX, USA, 215–232.Google Scholar
Cortesi, A., Le Charlier, B. and Rossi, S. 2001. Re-execution-based analysis of logic programs with delay declarations. In Proceedings of the Andrei Ershov Fourth International Conference on Perspectives of System Informatics (PSI'01). LNCS vol. 2244. Springer-Verlag, NY, USA, 395–405.Google Scholar
Cousot, P. and Cousot, R. 1992. Abstract interpretation and application to logic programs. Journal of Logic Programming 13, 2 & 3, 103–179.Google Scholar
Genaim, S. and King, A. 2008. Inferring non-suspension conditions for logic programs with dynamic scheduling. ACM Transactions on Computational Logic 9, 3, 1–41.Google Scholar
Giacobazzi, R. and Scozzari, F. 1998. A logical model for relational abstract domains. ACM Transactions on Programming Languages and Systems 20, 5, 1067–1109.Google Scholar
Lloyd, J. W. 1984. Foundations of Logic Programming (Springer Series in Symbolic Computation). Springer-Verlag, NY, USA.Google Scholar
Maher, M. J. 1988. Eqivalences of logic programs. In Foundations of Deductive Databases and Logic Programming, Minker, J., Ed. Morgan-Kaufmann, Los Altos, CA, USA, 627–658.Google Scholar
Marriott, K., García de la Banda, M. and Hermenegildo, M. 1994. Analyzing logic programs with dynamic scheduling. In Proceedings of the 20th Annual ACM Conference on Principles of Programming Languages. ACM, NY, USA, 240–254.Google Scholar
Marriott, K., Søndergaard, H. and Dart, P. 1990. A characterization of non-floundering logic programs. In Proceedings of the North American Conference on Logic Programming, Debray, S. and Hermenegildo, M., Eds. The MIT Press, Austin, TX, USA, 661–680.Google Scholar
Naish, L. 1988. Parallelizing NU-Prolog. In Proceedings of the Fifth International Conference Symposium on Logic Programming, Bowen, K. A. and Kowalski, R. A., Eds. Seattle, WA, USA, 1546–1564.Google Scholar
Naish, L. 1993. Coroutining and the construction of terminating logic programs. Australian Computer Science Communications 15, 1, 181–190.Google Scholar
Naish, L. 1996. A declarative view of modes. In Proceedings of the 1996 Joint International Conference and Symposium on Logic Programming. MIT Press, Austin, TX, USA, 185–199.Google Scholar
Naish, L. 2000. A three-valued declarative debugging scheme. Australian Computer Science Communications 22, 1 (January), 166–173.Google Scholar
Naish, L. 2006. A three-valued semantics for logic programmers. Theory and Practice of Logic Programming 6, 5 (September), 509–538.Google Scholar
Naish, L. 2007. Resource-oriented deadlock analysis. In Proceedings of the 23rd International Conference on Logic Programming, Dalh, V. and Niemela, I., Eds. Porto, Portugal, 302–316.Google Scholar
Naish, L. 2012. Declarative debugging of floundering in Prolog. In Proceedings of the 35th Australasian Computer Science Conference (ACSC 2012), CRPIT vol. 122. CRPIT, Sydney, Australia.Google Scholar
Puebla, G., García de la Banda, M., Marriott, K. and Stuckey, P. 1997. Optimization of logic programs with dynamic scheduling. In Proceedings of the 1997 International Conference on Logic Programming. MIT Press, Cambridge, MA, USA, 93–107.Google Scholar
Ross, K. 1989. A procedural semantics for well founded negation in logic programs. In Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, PA, March 29–31, Silberschatz, A., Ed. ACM Press, New York, 22–33.Google Scholar
Shapiro, E. Y. 1983. Algorithmic Program Debugging. MIT Press, Cambridge, MA, USA.Google Scholar
Somogyi, Z., Henderson, F. J. and Conway, T. 1995. Mercury: An efficient purely declarative logic programming language. In Proceedings of the Australian Computer Science Conference, Glenelg, Australia, 499–512.Google Scholar
van Emden, M. and Kowalski, R. 1976. The semantics of predicate logic as a programing language. Journal of the ACM 23, 4, 733–742.Google Scholar