Application of Conditional Rewrite Systems to Declarative Programming Languages

条件重写系统在声明式编程语言中的应用

• 批准号: 06680300
• 负责人: IDA Tetsuo
• 金额: $ 1.41万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 1995
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-06680300/
• 关键词: conditional rewrite system; declarative programming; functional-logic programming language; narrowing; level-confluence; modular property; semantics of programs; 条件付き書換え系; 宣言型プログラミング; 宣言型言語; 関数 論理型言語; 条件付項書換え系

The objective of our research is the investigation of conditional rewrite systems as a computational model of declarative programming languages. We study narrowing since it is fundamental to give a computational mechanism of functional-logic languages, a class of declarative programming languages. The results we obtained are as follows.1. We designed two narrowing calculi called OINC (Outside-In Narrowing Calculus) and LNC ( Lazy Narrowing Calculus) in order to give computational mechanisms of declarative programming languages. The two calculi enable us to incorporate the notion of lazy-evaluation, developed in functional programming languages, into functional-logic programming languages. We also obtained completeness results of these calculi for a class of term rewriting systems.2. We Proposed a syntactic sufficient condition for level-confluence of conditional rewrite systems with extra variables in the right-hand side of their rewrite rules. Level-confluence is an important property to guarantee completeness of narrowing for condtional rewrite systems. Using this result, we showed a new sufficient condition for completeness of narrowing for conditional rewrite systems with extra variables.3. We investigated a relationship between conditional narrowing and models of declarative programming languages. We showed conditional narrowing is sound and complete with respect to two typical models of functional-logic languages based on strict equations.4. In order to apply properties of conditional rewrite systems to meta programming in declarative programming languages, we investigated modular properties of conditional rewrite systems. We showed level-confluence in modular for conditional rewrite systems with extra variables.

我们研究的目标是研究条件重写系统作为声明性编程语言的计算模型。我们研究缩小，因为它是基本的函数逻辑语言，一类声明式编程语言的计算机制。主要研究结果如下：1.我们设计了两个缩窄演算OINC（Outside-In Narrowing Calculus）和LNC（Lazy Narrowing Calculus），以给出声明式编程语言的计算机制。这两个演算使我们能够将在函数式编程语言中开发的延迟求值的概念纳入函数式逻辑编程语言。对于一类项重写系统，我们也得到了这些演算的完备性结果.本文提出了重写规则右侧带有额外变量的条件重写系统的水平汇合的一个句法充分条件。层次汇合是保证条件重写系统收缩完备性的一个重要性质。利用这一结果，我们给出了一个新的具有额外变量的条件重写系统收缩完备性的充分条件.我们研究了声明式编程语言的条件缩小和模型之间的关系。我们证明，对于基于严格方程的函数逻辑语言的两个典型模型，条件缩窄是合理且完整的。4.为了将条件重写系统的性质应用到声明式编程语言的Meta编程中，我们研究了条件重写系统的模块性质。我们在模块化的条件重写系统中显示了额外变量的水平汇合。

项目成果

K.Nakagawa et al.: "Compiling Programs of an Applicative Narrowing Calculus" Proc.of Fuji Int.Workshop on Functional and Logic Programming. 78-91 (1995)

K.Nakakawa 等人：“Compiling Programs of an Applicative Narrowing Calculus”Proc.of Fuji Int.Workshop on 函数和逻辑编程。

T.Suzuki et al.: "Level-confluence of conditional rewrite systems with extra variables in right-hand sides" Proc.of the 6th Int.Conf.on RTA '95. LNCS 914. 179-193 (1995)

T.Suzuki 等人：“右侧有额外变量的条件重写系统的水平汇合”Proc.of the 6th Int.Conf.on RTA 95。

T.Ida and K.Nakahara: "Leftmost outside-in narrowing calculi" J.of Functional Programming. (To Appear).

T.Ida 和 K.Nakahara：“最左外向内缩小演算”J.of 函数式编程。

T.Suzuki,A.Middeldorp,and T.Ida: "Level-Confluence of Conditional Rewrite Systems with Extra Variables in Right-Hand Sides" Proceedings of the 6th International Conferece on Rewriting Techniques and Applications,Lecture Notes in Computer Science. (印刷中). (

T.Suzuki、A.Middeldorp 和 T.Ida：“右侧带有额外变量的条件重写系统的水平汇合”第六届国际重写技术和应用会议论文集，计算机科学讲义。 （。

鈴木大郎: "Completeness of Narrowing for Orthogonal Conditional Rewrite Systems" Proc.of Fuji Int. Workshop on Functionl and Logic Programming. 63-77 (1995)

Dairo Suzuki：“正交条件重写系统的缩小的完整性”Proc.of Fuji Int. Workshop on Functionl and Logic Planning (1995)。