This paper introduces a deterministic operational semantics for functional logic programs including notions like laziness, sharing, concurrency, non-deterministic functions, etc. Our semantic description is important not only to provide appropriate language definitions to reason about programs and check the correctness of implementations but it is also a basis to develop language-specific tools, like program tracers, profilers, optimizers, etc. Starting from a "big-step" semantics in natural style which relates expressions and their evaluated results---but it is not sufficient to cover concurrency, search strategies, or to reason about costs associated to particular computations---, we define a "small-step" operational semantics which actually covers the advanced features of modern functional logic languages.
Available: PS PDF BibTeX-Entry