Global Compilation of Constraint Logic Programs

点击翻译按钮获取中文摘要

9302746 Van Hentenryck Constraint logic programming is an extension of logic programming where unification is replaced by constraint solving. Constraint logic programming languages, and their generalizations in the cc framework, combine constraint handling and (don't know) nondeterminism; they are particularly appealing for a variety of combinatorial search problems for which they offer a short development time and a good efficiency. However there is still a difference in efficiency between special-purpose algorithms written in procedural languages and constraint programs. The research aims at reducing further the gap between constraint and procedural programming by using global compilation techniques. Global compilation will be based on abstract interpretation, a systematic framework for dataflow analysis, which has been studied intensively in the logic programming community. Recent results have indicated that abstract interpretation of logic programming can be performed with a reasonable efficiency and that significant benefits in efficiency can be achieved. The main result of the research will be the design and implementation of optimizing compilers for two languages: cc(FD) (a constraint language over finite sets of integers) and cc(Q) a constraint language over rational linear arithmetic). Beside the traditional Prolog optimizations, the global optimizations considered include constraint specialization, detection of determinacy, elimination of redundant constraints, exploitation of independent subsystems, and constraint clustering. New results in abstract interpretation may also be expected. In particular, new frameworks and algorithms, including reexecution- based analysis and forwards/backwards analysis, the impact of granularity on efficiency and accuracy, and new domains will be studied. ***