## 4.1 解析约束

### 4.1.1 使用prolog进行约束解析

apt install gprolog

```1 if b1
2     then
3         while b2 do x = a1
4     else
5         while b3 do x = a2
6 x = a3```

BB列表：

```1: b1
2: b2
3: x=a1
4: b3
5: x=a2
6: x=a3```

```1 digraph {
2     "1: b1" -> {"2: b2" "4: b3"}
3     "2: b2" -> "3: x=a1" -> "2: b2"
4     "4: b3" -> "5: x=a2" -> "4: b3"
5     {"2: b2" "4: b3"} -> "6: x=a3"
6 }```

``` 1 IN[x1] = {}
2 IN[x2] = OUT[x1] ∪ OUT[x3]
3 IN[x3] = OUT[x2]
4 IN[x4] = OUT[x1] ∪ OUT[x5]
5 IN[x5] = OUT[x4]
6 IN[x6] = OUT[x2] ∪ OUT[x4]
7 OUT[x1] = IN[x1]
8 OUT[x2] = IN[x2]
9 OUT[x3] = (IN[x3]\{3,5,6}) ∪ {3}
10 OUT[x4] = IN[x4]
11 OUT[x5] = (IN[x5]\{3,5,6}) ∪ {5}
12 OUT[x6] = (IN[x6]\{3,5,6}) ∪ {6}```

``` 1 diff([], _, []).
2 diff([H|T], L, LL) :- member(H, L), diff(T, L, LL).
3 diff([H|T], L, [H|LL])
4 :- \+ member(H, L), diff(T, L, LL).
5 union([], L, L).
6 union([H|T], L, [H|LL])
7 :- union(T, L, LL).
8
9
10 solution([X1_IN, X2_IN, X3_IN, X4_IN, X5_IN, X6_IN,
11 X1_OUT, X2_OUT, X3_OUT, X4_OUT, X5_OUT, X6_OUT]) :-
12     X1_IN = [],
13     union(X1_OUT, X3_OUT, X2_IN),
14     X3_IN = X2_OUT,
15     union(X1_OUT, X5_OUT, X4_IN),
16     X5_IN = X4_OUT,
17     union(X2_OUT, X4_OUT, X6_IN),
18     X1_OUT = X1_IN,
19     X2_OUT = X2_IN,
20     diff(X3_IN, [3, 5, 6], XA), union(XA, [3], X3_OUT),
21     X4_OUT = X4_IN,
22     diff(X5_IN, [3, 5, 6], XB), union(XB, [5], X5_OUT),
23     diff(X6_IN, [3, 5, 6], XC), union(XC, [6], X6_OUT), !.```

prolog的语法可以参考swi-prolog的手册 manual (swi-prolog.org) ，注意swi的prolog自己扩展了一些prolog函数，有些函数在其他版本的prolog里面不一定能用。

`solution([[], [3], [3], [5], [5], [3, 5], [], [3], [3], [5], [5], [6]]) 返回值是true（gprolog返回yes）。如果想知道推导过程，可以用“trace.”打开单步执行：`

``` 1 PS D:\doc\DC888\hw> swipl
2
3 1 ?- [rd].
4 true.
5
6 2 ?- solution([[], [3], [3], [5], [5], [3, 5], [], [3], [3], [5], [5], [6]]).
7 true.
8
9 3 ?- trace.
10 true.
11
12 [trace] 3 ?- solution([[], [3], [3], [5], [5], [3, 5], [], [3], [3], [5], [5], [6]]).
13    Call: (10) solution([[], [3], [3], [5], [5], [3, 5], [], [...]|...]) ? creep
14    Call: (11) []=[] ? creep
15    Exit: (11) []=[] ? creep
16    Call: (11) union([], [3], [3]) ? creep
17    Exit: (11) union([], [3], [3]) ? creep
18    Call: (11) [3]=[3] ? creep
19    Exit: (11) [3]=[3] ? creep
20    Call: (11) union([], [5], [5]) ? creep
21    Exit: (11) union([], [5], [5]) ? creep
22    Call: (11) [5]=[5] ? creep
23    Exit: (11) [5]=[5] ? creep
24    Call: (11) union([3], [5], [3, 5]) ? creep
25    Call: (12) lists:member(3, [5]) ? creep
26    Fail: (12) lists:member(3, [5]) ? creep
27    Redo: (11) union([3], [5], [3, 5]) ? creep
28    Call: (12) lists:member(3, [5]) ? creep
29    Fail: (12) lists:member(3, [5]) ? creep
30    Redo: (11) union([3], [5], [3, 5]) ? creep
31    Call: (12) union([], [5], [5]) ? creep
32    Exit: (12) union([], [5], [5]) ? creep
33    Exit: (11) union([3], [5], [3, 5]) ? creep
34    Call: (11) []=[] ? creep
35    Exit: (11) []=[] ? creep
36    Call: (11) [3]=[3] ? creep
37    Exit: (11) [3]=[3] ? creep
38    Call: (11) diff([3], [3, 5, 6], _20084) ? creep
39    Call: (12) lists:member(3, [3, 5, 6]) ? creep
40    Exit: (12) lists:member(3, [3, 5, 6]) ? creep
41    Call: (12) diff([], [3, 5, 6], _20084) ? creep
42    Exit: (12) diff([], [3, 5, 6], []) ? creep
43    Exit: (11) diff([3], [3, 5, 6], []) ? creep
44    Call: (11) union([], [3], [3]) ? creep
45    Exit: (11) union([], [3], [3]) ? creep
46    Call: (11) [5]=[5] ? creep
47    Exit: (11) [5]=[5] ? creep
48    Call: (11) diff([5], [3, 5, 6], _27698) ? creep
49    Call: (12) lists:member(5, [3, 5, 6]) ? creep
50    Exit: (12) lists:member(5, [3, 5, 6]) ? creep
51    Call: (12) diff([], [3, 5, 6], _27698) ? creep
52    Exit: (12) diff([], [3, 5, 6], []) ? creep
53    Exit: (11) diff([5], [3, 5, 6], []) ? creep
54    Call: (11) union([], [5], [5]) ? creep
55    Exit: (11) union([], [5], [5]) ? creep
56    Call: (11) diff([3, 5], [3, 5, 6], _2514) ? creep
57    Call: (12) lists:member(3, [3, 5, 6]) ? creep
58    Exit: (12) lists:member(3, [3, 5, 6]) ? creep
59    Call: (12) diff([5], [3, 5, 6], _2514) ? creep
60    Call: (13) lists:member(5, [3, 5, 6]) ? creep
61    Exit: (13) lists:member(5, [3, 5, 6]) ? creep
62    Call: (13) diff([], [3, 5, 6], _2514) ? creep
63    Exit: (13) diff([], [3, 5, 6], []) ? creep
64    Exit: (12) diff([5], [3, 5, 6], []) ? creep
65    Exit: (11) diff([3, 5], [3, 5, 6], []) ? creep
66    Call: (11) union([], [6], [6]) ? creep
67    Exit: (11) union([], [6], [6]) ? creep
68    Exit: (10) solution([[], [3], [3], [5], [5], [3, 5], [], [...]|...]) ? creep
69 true.```

solution([[], [3], [3], [5], [5], [3, 5], [], [3], [3], [5], [5], [6]])执行返回true表示，1~6处的reaching definition的输入集合分别为：

`[], [3], [3], [5], [5], [3, 5]，`

`输出集合分别为：`

`[], [3], [3], [5], [5], [6]`

solution([[], [3], [3], [4, 5], [4, 5], [3, 4, 5], [], [3], [3], [4, 5], [4, 5], [4, 6]]).

```1 PS D:\doc\DC888\hw> swipl
2
3 1 ?- [rd].
4 true.
5
6 2 ?- solution([[], [3], [3], [a, 5], [a, 5], [3, a, 5], [], [3], [3], [a, 5], [a, 5], [a, 6]]).
7 true.
8
9 3 ?-```

```1 diff([H|T], L, [H|LL])
2 :- \+ member(H, L), diff(T, L, LL).
3 union([H|T], L, [H|LL])
4 :- \+ member(H, L), union(T, L, LL).
5 ji```

```1 PS D:\doc\DC888\hw> swipl
2
3 1 ?- [rd].
4 true.
5
6 2 ?- solution([[], [3], [3], [a, 5], [a, 5], [3, a, 5], [], [3], [3], [a, 5], [a, 5], []]).
7 false.
8
9 3 ?-```

### 4.1.3 使用prolog找到解决方案

solution([X1_IN, X2_IN, X3_IN, X4_IN, X5_IN, X6_IN, X1_OUT, X2_OUT,

X3_OUT, X4_OUT, [5], X6_OUT]).

``` 1 root@794bb5fbd58a:~/DCC888# gprolog
2 GNU Prolog 1.3.0
3 By Daniel Diaz
4 Copyright (C) 1999-2007 Daniel Diaz
5 | ?- [rd1].
6 compiling /home/ronghua.zhou/DCC888/rd1.pl for byte code...
7 /home/ronghua.zhou/DCC888/rd1.pl compiled, 21 lines read - 4036 bytes written, 6 ms
8
9 yes
10 | ?- X5_OUT = [5],
11 X1_IN = [],
12 X2_IN = [3],
13 X3_IN = [3],
14 X4_IN = [5],
15 X5_IN = [5],
16 X6_IN = [3, 5],
17 OUT = [],
18 X2X1_OUT = [],
19 _OUTX2_OUT = [3],
20 X3_OUT = [3],
21 X4_OUT = [5],
22 X6_OUT = [6] .
23
24 X1_IN = []
25 X1_OUT = []
26 X2_IN = [3]
27 X2_OUT = [3]
28 X3_IN = [3]
29 X3_OUT = [3]
30 X4_IN = [5]
31 X4_OUT = [5]
32 X5_IN = [5]
33 X5_OUT = [5]
34 X6_IN = [3,5]
35 X6_OUT = [6]
36
37 yes
38 | ?- length(X5_OUT, 1), solution([X1_IN, X2_IN, X3_IN, X4_IN, X5_IN, X6_IN,
39 X1_OUT, X2_OUT, X3_OUT, X4_OUT, X5_OUT, X6_OUT]).
40
41 X1_IN = []
42 X1_OUT = []
43 X2_IN = [3]
44 X2_OUT = [3]
45 X3_IN = [3]
46 X3_OUT = [3]
47 X4_IN = [5]
48 X4_OUT = [5]
49 X5_IN = [5]
50 X5_OUT = [5]
51 X6_IN = [3,5]
52 X6_OUT = [6]
53
54 yes
55 | ?- solution([X1_IN, X2_IN, X3_IN, X4_IN, X5_IN, X6_IN,
56 X1_OUT, X2_OUT, X3_OUT, X4_OUT, X5_OUT, X6_OUT]).
57
58 Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ)```

## 4.2 解决循环worklist的方法

### 4.2.1 用混沌迭代解决reaching definition

``` 1 for each i ∈ {1, 2, 3, 4, 5, 6}
2     IN[xi] = {}
3     OUT[xi] = {}
4 repeat
5     for each i ∈ {1, 2, 3, 4, 5, 6}
6         IN'[xi] = IN[xi];
7         OUT'[xi] = OUT[xi];
8         OUT[xi] = def(xi) ∪ (IN[xi] \ kill(xi));
9         IN[xi] = ∪ OUT[s], s ∈ pred[xi];
10 until ∀ i ∈ {1, 2, 3, 4, 5, 6}
11     IN'[xi] = IN[xi] and OUT'[xi] = OUT[xi]```

### 4.2.2 抽象之后的混沌迭代算法

```1 x1 = ⊥ , x2 = ⊥ , … , xn = ⊥
2 do
3     t1 = x1 ; … ; tn = xn
4     x1 = F1 (x1, …, xn)
5     …
6     xn = Fn (x1, …, xn)
7 while (x1 ≠ t1 or … or xn ≠ tn)```

### 4.2.4 混沌迭代的worklist表达

```1 x1 = ⊥ , x2 = ⊥ , … , xn = ⊥
2 w = [v1, …, vn]
3 while (w ≠ [])
4     vi = extract(w)
5     y = Fi (x1, …, xn)
6     if y ≠ xi
7         for v ∈ dep(vi)
8         w = insert(w, v)
9         xi = y```

```1 solution([X1_IN, X2_IN, X3_IN, X4_IN, X5_IN, X6_IN]) :-
2     X1_IN = [], /* F1 */3     diff(X3_IN, [3, 5, 6], XA), union(XA, X1_IN, XB), union(XB, [3], X2_IN), /* F2 */4     X3_IN = X2_IN, /* F3 */5     diff(X5_IN, [3, 5, 6], XC), union(XC, X1_IN, XD), union(XD, [5], X4_IN), /* F4 */6     X5_IN = X4_IN, /* F5 */7     union(X2_IN, X5_IN, X6_IN), !. /* F6 */```

```1 digraph {
2     "X1_IN" -> {"X2_IN" "X4_IN"}
3     "X2_IN" -> "X3_IN" -> "X2_IN"
4     "X4_IN" -> "X5_IN" -> "X4_IN"
5     {"X2_IN" "X4_IN"} -> "X6_IN"
6 }```

### 4.2.5 寻找更好的遍历顺序

``` 1 def dfs(graph, root, visitor):
2     """DFS over a graph.
4     """
5     visited = set()
6     def dfs_walk(node):
8         visitor(node)
9         for succ in graph.successors(node):
10             if not succ in visited:
11                 dfs_walk(succ)
12     dfs_walk(root)```

``` 1 def postorder(graph, root):
2     """Return a post-order ordering of nodes in the graph."""
3     visited = set()
4     order = []
5     def dfs_walk(node):
7         for succ in graph.successors(node):
8             if not succ in visited:
9                 dfs_walk(succ)
10         order.append(node)
11     dfs_walk(root)
12     return order```

``` 1 insert(v, P):
2     return P ∪ {v}
3
4 extract(C, P):
5     if C = []
6         C = sort_rPostorder(P)
7         P = {}
9
10 main:
11     x1 = ⊥ , x2 = ⊥ , … , xn = ⊥
12     C=[], P={v1, ... , vn}
13     while (C ≠ [] || P ≠ {})
14         vi, C, P = extract(C, P)
15         y = Fi (x1, …, xn)
16         if y ≠ xi
17             for v ∈ dep(vi)
18             P = insert(v, P)
19             xi = y```

## 4.3 强子图

```1 digraph {
2     "1: b1" -> {"2: b2, 3: x=a1" "4: b3, 5: x=a2"} -> "6: x=a3"
3 }```

## 4.4 算法简化：轮转迭代

```1 x1 = ⊥ , x2 = ⊥ , … , xn = ⊥
2 change = true
3 while (change)
4     change = false
5     for i = 1 to n do
6         y = Fi (x1, …, xn)
7         if y ≠ xi
8             change = true
9             xi = y```

15步可以把约束系统计算完毕：