MarkovJunior is a probabilistic programming language where programs are combinations of rewrite rules and inference is performed via constraint propagation.

https://github.com/mxgmn/MarkovJunior