Control Generation by Program Transformation

• Autorzy: King A. , Martin J.C.
• Języki publikacji: EN

Abstrakty

EN

The objective of control generation in logic programming is to derive a computation rule for a program that is efficient and yet does not compromise program correctness. Progress in solving this fundamental problem in logic programming has been slow and, to date, only partial solutions have been proposed. Previously proposed schemes are either inefficient, incomplete (incorrect) or difficult to apply for programs consisting of many components (the scheme is not modular). This paper shows how the control generation problem can be tackled by program transformation. The transformation relies on information about the depths of derivations to derive delay declarations which orchestrate the control. To prove correctness of the transformation, the notion of semi-delay recurrency is introduced, which generalises previous ideas in the termination literature for reasoning about logic programs with delay declarations. In contrast to previous work, semi-delay recurrency does not require an atom to be completely resolved before another is selected for reduction. This enhancement permits the transformation to introduce control which is flexible and relatively efficient.

Słowa kluczowe

EN

Logic Programming (LP); program transformation; control generation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 69, nr 1,2
• Strony: 179--218
• Opis fizyczny: bibliogr. 43 poz.

Twórcy

autor

King A.

autor

Martin J.C.

• Computing Laboratory, University of Kent, Canterbury, CT2 7NF, UK,

Bibliografia

• [1] Apt, K. R., Pedreschi, D.: Reasoning about Termination of Pure Prolog Programs, Information and Computation, 106(1), 1993, 109-157.
• [2] Apt, K. R., Pedreschi, D.: Modular Termination Proofs for Logic and Pure Prolog programs, Advances in Logic Programming Theory (G. Levi, Ed.), Oxford University Press, 1994, Also available as technical report CS-R9316 from Centrum voorWiskunde en Informatica, CWI, Amesterdam.
• [3] Barbuti, R., Giacobazzi, R., Levi, G.: A General Framework for Semantics-Based Bottom-Up Abstract Interpretation of Logic Programs, ACM Transations on Programming Languages and Systems, 15(1), 1993, 133-181.
• [4] Benoy, F., King, A.: Inferring Argument Size Relationships with CLP('R), Logic Programming Synthesis and Transformation (J. P. Gallagher, Ed.), 1207, Springer-Verlag, 1996.
• [5] Bezem, M.: Strong Termination of Logic Programs, The Journal of Logic Programming, 15(1&2), 1993, 79-97.
• [6] Bossi, A., Etalle, S., Rossi, S., J.-G. Smaus: Semantics and Termination of Simply-Moded Logic Programs with Dynamic Scheduling, ACM Transactions on Computational Logic, 15(3), 2004, 470-507.
• [7] Brodsky, A., Sagiv, Y.: Inference of Monotonicity Constraints in Datalog Programs, Principles of Database Systems, ACM Press, 1989.
• [8] Bruynooghe, M., De Schreye, D., Krekels, B.: Compiling Control, The Journal of Logic Programming, 6(1&2), 1989, 135-162.
• [9] Carlsson, M.: Freeze, Indexing and Other Implementation Issues in the WAM, International Conference on Logic Programming (J.-L. Lassez, Ed.), MIT Press, 1987.
• [10] Carlsson, M.: Personal communications with Mats Carlsson on the SICStus abstract machine, 2002-2004.
• [11] Cavedon, L.: Continuity, consistency, and completeness properties of logic programs, International Conference on Logic Programming (G. Levi, M. Martelli, Eds.), MIT Press, 1989.
• [12] Clark, K. L., McCabe, F. G., Gregory, S.: IC-Prolog Language Features, Logic Programming (K. L. Clark, S.-°A. Tärnlund, Eds.), Academic Press, 1982.
• [13] Dahl, V.: Two Solutions for the Negation Problem, Workshop on Logic Programming (S.-°A. Tärnlund, Ed.), 1980.
• [14] De Schreye, D., Decorte, S.: Termination of Logic Programs: The Never-Ending Story, The Journal of Logic Programming, 19&20, 1994, 199-260.
• [15] De Schreye, D., Verschaetse, K.: Deriving Linear Size Relations for Logic Programs by Abstract Interpretation, New Generation Computing, 13(2), 1995, 117-154.
• [16] Deransart, P., Ed-Dbali, A., Cervoni, L.: Prolog: The Standard Reference Manual, Springer-Verlag, 1996.
• [17] Genaim, S., King, A.: Inferring Non-Suspension Conditions for Logic Programs with Dynamic Scheduling, Technical Report 20-04, Computing Laboratory, 2004, See http://www.cs.kent.ac.uk/pubs/2004/2008.
• [18] Giacobazzi, R., Debray, S. K., Levi, G.: Generalized Semantics and Abstract Interpretation for Constraint Logic Programs, The Journal of Logic Programming, 3(25), 1995, 191-248.
• [19] Hill, P. M., Lloyd, J. W.: The G¨odel Programming Language, MIT Press, 1994.
• [20] Hoarau, S., Mesnard, F.: Inferring and Compiling Termination for Constraint Logic Programs, Logic-based Program Synthesis and Transformation (P. Flener, Ed.), 1559, Springer-Verlag, 1998.
• [21] Jaffar, J.,Michaylov, S., Stuckey, P. J., Yap, R. H. C.: The CLP('R) Language and System, ACMTransactions on Programming Languages and Systems, 14(3), 1992, 339-395.
• [22] Kowalski, R. A.: Algorithm = Logic + Control, Communications of the ACM, 22(7), 1979, 424-436.
• [23] Lloyd, J.: Foundations of Logic Programming, Springer-Verlag, 1987.
• [24] Lüttringhaus-Kappel, S.: Control Generation for Logic Programs, International Conference on Logic Programming (D. S. Warren, Ed.), The MIT Press, 1993.
• [25] Marchiori, E.: Personal communication between Jonathan Martin and Elena Marchiori, 1996.
• [26] Marchiori, E., Teusink, F.: Termination of Logic Programs with Delay Declarations, International Logic Programming Symposium (J. W. Lloyd, Ed.), MIT Press, 1995.
• [27] Marchiori, E., Teusink, F.: Termination of Logic Programs with Delay Declarations, The Journal of Logic Programming, 39(1-3), 1999, 95-124.
• [28] Martin, J. C., King, A.: Generating Efficient, Terminating Logic Programs, Theory and Practice of Software Development (M. Bidoit, M. Dauchet, Eds.), 1214, Springer-Verlag, 1997.
• [29] Martin, J. C., King, A.: On the Inference of Natural Level Mappings, Program Development in Computational Logic (M. Bruynooghe, K.-K. Lau, Eds.), 3049, Springer-Verlag, 2004.
• [30] Mesnard, F.: Towards Automatic Control for CLP('R) Programs, Logic Programming Synthesis and Transformation (M. Proietti, Ed.), 1048, Springer-Verlag, 1995.
• [31] Mesnard, F., Ruggieri, S.: On Proving Left Termination of Constraint Logic Programs, ACM Transactions on Computational Logic, 4(2), 2003, 207-259.
• [32] Naish, L.: Negation and Control in Logic Programs, Springer-Verlag, 1986.
• [33] Naish, L.: Coroutining and the Construction of Terminating Logic Programs, Australian Computer Science Communications, 15(1), 1993, 181-190.
• [34] Pedreschi, D., Ruggieri, S.: Bounded Nondeterminism of Logic Programs, International Conference on Logic Programming (D. De Schreye, Ed.), MIT Press, 1999.
• [35] Pedreschi, D., Ruggieri, S., J.-G. Smaus: Classes of Terminating Logic Programs, Theory and Practice of Logic Programming, 2(3), 2002, 369-418.
• [36] Rodr´ıguez-Carbonell, E., Kapur, D.: An Abstract Interpretation Approach for Automatic Generation of Polynomial Invariants, Static Analysis Symposium (R. Giacobazzi, Ed.), 3148, Springer-Verlag, 2004.
• [37] SICS: SICStus Prolog User's Manual, 2005, See http://www.sics.se/sicstus.
• [38] Simon, A., King, A., Howe, J. M.: Two Variables per Linear Inequality as an Abstract Domain, Logic Based Program Synthesis and Tranformation (M. Leuschel, Ed.), 2664, Springer-Verlag, 2003.
• [39] Takeuchi, A., Furukawa, K.: Bounded Buffer Communication in Concurrent Prolog, New Generation Computing, 3(2), 1985, 145-155.
• [40] van Emden, M. H., de Lucena Filho, G. J.: Predicate Logic as a Language for Parallel Programming, Logic Programming (K. L. Clark, S.-°A. Tärnlund, Eds.), Academic Press, 1982.
• [41] Van Leeuwen, J., Ed.: Handbook of Theoretical Computer Science: Volume B, Elsevier, 1990.
• [42] Verschaetse, K., De Schreye, D., Bruynooghe, M.: Generation and Compilation of Efficient Computation Rules, International Conference on Logic Programming (D. H. D. Warren, P. Szeredi, Eds.), MIT Press, 1990.
• [43] Vieille, L.: Recursive Query Processing: The Power of Logic, Theoretical Computer Science, 69(1), 1989, 1-53.