Skip to content

传名调用

Call by name · CBN

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

条目类型
模型

形式陈述

传名调用(call-by-name)在函数应用 (λx.t)s 中不先求值实参 s,而直接执行

(λx.t)st[x:=s].

小步语义中,典型的弱传名求值上下文不进入 λ 抽象体,并优先计算最外层、最左侧的应用位置。每次函数体使用参数时,代入的实参表达式都可能重新求值。按需调用在非严格性之上增加有身份的 thunk 与首次求值后的堆更新;这些共享机制不属于传名替换本身。

直觉

传名调用把实参当作一份尚未兑现的计算配方,只有函数体真正需要它时才展开。未使用的参数完全不会求值,因此它能绕过无关的发散或错误。代价是同一参数出现多次时,配方也可能执行多次;“懒”只表示延后,不表示自动共享。最外最左策略还具有一个理论优势:在纯 λ 演算中,只要项存在 β-正规形,这种正规序能够找到它。

例子与边界

(λx.0)Ω0,因为参数从未使用。对 (λx.x+x)(1+2),传名替换得到 (1+2)+(1+2),两个副本分别求值;按需求调用则会把第一次得到的 3 共享给第二处。

边界出现在副作用中。若实参是“读取并递增计数器”,传名调用在参数出现两次时会执行两次副作用,按需求调用只执行一次,传值调用则在进入函数前执行一次;三者可产生不同结果。因此不能把纯 λ 演算中的等价直觉不加说明地搬到有状态语言。

推论与应用

传名调用解释了惰性语言的语义起点,并与Church–Rosser 定理、标准化定理相联系。实际惰性语言通常采用按需调用来共享一次绑定的结果;thunk 状态、黑洞检测和空间行为由专门页面给出,本页只保留非严格替换与可能重复求值的语义。

宏展开、短路逻辑和控制结构也常表现出“参数不是先算好的值”的行为。与传值调用的对照是研究上下文等价、严格性分析和效果系统的基本案例。

参考资料
  • 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。
关系图谱6 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系