Incremental Computation of Success Patterns of Logic Programs

Lunjin Lu

Department of Computer Science and Engineering, Oakland University, Rochester, USA..

DOI: 10.4236/jsea.2010.33025                

Abstract

A method is presented for incrementally computing success patterns of logic programs. The set of success patterns of a logic program with respect to an abstraction is formulated as the success set of an equational logic program modulo an equality theory that is induced by the abstraction. The method is exemplified via depth and stump abstractions. Also presented are algorithms for computing most general unifiers modulo equality theories induced by depth and stump abstractions.

Keywords

Incremental Analysis, Success Patterns, Abstract Interpretation, Depth Abstract, Stump Abstraction, Logic Programs

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	P. Cousot and R. Cousot, “Systematic design of program analysis frameworks,” Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, The ACM Press, New York, pp. 269–282, 1979.
[2]	P. Cousot and R. Cousot, “Abstract interpretation and application to logic programs,” The Journal of Logic Programming, Vol. 13, No. 2–3, pp. 103–179, 1992.
[3]	H. S?ndergaard, “An application of abstract interpretation of logic programs: Occur check problem,” In: B. Robinet and R. Wilhelm, Ed., European Symposium on Progr- amming, Lecture Notes in Computer Science, Springer, Vol. 213, pp. 324–338, 1986.
[4]	C. Mellish, “Some global optimizations for a Prolog compiler,” Journal of Logic Programming, Vol. 2, No. 1, pp. 43–66, 1985.
[5]	C. Mellish, “Abstract interpretation of Prolog programs,” In: S. Abramsky and C. Hankin, Ed., Abstract interp- retation of declarative languages, Ellis Horwood Ltd., pp. 181–198, 1987.
[6]	M. Bruynooghe and G. Janssens, “An instance of abstract interpretation integrating type and mode inferencing,” Proceedings of the Fifth International Conference and Symposium on Logic Programming, The MIT Press, Seattle, pp. 669–683, 15–19 August 1988.
[7]	D. Jacobs and A. Langen, “Static analysis of logic prog- rams for independent and parallelism,” Journal of Logic Programming, Vol. 13, No. 2–3, pp. 291–314, 1992.
[8]	X. Li, A. King, and L. Lu, “Collapsing closures,” In: S. Etalle and M. Truszczynski, Ed., Proceedings of the Twenty Second International Conference on Logic Programming, Lecture Notes in Computer Science, Vol. 4079, pp. 148–162, 2006.
[9]	M. Bruynooghe, G. Janssens, A. Callebaut, and B. Demoen, “Abstract interpretation: Towards the global optimisation of Prolog programs,” Proceedings of the 1987 Symposium on Logic Programming, The IEEE Computer Society Press, San Francisco, pp. 192–204, 31 August–4 September 1987.
[10]	L. Lu, “Improving precision of type analysis using non- discriminative union,” Theory and Practice of Logic Programming, Vol. 8, pp. 33–80, 2008.
[11]	K. Marriott, H. S?ndergaard, and N. D. Jones, “Denota- tional abstract interpretation of logic programs,” ACM Transactions on Programming Languages and Systems, Vol. 16, No. 3, pp. 607–648, 1994.
[12]	K. Marriott and H. S?ndergaard, “Bottom-up abstract interpretation of logic programs,” Proceedings of the Fifth International Conference and Symposium on Logic Pro- gramming, The MIT Press, Seattle, pp. 733–748, 15–19 August 1988.
[13]	M. H. van Emden and R. A. Kowalski, “The semantics of predicate logic as a programming language,” Artificial Intelligence, Vol. 23, No. 10, pp. 733–742, 1976.
[14]	J. Jaffar, J. L. Lassez, and M. J. Maher, “Theory of complete logic programs with equality,” Journal of Logic Programming, Vol. 1, No. 3, pp. 211–23, October 1984.
[15]	T. Sato and H. Tamaki, “Enumeration of success patterns in logic programs,” Theoretical Computer Science, Vol. 34, No. 1, pp. 227–240, 1984.
[16]	P. M. Hill and F. Spoto, “Generalizing Def and Pos to type analysis,” Journal of Logic and Computation, Vol. 12, No. 3, pp. 497–542, 2002.
[17]	M. Li, Z. Li, H. Chen, and T. Zhou, “A novel derivation framework for definite logic program,” Electronic Notes in Theoretical Computer Science, Vol. 212, pp. 71–85, 2008.
[18]	J. A. Robinson, “A machine-oriented logic based on the resolution principle,” Journal of the ACM, Vol. 12, No. 1, pp. 23–41, 1965.
[19]	J. Xu and D. S. Warren, “A type inference system for Prolog,” Proceedings of the 5th International Conference and Symposium on Logic Programming, The MIT Press, Seattle, pp. 604–619, 15–19 August 1988.
[20]	M. Codish, S. K. Debray, and R. Giacobazzi, “Composi- tional analysis of modular logic programs,” Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages, The ACM Press, New York, USA, pp. 451–464, January 1993.