某些分配函数允许紧凑的表示方式。在这个章节,我们考虑两类方程:
形如$f: \mathcal{P}(D) \rightarrow \mathcal{P}(D)$ 的分配律方程,其中D是一个有限集合。(例如就是变量集合的增加删除的哪些分析的变迁函数)
形如$f: (D \rightarrow L) \rightarrow (D \rightarrow L)$ 的分配律方程,其中D是一个有限集合,L是一个完全格。(例如一些变量到抽象域映射的变迁函数,符号分析)
第一个函数包括第9.2节中可能未初始化变量分析的替代表述中使用的函数,并构成了第9.4节中介绍的IFDS框架的基础,而第二个函数则用于第9.6节中的IDE框架。
第一类函数是第二类的一种特殊情况。如果将L设置为两个元素Top、Bottom的格,那么P(D)和 D → L就是同构的(拥有相同的最小上边界和最大下边界)。对于P(D)里面的元素s,可以用一个特征方式D → L来表示:
令$f: \mathcal{P}(D) \rightarrow \mathcal{P}(D)$ 是一个分配律的函数,其中D是一个有限集合。一个朴素的f的表示,是一个具有$2^{|D|}$ 个元素的表格。(如果D是程序变量的集合,在一个典型的程序里面,这个表格会非常大!这是指数增长)一个分配律函数的特征在于它在空集和每个单元素集上的取值,例如:
这个含义是说,f可以分解为一个g函数,输入变为D和空集合,输出还是D的幂集合
其中g的定义如下:
那么现在,f(X),就可以由如下计算:
也就是说,f完全可以通过g来计算。(注意,g在计算d的时候移除了空集合的结果,因为这些元素已经在$g(\bullet)$ 里面计算过。这时候就变成了线性增长)
任何这样的函数都可以用一个具有2 * (|D| + 1)个节点的二分图来紧凑地表示,换句话说,比上面提到的朴素表示方法更简洁得多,呈指数级别的简洁。例如,如果D = {d1 d2 d3},三个元素,那么如下二分图的含义:
是g计算的结果,其中$g(\bullet)$ = d1,g(d1)是空集,d2和d3的结果是d3,因此对于f: