Круговые указатели в лиспе - PullRequest
Новая
       80

Круговые указатели в лиспе

0 голосов
/ 17 мая 2018

Работая с книгой "Введение в алгоритмы CLRS" и пытаясь реализовать красно-черное двоичное дерево поиска в общем lisp, я столкнулся со следующей проблемой с круговыми указателями: 

(defstruct node (ptr nil))

(defparameter *x* (make-node))

(defparameter *y* (make-node :ptr *x*))

(setf (node-ptr *x*) *y*)

Этот код приводит кошибка кучи-исчерпанной, предположительно из-за бесконечной рекурсии, вызванной наличием указателя на указатель, который указывает на этот указатель и т. д.

Есть ли способ предотвратить возникновение этой бесконечной рекурсии при сохраненииуказанная здесь структура указателя?

Я знаю, что есть и другие способы реализации красно-черных деревьев (например, без использования setf), но мне интересно воспроизвести императивный стиль в CLRS, так как обычный lisp являетсяязык парадигмы.

PS.BST в CLRS имеют родительские указатели в дополнение к обычным указателям на левый и правый дочерние элементы.

1 Ответ

0 голосов
/ 17 мая 2018

В Лиспе нет проблем с округлостью.Common Lisp даже имеет специальный синтаксис для выражения его во время чтения: например, что-то вроде #1=(#1# . #1#) является минусом, оба элемента которого являются минусами самим: вы могли бы сконструировать это явно с помощью выражения типа 

(let ((c (cons nil nil)))
  (setf (car c) c
        (cdr c) c))

Однако является проблемой, когда печатает структуру, которая может содержать округлость.Для того, чтобы сделать это правильно, вам нужно что-то под названием происходит, проверьте : поскольку вы печатаете объекты (в частности, объекты, имеющие компоненты), вам нужно отслеживать, видели ли вы этот объект уже, и если выдоговорились ли вы напечатать ссылку, что CL делает, печатая #n#, где n - это целое число, которое сообщает читателю - как человеку-читателю, так и читателю Lisp - какому объекту это соответствует, поэтому они / ономожет реконструировать структуру, включая ее совместное использование.Что еще хуже, вы должны либо аннотировать каждый возможно совместно используемый объект (#n=), когда начнете его печатать, что было бы ужасно, либо избегать печати чего-либо до тех пор, пока вы не наткнетесь на все объекты, чтобы знать, какие из них вам нужнытак что аннотируйте.

Проверка происходящего в вычислительном отношении дорогостоящая в пространстве (или это казалось так в 1980-х годах, когда CL стандартизировался: это все еще может быть для очень больших структур, конечно), поэтому это не поведение по умолчаниюпринтера CL, но он управляется специальной переменной *print-circle*: если это так, то принтер распознает циклическую (и фактически общую структуру);если оно ложно, это не так, и принтер может зацикливаться или бесконечно повторяться при печати круговой структуры.

Обратите внимание, что проблема является более общей, чем циклическая: как должен печататься этот объект: 

(let ((c1 (cons nil nil))
      (c2 (cons nil nil)))
  (setf (car c1) c2
        (cdr c1) c2))

Ну, мы можем построить это явно так: 

(#1=(nil) . #1#)

И вот как это будет напечатано, , если *print-circle* верно, потому что в этом случаеридер обнаруживает общую структуру и печатает ее правильно.Вот демонстрация всего этого: 

(let ((unshared (cons (cons nil nil) (cons nil nil)))
      (shared (cons (cons nil nil) nil))
      (circular (cons nil nil)))
  ;; construct the sharing explicitly rather than via syntax
  (setf (cdr shared) (car shared)
        (car circular) circular
        (cdr circular) circular)
  (with-standard-io-syntax
    (let ((*print-circle* nil))         ;it is anyway
      ;; don't print cicrular!
      (pprint unshared)
      (pprint shared))
    (let ((*print-circle* t))
      (pprint unshared)
      (pprint shared)
      (pprint circular)))
  ;; be careful not to return anything possibly toxic to the printer
  (values))

Это напечатает 

((NIL) NIL)
((NIL) NIL)
((NIL) NIL)
(#1=(NIL) . #1#)
#1=(#1# . #1#)

Обратите внимание, что некоторые очень старые Лиспы (особенно InterLisp) использовали подсчет ссылок для управления хранилищем ив то время как у языка не было проблем с округлостью, счетчик ссылок делал.Однако я уверен, что ни один современный язык не использует подсчет ссылок.

...