IDFS下什么是分布式函数，为什么指针分析是非分布式的？
What is a distributive function under IDFS and why is pointer analysis non-distributive?
我目前正在 Java 进行过程间分析项目，我正在研究使用 IFDS 求解器来计算程序的控制流图。我发现很难遵循 IFDS 框架和图形可达性描述中涉及的数学。我在几个地方读到过，使用此求解器无法计算程序的指向集 "pointer analysis is known to be a non-distributive problem." [1] 其他消息来源表示，这通常专门针对 'strong updates' ，据我所知，这是现场写陈述。
我想我基本上可以了解求解器如何计算边并计算出数据流事实。但我不太明白这个是什么：f(A ∪ B) = f(A) ∪ f(B) 实际上意味着作为分配函数的定义，因此说指向分析是什么意思处理非分配函数。
链接源 [1] 给出了一个特定于字段写入语句的示例：
A a = new A();
A b = a;
A c = new C();
b.f = c;
它声称，为了推理对 b.f 的赋值，还必须考虑基数 b 的所有别名。我可以跟着这个。但我不明白的是，这个动作的属性是什么使其成为非分配的。
来自 [2] 的类似（我认为）示例：
x = y.n
where语句之前有指向边y-->obj1和obj1.n-->obj2（其中obj1和2是堆对象）。他们声称
it is not possible to correctly deduce that the edge x-->obj2 should be generated after the statement if we consider each input edge independently. The flow function for this statement is a function of the points-to graph as a whole and cannot be decomposed into independent functions of each edge and then merged to get a correct result.
我想我几乎明白了，至少第一个例子在说什么，但我没有理解分配函数的概念，这阻碍了我了解全貌。谁能在不使用我难以理解的集合论的情况下，在指针分析的实际基础上解释什么是分配函数或非分配函数？
[1] http://karimali.ca/resources/pubs/conf/ecoop/SpaethNAB16.pdf
[2] http://dl.acm.org/citation.cfm?doid=2487568.2487569（付费专区，抱歉）
流函数的分配性定义为：f(a Π b) = f(a) Π f(b)，其中 Π 为合并函数。在 IFDS 中，Π 被定义为集合并集 ∪。
这意味着无论你在流函数之前还是之后应用合并函数，最终都会得到相同的结果。
在传统的数据流分析中，您遍历 CFG 的语句并传播数据流事实集。因此，对于流函数 f，对于每个语句，您计算 f(in, stmt) = out，其中包含您要保留的信息集的 in 和 out（例如：对于 in-set {(a, allocA), ( b, allocA)} - 表示对象 a 和 b 的分配位置是 allocA，语句 "b.f = new X();" - 我们将其命名为 allocX，你可能会得到开头集 {(a, allocA), ( b, allocA), (a.f, allocX), (b.f, allocX)} 因为 a 和 b 是别名).
IFDS 将内嵌分解为单独的数据流事实。因此，对于每个事实，不是 运行 将你的流函数与你的整个 inset 连接一次，你 运行 它在 inset 的每个元素上：∀ d ∈ in, f(d, stmt) = out_d。然后该框架将所有 out_d 合并到最终的输出集中。
这里的问题是，对于每个流函数，您无法访问整个集合，这意味着对于我们上面给出的示例，运行设置流函数 f((a, allocA))该语句将产生第一个输出集 {(a, allocA)}，f((b, allocA)) 将产生第二个输出集 {(b, allocA)}，而 f(0) 将产生第三个out-set {(0), (b.f, allocX)}。
因此，合并结果后的全局输出将是 {(a, allocA), (b, allocA), (b.f, allocX)}。我们遗漏了事实 {(a.f, allocX)} 因为当 运行 流函数 f(0) 时，我们只知道 in-fact 是 0 而语句是 "b.f = new X();".因为我们不知道a和b指的是allocA的分配位点allocA，所以我们不知道它们是别名的，因此我们无法知道a.f语句后也应该指向allocX。
IFDS 运行s 基于分配性假设：在 运行 流函数之后合并输出集应该产生与在 [=28= 之前合并输入集相同的结果]宁流动功能。
换句话说，如果您需要组合来自集合内多个元素的信息以在您的集合中创建某个数据流事实，那么您不是分布式的，并且不应该在 IFDS 中表达您的问题（除非您这样做处理这些组合情况的东西，就像你提到的论文的作者 [1] 所做的那样）。
我目前正在 Java 进行过程间分析项目，我正在研究使用 IFDS 求解器来计算程序的控制流图。我发现很难遵循 IFDS 框架和图形可达性描述中涉及的数学。我在几个地方读到过，使用此求解器无法计算程序的指向集 "pointer analysis is known to be a non-distributive problem." [1] 其他消息来源表示，这通常专门针对 'strong updates' ，据我所知，这是现场写陈述。
我想我基本上可以了解求解器如何计算边并计算出数据流事实。但我不太明白这个是什么：f(A ∪ B) = f(A) ∪ f(B) 实际上意味着作为分配函数的定义，因此说指向分析是什么意思处理非分配函数。
链接源 [1] 给出了一个特定于字段写入语句的示例：
A a = new A();
A b = a;
A c = new C();
b.f = c;
它声称，为了推理对 b.f 的赋值，还必须考虑基数 b 的所有别名。我可以跟着这个。但我不明白的是，这个动作的属性是什么使其成为非分配的。
来自 [2] 的类似（我认为）示例：
x = y.n
where语句之前有指向边y-->obj1和obj1.n-->obj2（其中obj1和2是堆对象）。他们声称
it is not possible to correctly deduce that the edge x-->obj2 should be generated after the statement if we consider each input edge independently. The flow function for this statement is a function of the points-to graph as a whole and cannot be decomposed into independent functions of each edge and then merged to get a correct result.
我想我几乎明白了，至少第一个例子在说什么，但我没有理解分配函数的概念，这阻碍了我了解全貌。谁能在不使用我难以理解的集合论的情况下，在指针分析的实际基础上解释什么是分配函数或非分配函数？
[1] http://karimali.ca/resources/pubs/conf/ecoop/SpaethNAB16.pdf
[2] http://dl.acm.org/citation.cfm?doid=2487568.2487569（付费专区，抱歉）
流函数的分配性定义为：f(a Π b) = f(a) Π f(b)，其中 Π 为合并函数。在 IFDS 中，Π 被定义为集合并集 ∪。 这意味着无论你在流函数之前还是之后应用合并函数，最终都会得到相同的结果。
在传统的数据流分析中，您遍历 CFG 的语句并传播数据流事实集。因此，对于流函数 f，对于每个语句，您计算 f(in, stmt) = out，其中包含您要保留的信息集的 in 和 out（例如：对于 in-set {(a, allocA), ( b, allocA)} - 表示对象 a 和 b 的分配位置是 allocA，语句 "b.f = new X();" - 我们将其命名为 allocX，你可能会得到开头集 {(a, allocA), ( b, allocA), (a.f, allocX), (b.f, allocX)} 因为 a 和 b 是别名).
IFDS 将内嵌分解为单独的数据流事实。因此，对于每个事实，不是 运行 将你的流函数与你的整个 inset 连接一次，你 运行 它在 inset 的每个元素上：∀ d ∈ in, f(d, stmt) = out_d。然后该框架将所有 out_d 合并到最终的输出集中。 这里的问题是，对于每个流函数，您无法访问整个集合，这意味着对于我们上面给出的示例，运行设置流函数 f((a, allocA))该语句将产生第一个输出集 {(a, allocA)}，f((b, allocA)) 将产生第二个输出集 {(b, allocA)}，而 f(0) 将产生第三个out-set {(0), (b.f, allocX)}。 因此，合并结果后的全局输出将是 {(a, allocA), (b, allocA), (b.f, allocX)}。我们遗漏了事实 {(a.f, allocX)} 因为当 运行 流函数 f(0) 时，我们只知道 in-fact 是 0 而语句是 "b.f = new X();".因为我们不知道a和b指的是allocA的分配位点allocA，所以我们不知道它们是别名的，因此我们无法知道a.f语句后也应该指向allocX。
IFDS 运行s 基于分配性假设：在 运行 流函数之后合并输出集应该产生与在 [=28= 之前合并输入集相同的结果]宁流动功能。 换句话说，如果您需要组合来自集合内多个元素的信息以在您的集合中创建某个数据流事实，那么您不是分布式的，并且不应该在 IFDS 中表达您的问题（除非您这样做处理这些组合情况的东西，就像你提到的论文的作者 [1] 所做的那样）。