CLP and constraint abstraction

ABSTRACT

CLP*(D) is a class of constraint logic programming languages which incorporates the notion of abstraction. Predicates in CLP*(D) are (potentially) infinite rational trees which represent abstractions of constraint expressions. This view of predicates as constraint abstractions was motivated by the language Scheme, where closures are viewed as abstractions of functional expressions. A semantics and an efficient implementation of the language are provided, along with several examples of the novel programming techniques provided by this class of languages.

REFERENCES

• COLL 83: G.E. Collins, Quantifier Elimination for Real Closed Fields: a guide to the literature, In: (Buchberger, B., Collins, G.E., Loos, R., eds) Computer Algebra: Symbolic and Algebraic Computation, 2nd edn., Vienna: Springer- Verlag.
• COLM 82: A. Colmerauer, Prolog and Infinite Trees, in Logic Programming, K.L.Clark and S.A. Tarnlund (Eds.), Academic Press, New York, 1982.
• COLM 84: A. Colmerauer, Solving Equations and Inequations on Finite and Infinite Trees, Proceedings of the Conference on Fifth Generation Computer Systems, Tokyo, Nov, 1984.
• CLAR 78: K. Clark, Negation as Failure, in Logic and Databases, H. Gallaire and J. Minker (eds.), Plenum Press, New York, 1978.
• JAFF 87a: J. Jaffar, S. Michaylov, Methodology and Implementation of a Constraint Logic Programm/ng System, Proceedings of the Fourth International Conference on Logic Programming, Melbourne, 1987, MIT Press.
• JAFF 87b: 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]
• STEE 78: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• STER 86: L. Sterling, and E. Shapiro. The Art of Prolog, MIT Press, Boston, MA, 1986.
• TARS 48: A. Tarski, A decision method for elementary algebra and geometry, 2nd revised edition, University of California Press, 1948.
• WARR 83: D. H. D. Warren, An Abstract Prolog Instruction Set, Tech. Note 309, SRI 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.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Prolog

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Languages