More Web Proxy on the site http://driver.im/

research-article

Open access

A probabilistic language based on sampling functions

Authors:

Frank Pfenning,

Sebastian ThrunAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 31, Issue 1

Article No.: 4, Pages 1 - 46

https://doi.org/10.1145/1452044.1452048

Published: 12 December 2008 Publication History

Abstract

As probabilistic computations play an increasing role in solving various problems, researchers have designed probabilistic languages which treat probability distributions as primitive datatypes. Most probabilistic languages, however, focus only on discrete distributions and have limited expressive power. This article presents a probabilistic language, called λ_○, whose expressive power is beyond discrete distributions. Rich expressiveness of λ_○ is due to its use of sampling functions, that is, mappings from the unit interval (0.0,1.0] to probability domains, in specifying probability distributions. As such, λ_○ enables programmers to formally express and reason about sampling methods developed in simulation theory. The use of λ_○ is demonstrated with three applications in robotics: robot localization, people tracking, and robotic mapping. All experiments have been carried out with real robots.

References

[1]

Bratley, P., Fox, B., and Schrage, L. 1996. A Guide to Simulation 2nd Ed. Springer-Verlag.

Digital Library

[2]

Charniak, E. 1993. Statistical Language Learning. MIT Press, Cambridge, MA.

Digital Library

[3]

Devroye, L. 1986. Non-Uniform Random Variate Generation. Springer-Verlag.

[4]

Doucet, A., de Freitas, N., and Gordon, N. 2001. Sequential Monte Carlo Methods in Practice. Springer-Verlag.

[5]

Fox, D., Burgard, W., and Thrun, S. 1999. Markov localization for mobile robots in dynamic environments. J. A.I. Rese. 11, 391--427.

Digital Library

[6]

Gill, J. 1977. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6, 4, 675--695.

Digital Library

[7]

Giry, M. 1981. A categorical approach to probability theory. In Categorical Aspects of Topology and Analysis, B. Banaschewski, Ed. Lecture Notes In Mathematics, vol. 915. Springer-Verlag, 68--85.

[8]

Gupta, V., Jagadeesan, R., and Panangaden, P. 1999. Stochastic processes as concurrent constraint programs. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 189--202.

Digital Library

[9]

Henrion, M. 1988. Propagation of uncertainty in Bayesian networks by probabilistic logic sampling. In Uncertainty in Artificial Intelligence 2, J. F. Lemmer and L. N. Kanal, Eds. Elsevier/North-Holland, 149--163.

[10]

Isard, M. and Blake, A. 1998. CONDENSATION: Conditional density propagation for visual tracking. Int. J. Comput. Vision 29, 1, 5--28.

Digital Library

[11]

Jazwinski, A. H. 1970. Stochastic Processes and Filtering Theory. Academic Press, New York, NY.

[12]

Jelinek, F. 1998. Statistical Methods for Speech Recognition (Language, Speech, and Communication). MIT Press, Cambridge, MA.

Digital Library

[13]

Jones, C. 1990. Probabilistic nondeterminism. Ph.D. thesis, Department of Computer Science, University of Edinburgh.

Digital Library

[14]

Koller, D., McAllester, D., and Pfeffer, A. 1997. Effective Bayesian inference for stochastic programs. In Proceedings of the 14th National Conference on Artificial Intelligence and 9th Innovative Applications of Artificial Intelligence Conference. AAAI Press, 740--747.

Digital Library

[15]

Kozen, D. 1981. Semantics of probabilistic programs. J. Comput. Syst. Sci. 22, 3, 328--350.

[16]

Launchbury, J. and Peyton Jones, S. L. 1995. State in Haskell. Lisp Symbol. Comput. 8, 4, 293--341.

Digital Library

[17]

Leroy, X. 2000. A modular module system. J. Funct. Program. 10, 3, 269--303.

Digital Library

[18]

MacKay, D. J. C. 1998. Introduction to Monte Carlo methods. In Learning in Graphical Models, M. I. Jordan, Ed. NATO Science Series. Kluwer Academic Press, 175--204.

Digital Library

[19]

Martin-Löf, P. 1996. On the meanings of the logical constants and the justifications of the logical laws. Nordic J. Phil. Logic 1, 1, 11--60.

[20]

Mogensen, T. 2002. Roll: A language for specifying die-rolls. In Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, V. Dahl and P. Wadler, Eds. Lecture Notes in Computer Science, vol. 2562. Springer, 145--159.

Digital Library

[21]

Moggi, E. 1989. Computational lambda-calculus and monads. In Proceedings of the 4th Annual Symposium on Logic in Computer Science. IEEE Computer Society Press, 14--23.

Digital Library

[22]

Moggi, E. 1991. Notions of computation and monads. Inform. Comput. 93, 55--92.

Digital Library

[23]

Montemerlo, M. 2003. FastSLAM: A factored solution to the simultaneous localization and mapping problem with unknown data association. Ph.D. thesis, Robotics Institute, Carnegie Mellon University.

Digital Library

[24]

Montemerlo, M., Roy, N., and Thrun, S. CARMEN: Carnegie Mellon Robot Navigation Toolkit. http://www.cs.cmu.edu/~carmen/.

[25]

Montemerlo, M., Whittaker, W., and Thrun, S. 2002. Conditional particle filters for simultaneous mobile robot localization and people-tracking. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). 695--701.

[26]

Motwani, R. and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press, Cambridge, UK.

Digital Library

[27]

Park, S. 2003. A calculus for probabilistic languages. In Proceedings of the ACM SIGPLAN International Workshop on Types in Language Design and Implementation. ACM Press, 38--49.

Digital Library

[28]

Peyton Jones, S. L. 2001. Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. In Engineering Theories of Software Construction, C. A. R. Hoare, M. Broy, and R. Steinbrüggen, Eds. IOS Press, Amsterdam, The Netherlands.

[29]

Peyton Jones, S. L. and Wadler, P. 1993. Imperative functional programming. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 71--84.

Digital Library

[30]

Pfeffer, A. 2001. IBAL: A probabilistic rational programming language. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI'01), B. Nebel, Ed. Morgan Kaufmann Publishers, Inc., 733--740.

Digital Library

[31]

Pfenning, F. and Davies, R. 2001. A judgmental reconstruction of modal logic. Math. Struct. Comput. Sci. 11, 4, 511--540.

Digital Library

[32]

Pless, D. and Luger, G. 2001. Toward general analysis of recursive probability models. In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI'01), J. Breese and D. Koller, Eds. Morgan Kaufmann Publishers, 429--436.

Digital Library

[33]

Rabiner, L. R. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77, 2, 257--285.

[34]

Ramsey, N. and Pfeffer, A. 2002. Stochastic lambda calculus and monads of probability distributions. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 154--165.

Digital Library

[35]

Rudin, W. 1986. Real and Complex Analysis 3rd Ed. McGraw-Hill, New York, NY.

Digital Library

[36]

Russell, S. and Norvig, P. 1995. Artificial Intelligence: A Modern Approach. Prentice Hall.

Digital Library

[37]

Sabry, A. and Wadler, P. 1997. A reflection on call-by-value. ACM Trans. Program. Lang. Syst. 19, 6, 916--941.

Digital Library

[38]

Saheb-Djahromi, N. 1978. Probabilistic LCF. In Proceedings of the 7th Symposium on Mathematical Foundations of Computer Science, J. Winkowski, Ed. Lecture Notes in Computer Science, vol. 64. Springer, 442--451.

[39]

Thrun, S. 2000a. Probabilistic algorithms in robotics. AI Mag. 21, 4, 93--109.

[40]

Thrun, S. 2000b. Towards programming tools for robots that integrate probabilistic computation and learning. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).

[41]

Thrun, S. 2002. Robotic mapping: A survey. In Exploring Artificial Intelligence in the New Millenium, G. Lakemeyer and B. Nebel, Eds. Morgan Kaufmann.

Digital Library

[42]

Welch, G. and Bishop, G. 1995. An introduction to the Kalman filter. Tech. rep. TR95-041, Department of Computer Science, University of North Carolina—Chapel Hill.

Digital Library

Cited By

Goubault-Larrecq JJia XThéron C(2023)A Domain-theoretic Approach to Statistical Programming LanguagesJournal of the ACM10.1145/361166070:5(1-63)Online publication date: 11-Oct-2023
https://dl.acm.org/doi/10.1145/3611660
Westrick SArora JAcar U(2022)Entanglement detection with near-zero costProceedings of the ACM on Programming Languages10.1145/35476466:ICFP(679-710)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547646
Zhang YAmin N(2022)Reasoning about “reasoning about reasoning”: semantics and contextual equivalence for probabilistic programs with nested queries and recursionProceedings of the ACM on Programming Languages10.1145/34986776:POPL(1-28)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498677
Show More Cited By

Index Terms

A probabilistic language based on sampling functions
1. Software and its engineering
  1. Software notations and tools
    1. Context specific languages
      1. Specialized application languages

Recommendations

A probabilistic language based upon sampling functions
Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

As probabilistic computations play an increasing role in solving various problems, researchers have designed probabilistic languages that treat probability distributions as primitive datatypes. Most probabilistic languages, however, focus only on ...
A probabilistic language based upon sampling functions
POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

As probabilistic computations play an increasing role in solving various problems, researchers have designed probabilistic languages that treat probability distributions as primitive datatypes. Most probabilistic languages, however, focus only on ...
A calculus for probabilistic languages
TLDI '03: Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation

As probabilistic computation plays an increasing role in diverse fields in computer science, researchers have designed new languages to facilitate the development of probabilistic programs. In this paper, we develop a probabilistic calculus by extending ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 31, Issue 1

December 2008

261 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1452044

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 December 2008

Accepted: 01 April 2008

Received: 01 January 2008

Published in TOPLAS Volume 31, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
764
Total Downloads

Downloads (Last 12 months)99
Downloads (Last 6 weeks)18

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Goubault-Larrecq JJia XThéron C(2023)A Domain-theoretic Approach to Statistical Programming LanguagesJournal of the ACM10.1145/361166070:5(1-63)Online publication date: 11-Oct-2023
https://dl.acm.org/doi/10.1145/3611660
Westrick SArora JAcar U(2022)Entanglement detection with near-zero costProceedings of the ACM on Programming Languages10.1145/35476466:ICFP(679-710)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547646
Zhang YAmin N(2022)Reasoning about “reasoning about reasoning”: semantics and contextual equivalence for probabilistic programs with nested queries and recursionProceedings of the ACM on Programming Languages10.1145/34986776:POPL(1-28)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498677
Feldman YSagiv MShoham SWilcox J(2022)Property-directed reachability as abstract interpretation in the monotone theoryProceedings of the ACM on Programming Languages10.1145/34986766:POPL(1-31)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498676
Wang ZAlbarghouthi APrakriya GJha S(2022)Interval universal approximation for neural networksProceedings of the ACM on Programming Languages10.1145/34986756:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498675
Castagna GLaurent MNguyễn KLutze M(2022)On type-cases, union elimination, and occurrence typingProceedings of the ACM on Programming Languages10.1145/34986746:POPL(1-31)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498674
Arora JWestrick SAcar U(2021)Provably space-efficient parallel functional programmingProceedings of the ACM on Programming Languages10.1145/34342995:POPL(1-33)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434299
Lundén DBorgström JBroman D(2021)Correctness of Sequential Monte Carlo Inference for Probabilistic Programming LanguagesProgramming Languages and Systems10.1007/978-3-030-72019-3_15(404-431)Online publication date: 23-Mar-2021
https://doi.org/10.1007/978-3-030-72019-3_15
Szymczak MKatoen J(2020)Weakest Preexpectation Semantics for Bayesian InferenceEngineering Trustworthy Software Systems10.1007/978-3-030-55089-9_3(44-121)Online publication date: 1-Aug-2020
https://doi.org/10.1007/978-3-030-55089-9_3
Di Pierro A(2020)A Type Theory for Probabilistic $$\lambda $$–calculusFrom Lambda Calculus to Cybersecurity Through Program Analysis10.1007/978-3-030-41103-9_3(86-102)Online publication date: 15-Feb-2020
https://doi.org/10.1007/978-3-030-41103-9_3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents