Необычное переполнение стека при вставке узлов в бинарном дереве

Question

CLISP Версия: 2,49

Leaf Node

(value (NIL) (NIL)) 

Non-Leaf Node

(value (value (NIL) (NIL)) (NIL)) 

Code ("формат" для отладки только)

; (nil) means NULL 
(defun binary-insert (root obj <) 
(if (null (cdr root)) 
    (progn 
     (format t "In Null [~A] => " root) 
     (setf (car root) obj) 
     (format t "mid [~A] => " root) 
     (setf (cdr root) '((nil) (nil))) 
     (format t "[~A]~%" root)) 
    (if (funcall < obj (car root)) 
     (progn 
      (format t "In Left [~A] => " root) 
      (binary-insert (nth 1 root) obj <) 
      (format t "[~A]~%" root)) ; Left 
     (progn 
      (format t "In Right [~A] => " root) 
      (binary-insert (nth 2 root) obj <) 
      (format t "[~A]~%" root)) ; Right 
     ) 
    ) 
) 

Тест

[1]> (load "binary_tree.lisp") 
;; Loading file binary_tree.lisp ... 
;; Loaded file binary_tree.lisp 
T 
[2]> (setf *glb-rt* '(NIL)) 
(NIL) 
[3]> (binary-insert *glb-rt* 10 #'<) 
In Null [(NIL)] => mid [(10)] => [(10 (NIL) (NIL))] 
NIL 
[4]> *glb-rt* 
(10 (NIL) (NIL)) 
[5]> (binary-insert *glb-rt* 5 #'<) 
In Left [(10 (NIL) (NIL))] => In Null [(NIL)] => mid [(5)] => [ 
*** - Lisp stack overflow. RESET 

Кажется, программа умерла после выполнения

(setf (cdr root) '((NIL) (NIL))) 

Спасибо ....

[Update]

До (SETF (корд корень) «((NIL) (NIL))), «корень» равен (5)

Другое испытание

[6]> (setf glb-ls '(5)) 
(5) 
[7]> (setf (cdr glb-ls) '((NIL) (NIL))) 
((NIL) (NIL)) 
[8]> glb-ls 
(5 (NIL) (NIL)) 

Answer 1

Этот вопрос был дан ответ в CLISP FAQ How do I avoid stack overflow?

В вашем случае очень первое предложение работы: после того, как

(setq *print-circle* t) 

мы получаем

In Left [(10 (NIL) (NIL))] => In Null [(NIL)] => mid [(5)] => [#1=(5 #1# (NIL))] 

т.е. вы по ошибке создавая круговую структуру.

PS. Вы теперь должны мне 10 zorkmids :-)