The CLP( R ) language and system

ABSTRACT

The CLP R programming language is defined, its underlying philosophy and programming methodology are discussed, important implementation issues are explored in detail, and finally, a prototype interpreter is described. CLP R is designed to be an instance of the Constraint Logic Programming Scheme, a family of rule-based constraint programming languages defined by Jaffar and Lassez. The domain of computation R of this particular instance is the algebraic structure consisting of uninterpreted functors over real numbers. An important property of CLP R is that the constraints are treated uniformly in the sense that they are used to specify the input parameters to a program, they are the only primitives used in the execution of a program, and they are used to describe the output of a program. Implementation of a CLP language, and of CLP R in particular, raises new problems in the design of a constraint-solver. For example, the constraint solver must be incremental in the sense that solving additional constraints must not entail the resolving of old constraints. In our system, constraints are filtered through an inference engine, an engine/solver interface, an equation solver and an inequality solver. This sequence of modules reflects a classification and prioritization of the classes of constraints. Modules solving higher priority constraints are isolated from the complexities of modules solving lower priority constraints. This multiple-phase solving of constraints, together with a set of associated algorithms, gives rise to a practical system.

REFERENCES

• 1: BLAND, R.G. New finite pivoting rules for the simplex method. Math. Oper. Res. 2 (1977), 103-107.
• 2: Alan Borning, The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.353-387, Oct. 1981 [doi>10.1145/357146.357147]
• 3: COLLINS, G. E. Quantifier elimination for real closed fields: A guide to the literature. In Computer Algebra: Symbolic and Algebraic Computation. Computing Supplement No 4, Buchberger, B., Loos, R. and Collins, G. E. Eds., SpringerWerlag, New York, 1982, 79-81.
• 4: COLMERAUER, A. PROLOG II refercnce manua} and theoretlcal model. Intcrnal Rep. Groupe Intelligence Artificielle, Universit~ Aix--Marseille II, Oct. 1982.
• 5: Alain Colmerauer, Opening the Prolog III universe, BYTE, v.12 n.9, p.177-182, Aug. 1987
• 6: 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]
• 7: DE KLEER, J., AND SUSSMAX, G.J. Propagation of constramts applied to circuit synthesis. Circuit Theory Appl. 8 (1980), 127-144.
• 8: DINCBAS, M., VAN HENTENRYCK, P., SIMONIS, H., AND AGGOUN, A. The constraint logic programming language CHIP. In Proceedings of the 2nd Internatwnal Conference on Fifih Generatwrz Computer Systems (Tokyo, Nov. 1988), pp. 249-264.
• 9: DUFFIN, R.J. On Fourier's analysis of linear inequality systems. Math. Program. Stud. 1 (1974), 71-95.
• 10: Michael M. Gorlick , Carl F. Kesselman , Daniel A. Marotta , D. Scott Parker, Mockingbird: a logical methodology for testing, Journal of Logic Programming, v.8 n.1-2, p.95-119, Jan./Mar. 1990 [doi>10.1016/0743-1066(90)90053-8]
• 11: HANSEN, B. S. AND HANSEN, M.R. Simple symbolic and numeric computations based on equations and inequa}ities, Computer Science Res. Rep., IBM Res. Lab., San Jose, Calif., June 1985.
• 12: HARLAND, J. A., AND MICHAYLOV, S. Implementing an ODE solver: A CLP approach, Tech. Rep. 87/92, Dept. of Computer Science, Monash Univ., June 1987.
• 13: HEINTZlS, N. C., JAFFAI% J., L;rM, C. S., MICI4AYLOV, 8., 8TUCKEY, P. J.. YAP, R., AND YEE, C.N. The CLP(:2) Programmers Manual--Version 1, Tech. Rep. 59, Dept of Computer Science, Monash Univ., June 1986.
• 14: HEINTZE, N. C , MICttAYLOV, S., AND STUCKEY, P.J. CLP(~'~) and some electrical engineering problems. In Proceedmgs 4th Internatmnal Conference of Logic Programmmg, (Melbourne, June 1987), MIT Press, pp. 675 703. To appear m J Aurore. Reasonmg.
• 15: HEISSE~MAN, J. A Generative geometric design and boundary solid gTammars, Tech. Rep. EDRC-48-21-90, Engineering and Design Research Center, Carnegie Mellon Univ, Aug 1990.
• 16: HUYNH, T, AND LASSEZ, J.-L Practical issues on the projection of polyhedral sets, IBM Res. Rep. RC 15872-70560, June 1990.
• 17: 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]
• 18: JAFFAR, J., AND MICHAYLOV, S. Methodology and lmplementation of a CLP system, Tech. Rep 86/75, Dept of Computer Science, Monash Univ., Nov. 1986. Also in Proceedings 4th Internatwnal Conference on Logic Programming, (MeIbourne, June 1987), MIT Press, pp. 196-218.
• 19: KARWAN, M H., LOFTI, V., TELGEN, J., AND ZIONTS, S, Redundancy in mathematical programming: A state-of-the-art survey. Springer-Verlag Lecture Notes in Economics and Mathematical Systems 206, 1983.
• 20: KOHLER, D.A. Projections of polyhedral sets. Ph.D. Thesis, Tech. Rep. ORC-67-29, Opera~ tions Research Center, Unir. of California at Berkeley, Aug 1967
• 21: KONOPASEK, M., AND JAYARAMAN, S Constraint and declarative languages for engineering applications: The TK!Solver contribution. Proc. IEEE. 73, 12 (Dec. 1985), 1791- 1806.
• 22: LASSEZ, J.-L , HUYNH, T, AND McALOON, K. Simplification and elimination of redundant linear arithmetic constraints. In Proceedings of the Fzrst North Amemcan Conference on Logic Programming, (Cleveland, Oh., Oct. 1989), MIT Press, pp. 35-51
• 23: LASSEZ, J.-L, AND McALooN, K Generalized canonical forms for linear constraints and applications In Proceedmgs, Internatwnal Conference on Fifth Generation Computer Systems (Tokyo, Nov. 1988), pp. 703-710.
• 24: LASSEZ, C., McALooN, K., AND YAP, R. Constraint logic progTamming and options trading. IEEE Expert 2, 3 Special Issue on Financial Software (Aug. 1987), 41-50.
• 25: MATHLAB GRouP. Macsyma Reference Manual, MIT, 1977.
• 26: MUKAI, K A system oflogic programming for linguistic analysis. ICOT Tech Rep. TR-540, 1990.
• 27: NAm~, L. The MU-PROLOG 3.2db reference manual Tech. Rep, Dept. of Computer Science, Univ. of Melbourne, 1985.
• 28: Gerhard Rayna, REDUCE: Software for algebraic computation, Springer-Verlag New York, Inc., New York, NY, 1987
• 29: Kô Sakai , Akira Aiba, CAL: a theoretical background of constraint logic programming and its applications, Journal of Symbolic Computation, v.8 n.6, p.589-603, Dec. 1989 [doi>10.1016/S0747-7171(89)80063-X]
• 30: V. A. Saraswat, The concurrent logic programming language CP: Definition and operational semantics, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.49-62, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41630]
• 31: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 32: SICStus PROLOG Users ManuaL Swedish Institute of Computer Scmnce, 1989.
• 33: STALLMAN, R. M , AND SUSSMAN, G.J. Forward reasoning and dependency directed backtracking in a system for computer-aided circuit analysis. Art~f. Intell. 9, 2 (Oct. 1977), 135-196.
• 34: Guy Lewis Steele, Jr. , Gerald Jay Sussman, Constraints, Proceedings of the international conference on APL: part 1, p.208-225, May 30-June 01, 1979, New York, New York, United States
• 35: Guy L. Steele, Jr., The Definition and Implementation of a Computer Programming Language Based on Constraints, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 36: STERLING, L. AND SHAPmO, E. Y. The Art of PROLOG. MIT Press Series in Logic Programming, 1986.
• 37: SUSSMAN, G J., AND STALLMAN, R. M Heurmtic techniques in computer-aided circuit analysis. IEEE Trans. C~rcu~ts Syst. CAS-22, 11 (Nov 1975), 857-865.
• 38: STUCKE~, P.J. Incremental linear arithmetic constraint solving and detection of implicit equalities. ORSA J. Comput., 3, 4 (1991), 269-274.
• 39: THOM, J. A. AND ZOBEL, J., EDS. NU-PROLOG Reference Manual- Version 1.3. Tech. Rep. 86/10, Dept. of Computer Science, Univ. of Melbourne, 1986. Revised in 1988.
• 40: TOmAS II, J. C. Knowledge representation in the harmony intelligent tutoring system. Master's thesis, Dept. of Computer Science, Univ. of California at Los Angeles, 1988.
• 41: WALINSKY, C. CLP(~*): Constraint logic programming with regular sets. In Proceedings 6th International Conference on Logic Programming (Lisbon, June 1989), MIT Press, pp. 181-196.
• 42: YAP, R. H. C. Restriction site mapping in CLP(/2). In Proceedmgs 8th International Conference in Logic Programming (Paris, June 1991), MIT Press, pp. 521-534.
• 43: ZIMA, H. P. A constraint language and its interpreter. Computer Science Res. Rep., IBM Research Laboratory, San Jose, Calif. June 1985.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Languages

Keywords:
constraints, logic programming