Common Lisp中的Stackoverflow Mergesort

我已经写了我的第一个Common Lisp函数，并且无法跟踪我的错误产生的位置。如何排查以下错误：Common Lisp中的Stackoverflow Mergesort

Error: Stack overflow on value stack. While executing: 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)

来源

2016-06-22 defaultNINJA

我建议阅读一本介绍性的Lisp书。请参阅：https://www.cs.cmu.edu/~dst/LispBook/index.html 您的代码不可修复。这是foobar。 Lisp中几乎每行代码都是错误的。它看起来像C，但在Lisp中不起作用。把它扔掉。白手起家。尝试编写Lisp代码，而不是C代码。 –

您的**合并列表**已由Common Lisp提供为[**合并**]（http://www.lispworks.com/documentation/HyperSpec/Body/f_merge.htm）。 –

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

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's，setf's vs Let。

上面的代码通过设置它们在顶层环境中创建变量（除非当然，你已经在其他地方对它们进行了deframerametered）。随着程序变大，这可能会产生一些不良的副作用（如果两个功能同时使用“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.形式可以返回值

口齿不清形式往往会返回一个值。如果我们在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 :(MERGESORT（5 1 4 2 3）0 1/2） 4 :(MERGESORT（5 1 4 2 3）0 1/4） 5 :(MERGESORT（5 1 4 2 3 ）0 1/8） 6 :(MERGESORT（5 1 4 2 3）0 1/16） 7 :(MERGESORT（5 1 4 2 3）0 1/32） 8 :(MERGESORT（5 1 4 2 3）0 1/64） 9 :(MERGESORT（5 1 4 2 3）0 1/128） 10 :(MERGESORT（5 1 4 2 3）0 1/256） 11 :(MERGESORT（5 1 4 2 3）0 1/512） 12：（MERGESORT（5 1 4（MERGESORT（5 1 4 2 3）0 1/4096） 15 1 4 2 3）08192分之1） 16：（归并（5 1 4 2 3）016384分之1）

在线路600看到

600：（归并（5 1 4 2 3 ）0 1/1037378892220248239628101965922790287753111558060609224998914332422663202853227036599926762236775948572049471652825197295598787768852943826971718708528490921765295450850377380921344）

这是一个非常小的数量和解释关于truncate的错误消息。

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

我们需要做的是让mergelist在每次调用时都返回一个值的明确性。

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

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

此外，您将不得不在mergesort中捕获该返回值，并使mergesort返回一个显式值。

我也建议你阅读一下关于循环宏的内容 - 谷歌的“黑带实用通用Lisp循环”，这将有助于你掌握语法和你可以用循环做的事情。

现在，还有几件事情的代码来解决，但我希望我已经给你足够的通过这个迭代

来源

2016-06-22 03:18:38

谢谢，这非常有帮助。这是我的一次尝试。怀疑我会再次使用Common Lisp。试图获得足够的基础知识来将这种简单的排序结合在一起。一直无法找到Common Lisp的资源。 – defaultNINJA

@defaultNINJA还值得指出的是，您的**合并列表**已由Common Lisp提供为[** merge **]（http://www.lispworks.com/documentation/HyperSpec/Body/f_merge.htm）。 –

@defaultNINJA有关更多资源，请参阅：http://stackoverflow.com/questions/7224823/where-to-learn-how-to-practically-use-common-lisp –

获得有太多错误的代码：

将列表视为向量：如果您想要随机访问Lisp数据结构，则使用向量。不是一个列表。
不声明变量
while循环完全不
势在必行工作，而不是功能
错误代码布局

最好从头开始并避免上面的错误。如果你想要Lisp列表，那么使用不同的方式来编写mergesort。提示：列表不像载体。他们可能会这样使用，但通常这是错误的。

来源

2016-06-22 07:31:33

不错的尝试... Common Lisp允许它。阅读Common Lisp。 – defaultNINJA

Common Lisp中的Stackoverflow Mergesort

回答

相关问题