Recovering Sequentiality in Functional-Logic Programs.
Julio Mariño, Juan José Moreno-Navarro · 1998
. Efficient code generation in implementations of functional logic languages relies on the sequentiality of the program rules --- existence of an optimal evaluation order for arguments. Parallel evaluation of arguments in the presence of free variables is out of the question due to the possibility of backtracking and sharing of these variables among different arguments. In this paper we show that the lack of sequentiality is often syntactic rather than semantic and that a clever use of type information and strictness analysis can enable a compiler to generate sequential code from most programs. Keywords: Sequentiality, Abstract Interpretation, Functional Logic Programming. 1 Introduction The relationship between sequential term rewriting systems [8] and the implementation of lazy functional programming languages is well known --- see, for instance [16, 15] for an introduction to the subject. The typical example is parallel or, defined by the equations or true x = true or x true = true...