前面使用let和proc,可以进行函数的定义,但是并不支持在函数内部递归地调用改函数,究其原因,是在函数调用时,即proc的body语句执行的时候,它所引用的环境env,是在let语法中,扩展指向procedure的变量之前,所以在当时的env中,是没有指向该函数的变量的。 本文使用letrec扩展语法,实现函数的递归调用。
代码在https://github.com/wangdxh/eopl3-in-python letrec目录下
letrec语法如下:
letrec 后跟着 函数的名称,一对圆括号内包含着函数的参数名称,紧接着是 = 和 函数体,最后 in 和 要执行的body语句。
letrec解析的时候,函数的名称,参数,函数体,会直接解析出来,这里将函数的定义扩展进环境env,let+proc 扩展的时候通过procedure,将变量,body,“当时的环境”,通过闭包生成一个函数,当这个函数体真正执行的时候,所使用的env,生成函数时“当时的环境”+变量和其赋值的扩展。所以let声明的指向函数的变量,并不在执行的env中。
这里扩展进环境变量的时候,不用procedure生成一个闭包的函数,而是把相应的函数名称,参数,和body扩展到环境中。
现在有2个向环境中扩展变量和其对应值的函数。
从环境中查找变量的时候,进行了调整,当发现查找的是letrec对应的函数名称时,将其函数参数,body,和正在查找的env(注意这个env很重要,这是最小包含着函数名称的环境,相当于是letrec,将函数名称扩展到环境中后的那个环境)放在一个list里面,原来的其他变量和单个对应值查找也进行了微调,也放在list里,便于统一处理。
代码中唯一用到查找变量的地方就是var_fun,这里针对变量的名称,去查找对应的值,如果发现有3个元素的list,就是letrec定义的函数,1个元素就是原来的处理。如果是letrec的信息,就使用proceduer函数生成一个闭包函数,去执行,和let一致,这里注意list内的最后一个env,是最小的包含着letrec定义的函数名的环境。所以这个时候在函数调用的时候,在其环境中是包含着letrec定义的函数名的,借此来完成递归调用。
整个完成递归流程的处理点就是,生成procedure的时候,最后的env环境是包含着letrec定义的函数名的最小的环境集合。
下图是一个测试一个数值是否为奇数的例子