Skip to content

传名调用

Call by name · CBN

把尚未求值的实参表达式直接替入函数体且只在需要时展开的策略。

形式陈述

传名调用在 (λx.t)s 中不先求值 s,而直接无捕获替换为 t[x:=s],只在需要处继续归约。标准左最外归约若某项存在 β-正规形,就能找到它。传名可能重复求值同一实参;带共享缓存的 call-by-need 才是通常所说的惰性求值。

直觉

函数拿到的是尚未计算的表达式;只有真正使用它时才展开,所以未使用参数不会造成发散或副作用。

例子与边界

(λx.0)Ω0。在 x+x 中,传名会把实参展开两次,而 call-by-need 只计算一次并共享。含副作用时直接复制表达式会改变执行次数,因此纯 λ 演算结论不能不加说明地迁移到命令式语言。

推论与应用

传名用于理解正规序、宏展开和惰性语言语义,也是比较求值策略可观察行为的标准基线。

参考资料
  • Robert Harper, Practical Foundations for Programming Languages, 2nd ed., Cambridge University Press, 2016,Parts I–XVIII。
  • Gordon D. Plotkin, A Structural Approach to Operational Semantics, DAIMI FN-19, 1981; reprinted 2004,Full report。