由于一直没找到好的并且能答得上的问题，以后打算时不时往这发点paper，然后对之进行一定的解释，练练手&降低阅读门槛（希望）。
这次的是 Embedded Probabilistic Programming
建议前置知识：Probability Distribution，Monad，Continuation
P1-P6：我们想造一个编程语言，在这语言里面，所有变量都不是传统意义上的变量，而是Probability Distribution（PD）。
在本文中，一个a的PD可以看成一个List (probability, a)，其中，probability（简称prob）是double的别名，一个PD的元素，(probability, a)，代表在该概率下a的可能性是多小（这文章不考虑无限&连续的PD）
一个PD要满足两个条件：所有prob加起来是1，所有不同元素的a都不一样
在这定义下，我们可以定义多个PD下的函数：（此文皆为伪代码）
return : a -> PD a，接受一个非随机的值，变成一个PD
return x = [(1.0, x)] （这个随机变量只可能取一个值，就是传进来的那个）
map : (a -> b) -> (PD a -> PD b)，把PD里的所有a 都变成b
map f [] = []
map f ((prob, value):: rest) = (prob, f value):: map f rest
join : PD (PD a) -> PD a，把一个概率分布的概率分布变成概率分布
join [] = []
join (prob_of_prob, prob_value): rest = loop prob_value ++join rest
where
loop [] = []
loop ((prob, value): rest) = (prob * prob_of_prob, value) : loop rest
（对于每一个PD of PD里面的a，都有两个概率，一个是这个a的概率，一个是a的PD的概率，两个相乘就能扁平化）
对于所有M，符合这些定义
（return: a -> M a, map : (a -> b) -> (M a -> M b), join : M (M a) -> M a）的，
就叫一个Monad。
另一套定义法是，(return : a -> M a, bind : M a -> (a -> M b) -> M b)），
两者等价，自己可以试试看从一套推出另一套。
通过使用return，我们可以把普通的值看成PD，再通过bind，我们可以把任意PD的值当成普通的值使用，然后得出更多的PD。然后，需要随机性的时候，我们可以直接（通过构造列表）构造PD。比如说，如果要抛硬币，可以写[(0.5, Head), (0.5, Tail)]。这样，我们就可以在PD里面编程了。
有的时候，我们需要对我们的程序做一些限制（比如说，如果我们抛了两次硬币，然后被告知不可能两个都是Head）。这个时候，我们可以生成一个空的PD来代表‘不可能发生’。
例如，刚刚那个例子，可以表达为
let a = [(0.5, Head), (0.5, Tail)] （第零个硬币）
let b = [(0.5, Head), (0.5, Tail)] （第一个硬币）
bind a (\a_obs -> （观察第零个硬币）
bind b (\b_obs -> （观察第二个硬币）
if a_obs == Head && b_obs == Head then [] （空的PD，代表不可能） else return (a, b) （把观察到的a, b记录下来）))
这样，我们就有两个问题：
0：map, bind, join可能使得返回的PD（换句话说，List (prob, a)）中，两个元素的a一样的
1：bind x (\y -> [])会导致整个PD的概率的和不为1（如果只有特定的情况会fail，概率和就不是0也不是1）
这些问题都可以通过输出时，把同样的结果会合一起，再把整个PD的每一个prob乘一个数（使得概率和为1）解决。
P7:我们把这个语言放进OCaml里面，这样整个语言就是一推OCaml函数。这样就不需要自己写parser，typechecker，gc，然后OCaml也能自动帮你优化，还能用OCaml的库。
然后，由于可以用很多种方法实现PD，我们把一个PD的需求变成个模块签名，这样就可以用不同的实现。在这里面，PD实现者可以自定义什么是一个PD（叫做pm，因为PD是个Monad）这种方法叫做Finally Tagless。用Finally Tagless而不是用一个AST有两个好处：一是AST不可扩展（不可增加新的constructor），一是Int的AST跟Bool的AST（往往）是同一类型，所以是unsafe的。
P8:由于上面所述的PD的实现太慢，并且只能暴力算，无法做任何优化，所以用的是另一种数据结构。
P9:explore是尾递归的，susp是剩下的计算，ans是一个Map，用以把多个PD中一样的a会合到一起，解决问题0
P12:一个continuation可以看成：给定一个（算出a在一个值下，符合observation的概率，的函数），返回一个a的PD符合该observation的概率
P16-17:我们可以（通过explore）事先展开一个stochastic function，得出他的exact PD，然后就可以避免重复计算。这叫variable elimination。
P18:当Branching很大的时候，完全的展开不现实，这时候可以以一个branch的概率选择性的展开：这叫sampling。naive的sampling会很受指数爆炸的影响，所以可以只展开没展开过的，这叫importance sampling。