3

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?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Giorgio
  • 5,023
  • 6
  • 41
  • 71

2 Answers2

4

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))
sds
  • 58,617
  • 29
  • 161
  • 278
  • I did not know about `flet`, thanks a lot! I think this is the only solution: a plain lambda won't work because I need recursion. – Giorgio Apr 18 '14 at 21:24
  • I still do not understand why a nested `defun` is allowed (and seems to work properly) if it should not be used. – Giorgio Apr 18 '14 at 21:28
  • 1
    CL offers plenty of opportunities to shoot oneself in the foot. It is a sophisticated language which is vastly different from Scheme. – sds Apr 20 '14 at 01:01
  • 1
    I had misunderstood the semantics of nested `defun`. What I wanted was a nested function as with Scheme's nested `define`. Instead, I was just executing `defun` multiple times in the body of a function, which results in defining the function multiple times in the current package. I even doubt that this was working at all: even if all the tests passed because the output lists were sorted, I think that all the defined functions used the same algorithm, namely the last global `merge-sort` that had been defined. So, it was worth asking this question because I have learnt a lot from the answers. – Giorgio May 01 '14 at 12:42
1

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.

Joshua Schwartz
  • 55
  • 5
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Thanks a lot for a very useful answer (+1). So `defun` always defines a global function in the current name space. Executing it within another function does not change this. I was using the same semantics of Scheme's nested `define`s (I'm no expert in either Scheme or Common Lisp). What I really wanted was a local function, and `flet` or `labels` (for recursive functions) is the right solution. Your example also explains another warning I was getting all the time in some older code (caused by a nested `defun`). I have fixed it now. – Giorgio May 01 '14 at 11:48
  • glad to have helped. And +1 for the well-posed question and keeping engaged. – Will Ness May 01 '14 at 12:22