笔记仓库

正常人的正常笔记集

局部绑定和内部定义

在我曾经写的SICP从DrRacket钻了出来一文中我提到过不同的Scheme解释器实现对内部定义(internal definition)的处理不同,所以当需要定义一个中间变量时,需要格外小心地使用块结构(block structure,即在define中嵌套define)以及与之作用类似的let系列表达式。

这篇笔记沿用SICP 4.1 The Metacircular Evaluator 的背景演示这些结构和语法实际上是如何被解释器理解的。

lambda表达式

众所周知,lambda表达式用于定义一个可以当场被调用的匿名函数。由lambda引导的整个表达式

1
(lambda (<parameters>) <body>)

可以被看成一个被称为函数/过程的数据对象,形式参数为<parameters>,函数体<body>的内容并不在此时被求值,这就是延迟求值(delay evaluation)的基础。用<args>调用这个函数可以得到结果

1
((lambda (<parameters>) <body>) <args>)

当编写一个(eval exp env)函数来对这些过程求值时,可以考虑表达为一个形如'(lambda (<parameters>).<body>)的list结构,刚好与$\lambda$-calculus的表示法

1
<function> := λ <name>.<expression>

一致,于是构造和选择的操作可以写为

1
2
3
4
5
6
(define (make-lambda parameters body)
(cons 'lambda (cons parameters body)))

(define (lambda? exp) (tagged-list? exp 'lambda))
(define (lambda-parameters exp) (cadr exp))
(define (lambda-body exp) (cddr exp))

对lambda表达式的求值(结果为一个函数对象)在eval中体现为这个cond分支

1
2
3
4
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))

暂时先不用去看make-procedure源码具体做了什么,只要知道它把函数被定义时的环境env也放进了函数对象中,待调用时会在被调用环境中计算实参的值绑定到函数的形参上,再把这些绑定连同原有的env一起用来计算函数体得到函数调用的结果。这就是词法作用域(lexical scope)的特性之一,函数内的变量(除形参)对应的值由函数被定义时的环境决定。

当然,更常见的定义函数,也就是过程的标准定义为

1
2
(define (f <parameter1> ... <parametern>)
<body>)

实际上是

1
2
3
(define f
(lambda (<parameter1> ... <parametern>)
<body>))

的语法糖,变量f指向是一个lambda表达式,所以也可以说f就是这个匿名函数的函数名。把函数对象绑定到f可以让定义和调用很好的分离开来,在定义完成后,随时还可以再通过f去使用这个lambda表达式对应的函数。对刚才那个define过程的求值中,会把f和函数对象的绑定添加到当前环境。

let

let表达式提供了一种本地绑定的方法

1
2
(let ((<var1> <exp1>) ... (<varn> <expn>))
<body>)

<body>中可以直接使用<var1>...<varn>代表<exp1>...<expn>,这样的局部变量定义的写法实际上是

1
2
3
4
5
((lambda (<var1> ... <varn>)
<body>)
<exp1>
...
<expn>)

的语法糖。形参就是典型的局部变量,也无怪let定义局部变量还是把看似单独定义的变量当成某个过程的形参,而它们应当指向的值作为实参传入进行计算。

语法糖的实现可以通过把let直接转换为一个lambda表达式+调用的let->combination函数:

1
2
3
4
5
6
7
8
(define (let? exp) (tagged-list? exp 'let))
(define (let-vars exp) (map car (cadr exp)))
(define (let-vals exp) (map cadr (cadr exp)))
(define (let-body exp) (cddr exp))

(define (let->combination exp)
(cons (make-lambda (let-vars exp) (let-body exp))
(let-vals exp)))

再在(eval exp env)中添加一个cond分支:

1
((let? expr) (eval (let->combination expr) env))

接下来要做的又要回归到对lambda表达式的处理:对lambda表达式的eval求值返回的是封装了形参列表lambda-parameters,函数体lambda-body和定义时环境env的过程对象procedure。当用实参列表arguments来调用这个过程时,发生了如下的操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (apply procedure arguments)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
(else
(error
"Unknown procedure type -- APPLY" procedure))))

这是你自己写的lambda表达式所以肯定不会通过预言primitive-procedure?,只需要看(compound-procedure? procedure)分支的做法:(eval-sequence exps env)是在env环境下对一系列语句exps进行求值的过程;(extend-environment <variables> <values> <base-env>)表示把变量列表<variables>和值列表<values>绑定作为一个新的frame被包含在<base-env>形参一个新的环境。

当然extend-environment具体是怎么添加绑定的暂时不重要。虽然按照指令式编程的直觉,let语句如果引导了多个局部变量的绑定,它们的绑定应该是依次被添加到小环境中去的,比如

1
2
3
(let ((x 5)
(y (+ x 1)))
(+ x y))

是可以得到结果11的。但实际不是这样的,根据上文的分析,它被视为一个以(x y)为形参列表,函数体为(+ x y)的lambda表达式,以5(+ x 1)作为实参去调用的结果。在Applicative order的eval系统中,复合表达式作为实参时,需要在被传入前就在调用环境中完成求值。这体现在evalcond关于应用的分支

1
2
3
4
5
6
7
8
9
10
((application? exp)
(apply (eval (operator exp) env)
(list-of-values (operands exp) env)))

(define (list-of-values exps env)
(if (no-operands? exps)
'()
(cons (eval (first-operand exps) env)
(list-of-values (rest-operands exps) env))))
; similar to (map (lambda (exp) (eval exp env)) exps)

显然在当前计算实参(+ x 1)的值时,当前环境中没有任何关于变量x的信息。所以在let内部使用平级的局部变量去定义自己或另一个是不被允许的,在同一个let中,所有变量指向的表达式都必须与let规定的变量名无关。

let*

let*let表达式的一个变体

1
2
(let* ((<var1> <exp1>) ... (<varn> <expn>))
<body>)

可以从左到右依次实现var1-exp1varn-expn的绑定,使得当i<j时,在varj指向的expj用到变量vari成为可能,更符合指令式编程的思维习惯。它的实现也并不复杂,只是转换成了多层let的嵌套

1
2
3
4
(let ((<var1> <exp1>))
...
(let ((<varn> <expn>))
<body>))

给出一个参考实现的版本

1
2
3
4
5
6
7
8
9
10
11
(define (let-args exp) (cadr exp))
(define (let-body exp) (cddr exp))
(define (make-let args body) (cons 'let (cons args body)))

(define (let*->nested-lets exp)
(define (reduce-let* args body)
(if (null? args)
(sequence->exp body)
(make-let (list (car args))
(list (reduce-let* (cdr args) body)))))
(reduce-let* (let-args exp) (let-body exp)))

这里为了去除冗余的()而使用(sequence->exp body)代替body。在通过let*?检查后通过let*->nested-lets可以转化为之前已经规定了求值方法的let,就可以直接用(eval (let*->nested-lets exp) env)完成求值了。

internal define

define或其他语句内使用define就形成了一个block structure,体现为形如这样的“缩进”,内部define绑定的作用域范围无法突破外层的define

1
2
3
(define ...
(define ...)
...)

想要观察内部define的行为,为了理解还是需要先去观察top-level的普通define的行为。

defineeval通过(define-variable! var val env)在当前环境env的第一个frame添加变量var与值val的绑定。我们知道对lambda表达式的求值不会立即直接去计算它的函数体,而是和环境env一起打包成一个过程对象,对函数f定义语句的处理是让变量名f指向这个过程对象,再修改env使其包含这个绑定,以后再调用f时,函数体内部如果也用到了这个函数名f会在被封装到过程对象的env中找到f的定义。这就是函数递归实现的基础。

但当需要被指向的值不是像lambda表达式那样的延迟对象时,会在当前未添加绑定的envval进行立即求值(eager evaluation),如果val中出现需要被定义的变量名var那么是无法找到var的定义的。所以如果对这样的变量进行递归定义,会出现unbound identifier error提示。

继续回到内部的define,众所周知,和let以及let*不同,内部的define也是可以实现函数的递归定义的。

IEEE Scheme标准对于内部define的作用域应该如何被解释没有给出特别严格的规定,所以各个解释器的做法不相同。毕竟IEEE Scheme标准只允许常量和lambda表达式作为内部define的值1,内部define在其他表达式之前出现,所以具体哪个变量按照什么顺序在何时实现绑定,没有太大区别。但实践中大家似乎并不愿意遵守这个标准,因此制造出很多混乱。

如果在内部定义了这两个函数

1
2
3
4
5
6
7
8
9
10
(define (f x)
(define (even? n)
(if (= n 0)
true
(odd? (- n 1))))
(define (odd? n)
(if (= n 0)
false
(even? (- n 1))))
<rest of body of f>)

这个互递归结构让很多人设想解释器应该同时完成even?odd?的绑定,幸运的是两个变量都指向了lambda表达式,因此用普通的define就可以实现互递归,不需要实现真正意义上的同时。如GNU/MIT Scheme在内很多版本的解释器也是把它当成类似于top-level的define,从扫描到这个define语句开始把绑定放入当前环境。

但也有人追求这个真正意义上的同时,于是他们设计解释器的做法是:把一个代码块内所有内部定义的局部变量名都先扫描出来,用一个特定的标签进行初始化,放入当前环境。接下来再逐次对这些变量名按照指定表达式进行赋值,如此一来,这些表达式内如果包含其他局部变量,也不会被提示unbound identifier,但却有可能被警告 cannot use before initialization,因为表达式中的其他局部变量可能还没有指向可以用于计算的值。

也就是把

1
2
3
4
(lambda <vars>
(define u <e1>)
(define v <e2>)
<e3>)

处理成

1
2
3
4
5
6
(lambda <vars>
(let ((u '*unassigned*)
(v '*unassigned*))
(set! u <e1>)
(set! v <e2>)
<e3>))

具体源码我就不写了,能猜出需要借助一个函数先去扫描代码找出所有的中间定义变量,在make-procedure中把函数体解析成如上形式。另外还需要注意在env寻值时遇到返回结果为'*unassigned*时应该发起一个未初始化的异常。

Racket就是使用了类似的“同时”机制,所以我在3.5.4 Streams and Delayed Evaluation 中遇到的那个互相递归的内部变量定义即使在其中一个参数上加了delay也无法解决。现在再来想,让两个变量都定义为无参的lambda过程,也就是写为thunk就可以继续用了

1
2
3
4
(define (solve f y0 dt)
(define (y) (integral (delay (dy)) y0 dt))
(define (dy) (stream-map f (y)))
(y))

当然这种“同时”带来的弊端就是不能像let*那样让后面的变量绑定关于前面变量的表达式。比如这种写法就是不允许的

1
2
3
4
(define (f x)
(define a 1)
(define b (+ a 1))
(+ x b))

letrec

letrec也是let的一个变体,使用的就是上文提到的内部define的“同时”绑定机制,即表达式

1
2
(letrec ((<var1> <exp1>) ... (<varn> <expn>))
<body>)

被视为

1
2
3
4
5
6
7
(let ((<var1> '*unassigned*)
...
(<varn> '*unassigned*))
(set! <var1> <exp1>)
...
(set! <varn> <expn>)
<body>))

处理,每个变量的作用域都是一致的,可以用来定义内部递归/互递归函数,这是let*做不到的,但同时注意,let*能实现的顺序绑定沿用letrec也同样无法完成2

Y operator

完全不用这一类局部绑定和内部定义也是可以实现局部变量的定义的,毕竟let展开还是lambda表达式,甚至可以完成递归定义的局部函数。比如计算10!

1
2
3
4
5
6
7
8
((lambda (n)
((lambda (fact)
(fact fact n))
(lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))))
10)

定义一个(f x)判断x是否为偶数:

1
2
3
4
5
6
(define (f x)
((lambda (even? odd?) (even? even? odd? x))
(lambda (ev? od? n)
(if (= n 0) true (od? ev? od? (- n 1))))
(lambda (ev? od? n)
(if (= n 0) false (ev? ev? od? (- n 1))))))

不过Y operator这种东西还是看看就行了,没事就别给自己找麻烦了。