依赖问题

一个类似标记清扫算法的问题，用于求解变量依赖关系。

问题描述

实际问题描述

很多语言要求变量先定义后使用，因为无法对一个未定义/未初始化的变量求值。JavaScript 中通过 let 定义的变量就是如此（由var 定义的变量会在进入作用域时隐式初始化为 undefined）：

console.log(x) // x is not defined
let x = 0

不过 JavaScript 中的函数定义是会提升的，对于这样的代码

let x = 0
console.log(f()) // console output: 1
function f() {
  return x + 1
}

只要函数在 let x = 0 语句之后调用就行，这是因为函数 f 内部使用了变量 x。在更早的位置调用此函数的话会导致 x 还没有定义。我们可以说函数 f 依赖变量 x。当然，函数变量还可以依赖其他函数变量。

上述 JavaScript 的变量定义检查是在运行时实现的，但我希望在一些简化条件下静态分析变量的依赖关系。

下面我会给出这个问题的抽象描述

抽象描述

有两种对象 R 和 S，每个 R 对象有两种依赖关系的运算：

depR :: R -> [R] -- 可以循环依赖
depS :: R -> [S]

给定 r :: [R] 和 s :: [S]，要求筛选 r 中所有符合条件的元素 x：

1. x 依赖的 S 对象全部全部在 s 中，即 depS x \\ s == []；
2. x 依赖的所 R 对象也符合条件，或者 depR x == []。

R 对象对应函数变量，S 对象对应其他变量，只有函数变量之间可能存在嵌套或递归的依赖关系。

解决方法

很明显不能通过上面的描述直接解决问题，R 间存在循环依赖时第 2 步检测将无法结束。

和标记清扫式 GC 算法不同，这个问题并不是根据 root set 标记所有可达对象。而是反过来：确定一个对象是否只直接或间接引用给定集合内的元素。这意味着我们也不能通过已知集合 s 逐步推断出所有的结果元素。

但是我们依然可以参考一些思路来设计算法：

1. 从 r 中找出与 s 差集为空的元素，记为 r'，其余元素记为 d。由于不满足条件 1，d 会被淘汰。即

   (r', d) = partition (\x -> depS x \\ s == []) r
   

2. 将 r' 中依赖 d 中元素的值淘汰（因为这些元素引用了不在 s 集合内的元素），得到新的集合：

   (r'', d') = partition (\x -> depR x `intersect` d == []) r'
   

3. 在 2 的结果上进一步进行淘汰，直到没有元素被淘汰为止。

具体的实现方法如下：

resolve :: [R] -> [S] -> ([R], [R])
resolve r s = f $ partition (\x -> depS x \\ s) r where
  f (r, []) = (r, [])
  f (r, d) = let (r', d') = partition (\x -> depR x `intersect` d == []) r
              in second (++ d) $ f (r', d')