Using Static Analysis to Compile Non-sequential Functional Logic Programs ?
Julio Mari, Juan Jos, Campus de Montegancedo · 2000
The ecient implementation of functional logic languages re- lies on nding (if it exists) an optimal evaluation order for the arguments of functions. The problems of nding the best evaluation order, and the sequentiality of program rules are both dicult and can benet from us- ing static analysis techniques. The second problem is of special interest because the parallel evaluation of arguments is out of the question due to the possibility of backtracking and sharing of free logical variables among dierent arguments. However, the lack of sequentiality is often syntactic rather than semantic. In this paper we show that an adequate use of type information and strictness analysis can help a compiler to (i) derive an ecient evaluation order, and (ii) generate sequential code from most programs. Data structures (new versions of denitional trees) are introduced to take advantage of this kind of information and man- age run time tests when the computation cannot be made sequential at compile time.