×

zbMATH — the first resource for mathematics

Programming with narrowing: a tutorial. (English) Zbl 1192.68135
Summary: Narrowing is a computation implemented by some declarative programming languages. Research in the last decade has produced significant results on the theory and foundation of narrowing, but little has been published on the use of narrowing in programming. This paper introduces narrowing from a programmer’s viewpoint; shows, by means of examples, when, why and how to use narrowing in a program; and discusses the impact of narrowing on software development activities such as design and maintenance. The examples are coded in the programming language Curry, which provides narrowing as a first class feature.

MSC:
68N18 Functional programming and lambda calculus
PDF BibTeX Cite
Full Text: DOI
References:
[1] ACM,, 2000. ACM Pacific NW Region Programming Contest. Available at http://icpc.baylor.edu/past/icpc2001/regionals/PacNW00/ (accessed 16.03.09).
[2] Aït-Kaci, H., An overview of LIFE, (), 42-58
[3] Albert, E.; Hanus, M.; Vidal, G., A practical partial evaluator for a multi-paradigm declarative language, Journal of functional and logic programming, 2002, 1, (2002) · Zbl 0977.68593
[4] Alpuente, M.; Falaschi, M.; Vidal, G., Narrowing-driven partial evaluation of functional logic programs, (), 45-61
[5] Alpuente, M.; Falaschi, M.; Vidal, G., A unifying view of functional and logic program specialization, ACM computing surveys, 9, (1998) · Zbl 0911.68036
[6] Alpuente, M.; Hanus, M.; Lucas, S.; Vidal, G., Specialization of functional logic programs based on needed narrowing, Theory and practice of logic programming, 5, 3, 273-303, (2005) · Zbl 1092.68018
[7] Alpuente, M.; Lucas, S.; Falaschi, M.; Vidal, G.; Hanus, M., Specialization of functional logic programs based on needed narrowing, Theory and practice of logic programming, 5, 3, 273-303, (2005) · Zbl 1092.68018
[8] Antoy, S., Definitional trees, (), 143-157
[9] Antoy, S., Optimal non-deterministic functional logic computations, (), 16-30 · Zbl 0886.68034
[10] Antoy, S., Constructor-based conditional narrowing, (), 199-206
[11] Antoy, S., Evaluation strategies for functional logic programming, Journal of symbolic computation, 40, 1, 875-903, (2005) · Zbl 1129.68019
[12] Antoy, S.; Echahed, R.; Hanus, M., A needed narrowing strategy, Journal of the ACM, 47, 4, 776-822, (2000) · Zbl 1327.68141
[13] Antoy, S.; Hanus, M., Compiling multi-paradigm declarative programs into prolog, (), 171-185 · Zbl 0969.68667
[14] Antoy, S.; Hanus, M., Declarative programming with function patterns, (), 6-22 · Zbl 1156.68339
[15] Antoy, S.; Hanus, M., Overlapping rules and logic variables in functional logic programs, (), 87-101 · Zbl 1131.68364
[16] Antoy, S., Hanus, M., 2009. Set functions for functional logic programming. In: Proceedings of the 11th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, PPDP 2009, Lisbon, Portugal, pp. 73-82.
[17] Antoy, S.; Hanus, M.; Liu, J.; Tolmach, A., A virtual machine for functional logic computations, (), 108-125 · Zbl 1119.68326
[18] Antoy, S.; Hanus, M.; Massey, B.; Steiner, F., An implementation of narrowing strategies, (), 207-217
[19] Baader, F.; Nipkow, T., Term rewriting and all that, (1998), Cambridge University Press
[20] Barry, B., 1996. Needed narrowing as the computational strategy of evaluable functions in an extension of Gödel. Master’s thesis, Portland State University.
[21] ()
[22] Bird, R.; Wadler, P., Introduction to functional programming, (1988), Prentice Hall New York, NY
[23] Braßel, B.; Fischer, S.; Huch, F., Declaring numbers, Electronic notes in theoretical computer science, 216, 111-124, (2008) · Zbl 1283.68133
[24] Brassel, B., Huch, F., 2007. The Kiel Curry System KiCS. In: Seipel, D., Hanus, M. (Eds.), Preproceedings of the 21st Workshop on (Constraint) Logic Programming, WLP 2007, Würzburg, Germany, Technical Report 434, pp. 215-223.
[25] (), Available at: http://toy.sourceforge.net
[26] Christiansen, J.; Fischer, S., Easycheck — test data for free, (), 322-336
[27] Dershowitz, N.; Jouannaud, J., Rewrite systems, (), 243-320, (Chapter 6) · Zbl 0900.68283
[28] Dershowitz, N.; Plaisted, D.A., Equational programming, (), 21-56, (Chapter 2) · Zbl 0722.68070
[29] Echahed, R., Inductively sequential term-graph rewrite systems, (), 84-98 · Zbl 1175.68220
[30] Echahed, R., Janodet, J.C., 1997. On constructor-based graph rewriting systems. Tech. Rep. 985-I, IMAG.
[31] Fay, M.J., First-order unification in an equational theory, (), 161-167
[32] Fischer, S.; Kuchen, H., Systematic generation of Glass-box test cases for functional logic programs, (), 63-74
[33] Fischer, S.; Kuchen, H., Data-flow testing of declarative programs, ()
[34] Giovannetti, E.; Levi, G.; Moiso, C.; Palamidessi, C., Kernel LEAF: A logic plus functional language, The journal of computer and system sciences, 42, 139-185, (1991) · Zbl 0717.68013
[35] González Moreno, J.C.; López Fraguas, F.J.; Hortalá González, M.T.; Rodríguez Artalejo, M., An approach to declarative programming based on a rewriting logic, The journal of logic programming, 40, 47-87, (1999) · Zbl 0942.68060
[36] Hanus, M., The integration of functions into logic programming: from theory to practice, Journal of logic programming, 19&20, 583-628, (1994) · Zbl 0942.68526
[37] Hanus, M., 1997. A unified computation model for functional and logic programming. In: Proceedings of the 24th ACM Symposium on Principles of Programming Languages, POPL’97, pp. 80-93.
[38] (), Available at http://www.informatik.uni-kiel.de/ curry
[39] Hanus, M., Multi-paradigm declarative languages, (), 45-75 · Zbl 1213.68162
[40] (), Available at: http://www.informatik.uni-kiel.de/ pakcs
[41] Hanus, M., Kuchen, H., Moreno-Navarro, J.J., 1995. Curry: A truly functional logic language. In: Proceedings of the ILPS’95 Workshop on Visions for the Future of Logic Programming. Portland, Oregon, pp. 95-107.
[42] Hullot, J.M., Canonical forms and unification, (), 318-334
[43] Hussmann, H., Nondeterministic algebraic specifications and nonconfluent rewriting, Journal of logic programming, 12, 237-255, (1992) · Zbl 0763.68050
[44] ISO, 1995. Information technology-Programming languages — Prolog-Part 1. General Core. ISO/IEC 13211-1, 1995.
[45] Klop, J.W., Term rewriting systems, (), 1-112
[46] Lloyd, J.W., Programming in an integrated functional and logic language, Journal of functional and logic programming, 1-49, (1999)
[47] López-Fraguas, F.J.; Sánchez-Hernández, J., TOY: A multiparadigm declarative system, (), 244-247
[48] Lux, W., Implementing encapsulated search for a lazy functional logic language, (), 100-113 · Zbl 0988.68528
[49] Meseguer, J.; Thati, P., Symbolic reachability analysis using narrowing and its application to verification of cryptographic protocols, Higher-order and symbolic computation, 20, 1-2, 123-160, (2007) · Zbl 1115.68079
[50] Milner, R.; Tofte, M.; Harper, R.; MacQueen, D., The definition of standard ML — revised, (1997), MIT Press
[51] Moreno-Navarro, J.J.; Rodríguez-Artalejo, M., Logic programming with functions and predicates: the language BABEL, Journal of logic programming, 12, 191-223, (1992) · Zbl 0754.68031
[52] O’Donnell, M.J., Computing in systems described by equations, () · Zbl 0421.68038
[53] O’Donnell, M.J., Equational logic as a programming language, (1985), MIT Press · Zbl 0636.68004
[54] (), Available at: http://www.haskell.org/onlinereport/
[55] Plump, D., Term graph rewriting, (), 3-61
[56] Reddy, U.S., Narrowing as the operational semantics of functional languages, (), 138-151
[57] Robinson, J.A., A machine-oriented logic based on the resolution principle, Journal of ACM, 12, 1, 23-41, (1965) · Zbl 0139.12303
[58] Sheard, T., Type-level computation using narrowing in \(\Omega\)mega, Electronic notes in theoretical computer science, 174, 7, 105-128, (2007) · Zbl 1277.68046
[59] ()
[60] Tolmach, A.; Antoy, S.; Nita, M., Implementing functional logic languages using multiple threads and stores, (), 90-102 · Zbl 1323.68167
[61] Wirth, N., Program development by stepwise refinement, Communications of the ACM, 14, 4, 221-227, (1971) · Zbl 0214.43005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.