自己动手写解释器(5):变量的作用域和递归

(作者码字辛苦，转载请以超链接形式注明出处)

本系列的所有代码都已经/即将可以在这里找到：

在之前的过程中，为了简便起见我们都用一个全局变量表来保存局部变量。现在，我们尝试将其分离，并进一步的研究递归的原理。

对于一个任意一个结点，我们都有一个域，它指向一个变量表，通过这个变量表， 标明该结点所在的作用域存在的所有变量，我们可以根据变量名，获取到该变量代表的值。

example:

def fun(var){

    var = var+1;

}

以这一小段代码为例：

1.这一小段代码会生成一个FUN结点，我们记为funnode，该结点描述了个方法的语法树。

2.每次调用这段代码，也就是开始执行这个结点的时候，都会重新生成一个新的哈希表，用于记录fun函数这个作用域的所有局部变量。

3.在传递参数时，var根据传如的实参值，注册入哈希表中

4.执行语句时，先从哈希表中取出var,再执行var+1,最后赋值，更新哈希表中的var

5.执行完毕，释放掉这个哈希表。

对于所有funnode的子结点，他们都共享同一个哈希表。

每次调用的时候，我们都会新建一个新的表。以保证这个是局部变量。所以，当执行到step.2的时候，我们需要保证新的哈希表，在所有子节点中，都被更新了。

根据这种需求，可以设计出如下的数据结构。这个结构用了指向指针的指针。

每个节点存储的变量表，都是一个指向 Hash*的指针，即图中的 Pointer to Hash.

这样，当我们在根节点funnode中，更新了这个这个Pointer to Hash所指向的位置，即图中虚线所示，那么其所有子结点的变量表这个域，都可得到更新。

我们再考虑递归调用的特别之处。还是以一个小的代码段为例子。

def fun(var){

    if(var<3) {var = var+1; fun(var);};

}

假设我们调用的fun = 1,那么这个递归的方法，其深度为3层。

1. 执行fun(1),新建变量表, var = 1, 满足var<3, 执行var = var+1, 再执行fun(2)

2. 执行fun(2),新建变量表, var = 2, 满足var<3, 执行var = var+1, 再执行fun(3)

3. 执行fun(3),新建变量表, var = 3,  不满足var<3，返回上层

4. 返回上层

5. 返回上层

我们可以看到，fun被执行了3次，最深处的时候同时存在的变量表有3个，但是funnode在内存中只有一个.

因为递归调用的时候还需要回退，返回到上层的时候，我们仍然需要将变量表恢复到调用前的状态，所以在每次进入下一层的时候，我们需要保存现场，完成之后再恢复现场。

示意图以及部分代码如下：

1.在第一调用时，我们新建一个哈希表，这时，funnode的变量表就是紫色的方块的内容

2.进入下层时，我们仅需保存紫色表的地址0xac00,然后新建一个蓝色的哈希表0xbc00,将指针指向它

3.执行完一层，回退的时候，我们先将蓝色的哈希表free掉，再将指针指回0xac00,这样就恢复了现场。

更换变量表的过程除了建立新表之外，只需移动一下指针即可。

typedef struct {
	size_t size;
	void** table;
} structHash, *Hash;
...

typedef struct _Node{
	int op;
	char ismarkedforfree;
	struct _Node* left;
	struct _Node* right;
	Data* data;
	Hash* ptrlocalvars;
	Hash* ptrfuncs;
}Node;
...

Data ExFUNCALL(Node* node){

	//create new local vars and update
	printf ( "Executing FUNCALL\n" );
	Hash backup = *(node->ptrlocalvars);
	Hash localhash = initialHash(65536);
	*(node->ptrlocalvars) = localhash;

	//set param
	if(node->left!=NULL){
		Data params = ExGET(node->left);
		ExPARAMS(node->right->left, params.value.arrayValue);
	}
        //record return
	Data ret = Ex(node->right);
        //free hash and restore local vars
	freeHash(localhash);
	*(node->ptrlocalvars) = backup;
	return ret;
}

这里，还能够引申出一点对递归的认知。对于递归算法来说，每次进入一次调用，都会新建一个崭新的变量表，很显然，这个表实际的所占用的空间是一定，递归的层次越深，建立的表就越多，消耗内存也越大。但是，其消耗的内存仅与变量表的实现有关，例如例子中，变量表的大小是65536，每层中额外消耗的内存，最多就是在这里。至于方法中到底使用了几个变量和复杂程度，和内存消耗无关，实际上一个无参的简单递归调用方法和一个复杂的方法，所占用的内存是一样的。把递归方法中的一些变量写入到全局变量中，并不能减少内存的消耗。