Common Lisp递归辅助函数是否有样式约定？

Question

我想知道是否存在由ANSI或实现作者或其他有影响力的权威机构发布的样式指南,用于使用递归辅助函数实现的Lisp函数,这些函数采用其他参数,调用函数的人不需要考虑.这是我能想到的最简单的例子.这三个中的哪一个(如果有的话)在常见的lisp(如果有的话)的标准化样式指南中是首选的？

(defun factorial (n)
   (defun tail-factorial (n m)
      (if (= n 1)
          m
          (tail-factorial (- n 1) (* n m))))
   (tail-factorial n 1))

由于函数声明中的函数声明,这看起来很不愉快.我会使用lambda来避免命名辅助函数和卷积事物,但我不清楚如何通过调用自身来递归lambda表达式.即使有办法让匿名函数调用本身,它似乎会变得混乱,特别是如果帮助者需要帮助者需要帮助...

另一个选择是首先声明尾巴的人(或之后,但这会让sbcl抱怨):

(defun tail-factorial (n m)
   (if (= n 1)
      n
      (tail-factorial (- n 1) (* n m))))
(defun factorial (n)
   (tail-factorial n 1))

这看起来很不愉快,因为有人阅读我的代码会看到尾部因素并且可能觉得需要理解它,即使它只是阶乘的辅助函数而且不会在其他地方使用.在我自己的代码中,我一直在编写与此类似的函数,我很难提出一些评论,这些评论会让我重新理解我从现在开始几个月或几年的工作.再一次,当助手需要助手需要时,情况变得非常糟糕......

另一种选择使用选项:

(defun factorial (n &optional (m 1))
   (if (= n 1)
      m
      (factorial (- n 1) (* n m))))

这看起来很不愉快,因为我们只期望一个因子论证.在这个函数之外没有人有理由用第二个参数来调用它.我觉得尝试用我永远不会使用的可选参数来理解代码很烦人.

现在,我很清楚,问你认为最好的是主观对话堆栈溢流不喜欢,所以我的客观问题是,是否存在某种标准化的风格指南,关于哪些替代方案是首选.我使用SBCL,并没有在他们的网站上找到这种东西的指南,我不知道ANSI或任何其他标准化机构,包括其他实现者发布的这样的指南.

也许完全有另一种选择,我欢迎你的建议.我一直在遇到需要一个辅助函数(需要一个辅助函数等)的情况,我想习惯以大多数人都会发现的方式写作.有人在一个lambda函数的Recursing中提出了类似的问题,有几个人推荐了一些最喜欢的宠物项目,但没有人提到样式指南.

提前致谢!

Answer 1

defun只做全局功能.如果你defun在里面使用,defun你实际上每次调用时都会创建一个新的全局函数.要使本地词法功能只能factorial在标准方式内使用labels

(defun factorial (n)
   (labels ((tail-factorial (n m)
              (if (= n 1)
                  m
                  (tail-factorial (- n 1) (* n m)))))
     (tail-factorial n 1)))

Common Lisp无法保证尾部调用优化,因此这可能会破坏堆栈.对于认真的工作,你会使用loop宏来做到这一点.

可选参数有效,但如果不是用户想要提供它的意图,你真的不应该使内部可选.然后它只是泄漏抽象和制作令人困惑的文档.

Answer 2

我认为一些答案提供了更一般的答案,但我想指出尾部递归辅助函数的一些最常见的用法通常使用do循环非常干净地表达.使用do循环,您可以声明变量,它们的初始值,步骤形式(下一次迭代的值),终止条件和结果形式.(其中一些是可选的,但我们将在这里使用所有这些.)从这个意义上讲,do更像是Scheme的名为let,除了你最终不会在体内进行递归调用.事实上,很多时候,你最终根本不需要身体.对于阶乘函数,您的代码可以表示为:

(defun factorial (n)
  (do ((n n (1- n))    ; n starts as n, and is (1- n) on next iteration
       (m 1 (* n m)))  ; m starts at 1, and is (* m n) on next iteration
      ((= 1 n) m)))    ; if (= 1 n), then return m, else go to next iteration

CL-USER> (factorial 11)
39916800

说到命名let,你可以很容易地在Common Lisp中的标签实现它:

(defmacro nlet (name bindings &body body)
  `(labels ((,name ,(mapcar 'first bindings)
              ,@body))
     (,name ,@(mapcar 'second bindings))))

CL-USER> (macroexpand-1 '(nlet factorial ((n n) (m 1))
                          (if (= n 1) m
                              (factorial (1- n) (* m n)))))
(LABELS ((FACTORIAL (N M)
           (IF (= N 1)
               M
               (FACTORIAL (1- N) (* M N)))))
  (FACTORIAL N 1))

但是,仍然存在Common Lisp实现不必支持尾递归的问题,但如果你来自Scheme背景,它可能是一个有用的实用程序.你可以实现一个nlet类型的宏,它使递归调用进入下一次迭代,但这不会完全相同,因为你只想在尾部位置使用"重用堆栈帧"行为; 在非尾部位置,你仍然希望得到适当的回报.

上面的实现中一个非常微妙的错误

正如Sylwester在评论中指出的那样,上面的nlet实现中存在一个非常微妙的错误.因为对本地函数的调用发生在定义它的词法范围内,所以执行类似的操作

(nlet frob ((f #'frob))
   ...)

使初始化程序#'foo成为对新本地函数的引用.这可能不是你想要的,而且不是Scheme命名的let.你可以通过从标签表单返回本地函数并在该范围之外调用它来解决这个问题:

(defmacro nlet (name bindings &body body)
  `(funcall (labels ((,name ,(mapcar 'first bindings)
                       ,@body))
              #',name)
            ,@(mapcar 'second bindings)))

CL-USER> (macroexpand-1 '(nlet factorial ((n n) (m 1))
                          (if (= n 1) m
                              (factorial (1- n) (* m n)))))
(FUNCALL
 (LABELS ((FACTORIAL (N M)
            (IF (= N 1)
                M
                (FACTORIAL (1- N) (* M N)))))
   #'FACTORIAL)
 N 1)

(defmacro nlet (name bindings &body body)
  `(funcall (labels ((,name ,(mapcar 'first bindings)
                       ,@body))
              #',name)
            ,@(mapcar 'second bindings)))

Answer 3

好的风格是：

• 有用的功能名称
• 文档字符串
• 参数类型检查
• 可移植代码中没有控制堆栈溢出源->大多避免尾递归代码

例：

(defun factorial (n &aux (result 1))
  "Calculates the factorial N! for N >= 0"
  (check-type n (integer 0 *))
  (loop for i from 1 to n
        do (setf result (* result i)))
  result)

使用方法：

CL-USER 94 > (apropos "factorial")
FACTORIAL (defined)

CL-USER 95 > (documentation 'factorial 'function)
"Calculates the factorial N! for N >= 0"

CL-USER 96 > (factorial 7)
5040