A needed narrowing strategy

Antoy, Sergio; Echahed, Rachid; Hanus, Michael

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

報告書

A needed narrowing strategy

MPS-Authors

Antoy, Sergio
Programming Logics, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

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

フルテキスト (公開)

MPI-I-93-243.pdf
(全文テキスト（全般）), 193KB

付随資料 (公開)

There is no public supplementary material available

引用

Antoy, S., Echahed, R., & Hanus, M.(1993). A needed narrowing strategy (MPI-I-93-243). Saarbrücken: Max-Planck-Institut für Informatik.

引用: https://hdl.handle.net/11858/00-001M-0000-0014-B494-9

要旨

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.