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

[010496] sergio antoy波特兰州立大学itr /SY：功能逻辑程序的非确定性计算摘要：窄化允许功能和逻辑计算的无缝集成。缩窄策略从表达式中选择子表达式，以便在必要时计算和实例化变量。不同的选择策略从函数逻辑编程扩展到函数逻辑编程计算行为，如按值调用和按需要调用。健全、完整和最优（在不同程度上）的策略对于类似haskell的程序和允许某种形式并行的程序都是众所周知的。不幸的是，这类程序不支持非确定性计算。不确定性的缺乏是函数逻辑语言的一个严重限制。它阻止使用熟悉的逻辑编程习惯，并且在某些情况下，导致程序违背了问题固有的惰性。该研究提出了一个新的计算框架、一类程序和一种策略，以缩小该类中支持非确定性而不损失可靠性、完整性或效率的计算。在这个框架中，程序在文本上变得更短，概念上更简单，更模块化，更容易理解和维护，并且可以说更高效。所提出的策略有可能包含其他有趣的功能逻辑程序类的策略，并且有望统一各种并发的不一致的努力，旨在将不同的缩小策略集成到单一语言中。

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.