在Common Lisp中使用宏优化尾递归函数
尾递归函数
通俗地讲,递归函数就是指这个函数的定义当中调用了对自己。如果一个递归函数在调用了自己后就返回,这样便是尾递归。
例如,一个计算列表的长度的递归函数的定义可能是这样的
(defun my-length (lst) (if (null lst) 0 (+ 1 (my-length (cdr lst)))))
而一个使用欧几里得算法计算最大公约数的递归函数,可能是这样的
(defun my-gcd (a b) (if (zerop (mod a b)) b (my-gcd b (mod a b))))
在my-gcd中调用了自己后就返回了,那么它便是一个尾递归的函数。
尾递归函数的优势之一,是它们可以被优化成类似循环的代码。这样可以避免普通的递归函数执行过程中,递归深度过大造成的栈溢出。下面先演示一遍手动优化的办法,再给出一个宏辅助这一优化的过程。
手动优化尾递归函数的方法
一种机械化的优化尾递归的办法是使用“赋值”和“跳转”来改写函数定义。以上面的my-gcd函数为例,将b和(mod a b)传递给my-gcd函数,相当于是:
- 将b和(mod a b)“同时”赋值给参数a和b
- 将函数的执行流程跳回最开始的位置重新执行
按照这个方法,可以把my-gcd改写成下面的样子
(defun my-gcd-tco (a b) (tagbody begin (if (zerop (mod a b)) (return-from my-gcd-tco b) (progn (psetf a b b (mod a b)) (go begin)))))
使用Common Lisp内建的psetf,可以轻松实现将b和(mod a b)“同时”赋值给a和b。
不幸的是,由于if嵌在了tagbody内,所以必须使用return-from主动从my-gcd中返回最终的计算结果。
通过宏简化上述优化的过程
宏可以帮助我们简化上面的手动优化过程。关键的一点,是要将尾递归的函数调用替换为progn,其中含有psetf和go——听起来也是宏做的事情。所以,我们写出的宏展开后包含一个“子”宏,这个子宏与尾递归函数的同名,它将展开为所需要的progn——macrolet可以实现这个需求。这个辅助优化的宏定义如下
(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)))))
采用这个宏定义的my-gcd函数如下
(define-rec my-gcd (a b) (if (zerop (mod a b)) (return-from my-gcd b) (my-gcd b (mod a b))))
用macroexpand-1或SLIME提供的slime-expand-1命令展开上述代码可以得到如下结果
(DEFUN MY-GCD-TCO (A B) (TAGBODY #:G675 (MACROLET ((MY-GCD-TCO (&REST EXPRS) `(PROGN (PSETF ,@(MAPCAN #'LIST '(A B) EXPRS)) (GO ,'#:G675)))) (IF (ZEROP (MOD A B)) (RETURN-FROM MY-GCD-TCO B) (MY-GCD-TCO B (MOD A B))))))
与手动优化的结果可说是相差无几了