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

什么是尾递归

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

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

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

(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函数，可以改写为如下形式

(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中实现

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

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

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

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

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

(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-gcd和my-length函数的改写都是很有规律的，甚至可以通过一个宏来帮助我们自动完成这种变换。这个宏所需要做的事情其实只有三件：

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

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

(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))))))

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

(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)))))

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

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

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

(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)，在我的机器上会输出如下内容

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，求值同样的表达式的输出为

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确实不需要调用自身。

全文完