Common Lisp Mergesort 中的 Stackoverflow
Stackoverflow in Common Lisp Mergesort
我已经编写了我的第一个 Common Lisp 函数,但我无法追踪我的错误是在哪里产生的。我该如何解决以下错误:
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)
我的预期 return 是:
(1 2 3 4 5)
我们可以做很多事情来改进此代码。
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 vs 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。表格可以return值
Lisp 形式通常 return 是一个值。如果我们在 repl 中输入 (+ 1 2),我们将看到 3。defun 通常 return 一个通常作为其主体中最后形式的值。
如果我们查看 mergelist,我们会发现它不是显式 returning 任何值,而是试图使用变量 alist 来传达 return 值。这不起作用!
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 return 每次调用时都有一个值显式。
(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*
))
进一步提示,不需要函数中的最后一个循环。
此外,您必须在合并排序中捕获该 return 值,并使合并排序 return 也成为一个显式值。
我还建议您阅读一些有关循环宏的内容 - google for "Practical Common Lisp Loop for Black belts" 这将帮助您掌握语法以及可以使用循环执行的操作。
现在,代码中仍有一些问题需要修复,但我希望我已经给了你足够的时间来完成这次迭代
代码错误太多:
- 将列表视为向量:如果你想要一个随机访问的 Lisp 数据结构,那么使用向量。不是列表。
- 不声明变量
- while 循环根本不起作用
- 命令式的,而不是功能性的
- 错误的代码布局
最好从头开始,避免以上错误。如果您想要 Lisp 列表,请使用不同的方式来编写归并排序。提示:列表不像向量。它们可能会被这样使用,但通常这样做是错误的。
我已经编写了我的第一个 Common Lisp 函数,但我无法追踪我的错误是在哪里产生的。我该如何解决以下错误:
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)
我的预期 return 是:
(1 2 3 4 5)
我们可以做很多事情来改进此代码。
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 vs 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。表格可以return值
Lisp 形式通常 return 是一个值。如果我们在 repl 中输入 (+ 1 2),我们将看到 3。defun 通常 return 一个通常作为其主体中最后形式的值。
如果我们查看 mergelist,我们会发现它不是显式 returning 任何值,而是试图使用变量 alist 来传达 return 值。这不起作用!
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 return 每次调用时都有一个值显式。
(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*
))
进一步提示,不需要函数中的最后一个循环。
此外,您必须在合并排序中捕获该 return 值,并使合并排序 return 也成为一个显式值。
我还建议您阅读一些有关循环宏的内容 - google for "Practical Common Lisp Loop for Black belts" 这将帮助您掌握语法以及可以使用循环执行的操作。
现在,代码中仍有一些问题需要修复,但我希望我已经给了你足够的时间来完成这次迭代
代码错误太多:
- 将列表视为向量:如果你想要一个随机访问的 Lisp 数据结构,那么使用向量。不是列表。
- 不声明变量
- while 循环根本不起作用
- 命令式的,而不是功能性的
- 错误的代码布局
最好从头开始,避免以上错误。如果您想要 Lisp 列表,请使用不同的方式来编写归并排序。提示:列表不像向量。它们可能会被这样使用,但通常这样做是错误的。