Dynamic Detection of Determinism in Functional Logic Languages

Programs in functional logic languages usually have to satisfy a nonambiguity condition, that semantically ensures completeness of conditional narrowing and pragmatically ensures that the defined (non-boolean) functions are deterministic and do not yield different result values for the same argument tuples. The nonambiguity condition allows the dynamic detection of determinism in implementations of functional logic languages. In this paper we show how to achieve this and what can be gained by this optimization. 1 Introduction Functional logic languages are extensions of functional languages with principles derived from logic programming [Reddy 85,87]. While their syntax almost looks like the syntax of conventional functional languages, their operational semantics is based on narrowing, an evaluation mechanism that uses unification instead of pattern matching for parameter passing. Narrowing is a natural extension of reduction to incorporate unification. It means applying the minimal ..