Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T10:26:33.521Z Has data issue: false hasContentIssue false
  • English
  • Français

RedAlert: Determinacy inference for Prolog

Published online by Cambridge University Press:  06 July 2011

JAEL KRIENER  and
ANDY KING
JAEL KRIENER
Affiliation:
School of Computing, University of Kent, Canterbury, Kent CT2 7NF, UK (e-mail: [email protected], [email protected])
ANDY KING
Affiliation:
School of Computing, University of Kent, Canterbury, Kent CT2 7NF, UK (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper revisits the problem of determinacy inference addressing the problem of how to uniformly handle cut. To this end a new semantics is introduced for cut, which is abstracted to systematically derive a backward analysis that derives conditions sufficient for a goal to succeed at most once. The method is conceptionally simpler and easier to implement than the existing techniques, while improving the latter's handling of cut. Formal arguments substantiate correctness and experimental work, and a tool called ‘RedAlert’ demonstrates the method's generality and applicability.

Keywords

abstract interpretationbackwards analysisBoolean formulaeconstraintscutdeterminacy inferenceProlog
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 4-5: 27th International Conference on Logic Programming , July 2011 , pp. 537 - 553
Copyright
Copyright © Cambridge University Press 2011

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., Blair, H. A. and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann, Massachusetts, 89–148.CrossRefGoogle Scholar
Armstrong, T., Marriott, K., Schachte, P. and Søndergaard, H. 1998. Two classes of Boolean functions for dependency analysis. Science of Computer Programming 31 (1), 3–45.CrossRefGoogle Scholar
Baker, N. and Søndergaard, H. 1993. Definiteness analysis for CLP(). Australian Computer Science Communications 15 (1), 321–332. (Proceedings of the Sixteenth Australian Computer Science Conference.)Google Scholar
Billaud, M. 1990. Simple operational and denotational semantics for Prolog with cut. Theoretical Computer Science 71 (2), 193–208.CrossRefGoogle Scholar
Brauer, J., King, A. and Kriener, J. To appear. Existential quantification as incremental SAT. In Twenty-Third International Conference on Computer Aided Verification, Gopalakrishnan, G. and Qadeer, S., Eds. Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany.Google Scholar
Codish, M., Lagoon, V. and Stuckey, P. 2008. Logic programming with satisfiability. Theory and Practice of Logic Programming 8 (1), 121–128.CrossRefGoogle Scholar
Codish, M. and Søndergaard, H. 2002. Meta-circular abstract interpretation in Prolog. In The Essence of Computation: Complexity, Analysis, Transformation, Mogensen, T. Æ., Schmidt, D. and Sudborough, I. H., Eds. Lecture Notes in Computer Science, vol. 2566. Springer, New York, 109–134.CrossRefGoogle Scholar
Cousot, P. and Cousot, R. 1979. Systematic design of program analysis frameworks. In Sixth Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas, January 29–31. 269–282.Google Scholar
Dawson, S., Ramakrishnan, C. R., Ramakrishnan, I. V. and Sekar, R. C. 1993. Extracting determinacy in logic programs. In Proceedings of the Tenth International Conference on Logic Programming. MIT Press, Cambridge, MA, 424–438.Google Scholar
de Vink, E. P. 1989. Comparative semantics for Prolog with cut. Science of Computer Programming 13 (1), 237–264.CrossRefGoogle Scholar
Debray, S. K. and Mishra, P. 1988. Denotational and operational semantics for Prolog. Journal of Logic Programming 5 (1), 81–91.CrossRefGoogle 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–43.CrossRefGoogle Scholar
Giacobazzi, R. 1993. Semantic Aspects of Logic Program Analysis, PhD thesis, Dipartimento di Informatica, Universitá di Pisa, Pisa, Italy.Google Scholar
Howe, J. M. and King, A. 2001. Positive Boolean functions as multiheaded clauses. In Proceedings of the Seventeenth International Conference on Logic Programming, Codognet, P., Ed. Lecture Notes in Computer Science, vol. 2237. Springer, New York, 120–134.Google Scholar
King, A., Lu, L. and Genaim, S. 2006. Detecting determinacy in Prolog programs. In Proceedings of the Twenty-Second International Conference on Logic Programming. Etalle, S. and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 4079. Springer, New York, 132–147.Google Scholar
Kriener, J. and King, A. 2011. Appendix for RedAlert: Determinacy inference for Prolog. Technical Report 1-11, School of Computing, University of Kent, Kent, UK. Available at http://www.cs.kent.ac.uk/pubs/2011/3107/index.htmlCrossRefGoogle Scholar
Le Charlier, B., Rossi, S. and Van Hentenryck, P. 1994. An abstract interpretation framework which accurately handles Prolog search-rule and the cut. In Symposium on Logic Programming. Bruynooghe, M., Ed. MIT Press, Cambridge, MA, 157–171.Google Scholar
Lu, L. and King, A. 2005. Determinacy inference for logic programs. In Fourteenth European Symposium on Programming, Sagiv, S., Ed. Lecture Notes in Computer Science, vol. 3444. Springer, New York, 108–123.Google Scholar
Mogensen, T. Æ. 1996. A semantics-based determinacy analysis for Prolog with cut. In Ershov Memorial Conference, Novosibirsk, Russia. Bjørner, D., Broy, M. and Pottosin, I. V., Eds. Lecture Notes in Computer Science, vol. 1181. Springer, New York, 374–385.Google Scholar
O'Keefe, R. A. 1990. The Craft of Prolog. MIT Press, Cambridge, MA.Google Scholar
Sahlin, D. 1991. Determinacy analysis for full Prolog. In Symposium on Partial Evaluation and Semantics-Based Program Manipulation. ACM, New York, NY, 23–30.Google Scholar
Schneider-Kamp, P., Giesl, J., Ströder, T., Serebrenik, A. and Thiemann, R. 2010. Automated termination analysis for logic programs with cut. Theory and Practice of Logic Programming 10 (4–6), 365–381.CrossRefGoogle Scholar
Supplementary material: PDF

KRIENER and KING supplementary material

Appendix

Download KRIENER and KING supplementary material(PDF)
PDF 287.6 KB