Context-sensitive computations in functional and functional logic programs
is a refined form of rewriting which explores a smaller reduction space by
imposing some fixed restrictions on the replacements.
Any Term Rewriting System (TRS) can be given a context-sensitive rewrite
relation. In this paper, we review the theory of context-sensitive
rewriting and formulate conditions to guarantee the confluence of this relation.
Also, for left-linear TRSs, we show that the (eventually obtained) computed value of a given
expression can be produced by context-sensitive rewriting, thus furnishing more
efficient and still complete computations. We give the procedure to
establish the adequate replacement restrictions in order to achieve
this. We finally raise the concept of
context-sensitive restrictions from rewriting to narrowing and give
the corresponding completeness results.
confluence, functional programming,
functional logic languages, narrowing, replacement restrictions, term