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