An Operational Semantics for Declarative Multi-Paradigm Languages

by Elvira Albert, Michael Hanus, Frank Huch, Javier Oliver, Germán Vidal

Proc. of the 11th International Workshop on Functional and (Constraint) Logic Programming (WFLP 2002), Research Report UDMI/18/2002/RR, Università degli Studi di Udine, pp. 7-20, 2002

In this paper we define an operational semantics for functional logic languages covering notions like laziness, sharing, concurrency, non-determinism, etc. Such a semantics is not only important 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. First, we define a "big-step" semantics in natural style to relate expressions and their evaluated results. Since this semantics is not sufficient to cover concurrency, search strategies, or to reason about costs associated to particular computations, we also define a "small-step" operational semantics covering the features of modern functional logic languages.

Preprint (PDF) BibTeX-Entry