Nested `defun` produces a repeated warning in Allegro Common Lisp

Question

I have a generic implementation of merge sort in Common Lisp: I have different implementation of split and merge functions and, for each combination of a split and merge function I want to construct a merge sort function.

• Any split function takes a list of strings as input and returns a list of two list: the two halves of the original list.
• Any merge function takes two sorted lists as input and returns the sorted merged list.

Each merge sort function is created by invoking the following function:

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

I have defined merge-sort inside make-merge-sort-function in order to keep its name private and avoid spoiling the name space.

My code works with several Common Lisp implementations (e.g. Steel Bank Common Lisp):

• the output of all the my test runs is sorted properly,
• each resulting merge sort function has a different execution time, indicating that different split / merge combinations were used.

So, I assume that my code is correct.

However, if I run the program with Allegro Common Lisp, I get a warning:

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

where foo.lisp is the file in which make-merge-sort-function is invoked. So, the program works fine but it prints this warning once for each invocation of make-merge-sort-function after the first one. If I make the merge-sort function global (with two additional arguments split-function and merge-function), then the warnings go away.

I have not found any indication regarding the meaning of this warning in Allegro Common Lisp. Other implementations I have tried (ABCL, CMUCL, CCL, CLISP, SBCL) do not issue any warning. I think it is OK that a fresh instance of the internal function (closure) is defined multiple times and I do not understand why this should be a problem. Any ideas?

Answer 1

You never nest defun in Common Lisp.

Just like you use let inside defun instead of defvar, you use labels instead of nested 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))

Answer 2

You do not show your test code, so, consider this CLISP session transcript:

[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

Now you can see that your code was doing something different than what you thought it was doing, and your test code probably just didn't flush that problem out.

Apparently, the nested defun defines a globally-accessible function merge-sort, and the second invocation of make-merge-sort-function redefines it.