Optimizing Linear Recursive Formulas by Detaching Isolated Variables

摘要

Program transformation is a kind of optimization techniques for logic programs, which aims at transforming equally a program into an other form by exploiting some properties or information of the program, so as to make the pro-gram cheaper to evaluate. In this paper, a new kind of property of logic programs, called reducibility, is exploited in program transformation. A recursive predicate is reducible if the values of some variables in the recursive predicate are independent to the remainder part and can be detached from the predicate after finite times of expansions. After being proved that the semantic notion of reducibility can be replaced by the syntactic notion of disconnectivity of a R-graph, which is a kind of graph model to represent the behavior of formula expansions, an efficient testing and factoring algorithm is proposed. The paper also extends some existed results on compiled formulas of linear sirups, and compares with some related work.