User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

A Needed Narrowing Strategy


Hanus,  Michael
Programming Logics, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Antoy, S., Echahed, R., & Hanus, M. (1994). A Needed Narrowing Strategy. In Proceedings of the 21st ACM Symposium on Principles of Programming Languages (POPL'94) (pp. 268-279). New York, USA: ACM.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-AD59-4
Narrowing is the operational principle of languages that integrate functional and logic programming. We propose a notion of a needed narrowing step that, for inductively sequential rewrite systems, extends the Huet and Levy notion of a needed reduction step. We define a strategy, based on this notion, that computes only needed narrowing steps. Our strategy is sound and complete for a large class of rewrite systems, is optimal w.r.t. the cost measure that counts the number of distinct steps of a derivation, computes only independent unifiers, and is efficiently implemented by pattern matching.