Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-01-12T05:38:39.375Z Has data issue: false hasContentIssue false
  • English
  • Français

Purely functional lazy nondeterministic programming

Part of: JFP Research Articles

Published online by Cambridge University Press:  16 August 2011

SEBASTIAN FISCHER ,
OLEG KISELYOV  and
CHUNG-CHIEH SHAN
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Functional logic programming and probabilistic programming have demonstrated the broad benefits of combining laziness (nonstrict evaluation with sharing of the results) with nondeterminism. Yet these benefits are seldom enjoyed in functional programming because the existing features for nonstrictness, sharing, and nondeterminism in functional languages are tricky to combine. We present a practical way to write purely functional lazy nondeterministic 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 nondeterministic components, by working with custom monadic data types and search strategies, and by providing equational laws for the programmer to reason about their code.

Type
Articles
Information
Journal of Functional Programming , Volume 21 , Special Issue 4-5: Dedicated to ICFP 2009 , September 2011 , pp. 413 - 465
Copyright
Copyright © Cambridge University Press 2011

References

Acosta-Gómez, A. (2007) Hardware Synthesis in ForSyDe. Master's thesis, Stockholm, Sweden: Department of Microelectronics and Information Technology, Royal Institute of Technology.Google Scholar
Albert, E., Hanus, M., Huch, F., Oliver, J. & Vidal, G. (2005) Operational semantics for declarative multi-paradigm languages. J. Symb. Comput. 40 (1), 795–829.Google Scholar
Antoy, S. & Hanus, M. (2002) Functional logic design patterns. In Proceedings of Symposium on Functional and Logic Programming (FLOPS), pp. 67–87.Google Scholar
Antoy, S. & Hanus, M. (2006) Overlapping rules and logic variables in functional logic programs. In Proceedings of International Conference on Logic Programming, pp. 87–101.Google Scholar
Ariola, Z. M. & Felleisen, M. (1997) The call-by-need lambda calculus. J. Funct. Program. 7 (3), 265–301.CrossRefGoogle Scholar
Ariola, Z. M., Felleisen, M., Maraist, J., Odersky, M. & Wadler, P. (1995) The call-by-need lambda calculus. In Proceedings of Symposium on Principles of Programming Languages (POPL), pp. 233–246.Google Scholar
Bird, R., Jones, G. & de Moor, O. (1997) More haste, less speed: Lazy versus eager evaluation. J. Funct. Program. 7 (5), 541–547.Google Scholar
Bjesse, P., Claessen, K., Sheeran, M. & Singh, S. (1998) Lava: Hardware design in Haskell. In Proceedings of International Conference on Functional Programming (ICFP), pp. 174–184.CrossRefGoogle Scholar
Braßel, B. & Huch, F. (2007) On a tighter integration of functional and logic programming. In Proceedings of Asian Symposium on Programming Languages and Systems (APLAS), Shao, Z. (ed), LNCS, vol. 4807, Berlin: Springer, pp. 122–138.Google Scholar
Braßl, B. & Huch, F. (2009) The Kiel Curry System KiCS. In Proceedings of Workshop on Logic Programming (WLP), 195–205.Google Scholar
Christiansen, J. & Fischer, S. (2008) EasyCheck—Test data for free. In Proceedings of Symposium on Functional and Logic Programming (FLOPS), pp. 322–336.Google Scholar
Claessen, K. (2004) Parallel parsing processes. J. Funct. Program. 14 (6), 741–757.Google Scholar
Claessen, K. & Hughes, J. (2000). QuickCheck: A lightweight tool for random testing of Haskell programs. In Proceedings of International Conference on Functional Programming (ICFP), pp. 268–279.Google Scholar
Escardó, M. H. (2007) Infinite sets that admit fast exhaustive search. In Proceedings of IEEE Symposium on Logic in Computer Science (LICS), pp. 443–452.Google Scholar
Felleisen, M. (1985) Transliterating Prolog into Scheme. Technical Report 182. Computer Science Department, Indiana University.Google Scholar
Filinski, A. (1999) Representing layered monads. In Proceedings of Symposium on Principles of Programming Languages (POPL), pp. 175–188.Google Scholar
Fischer, S. & Kuchen, H. (2007) Systematic generation of glass-box test cases for functional logic programs. In Proceedings of Principles and Practice of Declarative Programming (PPDP), pp. 63–74.Google Scholar
Garcia, R., Lumsdaine, A. & Sabry, A. (2009) Lazy evaluation & delimited control. In Proceedings of Symposium on Principles of Programming Languages (POPL), pp. 153–164.Google Scholar
González-Moreno, J. C., Hortalá-González, M. T., López-Fraguas, F. J. & Rodríguez-Artalejo, M. (1999) An approach to declarative programming based on a rewriting logic. J. Log. Program. 40 (1), 47–87.Google Scholar
Goodman, N., Mansinghka, V. K., Roy, D., Bonawitz, K. & Tenenbaum, J. B. (2008). Church: A language for generative models. In Proceedings of Conference on Uncertainty in Artificial Intelligence, pp. 220–229.Google Scholar
Haynes, C. T. (1987) Logic continuations. J. Log. Prog. 4 (2), 157–176.Google Scholar
Hinze, R. (2000) Deriving backtracking monad transformers (functional pearl). In Proceedings of International Conference on Functional Programming (ICFP), pp. 186–197.Google Scholar
Hudak, P. (1996) Building domain-specific embedded languages. ACM Comput. Surv. 28 (4es): 196.Google Scholar
Hughes, J. (1989) Why functional programming matters. Comput. J. 32 (2), 98–107.Google Scholar
Kiselyov, O. & Shan, C. (2009) Embedded probabilistic programming. In Proceedings of the Working Conference on Domain-Specific Languages, pp. 360–384.Google Scholar
Kiselyov, O., Shan, C., Friedman, D. P. & Sabry, A. (2005) Backtracking, interleaving, and terminating monad transformers (functional pearl). In Proceedings of International Conference on Functional Programming (ICFP), pp. 192–203.Google Scholar
Kitchin, D., Quark, A., Cook, W. R. & Misra, J. (2009) The Orc programming language. In Proceedings of FMOODS 2009 and FORTE 2009 (Formal Techniques for Distributed Systems), Lee, D., Lopes, A. & Poetzsch-Heffter, A. (eds), LNCS 5522. Berlin: Springer, pp. 1–25.Google Scholar
Koller, D., McAllester, D. & Pfeffer, A. (1997) Effective Bayesian inference for stochastic programs. In Proceedings of National Conference on Artificial Intelligence (AAAI), pp. 740–747.Google Scholar
Launchbury, J. (1993) A natural semantics for lazy evaluation. In Proceedings of Symposium on Principles of Programming Languages (POPL), pp. 144–154.CrossRefGoogle Scholar
Launchbury, J. & Elliott, T. (2010) Concurrent orchestration in Haskell. In Haskell Symposium, Gibbons, J. (ed). ACM Press, pp. 79–90.Google Scholar
Launchbury, J. & Peyton Jones, S. L. (1994) Lazy functional state threads. In Proceedings of Conference on Programming Language Design and Implementation (PLDI). ACM Press, pp. 24–35.Google Scholar
López-Fraguas, F. J., Rodríguez-Hortalá, J. & Sánchez-Hernández, J. (2007) A simple rewrite notion for call-time choice semantics. In Proceedings of Principles and Practice of Declarative Programming (PPDP), pp. 197–208.Google Scholar
López-Fraguas, F. J., Rodríguez-Hortalá, J. & Sánchez-Hernández, J. (2008) Rewriting and call-time choice: The HO case. In Proceedings of Symposium on Functional and Logic Programming (FLOPS), pp. 147–162.Google Scholar
Maraist, J., Odersky, M. & Wadler, P. (1998) The call-by-need lambda calculus. J. Funct. Program. 8 (3), 275–317.Google Scholar
McCarthy, J. (1963) A basis for a mathematical theory of computation. In Proceedings of Computer Programming and Formal Systems. North-Holland, pp. 33–70.CrossRefGoogle Scholar
Michie, D. (1968) “Memo” functions and machine learning. Nature 218, 19–22.CrossRefGoogle Scholar
Moggi, E. (1989) Computational lambda-calculus and monads. In Proceedings of Logic in Computer Science (LICS). Piscataway, NJ, USA: IEEE Press, pp. 14–23.Google Scholar
MonadPlus. (2008) MonadPlus. http://www.haskell.org/haskellwiki/MonadPlus.Google Scholar
Morrisett, J. G. (1993) Refining first-class stores. In Proceedings of the Workshop on State in Programming Languages, pp. 73–87.Google Scholar
Naylor, M., Axelsson, E. & Runciman, C. (2007) A functional-logic library for Wired. In Proceedings of Haskell Workshop, pp. 37–48.Google Scholar
Nicollet, V., Minsky, Y. & Leroy, X. (2009) Lazy and threads. http://caml.inria.fr/pub/ml-archives/caml-list/2009/02/9fc4e4a897ce7a356674660c8cfa5ac0.fr.html.Google Scholar
Peyton Jones, S. L., Reid, A., Hoare, T., Marlow, S. & Henderson, F. (1999) A semantics for imprecise exceptions. In Proceedings of Conference on Programming Language Design and Implementation (PLDI). ACM Press, pp. 25–36.Google Scholar
Rabin, M. O. & Scott, D. (1959) Finite automata and their decision problems. IBM J. Res. Dev. 3, 114–125.Google Scholar
Runciman, C., Naylor, M. & Lindblad, F. (2008) SmallCheck and Lazy SmallCheck: Automatic exhaustive testing for small values. In Proceedings of Haskell Symposium, pp. 37–48.Google Scholar
Seaman, J. M. (1993) An Operational Semantics of Lazy Evaluation for Analysis. PhD. thesis. Pennsylvania State University.Google Scholar
Spivey, J. M. (2000) Combinators for breadth-first search. J. Funct. Program. 10 (4), 397–408.Google Scholar
Tolmach, A. & Antoy, S. (2003) A monadic semantics for core Curry. In Proceedings of Workshop on Functional and Logic Programming (WFLP), Valencia, Spain, pp. 33–46.Google Scholar
Tolmach, A., Antoy, S. & Nita, M. (2004) Implementing functional logic languages using multiple threads and stores. In Proceedings of International Conference on Functional Programming (ICFP), pp. 90–102.Google Scholar
de Vries, E. (2009) Just how unsafe is unsafe. http://www.haskell.org/pipermail/haskell-cafe/2009-February/055201.html.Google Scholar
Wadler, P. 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 Proceedings of Functional Programming Languages and Computer Architecture, pp. 113–128.Google Scholar
Wadler, P. L. (1992) The essence of functional programming. In Proceedings of Symposium on Principles of Programming Languages (POPL). ACM Press, pp. 1–14.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.