Purely functional lazy non-deterministic programming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Purely functional lazy non-deterministic programming

Full text

Pdf (433 KB)

Source

International Conference on Functional Programming archive
Proceedings of the 14th ACM SIGPLAN international conference on Functional programming table of contents

Edinburgh, Scotland

SESSION: Session 1 table of contents

Pages 11-22

Year of Publication: 2009

ISBN:978-1-60558-332-7

Also published in ...

Authors

Sebastian Fischer	Christian-Albrechts University, Kiel, Germany
Oleg Kiselyov	FNMOC, Monterey, CA, USA
Chung-chieh Shan	Rutgers University, Piscataway, NJ, USA

Sponsors

ACM: Association for Computing Machinery
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 40, Downloads (12 Months): 207, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1596550.1596556 What is a DOI?

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 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Acosta-Gómez, Alfonso. 2007. Hardware synthesis in ForSyDe. Master's thesis, Dept. of Microelectronics and Information Technology, Royal Institute of Technology, Stockholm, Sweden.
	2	Albert, Elvira, Michael Hanus, Frank Huch, Javier Oliver, and German Vidal. 2005. Operational semantics for declarative multi-paradigm languages. Journal of Symbolic Computation 40(1):795--829.
	3	Antoy, Sergio, and Michael Hanus. 2002. Functional logic design patterns. In FLOPS, 67--87.
	4	Antoy, Sergio, and Michael Hanus. 2006. Overlapping rules and logic variables in functional logic programs. In ICLP, 87--101.
	5	Ariola, Zena M., and Matthias Felleisen. 1997. The call-by-need lambda calculus. JFP 7(3):265--301.
	6	Ariola, Zena M., Matthias Felleisen, John Maraist, Martin Odersky, and Philip Wadler. 1995. The call-by-need lambda calculus. In POPL, 233--246.
	7	Bird, Richard, Geraint Jones, and Oege de Moor. 1997. More haste, less speed: Lazy versus eager evaluation. JFP 7(5):541--547.
	8	Bjesse, Per, Koen Claessen, Mary Sheeran, and Satnam Singh. 1998. Lava: Hardware design in Haskell. In ICFP, 174--184.
	9	Braßel, Bernd, and Frank Huch. 2009. The Kiel Curry System KiCS. In WLP 2007, 195--205.
	10	Christiansen, Jan, and Sebastian Fischer. 2008. EasyCheck - test data for free. In FLOPS, 322--336.
	11	Claessen, Koen, and John Hughes. 2000. QuickCheck: A lightweight tool for random testing of Haskell programs. In ICFP, 268--279.
	12	Escardó, Mart´1n H. 2007. Infinite sets that admit fast exhaustive search. In LICS, 443--452.
	13	Felleisen, Matthias. 1985. Transliterating Prolog into Scheme. Tech. Rep. 182, Computer Science Dept., Indiana University.
	14	Filinski, Andrzej. 1999. Representing layered monads. In POPL, 175--188.
	15	Fischer, Sebastian, and Herbert Kuchen. 2007. Systematic generation of glass-box test cases for functional logic programs. In PPDP, 63--74.
	16	Garcia, Ronald, Andrew Lumsdaine, and Amr Sabry. 2009. Lazy evaluation and delimited control. In POPL, 153--164.
	17	González-Moreno, Juan Carlos, Maria Teresa Hortalá-González, Francisco Javier López-Fraguas, and Mario Rodr´1guez-Artalejo. 1999. An approach to declarative programming based on a rewriting logic. Journal of Logic Programming 40(1):47--87.
	18	Goodman, Noah, Vikash K. Mansinghka, Daniel Roy, Keith Bonawitz, and Joshua B. Tenenbaum. 2008. Church: A language for generative models. In UAI, 220--229.
	19	Haynes, Christopher T. 1987. Logic continuations. Journal of Logic Programming 4(2):157--176.
	20	Hinze, Ralf. 2000. Deriving backtracking monad transformers (functional pearl). In ICFP, 186--197.
	21	Hudak, Paul. 1996. Building domain-specific embedded languages. ACM Computing Surveys 28(4es):196.
	22	Hughes, John. 1989. Why functional programming matters. The Computer Journal 32(2):98--107.
	23	Kiselyov, Oleg, and Chung-chieh Shan. 2009. Embedded probabilistic programming. In Working conf. on domain specific lang.
	24	Kiselyov, Oleg, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry. 2005. Backtracking, interleaving, and terminating monad transformers (functional pearl). In ICFP, 192--203.
	25	Koller, Daphne, David McAllester, and Avi Pfeffer. 1997. Effective Bayesian inference for stochastic programs. In AAAI, 740--747.
	26	Lämmel, Ralf, and Simon L. Peyton Jones. 2003. Scrap your boilerplate: A practical design pattern for generic programming. In TLDI, 26--37.
	27	Launchbury, John. 1993. A natural semantics for lazy evaluation. In POPL, 144--154.
	28	Lin, Chuan-kai. 2006. Programming monads operationally with Unimo. In ICFP, 274--285.
	29	López-Fraguas, Francisco Javier, Juan Rodríguez-Hortalá, and Jaime Sánchez-Hernández. 2007. A simple rewrite notion for call-time choice semantics. In PPDP, 197--208.
	30	López-Fraguas, Francisco Javier, Juan Rodríguez-Hortalá, and Jaime Sánchez-Hernández. 2008. Rewriting and call-time choice: The HO case. In FLOPS, 147--162.
	31	Maraist, John, Martin Odersky, and Philip Wadler. 1998. The call-by-need lambda calculus. JFP 8(3):275--317.
	32	McCarthy, John. 1963. A basis for a mathematical theory of computation. In Computer programming and formal systems, 33--70. North-Holland.
	33	Michie, Donald. 1968. "Memo" functions and machine learning. Nature 218:19--22.
	34	MonadPlus. 2008. MonadPlus. http://www.haskell.org/haskellwiki/MonadPlus.
	35	Morrisett, J. Gregory. 1993. Refining first-class stores. In Proceedings of the workshop on state in programming languages.
	36	Naylor, Matthew, Emil Axelsson, and Colin Runciman. 2007. A functional-logic library for Wired. In Haskell workshop, 37--48.
	37	Nicollet, Victor, et al. 2009. Lazy and threads. http://caml.inria.fr/pub/ml-archives/caml-list/2009/02/9fc4e4a897ce7a356674660c8cfa5ac0.fr.html.
	38	Nordin, Thomas, and Andrew Tolmach. 2001. Modular lazy search for constraint satisfaction problems. JFP 11(5):557--587.
	39	Rabin, Michael O., and Dana Scott. 1959. Finite automata and their decision problems. IBM Journal of Research and Development 3:114--125.
	40	Runciman, Colin, Matthew Naylor, and Fredrik Lindblad. 2008.
	41	SmallCheck and Lazy SmallCheck: Automatic exhaustive testing for small values. In Haskell symposium, 37--48.
	42	Seaman, Jill M. 1993. An operational semantics of lazy evaluation for analysis. Ph.D. thesis, Pennsylvania State University.
	43	Spivey, J. Michael. 2000. Combinators for breadth-first search. JFP 10(4):397--408.
	44	Tolmach, Andrew, and Sergio Antoy. 2003. A monadic semantics for core Curry. In WFLP, 33--46. Valencia, Spain.
	45	Tolmach, Andrew, Sergio Antoy, and Marius Nita. 2004. Implementing functional logic languages using multiple threads and stores. In ICFP, 90--102.
	46	de Vries, Edsko. 2009. Just how unsafe is unsafe. http://www.haskell.org/pipermail/haskell-cafe/2009-February/055201.html.
	47	Wadler, Philip L. 1985. How to replace failure by a list of successes: A method for exception handling, backtracking, and pattern matching in lazy functional languages. In FPCA, 113--128.