第3章 控制流分析 内容概述 -定义一个函数式编程语言，变量可以指称函数 以dynamic dispatch problemi为例（作为参数的 函数被调用时，究竟执行的是哪个函数) 规范该控制流分析问题，定义什么是可接受的控 制流分析 -定义可接受分析在语义模型上的可靠性 一讨论分析算法（语法制导、集合约束求解） -加上数据流分析 -加上上下文信息
第3章 控制流分析 • 内容概述 – 定义一个函数式编程语言，变量可以指称函数 – 以dynamic dispatch problem为例（作为参数的 函数被调用时，究竟执行的是哪个函数） – 规范该控制流分析问题，定义什么是可接受的控 制流分析 – 定义可接受分析在语义模型上的可靠性 – 讨论分析算法（语法制导、集合约束求解） – 加上数据流分析 – 加上上下文信息
第3章 控制流分析 函数的不动点 若x)=x,则x是函数f的不动点 -求解含函数变量f的方程 f=An.if n=0 then 1 else n x fn -1)end 看成找下面函数的不动点 F 入f入n.ifn=0then1 else n×fn-1)end F(阶乘函数)=阶乘函数 该函数只有唯一的不动点 阶乘函数
第3章 控制流分析 • 函数的不动点 – 若f(x) = x，则x是函数f 的不动点 – 求解含函数变量f 的方程 f = n. if n=0 then 1 else n f(n − 1) end – 看成找下面函数的不动点 F f. n. if n=0 then 1 else n f(n − 1) end F(阶乘函数) = 阶乘函数 – 该函数只有唯一的不动点 阶乘函数
第3章 控制流分析 函数的最小不动点 求解含函数变量f的方程 f=入n.ifn=0then1 else if n 1 then f3) else fn -2)end 一相应高阶函数有无数个不动点 当n是偶数时，结果是1 当n是奇数时，结果是a(a可以任取) 最小不动点 n为偶数时，结果是1；n为奇数时，结果未定义
第3章 控制流分析 • 函数的最小不动点 – 求解含函数变量f 的方程 f = n. if n=0 then 1 else if n = 1 then f(3) else f(n − 2) end – 相应高阶函数有无数个不动点 当n是偶数时，结果是1 当n是奇数时，结果是a（ a可以任取 ） – 最小不动点 n为偶数时, 结果是1; n为奇数时, 结果未定义
第3章 控制流分析 函数最小不动点的计算 -例：F 入fn.ifn=0then1 else n×fn-1) end -lfp(F)= FnL)(n=0,1,…) -0(L)=⊥（表示处处无定义的函数） -F1(L)=F(L) =(入fn.ifn=0then1 else n×fn-l)end)L =入n.ifn=0then1 else n×L(n-l)end ={K0,0)
第3章 控制流分析 • 函数最小不动点的计算 – 例：F f. n. if n=0 then 1 else n f(n − 1) end – lfp(F) = Fn (⊥) (n = 0, 1, …) – F0 (⊥) = ⊥ (表示处处无定义的函数) – F1 (⊥) = F(F0 (⊥)) = ( f. n. if n = 0 then 1 else n f(n − 1) end ) ⊥ = n. if n = 0 then 1 else n ⊥(n − 1) end = {0, 0!}
第3章 控制流分析 函数最小不动点的计算 -例：F 入f入n.ifn=0then1 else n×fn-l)〉 end -lfp(F)= Fm(L)(n=0,1,… -F2(L=F(F(L =(入f入n.ifn=0then1 else n×n-l)end)F(L) =入n.ifn=0then1 else n×F(L)(n-l)end ={K0,0),〈1,1} 依次逐步计算可得：⊥，{K0,0)},{《0,0),〈1,1}， {K0,0),〈1,1，〈2,2}，.（构成一个上升链
第3章 控制流分析 • 函数最小不动点的计算 – 例：F f. n. if n=0 then 1 else n f(n − 1) end – lfp(F) = Fn (⊥) (n = 0, 1, …) – F2 (⊥) = F(F1 (⊥)) =( f. n. if n=0 then 1 else n f(n −1)end)F1 (⊥) =n. if n = 0 then 1 else n F1 (⊥) (n − 1) end = {0, 0!, 1, 1!} – 依次逐步计算可得：⊥,{0, 0!}, {0, 0!, 1, 1!}, {0, 0!, 1, 1!, 2, 2!}, … (构成一个上升链) – lfp(F) = Fn (⊥) = {0, 0!, 1, 1!, 2, 2!, …}