TY - GEN
T1 - Purely functional lazy non-deterministic programming
AU - Fischer, Sebastian
AU - Kiselyov, Oleg
AU - Shan, Chung Chieh
PY - 2009
Y1 - 2009
N2 - 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 nondeterminism 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. Copyrightc 2009 ACM.
AB - 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 nondeterminism 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. Copyrightc 2009 ACM.
KW - Call-time choice
KW - Continuations
KW - Monads
KW - Side effects
UR - http://www.scopus.com/inward/record.url?scp=70450173859&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70450173859&partnerID=8YFLogxK
U2 - 10.1145/1596550.1596556
DO - 10.1145/1596550.1596556
M3 - Conference contribution
AN - SCOPUS:70450173859
SN - 9781605583327
T3 - Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP
SP - 11
EP - 22
BT - ICFP'09 - Proceedings of the 2009 ACM SIGPLAN International Conference on Functional Programming
T2 - 2009 ACM SIGPLAN International Conference on Functional Programming, ICFP'09
Y2 - 31 August 2009 through 2 September 2009
ER -