指令调度与命令式/函数式编程的相似之处
原文标题：Similarity between instruction scheduling and imperative functional programming 作者：Oleg Kiselyov 原文链接：https://okmij.org/ftp/Haskell/fp-arrays-assembly.txt 将「典型的命令式编程代码」转换为函数式编程代码的过程，似乎有些类似于现代 CPU 编译器中使用的数据流和控制流依赖分析——所谓典型命令式代码，就是涉及了嵌套循环和可变数组的「典型数值计算」代码。下面将考虑三个此类转换的例子。 第一个例子在本主题之前的回帖中就已经讨论过，为了使该代码的内循环更有意义，这里对其稍作修改。该示例的命令式形式为 for(int i=1; i<=zx; i++) for(int j=1, a=i+1, b=i*j; j<=zx; j+=1, a+=1, b+=1) for(z=j; z<=zu; z+=2) array[z] = a, array[z+1] = b; 这个例子其实很简单。我们注意到代码只会写入 array，而不会读取 array，也没有控制流分支，唯一需要担心的就是更新 array 操作的顺序性问题。那么，解决方案就呼之欲出了——首先生成一个「更新列表」，这个列表告诉我们应该将数组的某个元素设置为某个值；生成列表之后，我们再按列表执行更新。我们可以用函数式编程生成这样的列表，然后用命令式编程——Monad 来执行。而且由于 Haskell 的惰性求值特性，我们可以一边生成更新列表的元素，一边执行。 下面是对应的 Haskell 代码 import ST -- 提取代码中所有更新数组的操作 ex1_update_list zx zu = concat $ [ [(z,a), (z+1,b)] | i <- [1..zx], (j,a,b) <- takeWhile (\(j,_,_) -> j<=zx) $ iterate (\(j,a,b) -> (j+1,a+1,b+1)) (1,i+1,i*i), z <- [j,j+2....