Purely functional lazy non-deterministic programming
Purely functional lazy non-deterministic programming
复制标题
纯函数式惰性非确定性编程
DOI：
10.1145/1596550.1596556
复制
发表时间：
2009
影响因子：
1.1
通讯作者：
Chung
中科院分区：
文献类型：
--
作者：
Sebastian Fischer;O. Kiselyov;Chung
函数逻辑编程和概率编程已经证明了将惰性（非严格求值与共享结果）与非确定性相结合的广泛好处。然而，在函数式编程中很少能享受到这些好处，因为函数式语言中现有的非严格性、共享性和非确定性特性很难结合起来。
Functional logic programming and probabilistic programming have demonstrated the broad benefits of combining laziness (non-strict evaluation with sharing of the results) with non-determinism. Yet these benefits are seldom enjoyed in functional programming, because the existing features for non-strictness, sharing, and non-determinism in functional languages are tricky to combine.
We present a practical way to write purely functional lazy non-deterministic programs that are efficient and perspicuous. We achieve this goal by embedding the programs into existing languages (such as Haskell, SML, and OCaml) with high-quality implementations, by making choices lazily and representing data with non-deterministic components, by working with custom monadic data types and search strategies, and by providing equational laws for the programmer to reason about their code.