Great connection. Here's one way of looking at it: when you add stochasticity to your program, you make it easier to search the space of possible solutions (and

Great connection. Here's one way of looking at it: when you add stochasticity to your program, you make it easier to search the space of possible solutions (and you also relax the criteria for what it means to be "a solution"). In (deterministic) logic programming, the default search strategy is backtracking. We search the space of "inputs that could have produced this output" exhaustively. Each set of inputs we try either works or doesn't, and doesn't tell us anything about whether similar inputs will behave similarly. In probabilistic programming, we can use the information we have about probability densities to tell whether we're on the right track; as we search, we can tell if we're getting "warmer" or "colder." Suppose I have the simple probabilistic program: def f(): a = normal(0, 1) # mean 0, stddev 1 b = normal(0, 1) c = normal(a+b, 0.1) return c In this generative model, I choose two random numbers, add them together, and then pick a third number very close to their sum. This could be thought of as a probabilistic version of the deterministic program f(a, b) = a+b. If I want to "invert" it, and condition on c=2, say, I can walk around the space of a priori likely (a, b) values, "scoring" them based on how likely "c=2" would have been given the particular (a, b) under consideration. The tight bell curve around the value c=2 can be seen as an implicit "loss function," telling us how good or bad the current solution is. This is very different from a logic programming approach, which would be able to exactly invert the + operation; but as you pointed out, it's nontrivial to formulate `+` correctly as a logic program, whereas here, we are free to use an imperative implementation of `+` (or much more complex deterministic operations, like a 3D renderer). There is research in probabilistic logic programming languages, which can be seen as combining some of the strengths of both paradigms, though that's not covered by the introduction linked in the OP.