在众多编程语言复杂而不统一的设计的影响下,“引用类型”和“值类型”的问题,已经是一个相当混乱的问题了。在这里简单讲一下我的理解。

首先,我们必须知道这两个概念是什么意思。

  • 绑定(binding)。绑定是编程语言里一个符号的解释。
  • 环境(environment)。环境是所有绑定的形成的复合数据结构。

简单地说,在scheme里,我们使用


(define x 1)

(+ x 1)

就是把1这个值绑定到x这个符号上,下面(+ x 1)中的x就可以被解释为1.

**然而,事情其实没有这么简单。**下面,我们以C/C++为例,谈谈一个符号绑定上的,究竟是什么东西。

将符号解释为值

考虑下面的代码:


int a = 0;
printf("%d", a);

我们注意到,a这个变量,是可以被替换为0的,上面的代码和下面的代码等价:


printf("%d", 0);

这个特性叫做引用透明性(Referential transparency)。其本质就是,一个符号对应一个不变的值,就像上面的代码里,我们有:


a : 0

a这个符号,在这个词法作用域里,处处被解释为0,只有声明一个新的a覆盖掉这个符号(C里面不允许这样),a才能不被解释为0.

这才应该是所谓“a这个符号是值类型”的意义。但在C语言里,或者说在大多数命令式编程语言里,情况与此有些不同

将符号绑定为IR类型,仍然解释为值类型

“绑定上”和“解释为”的区别

简单来说,“绑定为”是实现上的概念,“解释为”是在外部观察到的现象。比如说,如果找一个C语言的REPL(类似于irb\fsi\scheme一样的东西),你输入


int a = 0;

a;

它必定告诉你:


int:0

但a这个符号到底在解释器里真正对应什么东西,仅凭这个是不能确认的。它在解释器里真正对应的东西,就是“绑定为”的东西。

IR类型和ER类型

在C语言里,一个变量是可以被赋值的:


int a = 0;
a = 2;

如果你还是让a绑定上一个值,那么必须要求绑定本身是可变的,而“可变”还不能是这样的可变:


int a = 0;
{
    int a = 2;
}

也就是说,不能是开一个新的作用域来“覆盖”,而必须是精准地改变(在这个例子里的)顶层作用域的a符号。我们先禁止这种操作,因为继续看下去,你会发现这本质上也是引用

如果a不能被直接绑定上一个值,它应该被绑定上什么东西呢?我们创造一个新的类型,叫做“IR类型”,这个符号绑定上“IR类型”.

IR类型”的构造方式为:

  • 声明一个局部变量,该局部变量的类型即为IR类型。

“IR类型”应该支持这两种操作:

  • 改变其值,记作 set(a, b),其中a为此类型的值,b为要set的值。
  • 得到其值,记作 get(a), 其中a为此类型的值,这个操作会返回最近一次set(a, b)中的b,如果没有被set过,则为未定义行为

如何去实现这个类型呢?实现这个类型的关键在于“记忆最近的b”,而在数字电路中,“记忆”的实现方式是触发器,在现代计算机中就是内存。一个比较自然的想法是,每一个IR类型值都占有一块内存。而这个想法的实现方式,就是在IR类型的实现中,记录这块内存的索引(即地址)。

我们用这种记法来写这个模型:


a : IR(location, value)

简写为:


a : location --> value

注意到,在静态语言里,set(a, b)中的B必须是某个类型的值,记此类型为B,我们这样表示这个特定的IR类型:


IR[B]

你可能会说,**这样不是把“变量”和“指针”混为一谈了吗?这和“指针”有什么区别呢?**不要着急,我们来向这个模型中加入“指针”。


&a;

这定义了一个新的操作和一个新的类型:

  • 对“IR类型”,可以用 get-ref(a),得到一个“ER类型”值
  • ER类型值有这几个操作:
    • de-ref(er),er为ER类型值且er = get-ref(ir). 这个操作会返回get(ir)
    • set-ref(er, b),er为ER类型值且er = get-ref(ir). 这个操作和 set(ir, b) 等价

把ER类型简写为:


er : location -> value

这么说,可能还不是特别清楚,我们来举个例子:


int a; // 相当于构造了一个IR类型值,并绑定到a这个符号上,可以记作 a : loc_0 --> undefined
a = 10; // 相当于set(a, 10),a:loc_0 --> 10
a; // 相当于get(a)

int * p = &a;
// 注意,这里是构造了一个IR类型值,并绑定到p这个符号上,该IR的值为一个ER类型值,应该记作:
// p : loc_1 --> loc_0 -> 10
*p = 1000;
// 相当于 set-ref(p, 1000), p: loc_1 --> loc_0 -> 1000

讲到这里,我实际上说明了一个问题:C语言的变量符号,实际上绑定到IR类型值, C语言的指针值,实际上是ER类型值,C语言的指针变量符号,实际上绑定到IR[ER]类型的值

从绑定值到解释值

从上面的例子中,我们看到,


int a = 0;

这个符号a,绑定为IR类型的值,在我们引用它时,通过


a;
<=>
get(a);

这个变换,实现了绑定值到解释值的转换。实际上,我们可以给出这时的绑定值和解释值的完整定义:

ExpVal = All C Value
BindVal = IR(ExpVal)

将符号解释为引用类型

我们知道C++中,有引用类型。就像下面这样:


int a = 0;
int &b = a;
b = 10;
a;

如果有C++的REPL,将这份代码打进去,它会告诉你:


int:10

这又是怎么一回事呢?实际上,它不过是将我们之前说的IR类型,同时也作为了一种解释值而已。

换句话说,


int &b = a;
// a: loc_1 --> value

这段代码中的b,接受的是a这个IR值本身,而不是它的解释值。b可以被记作:


b: loc_0-->loc_1-->value

这样一来,b的解释值就是


loc_1-->value

不过要注意的是,下面的代码:


int&& c = b;
// 如果没有右值引用,c应该是loc_2 --> loc_1 --> loc_0 --> value

会报错,这是因为c++用&&当作所谓的“右值引用”,导致引用值不能嵌套了。

传值(call-by-value)和传引用(call-by-reference)

在大多数语言中,函数调用都可以这样建模:


FUNCTION = BODY + ARG (+ ENV)?

BODY就是函数体,ARG就是形式参数,ENV是这个函数定义时的环境,如果有ENV,它就是一个闭包。C语言中的函数就不是闭包,所以它只有BODY和ARG。

在调用函数时,我们必须将ARG绑定上实际参数,怎么绑定就成了一个问题。

传值

传值是最自然、最合理的方法。

在传值的情况下,调用函数可以写成:

  1. 求每个参数的解释值
  2. 将对应的值绑定到形式参数上
  3. 求函数体的值(面向表达式)/运行函数体(面向陈述)

传引用

传引用需要满足两个前置条件:

  1. 这个语言的符号(可以)绑定到引用类型
  2. 对应的参数绑定到引用类型

也就是说,不绑定到引用类型的符号,或者不是符号的东西(例如字面值、调用函数的结果等等),一般来说是不能传引用的。

用一句话来解释传引用,可以这样说:传引用时,传递一个绑定到IR值的符号的绑定值,而非解释值。

这个规则,应该说,叫做"General call by reference",具体到C++,应该这么说:

如果符号的解释值是一个值,那么传递这个符号绑定的IR值;如果符号的解释值是一个IR值,那么传递这个解释值。

我们以一段代码为例,解释上面的话:


void func2(int& a){
  a = 2;
  // a会绑定到 loc_a --> loc_0 --> 0
  // 所以运行后,a会绑定到 loc_a --> loc_0 --> 2
}

int main(){
  int a = 0;
  // a: loc_0 --> 0
  func2(a);
  // 传入的是 loc_0 --> 0 这个IR值
  // 汇编形式为
  /*
   * 00B48E02 8D 45 B8             lea         eax,[a]  
   * 00B48E05 50                   push        eax  
   * 00B48E06 E8 AE 87 FF FF       call        func2
   */
  int &b = a;
  // b: loc_1 --> loc_0 --> 2
  func2(b);
  // 传入的是 b 的解释值 loc_0 --> 2
  // 汇编形式为
  /*
   * 007B8E02 8B 45 AC             mov         eax,dword ptr [b]  
   * 007B8E05 50                   push        eax
   * 007B8E06 E8 AE 87 FF FF       call        func2
   */
}

为啥C++的传引用和别的语言不太一样呢?这就要从那些带GC的语言说起了。

某些具有GC的语言:将符号绑定到引用类型,解释为值或引用类型

IER类型

预测一下下面的三个带GC的语言,运行差不多代码的结果:

C#:


void func(List<int> a){
    a[0] = 1;
}
var a = List<int>() {1, 2, 3};
func(a);

ruby:


a = [1,2,3]
def func a
  a[0] = 0
end
func a

scheme:


(define func
  (lambda (x)
    (vector-set! x 0 0)))
(define a (vector 1 2 3))
(func a)

先要提醒一句,这三个语言全部是传值的(C#可以传引用,默认传值)

这三段差不多的代码都会得到一个结果–a变成了 {0, 2, 3}.

为什么呢?因为在这三个语言中,数组这个结构,都是一个类似于ER类型、有IR类型的某些特征的值。

这个“类似于ER类型、有IR类型的某些特征的值”,我把它叫做“IER”类型值。

ER类型值的构造方法为:

  • 每当构造一个新的“引用类型值”(比如一个新的对象)时。

例如,.Net IL的newobj指令会构造一个IER类型值,并把它放在求值栈(evalution stack)的栈顶。

IER类型的行为为:

  • IER类型值的解释值为IER类型值本身
  • 通过IER类型的值a,可以获得a指向的值(但在绝大多数有GC的语言中,用户不能这样做
  • 通过IER类型的值a,可以获得a指向的值的一部分(例如,a指向的值是一个对象,那么可以通过a来获得某个成员的值、调用成员方法)
  • 通过IER类型的值a,可以改变a指向的值(“改变”的意义是模糊的,可以改变整个值,也可以改变这个值的一部分)
  • IER类型指向的值,由垃圾回收器负责回收。

我们记IRE类型的值为:

ier : loc ---> value

你也许会问,IER类型的值是IER类型本身,这个特征说明它更像ER类型。它具有IR类型的哪些特质呢?

观察这样的C#代码:


List<int> a = List<int>() {1, 2, 3};

a这个符号的绑定值的类型为:


IR[List<int>]
// 看起来像 loc_0 --> value
// 实际上是 loc_0 --> loc_1 ---> value

习惯上,这个类型标志的应该是List<int>本身,而不是对List<int>的引用。所以它形式上更像IR一些。

这样一来,整个类型体系可以被写成:


ExpVal = IER + Value
DenVal = IR[ExpVal]
IER = Ref(C# Reference Type)
Value = C# Value Type

从这里我们可以看到,此处的“引用类型”和C中的“引用类型”完全是两个东西。C中的引用类型,是IR,这里的引用类型,是IER。

IER类型的好处

  • IER类型使得程序员不需要考虑大规模对象的复制开销,因为IER类型的值是IER类型本身,赋值过程本质上是共享的。

    var a = new List<int>(){1, 2};
    // a: loc_a --> loc_1 ---> list0
    var b = a;
    // b: loc_b --> loc_1 ---> list0
  • 同时,GC的存在使得有一种可靠的方式释放该共享对象。

C#中的传引用

C#中的变量,也都是可变的,所以势必要有和IR类似的结构。(实际上就是IR)。它传引用的方式和我们前面说的一样:传引用时,传递一个绑定到IR值的符号的绑定值,而非解释值。

举个例子:


void func(ref List<int> x){
  // x被绑定到 loc_x --> loc_0 --> loc_1 ---> (list0)
  x = null;
  // x变为 loc_x --> loc_0 --> null
}

a = new List<int>();
// a: loc_0 --> loc_1 ---> (list0)
func(ref a);
// 传入a的绑定值loc_0 --> loc_1 ---> (list0)

真正的值类型

在F#、Haskell等等函数式语言里,有真正的、不可变的“值类型”。


let a = 1

上面的a,永远会被解释为1。这才是真正的“值类型”。