MPI-I-93-243
A needed narrowing strategy
Antoy, Sergio and Echahed, Rachid and Hanus, Michael
November 1993, 28 pages.
.
Status: available - back from printing
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.
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-243
BibTeX
@TECHREPORT{AntoyEchahedHanus93,
AUTHOR = {Antoy, Sergio and Echahed, Rachid and Hanus, Michael},
TITLE = {A needed narrowing strategy},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-93-243},
MONTH = {November},
YEAR = {1993},
ISSN = {0946-011X},
}