Abstract
Negation as failure is an important language feature within the logic programming paradigm. The natural notion generalizing negation as failure in a functional logic setting is that of finite failure of reduction. In previous works we have shown the interest of using such programming construct when writing functional logic programs, and we have given a logical status to failure by means of proof calculi designed to deduce failures from programs. In this paper we address the problem of the operational mechanism for the execution of functional logic programs using failure. Our main contribution is the proposal of a narrowing relation able to deal with failures, which is constructive in the usual sense of the term in the context of negation, that is, narrowing is able to find substitutions for variables even in presence of failures. As main technical results, we prove correctness and completeness of the narrowing relation with respect to the proof-theoretic semantics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Abengózar-Carneros et al. \( \mathcal{T}\mathcal{O}\mathcal{Y} \): a multiparadigm declarative language, version 2.0. Technical report, Dep. SIP, UCM Madrid, January 2001. 212, 213
S. Antoy. Definitional trees. In Proc. ALP’92, pages 143–157. Springer LNCS 632, 1992. 214, 217
S. Antoy. Constructor-based conditional narrowing. In Proc. PPDP’01, pages 199–206. ACM Press, 2001. 217, 225
K.R. Apt and R. Bol. Logic programming and negation: A survey. Journal of Logic Programming, 19&20:9–71, 1994. 212
D. Chan. Constructive negation based on the completed database. In Proc. ICSLP’88, pages 111–125, 1988. 214
K. L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 293–322. Plenum Press, 1978. 212
J.C. González-Moreno, T. Hortalá-González, F. J. López-Fraguas, and M. Rodríguez-Artalejo. A rewriting logic for declarative programming. In Proc. ESOP’96, pages 156–172. Springer LNCS 1058, 1996. 213, 225
J.C. González-Moreno, 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):47–87, 1999. 212, 213, 218, 225
M. Hanus. The integration of functions into logic programming: From theory to practice. Journal of Logic Programming, 19&20:583–628, 1994. 212
M. Hanus (ed.). Curry: An integrated functional logic language. Available at http://www-i2.informatik.rwth-aachen.de/~hanus/curry/report.html, February 2000. 212, 213
F. J. López-Fraguas and J. Sánchez-Hernández. \( \mathcal{T}\mathcal{O}\mathcal{Y} \): A multiparadigm declarative system. In Proc. RTA’99, Springer LNCS 1631, pages 244–247, 1999. 212, 213
F. J. López-Fraguas and J. Sánchez-Hernández. Proving failure in functional logic programs. In Proc. CL’00, Springer LNAI 1861, pages 179–193, 2000. 213, 214, 218
F. J. López-Fraguas and J. Sánchez-Hernández. Functional logic programming with failure: A set-oriented view. In Proc. LPAR’01, Springer LNAI 2250, pages 455–469, 2001. 213, 214, 217, 218
F. J. López-Fraguas and J. Sánchez-Hernández. Narrowing failure in functional logic programming (long version). Available at http://www.ucm.es/info/dsip/jaime/flopsExt.ps, 2002. 215
F. J. López-Fraguas and J. Sánchez-Hernández. A proof theoretic approach to failure in functional logic programming. Draft available at http://www.ucm.es/info/dsip/jaime/tplp.ps, 2002. 213, 214
J. J. Moreno-Navarro. Default rules: An extension of constructive negation for narrowing-based languages. In Proc. ICLP’94, pages 535–549. MIT Press, 1994. 214
J. J. Moreno-Navarro. Extending constructive negation for partial functions in lazy functional-logic languages. In Proc. ELP’96, pages 213–227. Springer LNAI 1050, 1996. 214, 216
J. C. Reynolds. Theories of Programing Languages. Cambridge Univ. Press, 1998. 216
P. J. Stuckey. Constructive negation for constraint logic programming. In Proc. LICS’91, pages 328–339, 1991. 214
P. J. Stuckey. Negation and constraint logic programming. Information and Computation, 118:12–33, 1995. 214
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
López-Fraguas, F.J., Sánchez-Hernández, J. (2002). Narrowing Failure in Functional Logic Programming. In: Hu, Z., Rodríguez-Artalejo, M. (eds) Functional and Logic Programming. FLOPS 2002. Lecture Notes in Computer Science, vol 2441. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45788-7_13
Download citation
DOI: https://doi.org/10.1007/3-540-45788-7_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44233-2
Online ISBN: 978-3-540-45788-6
eBook Packages: Springer Book Archive