《第3章控制流分析》由会员分享，可在线阅读，更多相关《第3章控制流分析（6页珍藏版）》请在金锄头文库上搜索。
1、第第3章章 控制流分析控制流分析内容概述内容概述定义一个函数式编程语言，变量可以指称函数定义一个函数式编程语言，变量可以指称函数以以dynamic dispatch problem为例（作为参数的为例（作为参数的函数被调用时，究竟执行的是哪个函数）函数被调用时，究竟执行的是哪个函数）规范该控制流分析问题，定义什么是可接受的控规范该控制流分析问题，定义什么是可接受的控制流分析制流分析定义可接受分析在语义模型上的可靠性定义可接受分析在语义模型上的可靠性讨论分析算法讨论分析算法加上数据流分析加上数据流分析加上上下文信息加上上下文信息第第3章章 控制流分析控制流分析函数的不动点函数的不动点若若f(x)
2、 = x，则，则x是函数是函数f 的不动点的不动点求解含函数变量求解含函数变量f 的方程的方程f = n. if n=0 then 1 else n f(n 1) end看成找下面函数的不动点看成找下面函数的不动点 f. n. if n=0 then 1 else n f(n 1) end该函数只有唯一的不动点该函数只有唯一的不动点阶乘函数阶乘函数第第3章章 控制流分析控制流分析函数的最小不动点函数的最小不动点求解含函数变量求解含函数变量f 的方程的方程f = n. if n=0 then 1 else if n = 1 then f(3) else f(n 2) end相应高阶函数有无数个不
3、动点相应高阶函数有无数个不动点当当n是偶数时，结果是是偶数时，结果是1当当n是奇数时，结果是是奇数时，结果是a （ a可以任取可以任取 ）最小不动点最小不动点n为偶数时为偶数时, 结果是结果是1; n为奇数时为奇数时, 结果未定义结果未定义第第3章章 控制流分析控制流分析函数最小不动点的计算函数最小不动点的计算例：例：F f. n. if n=0 then 1 else n f(n 1) endlfp(F) = Fn ( )(n = 0, 1, )F0 ( ) = (表示处处无定义的函数表示处处无定义的函数)F1 ( ) = F(F0 ( )= ( f. n. if n = 0 then 1
4、else n f(n 1) end ) = n. if n = 0 then 1 else n (n 1) end = 0, 0! 第第3章章 控制流分析控制流分析函数最小不动点的计算函数最小不动点的计算例：例：F f. n. if n=0 then 1 else n f(n 1) endlfp(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! 依次逐步
5、计算可得：依次逐步计算可得： , 0, 0! , 0, 0! , 1, 1! , 0, 0! , 1, 1! , 2, 2! , (构成一个构成一个上升链上升链)lfp(F) = Fn ( ) = 0, 0! , 1, 1! , 2, 2! , 第第3章章 控制流分析控制流分析归纳和余归纳归纳和余归纳(coinduction)归纳法归纳法初始条件、迭代规则、最小化条件初始条件、迭代规则、最小化条件字母表字母表A上的串集上的串集A 归纳定义如下归纳定义如下(1) A ; (2)若若a A且且x A , 则则ax A ;(3)除此除此以外，以外， A 不含其它元素不含其它元素余归纳法余归纳法迭代规则迭代规则(循环条件循环条件)，最大化条件，最大化条件流可以通过余归纳法来定义流可以通过余归纳法来定义(1) 若若t是是A上的流且上的流且a A，则，则(a,t)也是也是A上的流；上的流；(2) A上的流集是满足上述规则的最大集合上的流集是满足上述规则的最大集合
