如何用Common Lisp实现尾递归优化

什么是尾递归

如果一个函数在定义时引用了自身,那么这个函数就是一个递归函数。例如我们所熟知的阶乘就可以通过递归函数的形式予以定义

1
2
3
4
(defun fact (n)
(if (<= n 0)
1
(* n (fact (1- n)))))

在if语句的备选路径上,正在定义的函数fact被自身所调用,因此fact就是一个递归函数了。递归有一类较为特殊的形式,叫做尾递归,它们的特征是递归函数的调用位于被定义函数的最后一个步骤。也就是说,这个递归调用的返回值也就是整个函数调用的返回值,后面不再有其它的计算步骤了。例如实现了辗转相除法的下面这个函数就是尾递归的

1
2
3
4
(defun my-gcd (a b)
(cond ((zerop a) b)
((zerop b) a)
(t (my-gcd b (mod a b)))))

此处命名为my-gcd,是因为在Common Lisp中已经预置了一个叫做gcd的函数了

什么是尾递归优化

递归调用其实也就是函数调用,每一次调用都需要保存当前的执行上下文(寄存器的值、程序计数器的值等信息)并压入栈中。如果递归调用得非常深,那么很可能将栈空间消耗殆尽导致程序崩溃,因此很多时候都会选择使用循环来实现用递归实现的效果。尾递归形式的一个优势,就在于编译器可以对其进行优化,使得原本需要添加一个栈帧的函数调用操作,直接重用当前的调用中所使用的栈帧即可。这样一来,递归函数的调用就不会无节制地消耗栈空间了。

另一种对尾递归进行优化的方式,则是将其改写为【赋值】与【跳转】。例如对于上面的my-gcd函数,可以改写为如下形式

1
2
3
4
5
6
7
8
9
(defun my-gcd (a b)
(tagbody
rec
(cond ((zerop a) (return-from my-gcd b))
((zerop b) (return-from my-gcd a))
(t (progn
(psetf a b
b (mod a b))
(go rec))))))

如何在Common Lisp中实现

如果要使用递归的形式定义一个计算列表长度的函数,那么很可能会写出这样子的代码

1
2
3
4
(defun my-length (lst)
(if (null lst)
0
(1+ (my-length (rest lst)))))

采用累加器的思路,可以将上述函数改写为下面的尾递归形式

1
2
3
4
(defun my-length (lst acc)
(if (null lst)
acc
(my-length (rest lst) (1+ acc))))

对于第二个版本的my-length函数,同样可以手动改写为基于【赋值】和【跳转】的实现形式,结果如下

1
2
3
4
5
6
7
8
9
(defun my-length (lst acc)
(tagbody
rec
(if (null lst)
(return-from my-length acc)
(progn
(psetf lst (rest lst)
acc (1+ acc))
(go rec)))))

你可能已经注意到了,my-gcdmy-length函数的改写都是很有规律的,甚至可以通过一个宏来帮助我们自动完成这种变换。这个宏所需要做的事情其实只有三件:

  1. 将原本的定义中的函数体包裹在一个tagbody
  2. 将原本作为返回值的表达式包裹在一个return-from
  3. 将递归调用的表达式改为按顺序执行的psetfgo的组合

为了降低一下实现难度,第二点暂时就不处理了,函数的实现者必须手动编写return-from语句。因此,如果只考虑首尾两个条件,首先,可以考虑实现第三条,将函数体内的递归调用修改为prognpsetfgo的组合。要实现这个变换,可以使用macrolet,如下

1
2
3
4
5
6
7
8
9
10
(defun my-length (lst acc)
(tagbody
rec
(macrolet ((my-length (&rest args)
`(progn
(psetf ,@(mapcan #'list '(lst acc) args))
(go rec))))
(if (null lst)
(return-from my-length acc)
(my-length (rest lst) (1+ acc))))))

为了自动生成上面的代码,我编写了这样的一个宏

1
2
3
4
5
6
7
8
9
10
(defmacro define-rec (name lambda-list &body body)
(let ((rec (gensym)))
`(defun ,name ,lambda-list
(tagbody
,rec
(macrolet ((,name (&rest exprs)
,``(progn
(psetf ,@(mapcan #'list ',lambda-list exprs))
(go ,',rec))))
,@body)))))

利用上面这个宏编写一个计算列表长度的尾递归形式的函数,代码如下

1
2
3
4
(define-rec my-length (lst acc)
(if (null lst)
(return-from my-length acc)
(my-length (rest lst) (1+ acc))))

利用macroexpand-1或者是SLIME提供的展开一次宏的调试功能,在我的及其上得到的代码如下

1
2
3
4
5
6
7
8
9
10
(DEFUN MY-LENGTH (LST ACC)
(TAGBODY
#:G937
(MACROLET ((MY-LENGTH (&REST EXPRS)
`(PROGN
(PSETF ,@(MAPCAN #'LIST '(LST ACC) EXPRS))
(GO ,'#:G937))))
(IF (NULL LST)
(RETURN-FROM MY-LENGTH ACC)
(MY-LENGTH (REST LST) (1+ ACC))))))

跟上面手写的代码没有太大的差别,并且用于计算所得到的列表长度也是正确的。那么如何验证这个函数是采用了【赋值】和【跳转】的机制来完成运算的呢?可以借助Common Lisp提供的trace函数。如果使用的真实执行递归调用的my-length函数的定义,那么执行(trace my-length)后运行(my-length '(1 2 4 5) 0),在我的机器上会输出如下内容

1
2
3
4
5
6
7
8
9
10
11
12
CL-USER> (my-length '(1 2 4 5) 0)
0: (MY-LENGTH (1 2 4 5) 0)
1: (MY-LENGTH (2 4 5) 1)
2: (MY-LENGTH (4 5) 2)
3: (MY-LENGTH (5) 3)
4: (MY-LENGTH NIL 4)
4: MY-LENGTH returned 4
3: MY-LENGTH returned 4
2: MY-LENGTH returned 4
1: MY-LENGTH returned 4
0: MY-LENGTH returned 4
4

而如果是使用define-rec宏定义的my-length,求值同样的表达式的输出为

1
2
3
4
CL-USER> (my-length '(1 2 4 5) 0)
0: (MY-LENGTH (1 2 4 5) 0)
0: MY-LENGTH returned 4
4

显然,这当中没有递归的函数调用,my-length确实不需要调用自身。

全文完