 |
Purely Functional Lazy Non-deterministic Programming
Sebastian Fischer, Oleg Kiselyov and Chung-chieh Shan
The 14th ACM SIGPLAN International Conference on Functional Programming (ICFP 2009)Edinburgh, Scotland, 31st August - 2nd September 2009
Abstract
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 not straightforward to combine harmoniously.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 data types and monads embodying search strategies, and by providing equational laws for the programmer to reason about their code.
START Conference Manager (V2.56.8 - Rev. 748M)