Context-sensitive computations in functional and functional logic programs

Author

Salvador Lucas

Abstract

Context-sensitive rewriting 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.

Keywords

confluence, functional programming, functional logic languages, narrowing, replacement restrictions, term rewriting.