A Demand Driven Computation Strategy for Lazy Narrowing

. Many recent proposals for the integration of functional and logic programming use conditional term rewriting systems (CTRS) as programs and narrowing as goal solving mechanism. This paper specifies a computation strategy for lazy conditional narrowing, based on the idea of transforming patterns into decision trees to control the computation. The specification is presented as a translation of CTRS into Prolog, which makes it executable and portable. Moreover, in comparison to related approaches, our method works for a wider class of CTRS. 1 Introduction Many recent approaches to the integration of functional and logic programming take conditional term rewriting systems (CTRS) as programs and narrowing as goal solving mechanism. Narrowing is complete as an equation solving procedure, under suitable hypotheses, see e.g. [7]. In general, narrowing has a high degree of (don't know) nondeterminism, due to two different sources: the choice of the redex, and the choice of the rewriting rule..