Abstract
We investigate an extension of a lazy functional logic language, which uses term disequations both in programs and in computed answers. The semantic properties of the language are derived from the fact that it can be viewed as an instance of the CFLP(X)-scheme proposed in [Lo92] for constraint functional logic programming. In particular, the operational semantics for CFLP(X) — so called lazy constrained narrowing — is a computation mechanism parameterized by a constraint solver over the underlying domain. We define a constraint solver for our language, whose properties ensure completeness. As a further step towards implementation, we present an executable Prolog specification of the operational semantics, which has been implemented on top of a Prolog system. Experimental results have shown good performance.
This research has been partially supported by the Spanish National Project TIC92-0793 “PDR” and the Esprit BRA Working Group Nr. 6028 “CCL”.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P.H. Cheong: Compiling lazy narrowing into Prolog, Technical Report 25, LIENS, 1990, to appear in: Journal of New Generation Computing.
A. Colmerauer: Prolog and infinite trees, in K.L. Clark, S.A. Tarnlund (eds.) Logic Programming, Academic Press, 1982, 231–251.
A. Colmerauer: Equations and inequations on finite and infinite trees, Procs. FGCS'84, 1984, 85–99.
H. Comon: Disunification: A Survey, in: J.L.Lassez,G. Plotkin (eds.) Computational Logic, Essays in Honor of Alan Robinson, MIT Press, 1991,322–359.
A. Dovier, G.F. Rossi: Embedding extensional finite sets in CLP, Procs. Int. Logic Progr. Symp., MIT Press, 1993.
E. Giovannetti, G. Levi, C. Moiso, C. Palamidessi: Kernel LEAF: A Logic plus Functional Language, Journal of Computer and System Sciences, Vol. 42, No. 2, Academic Press 1991, 139–185.
J.C. González Moreno, M.T. Hortalá González, M. Rodríguez Artalejo: On the Completeness of Narrowing as the Operational Semantics of Functional Logic Programming, Procs. Computer Science Logic CSL'92, LNCS 702,1993, 216–230.
M. Hanus: The Integration of Functions into Logic: From Theory to Practice, to appear in J. of Logic Progr. Also available as Tech. Rep. MPI-I-94,201, 1994.
J. Jaffar, J.L. Lassez: Constraint Logic Programming, Procs. 14th ACM Symp. on Princ. of Prog. Lang., 1987, 114–119.
J. Jaffar, J.L. Lassez: Constraint Logic Programming, Tech. Rep. 86/73, Dep. of Computer Science, Monash University, 1986.
J. Jaffar,M.J. Maher: Constraint Logic Programming: A Survey, To appear in Journal of Logic Programming.
J.P. Jouannaud, C. Kirchner: Solving Equations in Abstract Algebras: A Rule-Based Survey of Unification, in: J.L.Lassez,G. Plotkin (eds.) Computational Logic, Essays in Honor of Alan Robinson, The MIT Press, 1991,357–321.
H. Kuchen, F.J. López-Fraguas, J.J. Moreno-Navarro, M. Rodríguez-Artalejo: Implementing Disequality in a Functional Logic Language, Procs. Joint Int. Conf and Symp. on Logic Programming, MIT Press, 1992, 207–221.
R. Loogen, F. J. López Fraguas, M. Rodríguez Artalejo: A Demand Driven Computation Strategy for Lazy Narrowing, Int. Symp. on Programming Language Implementation and Logic Programming (PLILP) 93, LNCS 714, 184–200.
F.J. López-Fraguas: Constraint Functional Logic Programming, PhD. dissertation (forthcoming).
F.J. López-Fraguas: A General Scheme for Constraint Functional Logic Programming, Procs. ALP, LNCS 632, 1992, 213–217.
M. Maher: Complete Axiomatizations of the Algebras of Finite, Rational and Infinite Trees, Procs. 3rd IEEE Symp. Logic in Computer Science, 1988, 348–357.
J. J. Moreno-Navarro, H. Kuchen, R. Loogen, M. Rodríguez-Artalejo: Lazy Narrowing in a Graph Machine, ALP, LNCS 463, 1990, 298–317.
J.J. Moreno-Navarro, M. Rodríguez-Artalejo: Logic Programming with Functions and Predicates: The Language BABEL, J. Logic Programming, 12, 1992, 189–223.
U.S. Reddy: Narrowing as the Operational Semantics of Functional Languages, Procs. Int. Symp. on Logic Programming, 1985, 138–151.
D.S. Scott: Domains for Denotational Semantics, Procs. ICALP, LNCS 140,1892, 577–613.
D.A. Smith: Constraint Operations for CLP(FT), Procs. 8th Int. Conf. on Logic Programming, MIT Press, 1991, 760–774.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arenas-Sánchez, P., Gil-Luezas, A., López-Fraguas, F.J. (1994). Combining lazy narrowing with disequality constraints. In: Hermenegildo, M., Penjam, J. (eds) Programming Language Implementation and Logic Programming. PLILP 1994. Lecture Notes in Computer Science, vol 844. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58402-1_27
Download citation
DOI: https://doi.org/10.1007/3-540-58402-1_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58402-5
Online ISBN: 978-3-540-48695-4
eBook Packages: Springer Book Archive