Functional Logic Programming with Distributed Constraint Solving System

我们的贡献是：(1)开发具有分布式约束求解系统的函数式逻辑程序设计语言的计算模型；(2)基于计算模型的编程环境的实现。(1)计算模型的设计。我们的研究项目始于一个称为延迟收缩演算的计算模型的设计。LNC是我们研究函数和逻辑编程的所有计算模型的基础。为了处理函数式逻辑程序设计语言中的约束求解问题，我们将LNC扩展到条件情形。由此产生的演算称为懒惰条件收缩演算(LCNC)。此外，我们消除了LCNC固有的不确定性。此外，我们还设计了高阶演算，即应用LNC，它用(一阶)应用项表示项来模拟高阶计算，以及高阶Lazy窄化演算(LNff)，它可以处理Lambda项。我们证明了上述演算的完备性。(Ii)编程系统的实现我们在分布式环境下实现了一个功能逻辑编程系统。该系统称为约束函数逻辑程序设计系统(CFLP)。CFLP由三个组件组成：解释器、调度器和约束求解系统。我们使用数学编程语言将CFLP实现为一个分布式软件系统。CFLP的计算机制是基于狭义演算的。CFLP系统中函数逻辑程序设计语言的解释器通过访问分布式环境中的约束求解器来求解给定的方程。狭义微积分在项代数域上寻找答案。其他特定于领域的常量和操作由提供特定于领域的求解方法的约束求解器处理。

Our contributions are (i) development of computation models for functional logic programming languages with distributed constraint solving systems and (ii) realization of a programming environment based on the computation models.(i) Design of computation modelsWe started the research project with the design of a computation model called Lazy Narrowing Calculus (LNC). LNC forms the basis of our investigation into all our computation models for functional and logic programming. To deal with constraint solving in functional logic programming languages, we extended LNC to the conditional case. The resulting calculus is called Lazy Conditional Narrowing Calculus (LCNC). Moreover, we removed the non-determinism inherent in LCNC. This simplifies the implementation of the calculus on computers and improves the computational efficiency.Furthermore we designed higher-order calculi, i.e. Applicative LNC, which simulates higher-order computation by using (first-order) applicative terms for representing terms, and Higher-Order Lazy Narrowing Calculus (LNff), which can handle lambda terms. We proved that all the above-mentioned calculi have completeness.(ii) Implementation of the programming systemWe implemented a functional logic programming system in a distributed environment. The system is called Constraint Functional Logic Programming system (CFLP). CFLP consists of three components : an interpreter, a scheduler, and a constraint solving system. We implemented CFLP as a distributed software system using the programming language Mathematica. The computation mechanism of CFLP is based on the narrowing calculi. The interpreter of the functional logic programming language in CFLP system solves given equations by accessing constraint solvers in a distributed environment. The narrowing calculi find solutions over the domain of term algebra. The other domain-specific constants and operations are handled by the constraint solvers which provide the domain-specific solving methods.