Wiki. “函数式编程” [函数式编程]

SimplicialCat

#计算机科学

相关概念

一般的过程式编程语言的求值顺序是作用序求值 (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

为了在当前已有的计算机上实现正序求值, 你需要维护名为 thunk 的数据结构, 来区分已求值和未求值的表达式, 这会导致

你需要大量的内存空间;

你需要做大量的内存读写操作; 而很不幸在本位面的计算机设备上:

内存很贵;

和做计算相比, 内存访问起来很慢;

虽然内存全名随机访问存储器 (random access memory, RAM), 但是你真的随机访问的话, 内存访问起来会更慢, 只有你在一段时间内访问比较相近的内存地址, 内存访问才比较快. 这些因素导致在本位面中, 函数式的编程语言有运行速度慢的刻板印象, 必须要非常努力的进行优化 (比如 GHC), 才能得到和过程式编程语言不相上下的运行速度, 从而限制了函数式编程的传播和推广.

Haskell