Functional Logic Programming with Distributed Constraint Solving System

分布式约束求解系统的函数逻辑编程

基本信息

批准号：
10480053
负责人：
IDA Tetsuo
金额：
$ 6.4万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 1999
项目状态：
已结题

项目摘要

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.

我们的贡献是（i）开发具有分布式约束求解系统的函数逻辑编程语言的计算模型，以及（ii）基于计算模型的编程环境的实现。（i）计算模型的设计我们开始了该研究项目的设计称为惰性缩小微积分（LNC）的计算模型。 LNC 构成了我们研究所有函数和逻辑编程计算模型的基础。为了处理函数逻辑编程语言中的约束求解，我们将 LNC 扩展到条件情况。由此产生的演算称为惰性条件缩小演算 (LCNC)。此外，我们消除了 LCNC 固有的非确定性。这简化了微积分在计算机上的实现，提高了计算效率。此外，我们设计了高阶微积分，即Applicative LNC，它通过使用（一阶）应用项来表示项来模拟高阶计算，以及Higher-Order惰性缩小微积分 (LNff)，可以处理 lambda 项。我们证明了上述所有演算的完备性。 (ii)编程系统的实现我们在分布式环境下实现了一个函数式逻辑编程系统。该系统称为约束功能逻辑编程系统（CFLP）。 CFLP 由三个组件组成：解释器、调度器和约束求解系统。我们使用编程语言 Mathematica 将 CFLP 实现为分布式软件系统。 CFLP的计算机制基于窄化演算。 CFLP系统中函数逻辑编程语言的解释器通过访问分布式环境中的约束求解器来求解给定的方程。缩小演算在项代数领域找到解决方案。其他特定于域的常量和运算由提供特定于域的求解方法的约束求解器处理。