Implementing randomised algorithms in constraint logic programming
Nicos Angelopoulos, Alessandra Di Pierro, Herbert Wiklicky · 1998
We propose a declarative-based implementation of randomised algorithms, which exploits the Constraint Logic Programming (CLP) paradigm. For the high-level formalisation of probabilistic programs expressing such algorithms we actually refer to a generalisation of CLP, namely the Probabilistic Concurrent Constraint Programming (PCCP) language, previously introduced in [DW97]. This language provides a construct for probabilistic choice which allows us to express randomness in a program. PCCP also includes synchronisation and concurrency aspects. However, for the purpose of this work, the (probabilistic) CLP fragment of PCCP is sufficient. We present a meta-interpreter for this language. This is just a standard prolog meta-interpreter, suitably extended so as to deal with probabilistic choice. For the constraint solving, the meta-interpreter exploits existing constraint handling facilities (and in more concrete terms to the SICStus 3.#6 system). This is possible because the design of PCCP ...