Abstract
Two general techniques for implementing a domain-specific language (DSL) with less overhead are the finally-tagless embedding of object programs and the direct-style representation of side effects. We use these techniques to build a DSL for probabilistic programming, for expressing countable probabilistic models and performing exact inference and importance sampling on them. Our language is embedded as an ordinary OCaml library and represents probability distributions as ordinary OCaml programs. We use delimited continuations to reify probabilistic programs as lazy search trees, which inference algorithms may traverse without imposing any interpretive overhead on deterministic parts of a model. We thus take advantage of the existing OCaml implementation to achieve competitive performance and ease of use. Inference algorithms can easily be embedded in probabilistic programs themselves.
Thanks to Olivier Danvy, Avi Pfeffer, and the anonymous reviewers. Thanks also to Aarhus University for hosting the second author in the fall of 2008.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Carette, J., Kiselyov, O., Shan, C.-c.: Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. Journal of Functional Programming (2008) (in press)
Cussens, J.: Logic-based formalisms for statistical relational learning. In: [18], ch. 9, pp. 269–290 (2007)
Danvy, O., Filinski, A.: A functional abstraction of typed contexts. Tech. Rep. 89/12, DIKU, University of Copenhagen, Denmark (1989), http://www.daimi.au.dk/~danvy/Papers/fatc.ps.gz
Danvy, O., Filinski, A.: Abstracting control. In: Proceedings of the 1990 ACM conference on Lisp and functional programming, pp. 151–160. ACM Press, New York (1990)
Daumé III, H.: Hierarchical Bayes compiler (2007), http://www.cs.utah.edu/~hal/HBC/
Dechter, R.: Bucket elimination: A unifying framework for probabilistic inference. In: Jordan, M.I. (ed.) Learning and inference in graphical models. Kluwer, Dordrecht (1998); Paperback: Learning in Graphical Models. MIT Press
Domingos, P., Richardson, M.: Markov logic: A unifying framework for statistical relational learning. In: [18], ch. 12, pp. 339–371 (2007)
Erwig, M., Kollmansberger, S.: Probabilistic functional programming in Haskell. Journal of Functional Programming 16(1), 21–34 (2006)
Feigin, B., Mycroft, A.: Jones optimality and hardware virtualization: A report on work in progress. In: Glück, R., de Moor, O. (eds.) Proceedings of the 2008 ACM SIGPLAN symposium on partial evaluation and semantics-based program manipulation, pp. 169–175. ACM Press, New York (2008)
Felleisen, M., Friedman, D.P., Duba, B.F., Merrill, J.: Beyond continuations. Tech. Rep. 216, Computer Science Department, Indiana University (1987)
Filinski, A.: Representing monads. In: POPL 1994: Conference record of the annual ACM symposium on principles of programming languages, pp. 446–457. ACM Press, New York (1994)
Filinski, A.: Representing layered monads. In: POPL 1999: Conference record of the annual ACM symposium on principles of programming languages, pp. 175–188. ACM Press, New York (1999)
Fischer, B., Schumann, J.: AutoBayes: A system for generating data analysis programs from statistical models. Journal of Functional Programming 13(3), 483–508 (2003)
Forbes, J., Huang, T., Kanazawa, K., Russell, S.J.: The BATmobile: Towards a Bayesian automated taxi. In: Proceedings of the 14th international joint conference on artificial intelligence, pp. 1878–1885. Morgan Kaufmann, San Francisco (1995)
Fung, R., Chang, K.-C.: Weighing and integrating evidence for stochastic simulation in Bayesian networks. In: Henrion, M., Shachter, R.D., Kanal, L.N., Lemmer, J.F. (eds.) Proceedings of the 5th conference on uncertainty in artificial intelligence (1989), pp. 209–220. North-Holland, Amsterdam (1990)
Getoor, L., Friedman, N., Koller, D., Pfeffer, A.: Learning probabilistic relational models. In: Džeroski, S., Lavrač, N. (eds.) Relational data mining, ch. 13, pp. 307–335. Springer, Berlin (2001)
Getoor, L., Friedman, N., Koller, D., Pfeffer, A., Taskar, B.: Probabilistic relational models. In: [18], ch. 5, pp. 129–174 (2007)
Getoor, L., Taskar, B. (eds.): Introduction to statistical relational learning. MIT Press, Cambridge (2007)
Giry, M.: A categorical approach to probability theory. In: Banaschewski, B. (ed.) Categorical aspects of topology and analysis: Proceedings of an international conference held at Carleton University, Ottawa. Lecture Notes in Mathematics, vol. 915, pp. 68–85. Springer, Berlin (1982)
Goodman, N.D., Mansinghka, V.K., Roy, D., Bonawitz, K., Tenenbaum, J.B.: Church: A language for generative models. In: McAllester, D.A., Myllymäki, P. (eds.) 2008: Proceedings of the 24th conference in uncertainty in artificial intelligence, pp. 220–229. AUAI Press (2008)
Gunter, C.A., Rémy, D., Riecke, J.G.: A generalization of exceptions and control in ML-like languages. In: Peyton Jones, S.L. (ed.) Functional programming languages and computer architecture: 7th conference, pp. 12–23. ACM Press, NewYork (1995)
Halpern, J.Y.: An analysis of first-order logics of probability. Artificial Intelligence 46, 311–350 (1990)
Haynes, C.T.: Logic continuations. Journal of Logic Programming 4(2), 157–176 (1987)
Hinze, R.: Deriving backtracking monad transformers. In: ICFP 2000: Proceedings of the ACM international conference on functional programming. ACM SIGPLAN Notices, vol. 35(9), pp. 186–197. ACM Press, New York (2000)
Hudak, P.: Building domain-specific embedded languages. ACM Computing Surveys 28(4es), 196 (1996)
Hughes, J.: The design of a pretty-printing library. In: Jeuring, J., Meijer, E. (eds.) AFP 1995. LNCS, vol. 925, pp. 53–96. Springer, Heidelberg (1995)
Jaeger, M., Lidman, P., Mateo, J.L.: Comparative evaluation of probabilistic logic languages and systems: A work-in-progress report. In: Proceedings of mining and learning with graphs (2007), http://www.cs.aau.dk/~jaeger/plsystems/
Kersting, K., De Raedt, L.: Bayesian logic programming: Theory and tool. In: [18], ch. 10, pp. 291–321 (2007)
Kiselyov, O.: Native delimited continuations in (byte-code) OCaml (2006), http://okmij.org/ftp/Computation/Continuations.html#caml-shift
Koller, D., McAllester, D.A., Pfeffer, A.: Effective Bayesian inference for stochastic programs. In: AAAI 1997: Proceedings of the 14th national conference on artificial intelligence. The American Association for Artificial Intelligence, pp. 740–747. AAAI Press, Menlo Park (1997)
Landin, P.J.: The next 700 programming languages. Communications of the ACM 9(3), 157–166 (1966)
Milch, B., Marthi, B., Russell, S., Sontag, D., Ong, D.L., Kolobov, A.: BLOG: Probabilistic models with unknown objects. In: [18], ch. 13, pp. 373–398 (2007)
Mogensen, Æ.T.: Self-applicable online partial evaluation of the pure lambda calculus. In: Proceedings of the 1995 ACM SIGPLAN symposium on partial evaluation and semantics-based program manipulation, pp. 39–44. ACM Press, New York (1995)
Muggleton, S., Pahlavi, N.: Stochastic logic programs: A tutorial. In: [18], ch. 11, pp. 323–338 (2007)
Murphy, K.: Bayes Net Toolbox for Matlab (2007), http://www.cs.ubc.ca/~murphyk/Software/BNT/bnt.html
Murphy, K.: Software for graphical models: A review. International Society for Bayesian Analysis Bulletin 14(4), 13–15 (2007)
Pearl, J.: Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan Kaufmann, San Francisco (1988) (Revised 2nd printing, 1998)
Pfeffer, A.: The design and implementation of IBAL: A general-purpose probabilistic language. In: [18], ch. 14, pp. 399–432 (2007)
Pfeffer, A.: A general importance sampling algorithm for probabilistic programs. Tech. Rep. TR-12-07, Harvard University (2007)
Phillips, A., Cardelli, L.: Efficient, correct simulation of biological processes in the stochastic pi-calculus. In: Calder, M., Gilmore, S. (eds.) CMSB 2007. LNCS (LNBI), vol. 4695, pp. 184–199. Springer, Heidelberg (2007)
Poole, D., Mackworth, A.: Artificial intelligence: Foundations of computational agents. Cambridge University Press, Cambridge (2009)
Ramsey, N., Pfeffer, A.: Stochastic lambda calculus and monads of probability distributions. In: POPL 2002: Conference record of the annual ACM symposium on principles of programming languages, pp. 154–165. ACM Press, New York (2002)
Sato, T.: A glimpse of symbolic-statistical modeling by PRISM. Journal of Intelligent Information Systems 31(2), 161–176 (2008)
Shachter, R.D., Peot, M.A.: Simulation approaches to general probabilistic inference on belief networks. In: Henrion, M., Shachter, R.D., Kanal, L.N., Lemmer, J.F. (eds.) Proceedings of the 5th conference on uncertainty in artificial intelligence (1989), pp. 221–234. North-Holland, Amsterdam (1990)
Sutton, C., McCallum, A.: An introduction to conditional random fields for relational learning. In: [18], ch. 4, pp. 93–127 (2007)
Taskar, B., Abbeel, P., Wong, M.-F., Koller, D.: Relational Markov networks. In: [18], ch. 6, pp. 175–199 (2007)
Thiemann, P.: Combinators for program generation. Journal of Functional Programming 9(5), 483–525 (1999)
Wadler, P.L.: The essence of functional programming. In: POPL 1992: Conference record of the annual ACM symposium on principles of programming languages, pp. 1–14. ACM Press, New York (1992)
Wand, M., Vaillancourt, D.: Relating models of backtracking. In: ICFP 2004: Proceedings of the ACM international conference on functional programming. ACM Press, New York (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 IFIP International Federation for Information Processing
About this paper
Cite this paper
Kiselyov, O., Shan, Cc. (2009). Embedded Probabilistic Programming. In: Taha, W.M. (eds) Domain-Specific Languages. DSL 2009. Lecture Notes in Computer Science, vol 5658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03034-5_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-03034-5_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03033-8
Online ISBN: 978-3-642-03034-5
eBook Packages: Computer ScienceComputer Science (R0)