Функция make-city-edges игры Wumpus вызывает переполнение кучи

Просматривая книгу 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)))

[здесь] — остальная часть кода, если вы хотите взглянуть на другие функции, Я добавил его на страницу GitHub Gist, так как он занял бы слишком много места в вопросе.

Что я могу сделать, чтобы решить эту проблему? Я использую Emacs 24.4 (9.0) на OSX 10.9 с SLIME и SBCL 1.2.10 для проекта.


overflow heap-memory common-lisp sbcl land-of-lisp
person Electric Coffee    schedule 12.04.2015    source источник
comment
Это может быть невозможно диагностировать без воспроизводимого тестового примера, платформы, версии sbcl и т. д.   -  person Rainer Joswig    schedule 12.04.2015
comment
@RainerJoswig, что ты предлагаешь мне сделать?   -  person Electric Coffee    schedule 12.04.2015
comment
Ну, в настоящее время этот вопрос предполагает, что у нас есть вся книга «страна шепелявости», это отличная книга, но без полного кода вы ограничиваете людей, которые могли бы ответить на этот вопрос. В настоящее время только люди, владеющие книгой и желающие повторить упражнение, могут помочь... Может быть, выложите полный код здесь или в кратком описании по ссылке здесь. Он должен быть завершен, чтобы любой здесь мог просто скомпилировать и протестировать его для вас.   -  person Baggers    schedule 13.04.2015
comment
@Baggers добавил оставшийся код в ссылку   -  person Electric Coffee    schedule 13.04.2015
comment
@ElectricCoffee: это хорошо. Я посмотрю, но это займет некоторое время.   -  person Rainer Joswig    schedule 13.04.2015
comment
Вы можете попробовать вставить breaks, чтобы определить, какой путь кода является проблемой.   -  person Svante    schedule 13.04.2015
comment
@ElectricCoffee Если посмотреть на это с глазу на глаз, я не верю, что рекурсия find-island когда-либо завершится. get-connected никогда не возвращает nil.   -  person m-n    schedule 13.04.2015
comment
@m-n это идентично тому, как это было написано в моей копии книги, что вы предлагаете в качестве исправления? Кроме того, почему вы думаете, что он должен возвращать ноль? Редактировать: Неважно, я нашел ошибку. Это в find-island   -  person Electric Coffee    schedule 13.04.2015
comment
@ElectricCoffee Прекращение рекурсии find-island было основано на возвращении nil :) Это должно было быть (when unconnected, и у вас все получилось?   -  person m-n    schedule 13.04.2015
comment
@m-n да, теперь он работает отлично, и молниеносно. Спасибо! Итак, если вы можете оставить предложение в качестве ответа, я могу его одобрить: D   -  person Electric Coffee    schedule 13.04.2015

Ответы (1)


arrow_upward
2
arrow_downward

В связанном коде

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

Несколько советов по отладке исчерпания кучи:

  1. Убедитесь, что ваши циклы и рекурсии действительно завершаются. (Вот что привело нас к такому решению — get-connected никогда не возвращает nil, поэтому find-island будет рекурсивно выполняться вечно.)
  2. CL trace может быть полезен, как и традиционное добавление операторов печати.
  3. 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) ...)

Это может привести к тому, что мы скажем: «Я не думал, что node когда-нибудь станет nil, а islands, будучи ((nil) (nil) (nil) ...), кажется сломанным».

person m-n    schedule 13.04.2015