Structs pointing to each other, stack overflow

[Pixel_Outlaw]

I'm trying to build a simply binary tree (made of node structs which each have two "child" slots and one "parent" slot)

(defstruct node child-a child-b parent)

I can for example create two new nodes like so:
(defparameter a (make-node))
(defparameter b (make-node))

Now I want to create their parent like so:
(defparameter c (make-node :child-a a :child-b b))

Fine, good so far.
Now I need to let the children nodes (a and b) link back to their parent c. (so the binary tree can be traversed in 2 directions)
HOWEVER I get an immediate error when trying to set the parent value for a and b:
(setf (node-parent a) c)

*** - Program stack overflow. RESET

Does CL not allow structs pointing to each other?

[edgar-rft]

DEFSTRUCT is too simple-minded to handle inheritance properly, you would need to write some extra functions to keep track of all possible inheritance issues. In Paul Graham's ANSI Common Lisp are some examples how this would work.

(setf (node-parent a) c) creates an infinite loop because a already contains a reference to c, where a, b, c are instances of one and the the same STRUCTURE-CLASS, so CLOS can't resolve the precedence properly.

DEFCLASS and MAKE-INSTANCE give much better options to define and control inheritance dependencies.

Nick Levine's Fundamentals of CLOS tutorial describes on one single page pretty well how to implement single and multiple inheritance with CLOS.

If you want to read books:

• Sonya E. Keene Object-oriented programming in Common LISP - easy to understand
• Gregor Kiczales The Art of the Metaobject Protocol - hardcore OOP (don't read this first)

- edgar

[edgar-rft]

Some time later...

Here is a readable version of the code from ANSI Common Lisp, using DEFSTRUCT to create doubly-linked binary trees:

Code: Select all

(defstruct node
  (value nil)
  (prev  nil)
  (next  nil))

Adding a new node to the tree:

Code: Select all

(defun tree-insert (object tree sort-function)
  "Insert a node containing OBJECT in a binary TREE."
  (if (null tree)
      (make-node :value object)
      (let ((value (node-value tree)))
        (if (equal object value)
            tree
            (if (funcall sort-function object value)
                (make-node
                  :value value
                  :prev (tree-insert object (node-prev tree) sort-function)
                  :next (node-next tree))
                (make-node
                  :value value
                  :next (tree-insert object (node-next tree) sort-function)
                  :prev (node-prev tree)))))))

The trick is to define the precedence by a sort-function. If the tree contains only numbers, the sort-function would be #'< or #'>, like here:

Code: Select all

(defvar *tree* nil
  "Empty tree.")

(dolist (x '(5 8 4 2 1 9 6 7 3))
  (setf *tree* (tree-insert x *tree* #'<)))

Finding nodes in the tree:

Code: Select all

(defun tree-find (object tree sort-function)
  "Find a node containing OBJECT in a binary TREE."
  (if (null tree)
      nil
      (let ((value (node-value tree)))
        (if (equal object value)
            tree
            (if (funcall sort-function object value)
                (tree-find object (node-prev tree) sort-function)
                (tree-find object (node-next tree) sort-function))))))

Here is how it works:

Code: Select all

CL-USER> (tree-find 12 *tree* #'<)
NIL

CL-USER> (tree-find 4 *tree* #'<)
#S(NODE :VALUE 4 :PREV NIL :NEXT NIL)

The original code, including functions to remove elements and other stuff, can be found here:

• http://ep.yimg.com/ty/cdn/paulgraham/acl2.lisp

Look for function names starting with "bst-..." (binary search tree).

But I still think that using DEFCLASS and MAKE-INSTANCE is the better idea.

- edgar

[Pixel_Outlaw]

Thanks so much for the information.
I was trying to play C with CL and I think I didn't realize the simple nature of the structs.

[budden73]

You do all ok, stack overflow is just as lisp tries to print your circular graph
of structures.
Set *print-circle* to t and all would work.
Answer by edgar-rft is wrong.

[marcoxa]

You do all ok, stack overflow is just as lisp tries to print your circular graph
of structures.
Set *print-circle* to t and all would work.
Answer by edgar-rft is wrong.

Yep. budden73 is perfectly right. The problem is the "printing". Nothing to do with the structures setup. Doing

Code: Select all

cl-prompt> (progn (setf (node-parent c) a) t)


would just print T. Of course, setting *print-circle* to NIL will also solve the problem.

Finally, let's not forget the print-object/print-function facilities in DEFSTRUCT.

Cheers
--
MA