From Logic to Stochastic Processes

Prakash Panangaden

To appear at the 2nd International Conference on Principles and Practice of Declarative Programming (PPDP 2000), Montreal, Canada, September 20-22, 2000

Abstract

The evolution of the concurrent constraint programming paradigm is a striking illustration of the evolution of computer science. Fifteen years ago probability was a special topic of interest to complexity and algorithm peoples and hybrid systems were new and exotic. Now there are conferences and workshops devoted to probabilistic systems, hybrid systems and verification. The concurrent constraint paradigm has similarly assimilated ideas from AI, probability and even analysis and become far richer for it.

I will give a survey of developments in the cc languages from plain cc to -- the as yet undiscovered -- stochastic cc. Roughly speaking, one can trace the development as follows. The original cc languages were developed as a concurrent programming language with the constraint system as a parameter. They abstracted from the variety of control mechanisms that were current then in concurrent logic programming languages and in functional languages with so called "logic variables". The cc family was purely asynchronous.

In order to express reactive programs as in the family of synchronous languages one had to introduce time. This led to the language tcc which captured temporal notions. However, for synchronous programs one needs an orthogonal idea as well, that of a default.

The presence of defaults introduces nonmonotonicity into the language. As we refine the notion of time and introduce a mixture of continuous time as well as discrete time we get a hybrid language called hcc. In fact the language of this name developed by Gupta, Jagadeesan and Saraswat has hybrid time-evolution and defaults, we will call it hdcc.

In 1997 Gupta, Jagadeesan and Saraswat introduced a probabilistic cc language and in 1999 this was extended to handle recursion by Gupta, Jagadeesan and Panangaden. In later investigation we noticed that one could use probabilities instead of defaults. In other words the way probability works one can emulate the effect of defaults. Thus if one were to add time to Probcc one would have the effect of the language tdcc or -- if one adds continuous time -- hdcc. We are currently working on the development of a modelling language analogous to hdcc for dealing with general stochastic differential equations in the same way hdcc deals with differential equations.