Parallel Processors for Constraint Languages

该项目的重点是为在顺序和并行机器上执行的逻辑和约束编程(CLP)语言开发编译器和解释器。Prolog就是这样一种语言，它为用户提供了解决包括实数、布尔和字符串在内的域中问题的能力。该项目的四个具体主题是：(1)约束并行性。在并行机上设计、实现和分析了几个域(包括整型、实型和布尔型)的约束求解器。这些求解器用于约束并行PROLOG系统的原型：(2)程序分析和转换。开发了并行约束分析工具和逻辑程序分析工具。所考虑的一些技术是基于局部评估和抽象解释的全局分析；(3)CLP的扩展。设计、实现和分析了基于约束和区间运算的高级类C语言。研究了在一个高阶逻辑程序设计框架中集成函数式语言、集合论语言和CLP语言的可能性；(4)并行CLP语言的应用。考虑了几类并行CLP应用，包括基因组解析、组合搜索问题(如调度)和非线性约束系统的优化。

The focus of this project is the development of compilers and interpreters for Logic and Constraint Programming (CLP) languages executing on sequential and parallel machines. Prolog is an example of such a language, and it offers the users capabilities of solving problems in domains including reals, booleans and strings. The four specific topics of the project are: (1) Constraint Parallelism. Constraint solvers for several domains (including integers, reals and booleans) are designed, implemented and analyzed on parallel machines. These solvers are used to prototype constraint parallel Prolog systems; (2) Program Analysis and Transformations. Tools for the analysis of parallel constraint and logic programs are developed. Some of the techniques that are considered are partial evaluation and abstract interpretation based global analysis; (3) Extension of CLP. High-level, C-like languages based on constraints and interval arithmetic are designed, implemented and analyzed. The possibility of integrating, functional, set-theoretic and CLP languages in a single higher order logic programming framework is also studied; and (4) Applications of Parallel CLP. Several classes of parallel CLP applications are considered, including genome parsing, combinatorial search problems (such as scheduling), and optimization of non-linear constraint systems.