Incremental Rewriting in Narrowing Derivations

Hanus, Michael

doi:10.1007/BFb0013829

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Incremental Rewriting in Narrowing Derivations

MPS-Authors

/persons/resource/persons44582

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

External Resource

https://rdcu.be/dtn2l
(Publisher version)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Hanus, M. (1992). Incremental Rewriting in Narrowing Derivations. In H. Kirchner, & G. Levi (Eds.), Proceedings of the 3rd International Conference on Algebraic and Logic Programming (ALP-92) (pp. 228-243). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-AE12-9

Abstract

The operational semantics of many proposals for the integration of functional
and logic programming languages is based on narrowing. In order to reduce the
search space and to prefer deterministic computations, the goal is rewritten to
normal form between narrowing steps (normalizing narrowing). This rewriting
process may be costly since the entire goal must be reduced to normal form
after each narrowing step. We propose a useful optimization of the rewriting
process: since the goal is in normal form before the narrowing step is applied
and the narrowing step changes only small parts of the goal, rewriting can be
restricted to a small number of positions in the narrowed goal in order to
compute a new normal form. This optimization can speed up the execution
mechanism of programming languages based on normalizing narrowing like SLOG or
ALF.