ITR/SY: Non-Deterministic Computations for Functional Logic Programs

ITR/SY：功能逻辑程序的非确定性计算

• 批准号: 0110496
• 负责人: Sergio Antoy
• 金额: $ 18.6万
• 依托单位: Portland State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-15 至 2005-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0110496&HistoricalAwards=false
• 关键词: ITR; SY; Non; Deterministic; Computations

0110496Sergio AntoyPortland State UniversityITR/SY: Non-Deterministic Computations for Functional Logic Programs Abstract: Narrowing allows the seamless integration of functional and logic computations. A narrowing strategy selects from an expression the subexpression(s) to evaluate and instantiates variables if necessary. Different selection strategies extend from functional to functional logic programming computational behaviors such as call-by-value and call-by-need. Sound, complete, and optimal (to varying degrees) strategies are known for both Haskell-like programs and programs that allow some forms of parallelism. Unfortunately, these classes of programs do not support non-deterministic computations. The lack of non-determinism is a severe limitation in functional logic languages. It prevents the use of familiar logic programming idioms and, in some cases, leads to programs that violate the inherent laziness of a problem. The research proposes a new computational framework, a class of programs, and a strategy for narrowing computations in this class that supports non-determinism without loss of soundness, completeness or efficiency. Within this framework, programs become textually shorter, conceptually simpler, more modular, easier to understand and maintain, and arguably more efficient. The proposed strategy has the potential to encompass strategies for other interesting classes of functional logic programs and it is expected to unify various concurrent disjoint efforts aiming at integrating different narrowing strategies within a single language.

0110496 Sergio AntoyPortland State University ITR/SY：函数逻辑程序的非确定性计算 摘要： 缩小范围可实现功能和逻辑的无缝集成 计算。收缩策略从表达式中选择 子表达式来计算和实例化变量，如果 必要不同的选择策略从功能上扩展到 到函数逻辑编程计算行为， 按价值呼叫和按需要呼叫。健全、完整和最佳（以 不同程度）的策略都是已知的Haskell类 程序和允许某种形式并行的程序。 不幸的是，这些类的程序不支持 非确定性计算缺乏非决定论是一个 函数逻辑语言的严重局限性。它防止 使用熟悉的逻辑编程习惯，在某些情况下， 到违反问题固有惰性的程序。的 研究提出了一种新的计算框架，一类 程序，以及在该类中缩小计算范围的策略 支持非决定论而又不失其合理性， 完整性或效率。在这个框架内，方案成为 文本更短，概念更简单，更模块化，更容易 理解和维护，而且可以说更高效。 拟议的战略有可能包括 对于其他有趣的函数逻辑程序类， 预计将统一各种并行的不一致的努力， 将不同的缩小范围策略集成到一个 语言