A Refinement Approach for Developing Probabilistic Programs

In this paper, we introduce a refinement approach to develop probabilistic programs formally. To achieve this goal, we first present a way to specify probabilistic programs in a Z-based notation. We then use an existing method of translating Z into a refinement calculus to transform our Z-style specifications of probabilistic programs into specification statements of the refinement calculus. We finally add new laws to the refinement calculus helping us to refine the resulting specification statements into probabilistic choice constructs of a probabilistic imperative language. In this way, we will provide a completely formal way for developing probabilistic programs.