An Implementation of Narrowing Strategies
Sergio Antoy, Michael Hanus, Bart Massey and Frank Steiner
In Proc. of the International Workshop on Functional and (Constraint) Logic Programming (WFLP 2001)
, Report No. 2017, University of Kiel
Abstract
This paper describes an implementation of narrowing, an essential component of implementations of
modern functional logic languages. These implementations rely on narrowing, in particular on some
optimal narrowing strategies, to execute functional logic programs. We translate functional logic
programs into imperative (Java) programs without an intermediate abstract machine. A central idea of
our approach is the explicit representation and processing of narrowing computations as data objects.
This enables the implementation of operationally complete strategies (i.e., without backtracking) or
techniques for search control (e.g., encapsulated search). Thanks to the use of an intermediate and
portable representation of programs, our implementation is general enough to be used as a common
back-end for a wide variety of functional logic languages.