笔记仓库

正常人的正常笔记集

函数的函数

知らないわ そんな魔法

头等函数 (First-class Function)

一般来说,程序设计语言(编程语言)会在计算元素的使用上推行一些限制,限制最少的函数拥有最高的特权,被称为一等公民,它们有包括但不限于以下特权1

  • 可以以变量命名
  • 可以作为过程(函数)的参数传入
  • 可以作为过程(函数)的结果返回
  • 可以被包含在数据结构中

无疑是该语言下的成功元素了。函数式编程语言(functional languages)的重要特征之一是将函数视为头等成功人士,赋予这些特权。函数的名字在此仅仅是一个函数类型的变量,这些函数能和其他变量一样被计算、存储、传递,被称为头等函数。匿名函数也可以作为这样的一等公民,正如匿名用户也可以享受其他用户一样的权利,但当你怀疑这些用户在分享刚编的故事时,又想再次引用他们的经历作为参数时往往很难再找到他们。在函数式编程语言中,我们日常接触到的函数都是头等函数比如

1
2
(define (square x)
(* x x))

借助这个函数进行定义的

1
2
(define (square-sum x y)
(+ (square x) (square y))

也是头等函数。

高阶函数 (Higher-order Function)

与头等函数相对的一个概念为高阶函数,但这并不能说是对立的(与之对立的函数称为一阶函数)。或许应该说引入头等函数这个名词,是为了引出理解高阶函数的存在。

上面说到函数和其他数值变量在应用时可以做到某种意义上的一视同仁,函数名即函数变量的名字,那么也可以被当成实参变量传入另一个过程。高阶函数至少满足以下一个条件:

  1. 至少参数中有一个是函数
  2. 返回的是一个函数

在几乎所有语言中都会定义一些idiom来方便应用,比较有代表性的有mapfoldfilter这三个高阶函数,暂时先无视命名冲突问题,为了直观理解这些函数的意义,可以自己这样定义一遍

1
2
3
4
(define (map f xs)
(if (null? xs)
null
(cons (f (car xs)) (map f (cdr xs)))))

map将一个函数f和一个listxs作为参数,xs中的每个元素作为f的参数返回的结果组成一个新的list作为map的返回结果。

1
2
3
4
(define (fold f acc xs)
(if (null? xs)
acc
(fold f (f acc (car xs)) (cdr xs))))

fold将一个函数f,初始值acc,和一个listxs作为参数,取xs中每个值x与当前的acc计算f(acc,x)作为下一个acc依次传递,如多米诺骨牌,与函数名的意义“折叠”不谋而合。

1
2
3
4
5
6
(define (filter f xs)
(if (null? xs)
null
(if (f (car xs))
(cons (car xs) (filter f (cdr xs)))
(filter f (cdr xs)))))

filter使用函数f对listxs中的每个元素进行筛选,当且仅当返回值为真(#t)时把这个元素放入作为返回结果的新list

这三个高阶函数都是把一个函数作为了自己的参数,但返回的并不一定是一个函数(mapfilter返回的必然不是,fold看具体情况),它们也可以作为头等函数成为其他函数的参数。这些函数的参数f可以用函数的变量名传入,也可以用匿名函数,实际应用时匿名函数的使用情况也非常常见,甚至可以说匿名函数的一个重要作用就是临时地定义一个高阶函数中的过程参数,如计算一个常数c和行向量xs的乘积可表示为

1
(map (lambda (x) (* c x)) xs)

再如在Python中经常问的一个基础问题:如何将dict中的元素按value的大小排序?

1
sorted(mydict.iteritems(), key=lambda (k,v): v)

Currying

当我们说一个函数有几个参数的时候我们在说什么?很多语言(如ML)中形如f(arg1,arg2,...,argn)的函数定义,看似使用了好几个参数,实际上这些参数只是作为一个长度为nlisttuple传入,本质上还是一个单参数的函数。

有时我们并不需要或者来不及等所有参数都准备齐全才能使用函数,这种所有参数塞进一个数据结构的用法让人很恼火。curry正是这样一种方法:把这样的函数转化成只有真正意义上一个参数的函数的链。

如果每个参数arg都有一个类型t,那么在currying操作之前,f(arg1,arg2,...,argn)整个函数的类型为

1
(t1 * t2 * ... * tn) -> rtype

即取(t1 * t2 * ... * tn)类型的值(arg1 * arg2 * ... *argn)作为参数,返回rtype的值作为结果的函数。Currying操作之后的函数我们记为f arg1 arg2 ... argn,这个函数的类型为

1
t1 -> (t2 -> (... ->(tn -> rtype)...))

此时f仅使用一个t1类型的参数,返回一个t2 -> (... ->(tn -> rtype)...)类型的函数作为结果。当我们仅以一个参数去调用f arg1时,返回一个取t2类型数据为参数返回t3-> (... ->(tn -> rtype)...)类型函数的函数,就像洋葱一样一层层地调用函数才能剥出最后的返回结果,当然f(arg1,arg2,...,argn)f arg1 arg2 ... argn运算最后得到的结果是一致的。

按照这种思路可以重写map函数为curried-map

1
2
3
4
5
(define (curried-map f)
(lambda (xs)
(if (null? xs)
null
(cons (f (car xs)) ((curried-map f) (cdr xs)) ))))

当我们要写一个对list中每个元素的值进行乘2操作的函数时,可以直接写作

1
(define double-list (curried-map (lambda (x) (* x 2))))

这个(curried-map (lambda (x) (* x 2)))就是这样一个函数,是curried-map的一个部分应用(partial application)实例,currying使得这样的用法更为便捷。当然,我不是说部分应用必须依靠curry函数,完全没有那样的意思,实际上一定要用原来的map函数也可以达到目的

1
2
(define (double-list2 xs)
(map (lambda (x) (* x 2)) xs))

差不多就是绑定了参数y的值然后定义g(x)=f(x,y)的意思,map只有两个参数,所以固定其中一个,然后把其他形参照着“抄写”一遍在定义里走个过场也不费事,但参数一多的时候不用curry函数就显得麻烦了。

*部分应用 (Partial Application)

Optional

这部分并非必须内容,我只是以自己的理解给出一个概念的实例实现,直接跳过不影响全文的内容脉络,仅供感兴趣的读者加深印象和交流改进。

部分应用的作用在于,将抽象的模型的一部分具体转化成为一个常见,实用的不那么抽象的模型。众所周知,Maclaurin公式(省略余项)
$$f\left( x \right) \approx f\left( 0 \right) + \frac{f’\left( 0 \right)}{1!}x + \frac{f^{\left(2 \right)}\left( 0 \right)}{2!}{x^2} + \ldots + \frac{f^{\left( n \right)}\left( 0 \right)}{n!}{x^n}$$
是Taylor公式(省略余项)$$f\left( x \right) \approx f\left( {x_0} \right) + \frac{f’\left( {x_0} \right)}{1!}\left( x - {x_0} \right) + \frac{f^{\left( 2 \right)}\left( x_0 \right)}{2!}{\left(x - x_0\right)^2} + \ldots + \frac{f^{\left( n \right)}\left( x_0 \right)}{n!}{\left( x - x_0\right)^n}$$在$x_0=0$处的特例,换言之也是绑定了参数x0的一个部分应用,两个公式给出的也都是包含参数x的函数作为返回结果,即一个f的近似函数。对于毫无编程基础或者像我这样编程基础薄弱的人来说,理解这个“部分应用”不需要借助任何代码,借助这个例子可以很好地感受“部分应用”概念本身的含义。

但是为了完整性,我还是试图从最基础的部分开始一步步给出它们的实现。

首先利用导数的定义$$f’\left( x \right) = \mathop {\lim }\limits_{dx \to 0} \frac{f\left( x + dx \right) - f\left( x \right)}{dx}$$写出导函数的定义


1
2
3
4
5
(define dx 0.000001)

(define (deriv f)
(lambda (x)
(/ (- (f (+ x dx)) (f x)) dx)))

deriv函数是部分curry化的,调用(deriv f)返回的是f的导函数,如果你想求f在某点(x0,f(x0))的导数f'(x0),还需要再调用一次这个结果,即((deriv f) x0),当然因为我只是取了一个数值上接近无穷小的dx常量,所以最后的结果也只会是一个近似值,但这也够用了。

接下来实现Taylor公式中各项的表达。一般来说,Taylor公式中的求和项数越多结,这个近似的结果越接近函数的真实值,当$n \to \infty$时可认为等号成立。但这个真正的“无穷”是编写程序的人无法实现的,如果要写出无限长的Taylor数列$\frac{f^{\left( n \right)}\left( x_0 \right)}{n!}{\left(x - x_0\right)^n}$,那么可以利用惰性计算(lazy evaluation)的特性去模拟一个无限的“流(stream)”

1
2
3
4
5
6
7
8
9
10
(define (taylor-stream f)
(lambda (x0)
(lambda (x)
(letrec ([taylor-series (lambda (n cof func base)
(cons ( / (* (func x0) base) cof)
(lambda () (taylor-series (+ n 1)
(* cof (+ n 1))
(deriv func)
(* base (- x x0))))))])
(lambda () (taylor-series 0 1 f 1))))))

(taylor-stream f)不仅是一个无限的流,也是关于xx0的curry函数,仅当xx0参数都传入时才进行真正的函数值计算,仅调用(taylor-stream f)时得到的只是如上罗列的公式。

然后然后针对这个数列(流)写一个前n项求和函数,没什么特别讲究的只需要随便写写就行

1
2
3
4
5
6
(define (stream-sum n s)
(if (= n 0)
0
(let ([p (s)])
(+ (car p)
(stream-sum (- n 1) (cdr p))))))

那么根据Taylor展开公式(取2阶导数),函数f(x)x0点的近似多项式函数为

1
2
3
4
5
6
7
(define order 2)

(define (taylor-approx x)
(lambda (x0)
(lambda (f)
(stream-sum (+ order 1)
(((taylor-stream f) x0) x)))))

接下来作为固定了取值点x0为0的特例Maclaurin公式可以按照上文的部分应用写法写为

1
(define (maclaurin-approx x) ((taylor-approx x) 0))

然后就可以同时地,方便地去用这两个近似公式求多项式近似函数的值了。比如$2^x$在$x=0$时的Taylor近似函数在$x=2$处的值

1
((maclaurin-approx 2) (lambda (x) (expt 2 x))) ;;3.347303891703234

Warning

注意这里的求导方法也是数值近似的,因此对于低阶函数,高阶近似,所求近似的自变量与取值点相距较远时,会产生巨大的误差。如果想提高微分的精确度,可以考虑用类似eval函数或解释器的方法递归地对表达式结果编写求导函数(参阅SICP: 2.3.2 Example: Symbolic Differentiation P197-199

词法作用域 (Lexical Scope)

众所周知,为变量命名是件非常苦手的事,一般我们不提倡在一个程序内多次使用一个变量名,但这是个正确的废话,现实中总是无法避免的。而重复使用同一个变量名带来的问题就是不知道这个变量名到底和什么绑定了,我调用这个变量(包括函数)的时候,这个变量绑定的是哪个表达式,这个表达式中出现的变量绑定的又是哪个?好在程序设计语言的语法中对作用域(scope)都作出了相应的规定。

词法作用域是现在大多数语言采用的作用域类型,或者被称为静态作用域(static scope) 也是相对容易实现的类型。在这种规定下,函数体中的变量根据函数被定义的环境进行计算,而不是放在被调用的环境中计算。

有的教材在解释这个概念的时候会用到形如这样的例子2


1
2
3
4
5
val x = 1
fun f y = x + y
val x = 2
val y = 3
val z = f (x+y)

这里z的值为6。f的函数体在被计算时,在f被定义的环境中查找变量x的绑定,所以不管后面x怎样被shadow了,f执行的都是+1操作,不会出现z==7的结果。函数的参数x+y在被调用的新环境计算后传入函数体,但函数体却在被定义的旧环境中进行计算。

如果想要这个使f中的x更新为2,那么语言的作用域法则需要更改为动态作用域(dynamic scope)。在这种语法下,函数被调用时,函数体的求值过程中可以访问到现在的环境中的变量,而在词法作用域中,函数体的求值除了传入的参数之外,调用时的环境是被完全隔离开的,也就是不透明的。

上面是一个关于ML的例子,用同样的思路去写一个Python的例子

1
2
3
4
5
6
7
8
x=1

def f(y):
return x+y

x=2
y=3
z=f(x+y)

z的值为7,但这并不意味着Python是使用动态作用域的语言。Python是静态作用域的,但缺少类似于val关键字引导的类型声明。ML的val x=2所做的是重新声明了一个绑定为2的变量xshadow掉了原来的val x=1,实质上这是两个变量,虽然名字都是x,但作用域不同。而Python中x=2则是对已有的变量x的值的修改,即引用(reference)的更新。由于函数体f中并没有本地变量x的声明,遵循LEGB原则(Local, Enclosing, Global, Built-in),函数的定义环境中x即为全局变量x,函数体计算时使用的是x的引用。Python也支持前向引用(forward reference),换言之即使这个x在函数被定义时还没有被声明或者更新,函数值计算时x也是使用该全局变量最新的值。虽然整个过程看上去别扭,但始终遵循函数被放到了定义的环境中去计算的原则,只是在这个定义的环境中函数里面出现的变量被定义为一个可变的引用。Python不是函数式编程语言,但有部分函数式编程语言的特性,然而函数式编程认为使用可修改的变量(引用)是很不优雅的坏文明。

这样写就不会出现上面的困扰了

1
2
3
4
5
6
7
8
9
10
x=1

def f(y):
return x+y

def g(y):
x=2
return f(x+y)

z=f(3)

这里x=2是在函数g中声明了一个值为2的局部变量x去shadow掉了值为1的全局变量,然而根据词法作用域的原则,在g中调用的f并不会用这个新环境被求值,还是使用被定义时x为全局变量的旧环境,所以z的值为6。

Racket不允许top-level的变量重复定义,所以在top-level上重复使用一个变量名造成的混乱可以避免。但是,在函数(过程)中被调用的函数的定义里如果出现了和外界同名的变量,还是遵循词法作用域的原则,外面的过程中的局部变量对调用的函数不可见。这可以体现在用let引导的局部变量定义,比如这个与ML表示的例子完全相同的逻辑,毫不意外地,z的值为6

1
2
3
4
5
6
7
8
9
(define x 1)

(define (f y)
(+ x y))

(define z
(let ([x 2]
[y 3])
(f (+ x y)))) ;;z=6

也可以体现在一个函数定义时使用的形参名字,与该函数代码内调用的另一个函数中的变量名冲突时的情况:

1
2
3
4
(define (disp-deriv f x1 x2 dx)
(if (> x1 x2)
null
(cons ((deriv f) x1) (disp-deriv f (+ x1 dx) x2 dx))))

disp-deriv是一个求[x1,x2]区间内按dx为步长取点的f(x)的导数列表的函数,我们知道之前在deriv函数的定义里已经有了其中常数dx的指定,这里再用dx来当代表步长的形参,这种做法确实挺不好的,但人难免会有一拍大腿想不出什么好名字理性蒸发瞎写的时候。词法作用域保证了在调用deriv给取值点挨个求导的时候,deriv内部的极小增量dx的取值不会受到外部步长dx的干扰,所以当你调用

1
(disp-deriv square 0 4 1)

时,可以正确得到这5个整数点上的导数值。

环境(Environmnet)与闭包 (Closure

所谓环境,通俗来说就是记录变量名绑定的字典。作用域法则已经在大方向上规定了应该怎么去分类这些字典,在哪个情形下我们应该去翻哪本字典,新“注册”了一个绑定又应该往哪本字典里去添加“词条”。至于具体在去一个指定的字典查找一个变量的定义,可以用这样的写法

1
2
3
4
(define (envlookup env str)
(cond [(null? env) (error "unbound variable during evaluation" str)]
[(equal? (car (car env)) str) (cdr (car env))]
[#t (envlookup (cdr env) str)]))

环境env是一个由(str,exp)对表示(变量名,表达式)组成的列表,str是一个字符串类型的变量名字,exp则是该变量名所绑定的,在该语言中的一个表达式。

当表达式需要在指定环境env下进行“解释”(求值)的时候,把env作为求值过程的一个参数传进去就可以了,再在过程内部调用envlookup函数。

既然词法作用域严格地强调了定义与调用两种环境的隔离,那就需要用一种方法去把函数定义的环境和函数本身进行“打包封装”作为一个整体传入其他过程或函数,再等到调用时就地“拆包”进行求值。闭包就是为此而诞生的技术。如果函数体中有一些变量本身并没有在函数体中被定义,需要依赖函数被定义的环境确定这些变量的具体指代,那么这些变量的定义环境就需要连同函数代码本身一起被放进这样一个被称为闭包的数据结构

1
(struct closure (env fun) #:transparent)

闭包就是函数被“解释”的结果,它就是一个可以被用来传递的值。在这里闭包的实现方法实际是一个偷懒的trick,直接把函数定义时的环境和函数一起放进了closure

*自由变量 (Free variable

上面简单的“打包”将函数定义存在的所有绑定,无论函数体求值时是否用到,一并封装到了closure,当然仅根据词法作用域的定义也不能说这种做法存在什么错误,也完全可以通过下文中实现的方法正常地运行这个机制。但是把不必要的绑定放到closure里确实也会造成冗余,实践中的闭包实现也基本不会容忍这种低效的方法,一个可行的改进的思路就是仅在closure中引用与函数“相关”的变量名的绑定,这些变量就是所谓的自由变量。

和数学中所使用的“自由变量”和“约束变量”含义相似,自由变量是指仅在函数体代码中直接占位使用,却没有在函数体中给出定义(约束)的变量,它的定义在函数体外,不同的作用域法则争议的是对这些自由变量的“解释权”。在上面的例子x就是函数f的自由变量,在词法作用域下需要做的就是在闭包的环境中把x与整数值1对应,另外还有一些判断函数中那些变量是自由变量的例子2

1
2
3
4
5
6
(lambda () (+ x y z)) ; {x, y, z}
(lambda (x) (+ x y z)) ; {y, z}
(lambda (x) (if x y z)) ; {y, z}
(lambda (x) (let ([y 0]) (+ x y z))) ; {z}
(lambda (x y z) (+ x y z)) ; {}
(lambda (x) (+ y (let ([y z]) (+ y y)))) ; {y, z}

实际上会一点编程的人都能敏锐地凭借直感找出自由变量,仅凭自然语言描述怎么去找一堆代码里面有几个自由变量也有些困难,如果有兴趣可以看后文中的代码实现

*简易解释器

Optional

本部分内容和实践中的解释器(Interpreter)存在巨大的差异,给出实现仅为帮助理解以上概念所写。内容基本直接参考Programming Languages中给出的指导进行实现。

现在我们要定义一种由如下表达式表示出来的语言,可以命名该语言为MUPL (Make Up Programming Language)

1
2
3
4
5
6
7
8
9
10
11
12
(struct var  (string) #:transparent)  ;; 变量,例如(var "foo")
(struct int (num) #:transparent) ;; 常数, 例如(int 17)
(struct add (e1 e2) #:transparent) ;; 加法表达式
(struct ifgreater (e1 e2 e3 e4) #:transparent) ;; 如果 e1 > e2 则结果为 e3 否则为 e4
(struct fun (nameopt formal body) #:transparent) ;; 单参数函数,如果nameopt域即函数名为#f则为匿名函数
(struct call (funexp actual) #:transparent) ;; 函数调用
(struct mlet (var e body) #:transparent) ;;本地绑定 (let var = e in body)
(struct apair (e1 e2) #:transparent) ;; 定义一个(e1,e2)对
(struct fst (e) #:transparent) ;; 取对的第一个数
(struct snd (e) #:transparent) ;; 取对的第二个数
(struct aunit () #:transparent) ;; unit,list的“休止符”
(struct isaunit (e) #:transparent) ;; 判断e是不是unit,是则为1否则为0

我们的最终目的是写一个Racket程序(函数)来解释和MUPL语言给出的表达式,那么要做的就是用Racket模拟MUPL中各表达式的求值过程,对于复合的语义结构,无疑应该使用递归一层层去进行求值。首先列出一个框架:

1
2
3
4
5
6
7
8
(define (eval-under-env e env)
(cond [...]
[...]
....
[#t (error (format "bad (MUPL expression: ~v" e))]))

(define (eval-exp e)
(eval-under-env e null))

最终实现的结果就是eval-exp函数,用于解释MUPL程序。eval-under-env则是用于不同环境进行递归的辅助函数,可以说是这个解释器的“单元”,cond语句对不同类型的表达式做出了eval方面不同操作的规定,接下来我们要做的只有一步步按照MUPL的语义填充这些[...]从句。

首先,所有的变量都被当成变量本身(包括closure

1
2
3
[(int? e) e]
[(closure? e) e]
[(aunit? e) e]

接下来,遇到某个var "name"形式的变量的时候,利用envlookup函数找到在当前环境下这个变量名绑定的值

1
2
[(var? e)
(envlookup env (var-string e))]

对于加法运算,先对两个操作数(子表达式)进行求值,然后相加得到一个整数

1
2
3
4
5
6
7
8
[(add? e)
(let ([v1 (eval-under-env (add-e1 e) env)]
[v2 (eval-under-env (add-e2 e) env)])
(if (and (int? v1)
(int? v2))
(int (+ (int-num v1)
(int-num v2)))
(error "MUPL addition applied to non-number")))]

采用词法作用域规则,把函数与其被定义的环境打包成一个closure

1
[(fun? e) (closure env e)]

ifgreater的情况和add差不多,但注意e3e4只能根据条件选一个计算一次

1
2
3
4
5
6
7
8
[(ifgreater? e)
(let ([v1 (eval-under-env (ifgreater-e1 e) env)]
[v2 (eval-under-env (ifgreater-e2 e) env)])
(if (and (int? v1) (int? v2))
(if (> (int-num v1) (int-num v2))
(eval-under-env (ifgreater-e3 e) env)
(eval-under-env (ifgreater-e4 e) env))
(error "MUPL ifgreater applied to non-number")))]

mlet先将表达式e进行求值并与变量名var绑定,再把这个绑定添加到现在的环境,在这个环境中去body进行求值

1
2
3
[(mlet? e) (let ([v (eval-under-env (mlet-e e) env)])
(eval-under-env (mlet-body e)
(cons (cons (mlet-var e) v) env)))]

当遇到函数调用语句call时,按如下步骤进行求值

  1. 对第一个域funexp在当前环境下进行求值,是否为一个closure,即这个域本来是不是一个funcclosure或函数名,如果不是则直接报错跳出
  2. 如果对funexp求值产生的closure中,函数部分fun的函数名optname不是#f,则把函数名和在closureenv环境下对函数体的求值结果绑定,并把这个绑定添加到这个closureenv环境
  3. 对第二个域actual在当前环境下求值,把这个值与函数的参数名formal绑定,添加到上面的closureenv环境。
  4. 在这个被添加了函数名绑定和参数绑定的旧env下对函数体进行求值作为返回结果

1
2
3
4
5
6
7
8
9
10
[(call? e) (let ([c (eval-under-env (call-funexp e) env)])
(if (closure? c)
(letrec ([parameter (eval-under-env (call-actual e) env)]
[f (closure-fun c)]
[fbody (fun-body f)]
[fname (fun-nameopt f)]
[old-env (cons (cons (fun-formal f) parameter) (closure-env c))]
[new-env (if fname (cons (cons fname c) old-env) old-env)])
(eval-under-env fbody new-env))
(error "MUPL call applied to non-closure")))]

apair中的两个表达式分别进行求值,再把结果重组成一个apair

1
2
[(apair? e) (apair (eval-under-env (apair-e1 e) env)
(eval-under-env (apair-e2 e) env))]

至于fstsnd就更与上面的做法大同小异了,先对子表达式求值再取其中的一个域,按照语义随便写就行

1
2
3
4
5
6
7
8
[(fst? e) (let ([subexp (eval-under-env (fst-e e) env)])
(if (apair? subexp)
(apair-e1 subexp)
(error "not a pair")))]
[(snd? e) (let ([subexp (eval-under-env (snd-e e) env)])
(if (apair? subexp)
(apair-e2 subexp)
(error "not a pair")))]

isaunit也是如此,先对表达式求值再判断是不是aunit

1
2
[(isaunit? e) (let ([subexp (eval-under-env (isaunit-e e) env)])
(if (aunit? subexp) (int 1) (int 0)))]

当然我们还可以为了使用方便再去“创造”一个(ifaunit e1 e2 e3)语句,也可以说是这个语言的idiom,也可以把它当成一个使用前预处理的“宏(macro)”,当我们用我们写的“解释器”即eval-exp函数去求这个语句的值时,如果e1是aunit则对e2求值作为结果,否则对e3求值

1
2
(define (ifaunit e1 e2 e3)
(ifgreater (isaunit e1) (int 0) e2 e3))

接下来用MUPL语言写一个map函数

1
2
3
4
5
6
7
(define mupl-map
(fun #f "func"
(fun "loop" "mlst"
(ifaunit (var "mlst")
(aunit)
(apair (call (var "func") (fst (var "mlst")))
(call (var "loop") (snd (var "mlst"))))))))

以及它的部分应用,对MUPL列表中所有整数元素进行自增操作的函数mupl-mapAddOne

1
2
3
(define mupl-mapAddOne
(mlet "map" mupl-map
(call (var "map") (fun #f "j" (add (int 1) (var "j"))))))

当我们用eval-expmupl-mapAddOne的如下调用实例求值时可以得到预期的结果

1
2
3
4
(eval-exp (call mupl-mapAddOne
(apair (int 3) (apair (int 4) (apair (int 9) (aunit))))))

;; (apair (int 4) (apair (int 5) (apair (int 10) (aunit))))

更轻的环境

Optional

本部分直接使用Programming Languages中给出的样例代码。

基于自由变量部分所提的优化思路,把函数的结构(struct fun (nameopt formal body))重写为

1
(struct fun-challenge (nameopt formal body freevars) #:transparent)

freevars域用于存储函数用到的自由变量名,是一个字符串类型的list

接下来需要定义一个函数compute-free-vars去找到原函数fun的所有自由变量,直接得到新函数fun-challengefreevars域,在此之前可以先定义compute-free-vars用到的返回类型为

1
(struct res (e fvs))

e域为MUPL表达式,fvs域即freevars列表的一种形式,这里用的是set,避免同一个自由变量多次被算到里面。接下来和eval的思路相似,也是使用递归一层层去找函数中每个结构含有哪些自由变量3

1
2
3
4
5
6
(define (compute-free-vars e)
(struct res (e fvs)) ; result type of f (could also use a pair)
(define (f e)
(cond [(var? e) (res e (set (var-string e)))]
[...]))
(res-e (f e)))

这里的f就是用于递归的辅助函数,rese存储着表达式本身,当然在后文我们可以看到,除了fun的情况这个e域会成为一个新的携带着freevars结果的fun-challenge变量,其余情况输出res-e都与输入e一致。实际上真正涉及到自由变量集合的增删的操作只会在varfunmlet语句中出现,其他语句只是把子表达式中的自由变量集合进行合并。var的情况已经给出了,只需要构造一个仅包含其变量名的自由向量集合即可,接下来我们又要按着这样的想法去填充这些[...]了:

先看数值类型的数据结构intaunit,它们不可能包含任何自由变量,直接返回空集

1
2
[(int? e) (res e (set))]
[(aunit? e) (res e (set))]

addifgreater语句本身不创造自由变量,对其所有的操作数(子表达式)逐个寻找出现过的自由变量,然后返回它们的并集

1
2
3
4
5
6
7
8
9
10
[(add? e) (let ([r1 (f (add-e1 e))]
[r2 (f (add-e2 e))])
(res (add (res-e r1) (res-e r2))
(set-union (res-fvs r1) (res-fvs r2))))]
[(ifgreater? e) (let ([r1 (f (ifgreater-e1 e))]
[r2 (f (ifgreater-e2 e))]
[r3 (f (ifgreater-e3 e))]
[r4 (f (ifgreater-e4 e))])
(res (ifgreater (res-e r1) (res-e r2) (res-e r3) (res-e r4))
(set-union (res-fvs r1) (res-fvs r2) (res-fvs r3) (res-fvs r4))))]

举一反三,接下来要处理的情况中,funmlet以外的语句都是与上面相似的情况,直接写就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[(call? e) (let ([r1 (f (call-funexp e))]
[r2 (f (call-actual e))])
(res (call (res-e r1) (res-e r2))
(set-union (res-fvs r1) (res-fvs r2))))]
[(apair? e) (let ([r1 (f (apair-e1 e))]
[r2 (f (apair-e2 e))])
(res (apair (res-e r1) (res-e r2))
(set-union (res-fvs r1) (res-fvs r2))))]
[(fst? e) (let ([r (f (fst-e e))])
(res (fst (res-e r))
(res-fvs r)))]
[(snd? e) (let ([r (f (snd-e e))])
(res (snd (res-e r))
(res-fvs r)))]
[(isaunit? e) (let ([r (f (isaunit-e e))])
(res (isaunit (res-e r))
(res-fvs r)))]

在考虑fun的情况时,需要注意的是函数的形参虽然在函数体中出现过,但它并不是一个自由变量,所以要从函数体的自由变量集合中去除这个变量;另外,当函数还具有函数名时,如果这个函数名又在函数体中出现了,也就是发生了递归,显然这个函数本身并不是自由变量,那么函数名也需要从自由变量列表fvs中去除。

1
2
3
4
5
6
7
[(fun? e) (let* ([r (f (fun-body e))]
[fvs (set-remove (res-fvs r) (fun-formal e))]
[fvs (if (fun-nameopt e)
(set-remove fvs (fun-nameopt e))
fvs)])
(res (fun-challenge (fun-nameopt e) (fun-formal e)
(res-e r) fvs)

mlet的处理稍简单一些,只需把var这个局部变量名从body的自由变量列表中去除,再合并e的自由变量列表

1
2
3
4
[(mlet? e) (let* ([r1 (f (mlet-e e))]
[r2 (f (mlet-body e))])
(res (mlet (mlet-var e) (res-e r1) (res-e r2))
(set-union (res-fvs r1) (set-remove (res-fvs r2) (mlet-var e)))))]

完成compute-free-vars函数后,可以重写eval-under-enveval-under-env-c,只需要添加fun-challenge的情况,其余部分与原函数一致

1
2
3
4
5
6
7
8
9
(define (eval-under-env-c e env)
(cond
[(fun-challenge? e)
(closure (set-map (fun-challenge-freevars e)
(lambda (s) (cons s (envlookup env s))))
e)]
; call case uses fun-challenge as appropriate
; all other cases the same
[...] ))

对于fun-challenge的闭包封装指令为找到freevars中所有变量名在env的对应(绑定),这里的set-map是作用于set类型的高阶函数map。再把这些绑定关系构成的列表作为closure中的环境。最后改写这个解释函数的函数:

1
2
(define (eval-exp-c e)
(eval-under-env-c (compute-free-vars e) null))

在更轻的环境负担下发挥和原来的解释器一样的作用。


  1. 1.Abelson, Harold, Gerald Jay Sussman, and Julie Sussman. Structure and interpretation of computer programs. Justin Kelly, 1996.
  2. 2.样例代码来源于University of Washington在Coursera的公开课Programming Languages讲义section3sum.pdfslides
  3. 3.这里对应的源代码第六行是(res-fvs (f e))),我认为这是一个typo,根据逻辑应该是(res-e (f e))),我已经向该材料的制作者反映过这个问题,且也有其他人认为这里有问题,正在等候回复。