Hello,
in the course of learning lisp, I want to implement some kinds of binary
trees, to begin with ordinary binary trees, then red-black-trees and
then avl trees. As there is a certain kind of hierarchy between these
objects and to be general, I wanted to use CLOS and define some classes
for different kinds of trees (respectively their nodes) and for the
items, that are associated with the nodes of the trees.
; ordinary binary tree node
(defclass bin-tree-node ()
((node-item :accessor item :initform nil :initarg :node-item)
(left :accessor left :initform nil :initarg :left)
(right :accessor right :initform nil :initarg :right)))
; additional infos for nodes of red-black trees
(defclass rb-tree-node (bin-tree-node)
((color :accessor color :initform :black :initarg :color)
(parent :accessor parent :initform nil :initarg :parent)))
; the simplest tree-item class, only keys
(defclass tree-item ()
((key :accessor key :initform nil :initarg :key)))
; a tree-item class for key-value pairs
(defclass val-tree-item (tree-item)
((val :accessor val :initform nil :initarg :val)))
; the two comparison methods necessary for the algorithms
(defmethod item-less ((a tree-item) (b tree-item))
(< (key a) (key b)))
(defmethod item-equal ((a tree-item) (b tree-item))
(= (key a) (key b)))
Now I define two methods which insert tree-item "it" into a tree, which
has "bt-node"/"rb-node" as its root
; two tree insertion methods
(defmethod node-insert-item ((it tree-item) (bt-node bin-tree-node))
(format t "test1 :") ; actual code omitted
)
(defmethod node-insert-item ((it tree-item) (rb-node rb-tree-node))
(format t "test0") ; actual code omitted
)
As red-black tree insertion is achieved by ordinary bin-tree insertion
followed by rebalancing the tree, I want to use the first of the two
methods above inside the second. I tried to write
(defmethod node-insert-item ((it tree-item) (rb-node rb-tree-node))
(node-insert-item it (coerce rb-node 'bin-tree-node))
(format t "test0"))
I wanted to see
test1 :test0
in the output, but got a stack overflow and no result.
With call-next-method, it worked, but I did not want to use this
mechanism, because I want explicit control, which method gets invoked.
But the more I think about this approach with classes I fear that I am
doing bad C++ programming in lisp. Is this true - or how can I get onto
the right track with this problem (without giving up using classes) ?
Should I stop using methods for insertion and write explicitly and
simply
(defun bt-node-insert-item (it bt-node)
...
(defun rb-node-insert-item (it rb-node)
(bt-node-insert-item it rb-node)
...
-----------------------------------------------------------------------
Dipl.-Math. Jürgen Böhm http://www.aviduratas.de
"At a time when so many scholars are calculating, is it not desirable,
that some, who can, dream ?" R. Thom
J�rgen B�hm <··········@gmx.net> writes:
> ; two tree insertion methods
>
> (defmethod node-insert-item ((it tree-item) (bt-node bin-tree-node))
> (format t "test1 :") ; actual code omitted
> )
>
> (defmethod node-insert-item ((it tree-item) (rb-node rb-tree-node))
> (format t "test0") ; actual code omitted
> )
>
> As red-black tree insertion is achieved by ordinary bin-tree insertion
> followed by rebalancing the tree, I want to use the first of the two
> methods above inside the second. I tried to write
>
>
> (defmethod node-insert-item ((it tree-item) (rb-node rb-tree-node))
> (node-insert-item it (coerce rb-node 'bin-tree-node))
> (format t "test0"))
>
> I wanted to see
>
> test1 :test0
>
> in the output, but got a stack overflow and no result.
>
> With call-next-method, it worked, but I did not want to use this
> mechanism, because I want explicit control, which method gets invoked.
> But the more I think about this approach with classes I fear that I am
> doing bad C++ programming in lisp. Is this true - or how can I get onto
> the right track with this problem (without giving up using classes) ?
The correct approach in CLOS is to use CALL-NEXT-METHOD. As you
noticed, the coerce approach would only work in C++.
> Should I stop using methods for insertion and write explicitly and
> simply
>
> (defun bt-node-insert-item (it bt-node)
> =2E..
>
> (defun rb-node-insert-item (it rb-node)
> (bt-node-insert-item it rb-node)
>
> =2E..
If you really want to control precisely which FUNCTION is called then
you will have to use DEFUN instead of DEFMETHOD. The whole point of
defining methods is to have the appropriate method called based on the
dynamic type of the arguments.
CALL-NEXT-METHOD allows you to invoke more general methods, but this
will require that your methods be designed with this composability in
mind.
As a matter of fact, for something like this I would consider making the
red-black aspect of the tree (with its attendant rebalancing) be what is
often known as a MIXIN class: In other words something that you add to
some other class to provide this particular functionality.
This provides you with the flexibility to easily create different types
of red-black trees by composing the red-black-node-mixin with the other
more basic types of nodes. Once you decide to do this, you will quickly
see why you would want to use CALL-NEXT-METHOD instead of having
explicit control.
For example:
(defclass basic-tree-node ()
((node-item :accessor item :initform nil :initarg :node-item)
(left :accessor left :initform nil :initarg :left)
(right :accessor right :initform nil :initarg :right)))
; additional infos for nodes of red-black trees
(defclass rb-tree-node (basic-tree-node)
((color :accessor color :initform :black :initarg :color)
(parent :accessor parent :initform nil :initarg :parent)))
; A new class:
(defclass logging-tree-node (basic-tree-node)
((log-file :accessor log :initform nil :initarg :log-file)))
Now consider the following defmethods:
(defmethod node-insert-item ((it tree-item) (rb-node basic-tree-node))
...)
(defmethod node-insert-item ((it tree-item) (rb-node rb-tree-node))
(call-next-method)
(rebalance-tree rb-node)
...)
(defmethod node-insert-item ((it tree-item) (log-node logging-tree-node))
(call-next-method)
(format (log log-node) "Added ~S~%" it))
With three classes we can get more interesting multiple inheritance
results:
(defclass logging-rb-tree-node (rb-tree-node logging-tree-node)
If you then call
(node-insert-item some-item a-loggin-rb-tree-node)
you need to have all three methods called. If CLOS had actually allowed
you to write NODE-INSERT-ITEM on RB-TREE-NODE in such a way that you
could call a specific method (rather than following the method
inheritance chain), you would not be able to compose the Red-Black
functionality of the tree with the Logging functionality.
You would have given up the flexibility to more easily compose the
system out of its consituent parts. It is this sort of compositional
design that you should be striving to achieve. One of the supposed
benefits of Object-Oriented programming is to promote the reuse of
objects. If your objects explicitly require a particular
known-in-advance single-line inheritance path to operate, then you lose
the ability to compose them in more interesting ways. The CLOS idiom
encourages such composability. The C++ idiom precludes it.
=================
By the way, there is a way to call a specific method, but I would hope
that by this point I have convinced you it is a bad idea. It would
involve using CALL-METHOD with FIND-METHOD and possibly
COMPUTE-APPLICABLE-METHODS using a stand-in instance of the specific
class involved.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
On Thu, 21 Jun 2001, [iso-8859-1] Jürgen Böhm wrote:
> ; additional infos for nodes of red-black trees
>
> (defclass rb-tree-node (bin-tree-node)
> ((color :accessor color :initform :black :initarg :color)
> (parent :accessor parent :initform nil :initarg :parent)))
>
> ; two tree insertion methods
>
> (defmethod node-insert-item ((it tree-item) (bt-node bin-tree-node))
> (format t "test1 :") ; actual code omitted
> )
>
> (defmethod node-insert-item ((it tree-item) (rb-node rb-tree-node))
> (format t "test0") ; actual code omitted
> )
>
>
> As red-black tree insertion is achieved by ordinary bin-tree insertion
> followed by rebalancing the tree, I want to use the first of the two
> methods above inside the second. I tried to write
>
>
> (defmethod node-insert-item ((it tree-item) (rb-node rb-tree-node))
> (node-insert-item it (coerce rb-node 'bin-tree-node))
> (format t "test0"))
>
> I wanted to see
>
> test1 :test0
>
> in the output, but got a stack overflow and no result.
Do you understand why? First of all, coerce should signal an error in
this case; it only works for a few types. CLOS classes ain't one of them.
COERCE is probably returning the original object, hence your infinite
recursion.
You want:
(defmethod node-insert-item :after ((it tree-item) (rb-node rb-tree-node))
;; Balance the tree
)
> With call-next-method, it worked, but I did not want to use this
> mechanism, because I want explicit control, which method gets invoked.
In good CLOS style you usually abandon explicit control over specific
methods and try to write things so that the total order in which methods
are invoked doesn't matter much. On the other hand, CLOS method
combination gives you an incredible amount of power in the relative
ordering of methods.
> But the more I think about this approach with classes I fear that I am
> doing bad C++ programming in lisp. Is this true - or how can I get onto
> the right track with this problem (without giving up using classes) ?
>
> Should I stop using methods for insertion and write explicitly and
> simply
>
> (defun bt-node-insert-item (it bt-node)
> (defun rb-node-insert-item (it rb-node)
> (bt-node-insert-item it rb-node)
And admit defeat? Never.
Tim
From: Tim Bradshaw
Subject: Re: Beginner's problems with CLOS
Date:
Message-ID: <nkjzob1k89b.fsf@tfeb.org>
Tim Moore <·····@herschel.bricoworks.com> writes:
> Do you understand why? First of all, coerce should signal an error in
> this case; it only works for a few types. CLOS classes ain't one of them.
> COERCE is probably returning the original object, hence your infinite
> recursion.
No, it shouldn't. If (typep x y) then (coerce x y) will return x.
And since here one object is an instance of a subclass (and hence a
subtype) of the other, this is OK.
> In good CLOS style you usually abandon explicit control over specific
> methods and try to write things so that the total order in which methods
> are invoked doesn't matter much. On the other hand, CLOS method
> combination gives you an incredible amount of power in the relative
> ordering of methods.
I disagree with this I think. The whole before/after/around stuff in
standard method combination is about expressing these kinds of
orderings. I think what you may mean is that you should not be
stressing about what something like CALL-NEXT-METHOD does - if the
design is right then whatever it invokes is right. Or something.
--tim
On 21 Jun 2001, Tim Bradshaw wrote:
> Tim Moore <·····@herschel.bricoworks.com> writes:
>
> > Do you understand why? First of all, coerce should signal an error in
> > this case; it only works for a few types. CLOS classes ain't one of them.
> > COERCE is probably returning the original object, hence your infinite
> > recursion.
>
> No, it shouldn't. If (typep x y) then (coerce x y) will return x.
> And since here one object is an instance of a subclass (and hence a
> subtype) of the other, this is OK.
Whoops! Of course you're right.
> > In good CLOS style you usually abandon explicit control over specific
> > methods and try to write things so that the total order in which methods
> > are invoked doesn't matter much. On the other hand, CLOS method
> > combination gives you an incredible amount of power in the relative
> > ordering of methods.
>
> I disagree with this I think. The whole before/after/around stuff in
> standard method combination is about expressing these kinds of
> orderings. I think what you may mean is that you should not be
> stressing about what something like CALL-NEXT-METHOD does - if the
> design is right then whatever it invokes is right. Or something.
What I meant was that standard method combination is good for placing
methods into those "times", and controlling order with respect to methods
on superclasses, but not good for controlling the strict ordering of
methods because that is so dependent on a given classes' class precedence
list. So, "Yeah, what you said."
Tim
From: Tim Bradshaw
Subject: Re: Beginner's problems with CLOS
Date:
Message-ID: <nkj3d8tlocs.fsf@tfeb.org>
J�rgen B�hm <··········@gmx.net> writes:
>
> As red-black tree insertion is achieved by ordinary bin-tree insertion
> followed by rebalancing the tree, I want to use the first of the two
> methods above inside the second. I tried to write
>
> (defmethod node-insert-item ((it tree-item) (rb-node rb-tree-node))
> (node-insert-item it (coerce rb-node 'bin-tree-node))
> (format t "test0"))
>
This won't work for a lot of reasons, mostly that COERCE does not do
what you expect. In general you can't tell Lisp to treat an object of
this type as if it was some other type than it is: Lisp has strong
typing unlike C/C++. In this case, an RB-NODE is already a
BIN-TREE-NODE, so COERCE will just return the RB-NODE object. If it
wasn't then you'd have got an error except in the few special cases
that COERCE knows about to do with numeric types. However even in
these cases COERCE does not make the same object look as if it has
another type, it returns a new object which does have that other type.
Surely the way to do this is an after method? Your specification of
the problem translates to this almost directly.
>
> With call-next-method, it worked, but I did not want to use this
> mechanism, because I want explicit control, which method gets invoked.
> But the more I think about this approach with classes I fear that I am
> doing bad C++ programming in lisp. Is this true - or how can I get onto
> the right track with this problem (without giving up using classes) ?
>
I think that `wanting explicit control over which method gets invoked'
is a bad sign. Why do you want that control?
--tim
In article <···············@tfeb.org>, Tim Bradshaw <···@tfeb.org> wrote:
>I think that `wanting explicit control over which method gets invoked'
>is a bad sign. Why do you want that control?
And if you really *do* need that control, the solution is to use a unique
generic function name for the method that you need to invoke explicitly:
(defmethod bin-tree-node-insert-item ((it tree-item) (node bin-tree-node))
...)
(defmethod node-insert-item ((it tree-item) (node bin-tree-node))
(bin-tree-node-insert-item it node))
(defmethod node-insert-item ((it tree-item) (node rb-tree-node))
(bin-tree-node-insert-item it node)
(rebalance-tree node))
Replace the third "-" in bin-tree-node-insert-item with "::" and it looks
alot like the C++ you're probably used to, doesn't it?
But as Tim indicated, this is probably the wrong way to do it, so try *not*
to get in the habit of doing this. C++ requires you to do stuff like this
because it doesn't have a built-in method combination mechanism. CLOS's
method combination facility usually provides you with the right building
blocks.
In particular, what if you insert another class between BIN-TREE-NODE and
RB-TREE-NODE? Presumably, its NODE-INSERT-ITEM should be used rather than
BIN-TREE-NODE's. With an :AFTER method or CALL-NEXT-METHOD, the right
thing will happen, but with the explicit calls you'll need to fix them all
up. Method combinations also support the "mixin" style of OO programming,
where you define small classes that can add behavior to a wide variety of
related classes; since they don't know what other classes they'll be
combined with, they can't call a specific class's methods directly.
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Tim Bradshaw
Subject: Re: Beginner's problems with CLOS
Date:
Message-ID: <nkjy9qlk82r.fsf@tfeb.org>
Barry Margolin <······@genuity.net> writes:
>
> In particular, what if you insert another class between BIN-TREE-NODE and
> RB-TREE-NODE? Presumably, its NODE-INSERT-ITEM should be used rather than
> BIN-TREE-NODE's. With an :AFTER method or CALL-NEXT-METHOD, the right
> thing will happen, but with the explicit calls you'll need to fix them all
> up. Method combinations also support the "mixin" style of OO programming,
> where you define small classes that can add behavior to a wide variety of
> related classes; since they don't know what other classes they'll be
> combined with, they can't call a specific class's methods directly.
Yes, this is axactly what I'm trying to get at. You don't want to go
assuming things about how your superclasses implement behaviours, you
just want to assume that they do implement it. If you start writing
code that knows how they implement it then you've removed their
freedom to change the implementation, and removed a modularity barrier
in the code.
--tim