Sungwoo Park
Abstract
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 the traditional lambda calculus. In our calculus, every expression denotes a probability distribution yet evaluates to a regular value. The most notable feature of our calculus is that it is founded upon sampling functions, which map the unit interval to probability domains. As a consequence, we achieve a unified representation scheme for all types of probability distributions. In order to support an efficient implementation of the calculus, we also develop a refinement type system which is capable of distinguishing expressions denoting regular values from expressions denoting probability distributions. We use a novel formulation of the intuitionistic modal logic S4 with an intersection connective in the refinement type system. We present preliminary evidence that a probabilistic language based upon our calculus is viable in applications involving massive probabilistic computation.
- P. Bratley, B. Fox, and L. Schrage. A guide to simulation. Springer Verlag, 2nd edition, 1996. Google Scholar
Digital Library
- R. Davies and F. Pfenning. Intersection types and computational effects. In ICFP-00, pages 198--208. ACM Press, 2000. Google Scholar
- R. Davies and F. Pfenning. A modal analysis of staged computation. Journal of the ACM, 48(3), 2001. Google ScholarDigital Library
- A. Edalat and P. J. Potts. A new representation for exact real numbers. In Electronic Notes in Theoretical Computer Science, volume 6. Elsevier Science Publishers, 2000.Google Scholar
- D. Fox, W. Burgard, F. Dellaert, and S. Thrun. Monte carlo localization: Efficient position estimation for mobile robots. In AAAI-99, pages 343--349. AAAI/MIT Press, 1999. Google Scholar
- J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675--695, 1977.Google ScholarDigital Library
- V. Gupta, R. Jagadeesan, and P. Panangaden. Stochastic processes as concurrent constraint programs. In 26th ACM POPL, pages 189--202. ACM Press, 1999. Google ScholarDigital Library
- A. H. Jazwinski. Stochastic Processes and Filtering Theory. Academic Press, New York, 1970.Google Scholar
- C. Jones. Probabilistic Non-Determinism. PhD thesis, Department of Computer Science, University of Edinburgh, 1990. Google ScholarDigital Library
- D. Koller, D. McAllester, and A. Pfeffer. Effective Bayesian inference for stochastic programs. In AAAI-97/IAAI-97, pages 740--747. AAAI Press, 1997. Google ScholarDigital Library
- D. Kozen. Semantics of probabilistic programs. Journal of Computer and System Sciences, 22(3):328--350, 1981.Google ScholarCross Ref
- J. Maraist, M. Odersky, and P. Wadler. The call-by-need lambda calculus. Journal of Functional Programming, 8(3):275--317, 1998. Google ScholarDigital Library
- A. Pfeffer. IBAL: A probabilistic rational programming language. In IJCAI-01, pages 733--740. Morgan Kaufmann Publishers, 2001. Google ScholarDigital Library
- F. Pfenning and R. Davies. A judgmental reconstruction of modal logic. Mathematical Structures in Computer Science, 11(4):511--540, 2001. Google ScholarDigital Library
- D. Pless and G. Luger. Toward general analysis of recursive probability models. In UAI-01, pages 429--436. Morgan Kaufmann Publishers, 2001. Google ScholarDigital Library
- N. Ramsey and A. Pfeffer. Stochastic lambda calculus and monads of probability distributions. In 29th ACM POPL, pages 154--165. ACM Press, 2002. Google ScholarDigital Library
- N. Saheb-Djahromi. Probabilistic LCF. In Proceedings of the 7th Symposium on S. Thrun.18. Probabilistic algorithms in robotics. AI Magazine, 21(4):93--109, 2000.Google Scholar
- S. Thrun. Towards programming tools for robots that integrate probabilistic computation and learning. In ICRA-00. IEEE, 2000.Google Scholar
Index Terms
- A calculus for probabilistic languages
Recommendations
A calculus for probabilistic languages
TLDI '03: Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementationAs 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 ...
Logical-Probabilistic Calculus: A Tool for Studying the Reliability and Safety of Structurally Complex Systems
The concept of the probabilistic logic is briefly described as an extension of inductive logic. A clear distinction is made between the probabilistic logic and logical-probabilistic calculus—the branch of mathematics that defines the rules of ...
An Axiomatisation of the Probabilistic -Calculus
Formal Methods and Software EngineeringAbstractThe probabilistic -calculus (PTL) is a simple and succinct probabilistic extension of the propositional -calculus, by extending the ‘next’-operator with a probabilistic quantifier. We extend the approach developed by Walukiewicz for propositional -...
Comments