You create a probabilistic model. So you tell the compiler: there's a 50% chance this will be true, and the program will compute both sides and say, there's a 50% chance for this result and 50% for this other result.
What I'm trying to say is that at the moment it looks like every programming language ever is trivially capable of expressing these sorts of programs using the random number generators that are wildly common. What is different in this programming paradigm?
In particular, this paragraph:
> Another way of thinking about this: unlike a traditional program, which only runs in the forward directions, a probabilistic program is run in both the forward and backward direction. It runs forward to compute the consequences of the assumptions it contains about the world (i.e., the model space it represents), but it also runs backward from the data to constrain the possible explanations.
Are these programs truly running backwards? Is there some backwards reduction relation in their semantics that I could look at?
Presumably, a programming language designed around this kind of task would make it easier to explore and develop larger, more intricate models.
Conceptually, the easiest way to understand things is via rejection sampling. You can "run things backward" but running things forward and just keeping the traces that match the observed output. That's Bayesian inference. Unfortunately, the probability of matching the observed output is zero for most problems so you need to use more advanced methods. Most accounts gloss over these methods since it's a huge research area.
Running things backwards is also not a perfect analogy because if fails to account for the probability distribution you start with.