Scheme是一门支持Proper tail recursion的语言，
实际上这是对语言本身的约束，
任何实现都必须满足，
我们可以依赖它写出可移植的程序。
那么，到底什么是尾递归呢？
什么样的才是Proper呢？
它给我们带来了什么好处呢？
这还要从函数的尾调用说起。
我们发现，
Proper tail recursion和continuation有很深的关联。
下文为了叙述方便，
我们用术语尾递归优化（tail recursion optimization）,
来介绍Proper tail recursion的技术细节。
尾调用
这是一个很常见的概念，
但是为了完整性，这里还是要说一说。
我们看两个函数，f和g，他们的定义如下，
(define (f a)
(g 2)
(display a))
(define (g b)
(display b))
(f 1)
结果：
21
我们分析一下实际的调用过程，
求值(f 1)，会导致f的函数体被求值，
于是，先求值(g 2)，导致g的函数体被求值，输出2，
然后函数g返回了，返回到f的函数体中，
再接着执行下一条语句，输出1。
我们看到，对g的调用，不是f的最后一个调用。
称为g不是f的尾调用。
我们改一下例子，
(define (f a)
(display a)
(g 2))
(define (g b)
(display b))
(f 1)
结果：
12
现在g是f的尾调用了。
为什么要强调尾调用呢？
因为，如果g是f的尾调用，
g就可以不返回到f中，
而直接返回到f该返回的地方。
调用g的时候，就不会增长调用栈，
而是废弃原来f的调用环境即可。
不必要的调用栈不会增加，
使得尾递归可以在常量的调用栈空间中执行，
我们就可以放心的使用尾递归来替代循环了。
调用栈和调用图
从语言的实现角度来看，
每一次函数调用会初始化一个新的frame，
frame中保存着形参与实参的绑定。
例如：
(f 1)会产生一个frame，[(a 1)]
而环境，是一个frame的链表，
top-level环境中只有一个frame，表示了变量f和g的绑定，
[(f #<procedure>) (g #<procedure>)]
所以，进入f的函数体后，
新创建的frame会添加到f定义时的环境头部，
([(a 1)] [(f #<procedure>) (g #<procedure>)])
环境中有两个frame了。
f的函数体是在这个新环境中求值的。
f函数体的执行环境是对定义时环境的扩展，
这是词法作用域规则的简单实现。
我们再调用g，看看环境会怎样变化，
调用g会创建一个新的frame，[(b 2)]
这个frame会添加到g定义时的环境头部，
([(b 2)] [(f #<procedure>) (g #<procedure>)])
注意，环境并没有变成，
([(b 2)] [(a 1)] [(f #<procedure>) (g #<procedure>)])
新的frame并不会添加到调用g时的环境中去。
当g返回时，
环境又变成了f的执行环境，
([(a 1)] [(f #<procedure>) (g #<procedure>)])
跟踪运行环境的变化，我们发现，
在实现词法作用域之后，环境并不是一个栈结构的。
([(f #<procedure>) (g #<procedure>)]) ;top-level： frame0
([(a 1)] [(f #<procedure>) (g #<procedure>)]) ;进入f： frame1 <- frame0
([(b 2)] [(f #<procedure>) (g #<procedure>)]) ;进入g： frame2 <- frame0
([(a 1)] [(f #<procedure>) (g #<procedure>)]) ;回到f： frame1 <- frame0
([(f #<procedure>) (g #<procedure>)]) ;回到top-level： frame0
我们可以把frame0看成树根，
frame1，frame2看成子节点，
于是，环境构成了一棵树，
这就是为什么我们之前说环境是frame的链表，而不是列表的原因了。
既然这样，
那么尾调用也就不必服从弹栈规则了，
g返回，可以让执行环境返回到f该返回的状态。
([(f #<procedure>) (g #<procedure>)]) ;top-level： frame0
([(a 1)] [(f #<procedure>) (g #<procedure>)]) ;进入f： frame1 <- frame0
([(b 2)] [(f #<procedure>) (g #<procedure>)]) ;进入g： frame2 <- frame0
([(f #<procedure>) (g #<procedure>)])) ;直接返回到top-level： frame0
这种技术，称为尾调用优化。
尾递归的执行环境
我们来分析一下尾递归的执行环境，
请看阶乘函数的尾递归版本，
(define (fact n result)
(if (= n 1)
result
(fact (- n 1) (* result n))))
(+ 4 (fact 3 1))
结果：
10
top-level环境：([(fact #<procedure>)])
要计算(+ 4 (fact 3 1))，先要求值(fact 3 1)，
调用(fact 3 1)，进入函数体：([(n 3) (result 1)] [(fact #<procedure>)])
再次调用(fact 2 3)：([(n 2) (result 3)] [(fact #<procedure>)])，
词法作用域规则，扩展定义环境，
然后调用(fact 1 6)：([(n 1) (result 6)] [(fact #<procedure>)])，
这里要返回result了，值为6。
可是要返回到哪里呢？
我们看到以上的一系列调用都是尾调用，
所以，直接返回到了最开始调用(fact 3 1)的地方，
执行环境变成了，([(fact #)])，
于是，在这环境中求值(+ 4 6) -> 10
与continuation的关联
我们看到，要想实现这样的调用结构，
需要把环境中的绑定关系分配在内存堆中，
这样就可以让函数的调用者，显式控制返回环境了。
实现了尾调用优化后，
函数的调用者多了一种选择，
或者让函数执行后，返回到调用前的执行环境，
或者返回到调用者该返回的执行环境。
这其实是一种continuation的操作。
即，f调用g，g的continuation，
或者是f调用g后的continuation，
或者是f的continuation。
我们用CPS改写一下上面的例子，
非尾调用的情况，
(define *cont*
(lambda (x) x))
(define (f a cont)
(g 2
(lambda (v)
(cont (display a)))))
(define (g b cont)
(cont (display b)))
(f 1 *cont*)
结果：
21
我们看到非尾调用的g的continuation，
是执行display，再执行f的continuation。即，
(lambda (v)
(cont (display a)))
我们再看尾调用情况，
(define *cont*
(lambda (x) x))
(define (f a cont)
(display a)
(g 2 cont))
(define (g b cont)
(cont (display b)))
(f 1 *cont*)
结果：
12
尾调用g的continuation，
是f的continuation。
这给了我们一种方案，在写解释器的时候，
可以使用CPS来进行尾调用优化。
结语
为了进行尾调用优化，
语言实现必须对调用图进行控制，
或者说，显式的控制continuation。
与其把这种显式的控制隐藏在语言的实现里面，
不如开放给语言的使用者，
因为开放出来并不是特别困难。
这种非弹栈形式的跳转，
称为非局部跳转（non-local jump），
类似C语言的setjmp和longjmp。
call/cc就是这样产生的，
并不是为了追求另类，
而是实现尾调用优化的直接后果。
而且，call/cc捕获的continuation是first-class的，
可以当做参数传递，或者返回，
这极大的丰富的Scheme语言的表现力，
让程序员可以最大限度的控制跳转范围。
参考：
An Introduction to Scheme and its Implementation
Essentials of Programming Languages
Concepts in Programming Languages