Constraint logic programming languages

ABSTRACT

Constraint Logic Programming (CLP) is an extension of Logic Programming aimed at replacing the pattern matching mechanism of unification, as used in Prolog, by a more general operation called constraint satisfaction. This aritcle provides a panoramic view of the recent work done in designing and implementing CLP languages. It also presents a summary of their theoretical foundations, discusses implementation issues, compares the major CLP languages, and suggests directions for further work.

REFERENCES

• 1: Aiba, A. ct al. Constraint logic programming language CAL. In Proceedings of the International Conference on Fifth Generation Computer Systems, (1988) Ohmsha Publishers, Tokyo, pp. 263-276.
• 2: Krzysztof R. Apt, Introduction to Logic Programming, University of Texas at Austin, Austin, TX, 1988
• 3: Dennis S. Arnon, Bibliography of quantifier elimination for real closed fields, Journal of Symbolic Computation, v.5 n.1-2, p.267-274, February/April 1988 [doi>10.1016/S0747-7171(88)80016-6]
• 4: Boi, j.M. and Benhamou, F. Boolean constraints in Prolog II1. Ph.D. dissertation, Groupe d'Intelligence Artificielle, Universit~ d'Aix- Marseille, Luminy, Nov. 1988.
• 5: constraint-oriented simulation laboratory. ACM 70PLAS 3,4 (Oct. 1981), 252-387.
• 6: Robert S. Boyer , J. Strother Moore, A computational logic handbook, Academic Press Professional, Inc., San Diego, CA, 1988
• 7: Bruynooghe, M. andJanssens, G. An instance of abstract interpretation integrating type and mode intcrferencing in logic programming. In Proceedings of the Fifth /nternational Conference and Symposium. (Seattle, Wash., 1988) vol. 1, MIT Press, pp. 669-683.
• 8: Buchberger, B. Gr6bner Bases: An algorithmic method in polynomial ideal theory. in multidimensional systems Theory. N.K. bose Ed., D.Reidel Publishing Co., 1985, pp. 184-232.
• 9: Wolfram Büttner , Helmut Simonis, Embedding Boolean expressions into logic programming, Journal of Symbolic Computation, v.4 n.2, p.191-205, Oct. 1987 [doi>10.1016/S0747-7171(87)80065-2]
• 10: Clark, K.L. Negation as Failure. In Logic and Data Bases, H. Gallaire and J. Minerk, Eds. Plenum Press, New York, 1978, pp. 293-322.
• 11: Jacques Cohen, A view of the origins and development of Prolog, Communications of the ACM, v.31 n.1, p.26-36, Jan. 1988 [doi>10.1145/35043.35045]
• 12: Collins, G.E. Quantifier Elimination for Real Closed Fields: A Guide to the Literature, in Computing. B. Buchberger, G.E. Collins and R. Loos, Eds. Computer Aigebra: Symboh'c and Aigebraic Computation, 2d ed. Springer- Verlag, Vienna, pp. 79-81.
• 13: Colmerauer, A. Prolog and Infinite Trees. In Logic Programming, K.L. clark nnd .KA Tarnlllnr{ F. ci; Acarlomlc Pre~ ~ewYnrk- IQR9 rsn 231-251.
• 14: Colmerauer, A. Prolog II Reference Manual and Theoretical Model. Rep. Groupe d'Intelligence Artificielle, Universit6 d'Aix-Marseille II, Luminy, Oct. 1982.
• 15: Colmerauer, A. Solving equations and inequations on finite and infinite trees. In Proceedings of the Conference on Fifth Generation Computer Systems, ('ibkyo, Nov. i984), pp. 85-99.
• 16: Alain Colmerauer, Opening the Prolog III universe, BYTE, v.12 n.9, p.177-182, Aug. 1987
• 17: Alain Colmerauer, An introduction to Prolog III, Communications of the ACM, v.33 n.7, p.69-90, July 1990 [doi>10.1145/79204.79210]
• 18: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 19: Dincbas, M. etat. The constraint logic programming language CHIP, In Proceedings of the international ConJ~rence on Fifth Generation Computer Systems, (1988), Ohmsha Publishers, Tokyo, pp. 693-702.
• 20: Elcock, E.W. Absys 1: The historical inevitability of logic programming. In proceedings of the North America Logic Programming Confere~ce. MIT Press Cambridge, Mass., 1989, pp. 1201-I214.
• 21: Foster, J.M. and Elcock, E.W. Absys 1: An Incremental Compiler for Assertions: an Introduction. In Mach. Intell. 4, Edinburgh University Press, 1969, pp. 423-429.
• 22: Bjorn N. Freeman-Benson , John Maloney , Alan Borning, An incremental constraint solver, Communications of the ACM, v.33 n.1, p.54-63, Jan. 1990 [doi>10.1145/76372.77531]
• 23: D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
• 24: Heintze, N.C., Michaylov, S. and Stuckey, P.J. CLP (R) and some electerence on Logz~ Programming, (Melbournc, 1987), MIT Press, pp. 675-703.
• 25: Pascal Van Hentenryck, Constraint satisfaction in logic programming, MIT Press, Cambridge, MA, 1989
• 26: Hill, R. LUSH-resolution and its completeness, DCL Memo 78, Dept. of Artificial Intelligence, Univ. of Edinburgh, U.K., 1974.
• 27: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 28: Jaffar, J., Lassez, J-L. and Lloyd, J.W. Completeness of the negation as failure rule. In Proceedings of the International Conference on Artificial/nte/hgence. (IJCAI), 1983, Karlsruhe,pp.500-506.
• 29: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 30: Jaffar, J. and Michaylov, S. Methodology and implementation of a constraint logic programming system. In Proceedings of the Fourth International Conference on Logic Programming~ (Melbourne, 1987), MIT Press, Cambridge, Mass., pp. i96-2i8. (A revised version of this paper has been presented in the Languages and Constraints Workshop, Alton Jones Campus, Rhode Island, April 1988.)
• 31: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint Query Languages, Brown University, Providence, RI, 1992
• 32: Kowalski, R. and Kuehner, D. Resolution with selection function. Artif. Intell. 3, 3 (1970), 227-260.
• 33: Catherine Lassez, Constraint logic programming, BYTE, v.12 n.9, p.171-176, Aug. 1987
• 34: Lassez, J-L., McAloon, K. Application of a canonical form for generalised linear arithmetic constrain ts. In Proceedings of the Fifth Generation Computer Systems, (1988), Ohmsha Publishers, Tokyo, pp. 703-710.
• 35: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 36: Luenberger, D.C. Linear arutNonlinearPrograrnming 2d ed. Addison-Wesley, Waltham, Mass., 1984.
• 37: Makanin, G.S. The Problem of Solvability of Equations on a Free Semi- Group. Math. USSR Sbornik 32, 2, (1977), English Translation, AMS, (1979), 129-198.
• 38: Matijasevic, Y. Diophantine sets, UspehiMat. Nauk 27, 5 (1972), 185-222; English translation: Russ. Math Surveys 27, 5 (1972), 124-164.
• 39: Murray, N.V. Completely Non-Clausal Theorem Proving. Artif. Intell. 18 (1982), 67-85.
• 40: Vijay Anand Saraswat , Dana S. Scott, Concurrent constraint programming languages, 1989
• 41: Siegel, P. Representation et utilisation de la connaissance en calcul propositionnel. Th~se de docteur d'Etat ~s Sciences, Universit~ Aix- Marseille, Luminy, 1987.
• 42: Smith, D.S. and Hickey, TJ. Partial evaluation of C LP (FT), Tech. Pep., CS-90-148 Brandeis Univ., 1990.
• 43: Guy L. Steele, Jr., The Definition and Implementation of a Computer Programming Language Based on Constraints, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 44: Leon Sterling , Ehud Shapiro, The art of Prolog: advanced programming techniques, MIT Press, Cambridge, MA, 1986
• 45: Tarski, A. A Decision Method for Elemtntary Algebra and Geometry, 2d revised ed., Univ. of California Press, 1948.
• 46: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 47: Warren, D.H.D. An abstract Prolog instruction set. Tech. Note 309, SKI International, Menlo Park, Calif., 1983.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

          Nouns: Prolog

General Terms:
Design, Languages