宣言型プログラムを対象とする高階項書換え系の計算理論

声明性程序的高阶项重写系统的计算理论

• 批准号: 12878047
• 负责人: 井田 哲雄
• 金额: $ 1.15万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12878047/
• 关键词: 宣言型プログラム; 計算モデル; ナローイング計算系; 選択関数; 球解完全性; 高階遅延ナローイング; 求解完全性

宣言型プログラミングの計算のモデルとしての高階項書換え系の諸性質の解明を行った.特に,高階の単一化に関わる機能や一階の項を操作する機構など,高階性に由来する強力な計算能力を活かした計算の理論の構築をはかり,宣言型プログラムのプログラム変換や自動導出研究の基礎の確立に貢献することを目指した.以下に得られた研究成果をまとめる.1.高階書換え系における簡約の戦略について,一階の場合と同様な標準化定理が成立することを確認した.高階簡約の標準化定理はLeft-linear Fully-extendedであるパターン書換え系について成立する.2.標準簡約の概念を組み込んだ高階の計算系HOLN(Higher-order Lazy Narrowing Calculi)を設計し,健全性・完全性の証明を得た.さらに,HOLNを関数・論理型言語の計算モデルとしたときに考えられるいくつかの最適化について考察した.最適化によっても,完全性が失われないことを示した.3.HOLNは高階単一化,遅延ナローイングを組み込んだ計算系であり,本研究の成果をシステムとして実現するものである.さらにHOLNを実装し,関数・論理型言語のモデルとしての適切性について評価を行った.条件付きナローイング計算系が,外変数のない合流性をもつ条件付き書換え系について,正規化可能解に関して完全であることを以前に示していたが,さらにゴールの中の等式選択の戦略として,最左戦略をとっても完全であることを新たに明らかにした.ここで得られた照明技法は上記2.において高階計算系HOLNの完全性を証明する上でも活用された.

The declaration type is to understand the behavior of the project. In particular, high-level equipment equipment is able to operate a project, and the reason for its high performance is that it is necessary to force the calculation of the ability to calculate, to calculate the theory, to make a statement, to automatically direct the research foundation, to make sure that the system is established, to provide information on the target. The following is about the results of the research. 1. The system of higher information is that the standard theorem is established in the same way. The normalization Theorem of Left-linear Fully-extended contract holds true for many years. 2. The standard agreement concept system is HOLN (Higher-order Lazy Narrowing Calculi) design program, and the soundness and completeness performance specification is satisfactory. The words "HOLN", "number", "calculation", "calculation, calculation and calculation. The results of this study show that there is a significant improvement in the calculation system of the computer system, and the results of this study show that the results of this study are very important. I don't know what to say. I don't know what to do. I don't know what to HOLN. The conditional calculation system is correct, and the external data confluence condition is related to the computer system. Normalization may be used to solve the problem. The equation in the equation is selected to select the correct one, and the leftmost column is to make sure that the new data is fully valid. I can't help you with your lighting techniques. The high-level calculation system of HOLN is used to improve the performance of the computer.

项目成果

M.Marin,T.Suzuki,T.Ida: "Cooperative Constraint Functional Logic Programming"International Symposium on Principles of Software Evolution. 223-230 (2000)

M.Marin，T.Suzuki，T.Ida：“协作约束功能逻辑编程”软件演化原理国际研讨会。

T.Suzuki,A.Middeldorp: "A Complete Selection Function for Lazy Conditional Narrowing"Proc.5th International Symposium on Functional and Logic Programming, LNCS. (印刷中). (2001)

T.Suzuki、A.Middeldorp：“惰性条件缩小的完整选择函数”Proc. 第五届函数和逻辑编程国际研讨会，LNCS（印刷中）。

Tetsuo Ida, Mircea Marin, Taro Suzuki: "Higher-order Lazy Narrowing Calculus : a Solver for Higher-order"Equations, Conference on Computer Aided Systems (EUROCAST 2001), Lecture Notes in Computer Science 2178, Las Palmas de Gran Canaria, Spain. 478-493 (2

Tetsuo Ida、Mircea Marin、Taro Suzuki：“高阶惰性窄化微积分：高阶求解器”方程，计算机辅助系统会议 (EUROCAST 2001)，计算机科学讲义 2178，西班牙拉斯帕尔马斯

M.Marin,T.Ida,T.Suzuki: "Higher-order Lazy Narrowing Calculi in Perspective"Proc.9th International Workshop on Functional and Logic Programming. 238-253 (2000)

M.Marin、T.Ida、T.Suzuki：“透视高阶惰性窄化演算”Proc.9th 国际函数和逻辑编程研讨会。

M.Marin,T.Suzuki: "Cooperative Constraint Functional Logic Programming"Proc.9th International Workshop on Functional and Logic Programming. 382-390 (2000)

M.Marin，T.Suzuki：“协作约束函数逻辑编程”Proc.9th 国际函数和逻辑编程研讨会。