Call-By-X

发表于 更新于

2021 年 5 月 14 日

我想谈一谈我对 call-by-value、call-by-name、call-by-need、call-by-reference 的理解。这只是我的理解，应该与 Wikipedia 有出入——但我仍然坚持我的理解。

太长不看

Call-by-value 与 call-by-name 放在一起比较时，call-by-value 表示函数调用时，实参要在调用函数前求到一个值。

Call-by-value 与 call-by-reference 放在一起比较时，call-by-value 表示函数调用时，实参的地址中的内容，而不是地址本身，被传入函数。

所以，call-by-value 这个词在不同的语境下的含义（居然）是截然不同的，这就是问题的根源。

不可变变量和值，以及 Call-by-Value

在（一些）函数式语言的世界，如 Haskell，变量是不可被再次赋值的。所以假使有 let x = True，那么 x 和 True 可以划上等号：凡是见到 x 的地方，都可以替换成 True。因为 x 不可变，我们也不需要关心 x 究竟是存储在内存中，还是存储在火星上，或者说我们有魔法，x 不占用任何存储空间——这根本不重要，x 就是个常量，我不会去找到 x 再它把它的内容换掉。

现在我们解释值这个概念。程序语言理论中，一门简单的语言可以只有表达式（expressions），或称之为项（terms），并且这些项最终都可以计算成值（values）。换句话说，值是不可再计算的项，它通常可以是项的子集。

例如，可以认为 1 是值但 2 + 3不是，因为 2 + 3 还可以计算到 5。或者说项 2 + 3 的值是 5，而项 1的值就是 1 本身。

有了值的定义，便可以解释 call-by-value、call-by-name、call-by-need。

对于函数定义 f(x) = x + x，项 t = 2 * 3 和函数调用 f(t)

  • Call-by-value 指的是先把项 t 的值求出来，即 6，再将其传给形参 x，进行函数调用。
  • Call-by-name 指的是将 t 直接传给形参，进行函数调用。也就是说，函数体内的（自由出现）的 x 都被替换为 t，即函数体变为 t + t。此时才会去求 t 的值，它还被求了 2 次。
  • Call-by-need 同 call-by-name，但保证 t 只求一次，可以用 memoization 实现。

小 tip：call-by-name 不一定就比 call-by-value 慢——例如，如果 name 在函数体内没被用到，则它根本不会被计算。

到这里，一切安好。

可变变量、地址、值，以及 Call-by-Value

然而，在函数式之外的世界，写程序几乎就是创建一些存储单元，再不断改变这些存储单元的内容——从图灵机开始，我们便知道纸带有左移右移操作和读写操作——这便是“万恶的源泉”。

为了方便地访问预先创建的存储单元，我们给这些存储单元加上标签，并起名为变量。例如，int a = 0; 这条语句创建了一块存储单元，将其中的内容设置为 0，并且可以用标签（变量） a 方便地找到。

那么就产生了一个严肃的问题。当我提到 a 的时候，我到底指的是那一块存储空间呢，还是那一块存储空间里面的内容 0 呢？a = a + 100; 这条赋值语句中，等号左右的 a 都是些什么货色呢？大多数命令式语言，为了方便书写程序，都会自动将 = 左边的 a 解释为存储空间（的别名），而将 = 右边的 a 解释为存储空间中的内容。所以 a = a + 100 执行后，a 存储单元的值就从 0 变成了 100。

因此，存储单元——引用，reference；存储单元的内容——值，value。

这就有了 call-by-value 和 call-by-reference 的区别。还是对于函数定义 f(x) = x + x，项 t = 2 * 3 和函数调用 f(t)

  • Call-by-value 指的是把项 t 的存储空间的内容传给实参。
  • Call-by-reference 指的是把项 t 的存储空间本身的地址、位置传给实参。

所以这里的 call-by-value 和 call-by-reference，与上一小节的 call-by-value 和 call-by-name，根本就是两个不相交的维度的概念，但却都使用了 call-by-value 这个词。

总结

所以说，call-by-value 在不同语境下会有不同的含义，既可以指代将 term 计算成 value 再做函数调用，也可以指代将存储地址的内容（而非地址本身）传给函数的参数。

大多数语言都是将 term 计算成 value 再做函数调用（也即 strict），如 C 系、Java 系（好吧，jvm 系）。也有 call-by-name 和 call-by-need 的（统称为 non-strict），如 Haskell。

C 系语言一般是传存储单元的值，array 例外。如果想传存储单元的地址，需要使用 & 符号。Java 系语言一般是传存储单元的地址，并且，（暂时还）没办法传存储单元的值。

思考题：设有函数

1
2
3
4
5
fn f(x) =
    print(x)
    x := x + 100
    print(x)
end fn

如果使用 call-by-name，f(2+3) 会得到什么样的函数体？x := x + 100 会变成 2 + 3 := 2 + 3 + 100 吗？

后记

后来竟然觉得 call-by-reference 可能说的是这种：变量 obj 有自己的地址，地址中存着一个值，但这个值永远是个固定大小的 pointer，指向（heap 里的）某个真实的存储空间——所以它仍然可以看作是地址。函数调用的时候就传那个指向（heap 里的）某个真实的存储空间的 pointer。遂去查了查，这个居然叫 call-by-sharing？哎呀哎呀，行吧，感觉这一领域术语太多太乱，会用就行，不需特别理解。