A lazy narrowing calculus for declarative constraint programming

ABSTRACT

The new generic scheme CFLP (D) has been recently proposed in [24] as a logical and semantic framework for lazy constraint functional logic programming over a parametrically given constraint domain D. In this paper we extend such framework with a suitable operational semantics, which relies on a new constrained lazy narrowing calculus for goal solving parameterized by a constraint solver over the given domain D. This new calculus is sound and strongly complete w.r.t. the declarative semantics of CFLP (D)programs, which was formalized in [24] by means of a Constraint Rewriting Logic CRWL (D).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Krzysztof R. Apt, Logic programming, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	2	Puri Arenas-Sánchez , Ana Gil-Luezas , Francisco Javier López-Fraguas, Combining Layz Narrowing with Disequality Constraints, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.385-399, September 14-16, 1994
	3	Puri Arenas-Sánchez , Francisco Javier López-Fraguas , Mario Rodrúguez-Arteljo, Functional Plus Logic Programming with Built-In and Symbolic Constraints, Proceedings of the International Conference PPDP'99 on Principles and Practice of Declarative Programming, p.152-169, September 29-October 01, 1999
	4	Puri Arenas-Sánchez , Mario Rodríguez-Artalejo, A general framework for lazy functional logic programming with algebraic polymorphic types, Theory and Practice of Logic Programming, v.1 n.2, p.185-245, March 2001
	5	Franz Baader , Tobias Nipkow, Term rewriting and all that, Cambridge University Press, New York, NY, 1998
	6	R. Caballero and M. Rodríguez-Artalejo. A Declarative Debugging System for Lazy Functional Logic Programs. Electronic Notes in Theoretical Computer Science 64, 63 pages, 2002.
	7	R. Caballero and M. Rodríguez-Artalejo. DDT: A Declarative Debugging Tool for Functional Logic Languages. To appear in Proc. of the 7th International Symposium on Functional and Logic Programming (FLOPS'2004), Springer LNCS.
	8	J. Darlington, Y.K. Guo and H. Pull. A New Perspective on the Integration of Functional and Logic Languages. Proc. of the Int. Conf. on Fifth Generation Computer Systems (FGCS'92), IOS Press, pp. 682--693, 1992.
	9	Doug DeGroot , Gary Lindstrom, Logic programming: functions, relations, and equations, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
	10	Antonio J. Fernández , Teresa Hortalá-González , Fernando Sáenz-Pérez, Solving Combinatorial Problems with a Constraint Functional Logic Language, Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, p.320-338, January 13-14, 2003
	11	J.C. González-Moreno, M.T. Hortalá-González, F.J. López-Fraguas and M. Rodríguez-Artalejo. An Approach to Declarative Programming Based on a Rewriting Logic. Journal of Logic Programming 40(1), pp. 47--87, 1999.
	12	J.C. González-Moreno, M.T. Hortalá-González and M. Rodríguez-Artalejo. Polymorphic Types in Functional Logic Programming. FLOPS'99 special issue of the Journal of Functional and Logic Programming, 2001. http://danae.uni-muenster.de/lehre/kuchen/JFLP.
	13	C. A. Gunter , D. S. Scott, Semantic domains, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	14	M. Hanus. The Integration of Functions into Logic Programming: From Theory to Practice. Journal of Logic Programming 19&20, pp. 583--628, 1994.
	15	M. Hanus (ed.), Curry: an Integrated Functional Logic Language, Version 0.8, April 15, 2003. http://www-i2.informatik.uni-kiel.de/~curry/.
	16	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]
	17	J. Jaffar and M.J. Maher. Constraint Logic Programming: A Survey. The Journal of Logic Programming 19&20, pp. 503--581, 1994.
	18	J. Jaffar, M.J. Maher, K. Marriott and P.J. Stuckey. The Semantics of Constraint Logic Programs. Journal of Logic Programming, 37 (1-3) pp. 1--46, 1998.
	19	Joxan Jaffar , Spiro Michaylov , Peter J. Stuckey , Roland H. C. Yap, The CLP( R ) language and system, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.3, p.339-395, July 1992 [doi>10.1145/129393.129398]
	20	J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
	21	Francisco Javier López-Fraguas, A General Scheme for Constraint Functional Logic Programming, Proceedings of the Third International Conference on Algebraic and Logic Programming, p.213-227, September 02-04, 1992
	22	Francisco Javier López-Fraguas , Jaime Sánchez Hernández, TOY: A Multiparadigm Declarative System, Proceedings of the 10th International Conference on Rewriting Techniques and Applications, p.244-247, July 02-04, 1999
	23	Francisco J. López-Fraguas , Jaime Sánchez-Hernández, A proof theoretic approach to failure in functional logic programming, Theory and Practice of Logic Programming, v.4 n.2, p.41-74, January 2004 [doi>10.1017/S1471068403001728]
	24	F.J. López-Fraguas, M. Rodríguez-Artalejo and R. del Vado-Vírseda. Constraint Functional Logic Programming Revisited. To appear in Proc. of the 5th International Workshop on Rewriting Logic and its Applications (WRLA'2004), Electronic Notes in Theoretical Computer Science, 2004.
	25	M. Marin. Functional Logic Programming with Distributed Constraint Solving. Ph. D. Thesis, Johannes Kepler Universität Linz, 2000.
	26	M. Marin, T. Ida and W. Schreiner. CFLP: a Mathematica Implementation of a Distributed Constraint Solving System. In Third International Mathematical Symposium (IMS'99), Hagenberg, Austria, August 23--25, 10 pages, 1999.
	27	M. Marin, T. Ida and T. Suzuki. Cooperative Constraint Functional Logic Programming. In International Symposium on Principles of Software Evolution (IPSE'2000), pp. 223--230, November 1--2, 2000.
	28	K. Marriott and P.J. Stuckey. Programming with Constraints, An Introduction. The MIT Press, 1998.
	29	A. Middeldorp and E. Hamoen. Completeness Results for Basic Narrowing. Applicable Algebra in Engineering, Communications and Computing 5, pp. 213--253, 1994.
	30	J.A. Robinson ans E.E. Sibert. LOGLISP: Motivation, Design and Implementation. In K.L. Clark and S.A. Tärnlund (eds.), Logic Programming, Academic Press, pp. 299--313, 1982.
	31	Rafael del Vado Vírseda, A demand-driven narrowing calculus with overlapping definitional trees, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.253-263, August 27-29, 2003, Uppsala, Sweden [doi>10.1145/888251.888275]
	32	P. Van Hentenryck. Constraint logic programming. The Knowledge Engineering Review, Vol. 6:3, pp. 151--194, 1991.