一般的过程式编程语言的求值顺序是作用序求值 (applicative order evaluation), 优先展开最靠内的 β-可约化式 (β-redex).
一般的函数式编程语言的求值顺序是正序求值, 每次化简都选择化简最外层的 β-可约化式.
比如说我们首先定义 bottom = (λx.xx)(λx.xx), 这是一个 β-redex; 对它 β-化简会得到自己, 所以它没有 β-范式. 现在考虑表达式 (λxy.x)(λx.x)(bottom), 那么按照作用序求值, 你会先展开 bottom, 化简就不会停止; 按照正序求值, 你会先展开 K = λxy.x 得到 λx.x, 到达范式.
比如说你在 Haskell 里面写 take 10 (iterate (+1) 0), 那么 iterate (+1) 0 是无穷列表 [0, 1, 2, 3, ...], 但是这个程序可以终止, 并输出有限的列表 [0, 1, 2, ..., 9], 在进入函数 take 10 前不需要把它的参数 iterate (+1) 0 完全求值了.
「如果求值有任何希望终止，那么正序求值总是可以让它终止」这个事实，我理解中它基本上是整个函数式编程的基础之一.
— 董子楷, 2025-04-02