CLISP-在QuickSort中排序并结合了两个列表

Question

我正在尝试在CLISP中实现QuickSort，到目前为止，我能够在枢轴周围划分列表。但是，当我尝试组合并递归对订书片进行递归分类时，我会出现堆栈溢出或let的错误，而我不确定出了什么问题。这是我的代码：

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

我的想法是拥有一个局部变量partition，该变量是2个列表的列表，其中car partition是小于枢轴的数字列表，而cdr partition是大于枢轴的数字列表。然后，在最终的cond构造中，如果没有少于枢轴的数字，我会递归对第二列表进行排序；如果没有大于枢轴的数字，我将排序第一列表；否则，我会递归对它们进行整理并按顺序附加附加。谁能帮我吗？

Answer 1

编译文件为您提供有关错误语法的提示。

gnu clisp产生以下诊断：

$ 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产生类似的诊断：

$ 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

您可以在CLHS中查找预期的语法：http：//www.ai.mit.mit.edu/projects/iiip/doc/doc/commonlisp/hyperspec/body/speope_letcm_letcm_letcm_letst.html

LET的语法是(令boding。body(，其中 bindings 是绑定的列表；每个绑定是(符号值(列表。或者，绑定只能是符号，代表(符号nil(。您的代码是：

(let (partition (pivot (car xs) xs))
  ...)

让我们写一个每行绑定，并将所有绑定标准化为适当的列表：

(let ((partition nil)
      (pivot (car xs) xs)))
  ...)

您可以看到代码：

• 将partition绑定到NIL
• 具有畸形的第二个绑定：共有三个元素，即pivot，(car xs)和xs，它们与预期(符号值(语法不匹配。语法。