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


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)