Implementing Randomised Algorithms in Constraint Logic Programming

this paper, we propose a declarative-based implementation of randomised algorithms, which exploits the Concurrent Constraint Programming (CCP) paradigm for the formalisation of such algorithms. The main advantage in doing so is that we can rely on a sound and mathematically rigorous semantical framework, instead of on intuition, for tasks related to reasoning about probabilistic programs (analysis, synthesis, transformation and verification). The foundations of such a semantical framework have been devised in previous papers [3, 2], where we introduce a probabilistic language based on CCP, namely Probabilistic CCP (PCCP), and provide it with an operational and a denotational semantics. In PCCP randomness is expressed by means of a construct for probabilistic choice, which replaces (or refines) nondeterminism, and allows the program to make stochastic moves during its execution. In this work we concentrate on the implementation aspects of PCCP by designing a meta-interpreter for it. PCCP also includes synchronisation and concurrency aspects. However, for the time being, we put aside these aspects, by treating the parallel construct as a purely sequential one. As a consequence, the guarded choice, yet present in our language as a global choice (guards are not necessarily to be true), does not allow any synchronisation. From this point of view we effectively use here only the (probabilistic) Constraint Logic Programming (CLP) fragment of PCCP. For the constraint solving, the meta-interpreter exploits existing constraint handling facilities (more concretely the SICStus 3.#6 system) . This is possible because the design of PCCP does not require any additional structure on the underlying constraint system (e.g. fuzzy or belief systems). The current prototype consists basica..