Structs pointing to each other, stack overflow

Discussion of Common Lisp

Structs pointing to each other, stack overflow

Postby 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?
Pixel_Outlaw
 
Posts: 41
Joined: Mon Aug 26, 2013 9:24 pm

Re: Structs pointing to each other, stack overflow

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

Re: Structs pointing to each other, stack overflow

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

Re: Structs pointing to each other, stack overflow

Postby 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.
Pixel_Outlaw
 
Posts: 41
Joined: Mon Aug 26, 2013 9:24 pm

Re: Structs pointing to each other, stack overflow

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

Re: Structs pointing to each other, stack overflow

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


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 2 guests

cron