list - Common Lisp Mergesort 中的 Stackoverflow

Question

我已经编写了我的第一个 Common Lisp 函数，但我无法追踪我的错误是在哪里产生的。我该如何解决以下错误:

错误:值堆栈上的堆栈溢出。执行时:TRUNCATE

这是我的代码:

(defun mergelist (alist low mid high)
    (setq i1 low)
    (setq i2 (+ mid 1))
    (setq i low)
    (setq blist `())
    (loop while (and (<= i1 mid) (<= i2 high)) do
        (if (<= (nth i1 alist) (nth i2 alist))
            (setf (nth (+ i 1) blist) (nth (+ i1 1) alist))
            (setf (nth (+ i 1) blist) (nth (+ i2 1) alist))
        )
    )
    (loop while (<= i1 mid) do
       (setf (nth (+ i 1) blist) (nth (+ i1 1) alist)) 
    )
    (loop while (<= i2 high) do
        (setf (nth (+ i 1) blist) (nth (+ i2 1) alist))  
    )
    (setq j low)
    (loop for j from j to high do
        (setf (nth i alist) (nth i blist))
    )
)

(defun mergesort (alist low high)
    (when (< low high)
        (mergesort alist low (/ (+ low high) 2))
        (mergesort alist (/ (+ low high) (+ 2 1)) high)
        (mergelist alist low (/ (+ low high) 2) high)
    )
)

以下是我测试功能的方式:

(setq dlist `(5 1 4 2 3))
(mergesort dlist 0 4)

我的预期返回是:

(1 2 3 4 5)

Answer 1

我们可以做很多事情来改进这段代码。

<强>1。缩进

Lisp 的语法相对较少，但我们使用缩进来帮助突出代码的结构。大多数支持 Lisp 的编辑器都有助于管理这一点。与传统缩进方法最明显的区别是在后面几行的右括号。我缩进了 mergelist 函数以显示一个更具可读性的函数体 - 好吧，至少对我来说是这样。

(defun mergelist (alist low mid high) 
  (setq i1 low)
  (setq i2 (+ mid 1))
  (setq i low)
  (setq blist `())
  (loop while (and (<= i1 mid) (<= i2 high)) do
       (if (<= (nth i1 alist) (nth i2 alist))
       (setf (nth (+ i 1) blist) (nth (+ i1 1) alist))
       (setf (nth (+ i 1) blist) (nth (+ i2 1) alist))))
  (loop while (<= i1 mid) do
       (setf (nth (+ i 1) blist) (nth (+ i1 1) alist)))
  (loop while (<= i2 high) do
       (setf (nth (+ i 1) blist) (nth (+ i2 1) alist)))
  (setq j low)
  (loop for j from j to high do
       (setf (nth i alist) (nth i blist))))

<强>2。 Setq、setf 与 Let。

上面的代码通过设置它们在顶级环境中创建变量(当然，除非您在别处对它们进行了 defparametered)。随着程序变大，这可能会产生一些不良副作用(如果两个函数同时使用“i”怎么办？)。最好使用 LET 来创建局部词法变量，例如

(defun mergelist-2 (alist low mid high)
  (let ((i1 low)
    (i2 (+ mid 1)
      i (low)
      blist '()))

   (loop while (and (<= i1 mid) (<= i2 high)) do
       (if (<= (nth i1 alist) (nth i2 alist))
       (setf (nth (+ i 1) blist) (nth (+ i1 1) alist))
       (setf (nth (+ i 1) blist) (nth (+ i2 1) alist))))
  (loop while (<= i1 mid) do
       (setf (nth (+ i 1) blist) (nth (+ i1 1) alist)))
  (loop while (<= i2 high) do
       (setf (nth (+ i 1) blist) (nth (+ i2 1) alist)))
  (setq j low)
  (loop for j from j to high do
       (setf (nth i alist) (nth i blist))) ))

<强>3。表单可以返回值

lisp 形式通常返回一个值。如果我们在 repl 中输入 (+ 1 2)，我们将看到 3。defun 通常会返回一个值，通常作为其主体中的最后一个形式。

如果我们查看 mergelist，我们会发现它不是显式返回任何值，而是试图使用变量 alist 来传达返回值。这行不通!

Lisp 提供了跟踪工具，让我们了解内部发生了什么

这是跟踪的前 16 行。我的系统在第 600 行崩溃了

0: (合并排序 (5 1 4 2 3) 0 4) 1: (合并排序 (5 1 4 2 3) 0 2) 2:(合并排序(5 1 4 2 3)0 1) 3:(合并排序(5 1 4 2 3)0 1/2) 4:(合并排序(5 1 4 2 3)0 1/4) 5:(合并排序(5 1 4 2 3)0 1/8) 6:(合并排序(5 1 4 2 3)0 1/16) 7:(合并排序(5 1 4 2 3)0 1/32) 8:(合并排序(5 1 4 2 3)0 1/64) 9:(合并排序(5 1 4 2 3)0 1/128) 10:(合并排序(5 1 4 2 3)0 1/256) 11:(合并排序(5 1 4 2 3)0 1/512) 12:(合并排序(5 1 4 2 3)0 1/1024) 13:(合并排序(5 1 4 2 3)0 1/2048) 14:(合并排序(5 1 4 2 3)0 1/4096) 15:(合并排序(5 1 4 2 3)0 1/8192) 16:(合并排序(5 1 4 2 3)0 1/16384)

第 600 行

600: (合并排序 (5 1 4 2 3) 0 1/1037378892220248239628101965922790287753111558060609224998914332422663202853227036599926762236775948572049471652825197295598787768852943826971718708528490921765295450850377380921344)

这是一个非常小的数字，解释了有关截断的错误消息。

您可以看到，当我们沿着调用堆栈向下进行时，列表数组没有改变。那是因为 alist 函数参数对于 mergelist 的每次调用都是本地的。

我们需要做的是每次调用 mergelist 时返回一个值 explicity。

(defun mergelist-3 (alist low mid high)
  (let ((i1 low)
    (i2 (+ mid 1)
      i (low)
      j
      blist '()))

   (loop while (and (<= i1 mid) (<= i2 high)) do
       (if (<= (nth i1 alist) (nth i2 alist))
       (setf (nth (+ i 1) blist) (nth (+ i1 1) alist))
       (setf (nth (+ i 1) blist) (nth (+ i2 1) alist))))
  (loop while (<= i1 mid) do
       (setf (nth (+ i 1) blist) (nth (+ i1 1) alist)))
  (loop while (<= i2 high) do
       (setf (nth (+ i 1) blist) (nth (+ i2 1) alist)))
  (setq j low)
  (loop for j from j to high do
       (setf (nth i alist) (nth i blist)))
  *;return value here*
  ))

作为进一步的提示，不需要函数中的最后一个循环。

此外，您必须在合并排序中捕获该返回值，并让合并排序也返回一个显式值。

我还建议您阅读一些有关循环宏的内容 - 谷歌搜索“黑带实用通用 Lisp 循环”，这将帮助您掌握语法以及可以使用循环执行的操作。

现在，代码中还有一些问题需要修复，但我希望我已经给了你足够的时间来完成这次迭代