Wumpus游戏的make-city-edges函数导致堆溢出

Question

通过 Land of Lisp 这本书，我设法找到了 Grand Theft Wumpus 游戏，它让我定义了一个 make-city-edges 函数。然而，当我尝试运行它时，SBCL 挂了一会儿，然后给我一个非常讨厌的错误，说

    Heap exhausted during garbage collection: 0 bytes available, 16 requested.
 Gen StaPg UbSta LaSta LUbSt Boxed Unboxed LB   LUB  !move  Alloc  Waste   Trig    WP  GCs Mem-age
   0:     0     0     0     0     0     0     0     0     0        0     0 10737418    0   0  0.0000
   1:     0     0     0     0     0     0     0     0     0        0     0 10737418    0   0  0.0000
   2: 27757     0     0     0 19204    70     0    10    54 631392704 505408  2000000    0   0  0.9800
   3:     0     0     0     0     0     0     0     0     0        0     0  2000000    0   0  0.0000
   4:     0     0     0     0     0     0     0     0     0        0     0  2000000    0   0  0.0000
   5:     0     0     0     0     0     0     0     0     0        0     0  2000000    0   0  0.0000
   6:     0     0     0     0  1638   251     0     0     0 61898752     0  2000000 1523   0  0.0000
   Total bytes allocated    = 1073069936
   Dynamic-space-size bytes = 1073741824
GC control variables:
   *GC-INHIBIT* = true
   *GC-PENDING* = true
   *STOP-FOR-GC-PENDING* = false
fatal error encountered in SBCL pid 85448(tid 140735276667664):
Heap exhausted, game over.

Error opening /dev/tty: Device not configured
Welcome to LDB, a low-level debugger for the Lisp runtime environment.
ldb>

我已经检查了三次，看是否有错误，但我找不到任何错误。

这是导致问题的函数：

(defun make-city-edges ()
  (let* ((nodes (loop for i from 1 to *node-num*
                      collect i))
         (edge-list (connect-all-islands nodes (make-edge-list)))
         (cops (remove-if-not (lambda (x)
                                (zerop (random *cop-odds*)))
                              edge-list)))
    (add-cops (edges-to-alist edge-list) cops)))

[here] 是代码的其余部分，如果您想查看其他函数，我将其添加到 GitHub Gist 页面，因为它会占用太多空间 space 在问题中。

我该怎么做才能解决这个问题？我在 OSX 10.9 上使用 Emacs 24.4 (9.0)，在项目中使用 SLIME 和 SBCL 1.2.10。

Answer 1

在链接代码中，

(defun find-islands (nodes edge-list)
  "returns a list of nodes that aren't interconnected"
  (let ((islands nil))
    (labels ((find-island (nodes)
           (let* ((connected (get-connected (car nodes) edge-list))
              (unconnected (set-difference nodes connected)))
         (push connected islands)
         (when connected
           (find-island unconnected)))))
      (find-island nodes))
    islands))

(when connected 应该是 (when unconnected.

调试堆耗尽的一些技巧：

检查您的循环和递归是否确实终止。（这就是导致我们得出这个解决方案的原因——get-connected 永远不会 returns nil，所以 find-island 将永远递归。）
CL 的 trace 和传统的打印语句添加一样有用。
C-c C-c 在 SLIME 中程序有运行一段时间后但在堆耗尽之前可能会提供有用的回溯。

例如回溯：

  0: ((:INTERNAL TRAVERSE GET-CONNECTED) NIL)
      Locals:
        NODE = NIL
        #:G11908 = ((2 . 21) (20 . 22) (22 . 20) (9 . 28) (28 . 9) (2 . 7) ...)
        EDGE-LIST = ((8 . 3) (3 . 8) (18 . 7) (7 . 18) (26 . 23) (23 . 26) ...)
        VISITED = (NIL)
  1: (GET-CONNECTED NIL ((8 . 3) (3 . 8) (18 . 7) (7 . 18) (26 . 23) (23 . 26) ...))
      Locals:
        NODE = NIL
        EDGE-LIST = ((8 . 3) (3 . 8) (18 . 7) (7 . 18) (26 . 23) (23 . 26) ...)
        VISITED = (NIL)
  2: ((:INTERNAL FIND-ISLAND FIND-ISLANDS) NIL)
      Locals:
        NODES = NIL
        ISLANDS = ((NIL) (NIL) (NIL) (NIL) (NIL) (NIL) ...)
        EDGE-LIST = ((8 . 3) (3 . 8) (18 . 7) (7 . 18) (26 . 23) (23 . 26) ...)
  3: (FIND-ISLANDS (1 2 3 4 5 6 ...) ((8 . 3) (3 . 8) (18 . 7) (7 . 18) (26 . 23) (23 . 26) ...))
      Locals:
        NODES = (1 2 3 4 5 6 ...)
        EDGE-LIST = ((8 . 3) (3 . 8) (18 . 7) (7 . 18) (26 . 23) (23 . 26) ...)
        ISLANDS = ((NIL) (NIL) (NIL) (NIL) (NIL) (NIL) ...)

这可能会让我们说 "I didn't think a node would ever be nil, and islands being ((nil) (nil) (nil) ...) seems broken."

Wumpus游戏的make-city-edges函数导致堆溢出

Wumpus game's make-city-edges function causes heap overflow

sbcl

heap-memory

common-lisp

overflow

land-of-lisp