Structs pointing to each other, stack overflow

Discussion of Common Lisp
Post Reply
Pixel_Outlaw
Posts: 43
Joined: Mon Aug 26, 2013 9:24 pm

Structs pointing to each other, stack overflow

Post by Pixel_Outlaw » Sat Oct 26, 2013 11:45 pm

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
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Structs pointing to each other, stack overflow

Post by edgar-rft » Sun Oct 27, 2013 6:10 am

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:
- edgar

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Structs pointing to each other, stack overflow

Post by edgar-rft » Sun Oct 27, 2013 8:42 am

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:
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
Posts: 43
Joined: Mon Aug 26, 2013 9:24 pm

Re: Structs pointing to each other, stack overflow

Post by Pixel_Outlaw » Sun Oct 27, 2013 1:13 pm

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
Posts: 8
Joined: Sat Jan 04, 2014 8:25 am

Re: Structs pointing to each other, stack overflow

Post by budden73 » Sat Jan 04, 2014 8:38 am

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
Posts: 85
Joined: Thu Aug 14, 2008 6:31 pm

Re: Structs pointing to each other, stack overflow

Post by marcoxa » Sun Jan 05, 2014 7:46 am

budden73 wrote: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
Marco Antoniotti

Post Reply