原文标题：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..zu]
]
-- 按顺序执行列表中的所有更新操作
-- 这里用 mapM_ 来执行更新
do_loops = do { array <- newSTArray (1,4) 0;
mapM_ (\(idx,new_value) -> writeSTArray array idx new_value) $
ex1_update_list 4 3;
return array }
-- 试运行上述代码，观察其返回值
array_to_list array = sequence
[ readSTArray array i |
let (lwb,upb) = boundsSTArray array, i<-[lwb..upb] ]
compute = runST( do_loops >>= array_to_list )
为了加载上述代码，读者需要带 -98 命令行参数启动 Hugs1；加载完成后，在 REPL 提示符下输入 compute 即可查看结果。请注意，在函数式版本的代码中，代码中的嵌套循环看起来被翻了个底朝天：原本在内循环的「数组赋值」操作现在出现在了外循环中，变成了 do_loops 中的一条语句。
第二个例子则要简单得多：给定整数数组 array[lwb..upb]，求数组中大于等于 7 的元素的和。同理，我们先从一个命令式实现开始：
int sum = 0;
for(int i=lwb; i<upb; i++)
if(array[i] >= 7)
sum += array[i];
对该循环进行分析，可以发现数组上不存在数据流和控制流的依赖关系：程序只是读取数组，而且最终会读取数组中的所有元素。这意味着我们可以预读数组的所有元素，而且可以很容易地把循环并行化。
-- 推测式预取数组所有元素，该操作不安全
-- 我们假设代码不存在任何数据流依赖关系
import IOExts(unsafePerformIO)
prefetch_array array = map (unsafePerformIO . stToIO)
[ readSTArray array i |
let (lwb,upb) = boundsSTArray array, i<-[lwb..upb] ]
-- 我们借用之前定义的 do_loops 函数来获取用于处理的数组
ex3 = sum $ filter (>=7) $ prefetch_array $ unsafePerformIO $
stToIO do_loops
正如我们的分析所示：求和循环确实是纯函数式的。prefetch_array 会「推测性」地预取数组元素——用数据库领域的术语来说，该函数进行的是脏读［dirty read］。我们注意到 map 会非确定性地将函数应用到列表元素上，但我们不存在数据依赖，所以这一点并不重要。同理，map 的内部循环也是纯函数式的。
第三个例子则是一个愚蠢的排序问题：对数组 [0..(n-1)] 按升序排序。
for(i=1; i<n; i++)
{
bool done_already = true;
for(j=0; j<n-i; j++)
if( array[j] > array[j+1] )
{
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
done_already = false;
}
if( done_already )
break;
}
这一算法在小数组上应该运行得不错，如果数组的顺序已经（基本）正确，那就更好不过了。
但对于超标量 CPU 而言，想要高效执行这段命令式代码其实相当复杂。我们可以看到迭代过程中存在复杂的数据依赖关系、代码对数组的读取和写入、依赖于数组元素和迭代历史记录的条件分支，以及两个循环间的控制流依赖关系等等。
下面用 Haskell 语言展示了这一问题的两种解法，两者都使用了快速、命令式的 STArrays；两者都试图将命令式部分和函数式部分分离：命令式部分在 Monad 中执行，而函数式部分则是普通 Haskell。这两种解决方案关系密切，在编写两种方案时，作者也有意强调了它们之间的相似关系。
首先提出的是最怪异的解决方案：
data Predicate = P1 -- 谓词寄存器 1
| P2 -- 谓词寄存器 2
| Ptrue -- 真值
| Pfalse -- 假值
deriving Show
-- 每条指令都引用了某个谓词：仅当引用的谓词为真时，指令才会执行
data Instruction = LDA Predicate Integer -- 从某内存位置读取到累加寄存器 A 中
| LDB Predicate Integer -- 从某内存位置读取到累加寄存器 B 中
| SET_gt Predicate Predicate -- 若 A>B，设置谓词
| CLR Predicate Predicate -- 清除谓词
| SET Predicate Predicate -- 设置谓词
| STA Predicate Integer -- 将累加寄存器 A 存入某内存位置
| STB Predicate Integer -- 将累加寄存器 B 存入某内存位置
| HALT Predicate
deriving Show
ex2_instr_stream n = concat
[[SET Ptrue P2] ++
concat [[LDA Ptrue j, LDB Ptrue (j+1), SET_gt Ptrue P1,
STA P1 (j+1), STB P1 j, CLR P1 P2] | j<-[0..(n-i-1)]] ++
[HALT P2] | i<-[1..(n-1)]]
这一解决方案展示了一种所谓谓词指令执行［predicate instruction execution］方式，目前最先进的 CPU（如 Itanium）以及 Konrad Zuse 的 Z-3 中就使用了这种指令执行方式。读者不妨自己在 Hugs 提示符下输入 ex2_instr_stream n 并观察结果，但我们现在先暂时按下不表，来看看第二种解决方案：
ex2_hi_stream n = concat
[ [\array done_already -> return $ Just True] ++
[\array done_already -> do {
a <- readSTArray array j;
b <- readSTArray array (j+1);
if a > b then
writeSTArray array j b >>
( writeSTArray array (j+1) a >>
( return $ Just False ))
else return $ Just done_already } | j<-[0..(n-i-1)] ] ++
[\array done_already -> return $
if done_already then Nothing else Just done_already]
| i<-[1..(n-1)]]
这一解决方案是 ex2_instr_stream 的高级版本；两个版本的函数都会产生一条用于执行的指令流，它们都把嵌套的循环规约成了一串指令流——这就是循环的「纯函数式」部分，而真正执行指令的代码就代表了循环的「命令式」部分。
-- fold 的一种变体，支持提前终止
executor init_state commands array = run init_state commands
where
run Nothing _ = return array
run _ [] = return array
run (Just state) (cmd:cmds) = (cmd array state) >>=
\new_state -> run new_state cmds
-- 用于排序的简单数组
sample_array = do {
array <- newSTArray (0,4) 0;
writeSTArray array 0 5;
writeSTArray array 1 7;
writeSTArray array 2 1;
writeSTArray array 3 8;
writeSTArray array 4 9;
return array }
ex2_hi = runST( sample_array >>=
executor (Just True) (ex2_hi_stream 5)
>>= array_to_list )
这些解决方案确实有效：在 Hugs 提示符下输入 ex2_hi 即可查看结果。
我们之前曾提出 ex2_hi_stream 生成的高级指令流与 ex2_instr_stream 生成的低级指令流存在关系。事实也确实如此，高级指令与低级指令间有一映射 alu 满足：
ex2_lo = runST( sample_array >>=
executor (Just (0,0,True,True)) (map alu $ ex2_instr_stream 5)
>>= array_to_list )
alu 代表我们虚拟机的算术逻辑单元［Arithmetic Logic Unit, ALU］，该函数的具体实现参见附录。而 executor 函数代表了我们虚拟 CPU 的控制单元。
分析循环迭代间的数据流和控制流依赖关系、调度指令、实现互锁［interlock］机制、预取内存数据……这些都是 CPU 或高级编译器的工作。但另一方面，人类在设计算法时也需进行类似的分析，从而分离计算的纯函数部分和命令式部分。函数式编程似乎要比人们所普遍认为的更接近裸机［bare metal］ 。
这里还可以举出更多的例子：譬如为了用函数式语言重写各种数值算法（高斯消除、卷积滤波等），对其进行数据流/控制流依赖性分析。但这篇文章已经太长，太无聊了。
后日谈
Andrew W. Appel 在他的文章 «SSA is Functional Programming» (ACM SIGPLAN Notices v. 33, no. 4, pp. 17-20, April 1998) 中写道：
The SSA (Static Single Assignment) algorithm … is automatically converting a FORTRAN or C procedure into a well-structured functional program with nested scope. Actually, I’ve only shown what to do with scalar variables. Arrays are handled in high-powered (parallelizing) compilers using sophisticated dependence analysis techniques [15], which is another way of extracting the functional program inside the imperative one.
译：所谓静态单赋值形式［Static Single Assignment, SSA］算法……就是一种自动将一个 Fortran 或 C 程序转换成一个结构良好，具有嵌套作用域的函数式程序的算法。实际上，本文中只展示了如何处理标量变量，高端（并行化）编译器中往往会通过复杂的依赖性分析技术来处理数组 [15]，这也是一种在命令式程序中提取函数式程序的方法。
引文的最后一段正是本文的主旨：我们人工分析了几个就地更新数组的代码片段的依赖性，通过分析，我们提取了命令式程序中的纯函数式部分。而函数式以外的部分则需要序列化，这些代码可以交给 ST monad 处理。
附录：ALU 函数
-- ALU State AccA AccB P1 P2
type ALUState elem = (elem,elem,Bool,Bool)
type Storage a elem = STArray a Integer elem
alu:: (Ord elem) => Instruction -> Storage a elem -> ALUState elem ->
ST a (Maybe (ALUState elem))
alu instr array state@(a,b,p1,p2) = case instr of
LDA p loc -> provided p $
readSTArray array loc >>= \a->return $ Just (a,b,p1,p2)
LDB p loc -> provided p $
readSTArray array loc >>= \b->return $ Just (a,b,p1,p2)
STA p loc -> provided p $
writeSTArray array loc a >> (return $ Just state)
STB p loc -> provided p $
writeSTArray array loc b >> (return $ Just state)
SET p P1 -> provided p $ return $ Just (a,b,True,p2)
SET p P2 -> provided p $ return $ Just (a,b,p1,True)
CLR p P1 -> provided p $ return $ Just (a,b,False,p2)
CLR p P2 -> provided p $ return $ Just (a,b,p1,False)
SET_gt p P1 -> provided p $ return $ Just (a,b,a>b,p2)
SET_gt p P2 -> provided p $ return $ Just (a,b,p1,a>b)
HALT p -> provided p $ return Nothing
where
provided P1 = if p1 then id else \_ -> return $ Just state
provided P2 = if p2 then id else \_ -> return $ Just state
provided Ptrue = id
provided Pfalse = \_ -> return $ Just state