Probabilistic Programming Category?

[AkihisaYamada]

Let's also discuss about probabilistic programs.
I'm informed of https://github.com/Sheshansh/prob_termination.

An example there

var tx,x,y;
if tx>=0 then
	while x>=y and tx>=0 do
	if prob(0.3) then
		if * then
			x:=x-1-tx+[-1,1]
		else
			y:=y+1+tx+[-3,2]
		fi
	else skip fi
	od
else
	skip
fi

There are probabilistic and nondeterminisitic branching, vars are reals, [l,r] is uniform sampling.
I guess a C-like format (or TRS-like one) with these features are good starting point.

[ffrohn]

I think we should use an extension of the format for LTSs with probabilities as in the format for PTRSs (which would suffice to represent the example above, as far as I can see).

We had far too many different formats and we're currently trying to unify them, so using a C-like (or entirely different) format would be counterproductive.

I think other potential participants (like KoAT) are more interested in integer-valued variables. Is there more than one potential participant with support for reals, or more than one potential participant with support for integers?

[AkihisaYamada]

We need at least uniform sampling ([-1,1] in the example). Maybe allow (uniform (- 1) 1) in expression?

[eleanoremeyer]

Another option would be to use a format similar to that of probabilistic integer programs used by our tool KoAT.
Probabilistic integer programs generalise integer transition systems which are already part of the TermComp & TPDB to also allow for the representation of probabilistic branching and sampling from (possibly parametrised & infinite) probability distributions (over the integers).
This is in extension to the concepts of nondeterministic branching and nondeterministic “sampling” (temporary variables).
The format is also similar to the concept of probabilistic control flow graphs as used in this publication (among others).

Another alternative that comes to mind, is a python-like imperative programming language as used by eco-imp/ev-imp and absynth (see this publication).
However, I fear that the usage of such a higher-level language would increase the entry barrier for tools.
Moreover, unlike as for probabilistic integer programs, this would not be a generalisation of a format that is already included in the termination competition.

[ffrohn]

Probabilistic integer programs generalise integer transition systems which are already part of the TermComp & TPDB

But they are about to be replaced.

Another alternative that comes to mind, is a python-like imperative programming language

See my previous comment:

We had far too many different formats and we're currently trying to unify them, so using a C-like (or entirely different) format would be counterproductive.

Anyway, before we fix the syntax, we should clarify some more important questions:

• Are there several tools that support the same kind of programs?
  • KoAT supports integers only (?)
  • The tool mentioned by Akihisa supports reals only (?)
• Would they be willing to participate?
• Do we have (sufficiently many) examples?