3

我在 Common Lisp 中有一个通用的合并排序实现：我有不同的拆分和合并函数实现，并且对于拆分和合并函数的每个组合，我想构造一个合并排序函数。

  • 任何拆分函数都将字符串列表作为输入并返回两个列表的列表：原始列表的两半。
  • 任何合并函数都将两个排序列表作为输入并返回排序后的合并列表。

每个归并排序函数都是通过调用以下函数创建的：

(defun make-merge-sort-function (split-function merge-function)

  (defun merge-sort (lst)
    (if (or (null lst) (null (cdr lst)))
        lst
        (let ((s (funcall split-function lst)))
          (funcall merge-function (merge-sort (car s)) (merge-sort (cadr s))))))

  (lambda (lst)
    (merge-sort lst)))

我在merge-sort里面定义make-merge-sort-function是为了保持它的名字私有并避免破坏命名空间。

我的代码适用于几个 Common Lisp 实现（例如 Steel Bank Common Lisp）：

  • 我所有测试运行的输出都正确排序，
  • 每个生成的合并排序函数都有不同的执行时间，表明使用了不同的拆分/合并组合。

所以，我假设我的代码是正确的。

但是，如果我使用 Allegro Common Lisp 运行程序，我会收到警告：

Warning: MERGE-SORT is defined more than once as `operator' in file foo.lisp.

调用foo.lisp的文件在哪里。make-merge-sort-function因此，该程序工作正常，但它会在第一次调用之后的每次调用时打印一次此警告make-merge-sort-function。如果我将merge-sort函数设为全局函数（带有两个附加参数split-function和merge-function），那么警告就会消失。

我没有在 Allegro Common Lisp 中找到有关此警告含义的任何指示。我尝试过的其他实现（ABCL、CMUCL、CCL、CLISP、SBCL）不会发出任何警告。我认为可以多次定义内部函数（闭包）的新实例，但我不明白为什么这应该是一个问题。有任何想法吗？

4

2 回答 2

4

你永远不会嵌套defun在 Common Lisp 中。

就像你使用letinside defun而不是 defvar，你使用 labels而不是嵌套defun：

(defun make-merge-sort-function (split-function merge-function)
  (labels ((merge-sort (lst)
             (if (or (null lst) (null (cdr lst)))
                 lst
                 (let ((s (funcall split-function lst)))
                   (funcall merge-function (merge-sort (car s)) 
                                           (merge-sort (cadr s)))))))
    #'merge-sort))
于 2014-04-18T21:06:39.190 回答
1

您没有显示您的测试代码，因此，请考虑以下 CLISP 会话记录：

[3]> (defun make-merge-sort-function (split-function merge-function)
  (defun merge-sort (lst)
    (if (or (null lst) (null (cdr lst)))
        lst
        (let ((s (funcall split-function lst)))
          (funcall merge-function (merge-sort (car s))
                                  (merge-sort (cadr s))))))
  (lambda (lst)
    (merge-sort lst)))
MAKE-MERGE-SORT-FUNCTION
[4]> (fboundp 'merge-sort)
NIL                         <<---------------------------- NB
[5]> (defun sp1(x)(princ" IN SPL1 ") x)
SP1
[6]> (defun sp2(x)(princ" IN SPL2 ") x)
SP2
[7]> (defun mg1(x y)(princ" IN MRG1 ") x)
MG1
[9]> (setq f1 (make-merge-sort-function #'sp1 #'mg1))
#<FUNCTION :LAMBDA (LST) (MERGE-SORT LST)>
[10]> (fboundp 'merge-sort)
T                           <<---------------------------- NB !!
[12]> (funcall f1 '(1 2 3))
 IN SPL1                    <<---------------------------- NB
*** - CDR: 1 is not a list
[14]> (setq f2 (make-merge-sort-function #'sp2 #'mg1))
#<FUNCTION :LAMBDA (LST) (MERGE-SORT LST)>
[15]> (funcall f1 '(1 2 3))
 IN SPL2                    <<---------------------------- NB !!!
*** - CDR: 1 is not a list

现在您可以看到您的代码所做的事情与您认为的有所不同，并且您的测试代码可能只是没有解决这个问题。

显然，嵌套defun定义了一个全局可访问的函数merge-sort，第二次调用make-merge-sort-function重新定义了它。

于 2014-05-01T07:13:14.710 回答