CLisp - sorting and combining two lists in quicksort

Question

I'm trying to implement quicksort in CLisp, and so far I'm able to partition the list around a pivot. However, when I try to combine and recursively sort the sublists, I get either a stack overflow or an error with let, and I'm not sure what's going wrong. Here's my code:

(defun pivot (n xs)
  (list (getLesser n xs) (getGreater n xs))
)

(defun getLesser (m l)
  (cond
    ((null l) nil)
    ((<= m (car l)) (getLesser m (cdr l)))
    (t (cons (car l) (getLesser m (cdr l)))))
)

(defun getGreater (m l)
  (cond
    ((null l) nil)
    ((> m (car l)) (getGreater m (cdr l)))
    (t (cons (car l) (getGreater m (cdr l)))))
)


(defun quicksort (xs)
  (cond
    ((null xs) nil)
    (t
      (let (partition (pivot (car xs) xs))
        (cond
          ((null (car partition)) (cons (quicksort (cdr partition)) nil))
          ((null (cdr partition)) (cons (quicksort (car partition)) nil))
          (t (append (quicksort (car partition)) (quicksort (cdr partition)))))))))

My idea was to have a local variable partition that is a list of 2 lists, where car partition is the list of number less than the pivot, and cdr partition is the list of numbers greater than the pivot. Then, in the final cond construct, if there were no numbers less than the pivot I would recursively sort the 2nd list; if there were no numbers greater than the pivot I would sort the 1st list; else I would recursively sort both and append them in order. Can anyone help me out?

Answer 1

Compiling the file gives you hints about wrong syntax.

GNU CLISP produces these diagnostics:

$ clisp -q -c foo.lisp
;; Compiling file /tmp/foo.lisp ...
WARNING: in QUICKSORT in lines 20..28 : Illegal syntax in LET/LET*: (PIVOT (CAR XS) XS)
         Ignore the error and proceed
;; Deleted file /tmp/foo.fas
There were errors in the following functions:
 QUICKSORT
1 error, 1 warning

SBCL produces similar diagnostics:

$ sbcl --eval '(compile-file "foo.lisp")' --quit
This is SBCL 1.3.1.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
; compiling file "/tmp/foo.lisp" (written 08 MAY 2019 08:58:54 PM):
; compiling (DEFUN PIVOT ...)
; compiling (DEFUN GETLESSER ...)
; compiling (DEFUN GETGREATER ...)
; compiling (DEFUN QUICKSORT ...)
; file: /tmp/foo.lisp
; in: DEFUN QUICKSORT
;     (LET (PARTITION (PIVOT (CAR XS) XS))
;       (COND ((NULL (CAR PARTITION)) (CONS (QUICKSORT #) NIL))
;             ((NULL (CDR PARTITION)) (CONS (QUICKSORT #) NIL))
;             (T (APPEND (QUICKSORT #) (QUICKSORT #)))))
; 
; caught ERROR:
;   The LET binding spec (PIVOT (CAR XS) XS) is malformed.
; 
; compilation unit finished
;   caught 1 ERROR condition


; /tmp/foo.fasl written
; compilation finished in 0:00:00.021

You can then look up the expected syntax in CLHS: http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/speope_letcm_letst.html