An Evaluation Semantics for Narrowing-Based Functional Logic
Michael Hanus and Salvador Lucas
We introduce a semantic characterization of narrowing, the computational
engine of many functional logic languages. We use a functional
domain for giving
a denotation to the narrowing space associated to a
given initial expression under an arbitrary narrowing strategy.
Such a semantic description highlights (and favours) the operational notion
of evaluation instead of the more usual model-theoretic notion of
interpretation as the basis for the semantic description. The
motivation is to obtain an abstract semantics which encodes information about
the real operational framework used by a given (narrowing-based) functional logic language.
Our aim is to provide a semantic foundation for the development of a
general, suitable, and accurate framework
for the analysis of functional logic programs.
Domain theory, functional logic languages, narrowing, program