Structs pointing to each other, stack overflow
-
- Posts: 43
- Joined: Mon Aug 26, 2013 9:24 pm
Structs pointing to each other, stack overflow
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?
(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?
Re: Structs pointing to each other, stack overflow
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:
(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)
Re: Structs pointing to each other, stack overflow
Some time later...
Here is a readable version of the code from ANSI Common Lisp, using DEFSTRUCT to create doubly-linked binary trees:
Adding a new node to the 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:
Finding nodes in the tree:
Here is how it works:
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
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))
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)))))))
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* #'<)))
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))))))
Code: Select all
CL-USER> (tree-find 12 *tree* #'<)
NIL
CL-USER> (tree-find 4 *tree* #'<)
#S(NODE :VALUE 4 :PREV NIL :NEXT NIL)
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
-
- Posts: 43
- Joined: Mon Aug 26, 2013 9:24 pm
Re: Structs pointing to each other, stack overflow
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.
I was trying to play C with CL and I think I didn't realize the simple nature of the structs.
Re: Structs pointing to each other, stack overflow
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.
of structures.
Set *print-circle* to t and all would work.
Answer by edgar-rft is wrong.
Re: Structs pointing to each other, stack overflow
Yep. budden73 is perfectly right. The problem is the "printing". Nothing to do with the structures setup. Doingbudden73 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.
Code: Select all
cl-prompt> (progn (setf (node-parent c) a) t)
Finally, let's not forget the print-object/print-function facilities in DEFSTRUCT.
Cheers
--
MA
Marco Antoniotti