Lambda Calculus and Probabilistic Computation
We introduce two extensions of λ-calculus with a probabilistic choice operator, modeling respectively the call-by-value and call-by-name probabilistic computation. We prove that both enjoys confluence and standardization, in an extended way: indeed these two fundamental notions have been revisited to take into account the asymptotic behaviour of terms. The common root of the two calculi is a further calculus based on Linear Logic, which allows us to develop a unified, modular approach.
READ FULL TEXT