Hello there,
I'm a little confused and seek some enlightment (i.e. explanations and
references). I have two classes, ternary-node and
ternary-data-node. The latter is obviously derived from the former and
just adds a value slot.
I now have a method, node-insert, that inserts sequences into
ternary-nodes (this implements the Bentley/Sedgewick
ternary-search-trees, basically). This is defined recursively,
modifying and returning nodes. To avoid code-duplication, I
intended to use an :around method for the data-nodes, that insert some
value whenever the end of a sequence is reached:
(defmethod node-insert :around ((sequence sequence) (node ternary-data-node)
&key (eql #'eql) (comp #'<)
(iter #'(lambda (seq) (subseq seq 1)))
(end #'(lambda (seq) (<= (length seq) 1)))
(value nil))
(format t "Around method called with ~A,~S~%" sequence node)
(let ((result (call-next-method)))
(when (funcall end sequence)
(format t "~A is empty, setting ~S~%" sequence result)
(setf (node-value result) value))
(format t "Value at ~S now: ~S~%" result (node-value result))
result))
The idea is to make use of the return value of the primary
method. When the end test succeeds, I have reached the node (which
will be returned by c-n-m) at which I want to set the value slot.
Well, it does not work (in CMUCL, ACL, Lispworks, non compiled
code). Here's what happens:
USER(19): (tree-insert "bar" *t* :value 'bar)
Around method called with bar,#<TERNARY-DATA-NODE @ #x204fe262>
Around method called with ar,#<TERNARY-DATA-NODE @ #x2050175a>
Around method called with r,#<TERNARY-DATA-NODE @ #x20501c12>
r is empty, setting #<TERNARY-DATA-NODE @ #x20501c12>
Value at #<TERNARY-DATA-NODE @ #x20501c12> now: NIL
Value at #<TERNARY-DATA-NODE @ #x2050175a> now: NIL
Value at #<TERNARY-DATA-NODE @ #x204fe262> now: BAR
#<TERNARY-DATA-NODE @ #x204fe262>
And the result looks like this:
USER(25): (pprint-tree *t*)
<b:BAR<NIL,<a:NIL<NIL,<r:NIL<NIL,NIL,NIL>>NIL>>NIL>>
NIL
Somehow, when I try to access the result of call-next-method, the
recursion seems to unrole, so that I end up modifying the end-result,
instead of some embedded node. The trace seems to validate this:
Around method called with r,#<TERNARY-DATA-NODE @ #x20501c12>
r is empty, setting #<TERNARY-DATA-NODE @ #x20501c12>
Value at #<TERNARY-DATA-NODE @ #x20501c12> now: NIL
2: returned #<TERNARY-DATA-NODE @ #x20501c12>
Value at #<TERNARY-DATA-NODE @ #x2050175a> now: NIL
1: returned #<TERNARY-DATA-NODE @ #x2050175a>
Value at #<TERNARY-DATA-NODE @ #x204fe262> now: BAR
0: returned #<TERNARY-DATA-NODE @ #x204fe262>
#<TERNARY-DATA-NODE @ #x204fe262>
What am I missing? Which piece in the CLHS?
Holger
--
--- http://www.coling.uni-freiburg.de/~schauer/ ---
"Im Unterschied zu Linux schiesst die Bank ihre Kunden nicht ab,
sondern teilt ihnen mit, dass sie kein Geld bekommen. ;-)"
-- Christian Knapmeyer in de.comp.os.unix.discussion
"Holger Schauer" <··············@gmx.de> wrote in message
···················@watchtower.coling.uni-freiburg.de...
> Hello there,
>
> I'm a little confused and seek some enlightment (i.e. explanations and
> references). I have two classes, ternary-node and
> ternary-data-node. The latter is obviously derived from the former and
> just adds a value slot.
>
> I now have a method, node-insert, that inserts sequences into
> ternary-nodes (this implements the Bentley/Sedgewick
> ternary-search-trees, basically). This is defined recursively,
> modifying and returning nodes. To avoid code-duplication, I
> intended to use an :around method for the data-nodes, that insert some
> value whenever the end of a sequence is reached:
>
> (defmethod node-insert :around ((sequence sequence) (node
ternary-data-node)
> &key (eql #'eql) (comp #'<)
> (iter #'(lambda (seq) (subseq seq 1)))
> (end #'(lambda (seq) (<= (length seq) 1)))
> (value nil))
> (format t "Around method called with ~A,~S~%" sequence node)
> (let ((result (call-next-method)))
> (when (funcall end sequence)
> (format t "~A is empty, setting ~S~%" sequence result)
> (setf (node-value result) value))
> (format t "Value at ~S now: ~S~%" result (node-value result))
> result))
>
> The idea is to make use of the return value of the primary
> method. When the end test succeeds, I have reached the node (which
> will be returned by c-n-m) at which I want to set the value slot.
>
[snip]
> Somehow, when I try to access the result of call-next-method, the
> recursion seems to unrole, so that I end up modifying the end-result,
> instead of some embedded node. The trace seems to validate this:
>
[I have not look really hard at what you are doing,but...]
Perhaps your confusion is with call-next-method. call-next-method in an
around method will call the next-most specific around method (if it exists)
and if it doesn't will call the most-specific before method (if it exists)
and if that doesn't exist will call the most specific primary method. But
it will not recall the same around method. So looking at your node-insert,
I don't see any recursion happening.
Perhaps you want something closer to:
(defmethod node-insert
:around ((sequence sequence) (node ternary-data-node)
&key (eql #'eql) (comp #'<)
(iter #'(lambda (seq) (subseq seq 1)))
(end #'(lambda (seq) (<= (length seq) 1)))
(value nil))
(declare (ignore eql comp))
(format t "Around method called with ~A,~S~%" sequence node)
(if (funcall end sequence)
(setf (node-value (call-next-method)) value)
(node-insert (funcall iter sequence) node)))
though I don't see where you are traversing the nodes. Of course I don't
know what is in your primary method either.
In general though, this might be less obfuscated if you just mapped over
your sequence argument...but absent the other methods I shouldn't say
anything really.
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
On Sun, 10 Feb 2002, Coby Beck wrote:
> "Holger Schauer" <··············@gmx.de> wrote in message
>> I now have a method, node-insert, that inserts sequences into
>> ternary-nodes (this implements the Bentley/Sedgewick
>> ternary-search-trees, basically). This is defined recursively,
>> modifying and returning nodes.
Just for the record: the primary method is recursive, not the around
method I gave below:
>>(defmethod node-insert :around ((sequence sequence) (node ternary-data-node)
>> &key (eql #'eql) (comp #'<)
>> (iter #'(lambda (seq) (subseq seq 1)))
>> (end #'(lambda (seq) (<= (length seq) 1)))
>> (value nil))
>> (format t "Around method called with ~A,~S~%" sequence node)
>> (let ((result (call-next-method)))
>> (when (funcall end sequence)
>> (format t "~A is empty, setting ~S~%" sequence result)
>> (setf (node-value result) value))
>> (format t "Value at ~S now: ~S~%" result (node-value result))
>> result))
>> Somehow, when I try to access the result of call-next-method, the
>> recursion seems to unrole, so that I end up modifying the
>> end-result, instead of some embedded node. The trace seems to
>> validate this:
> [I have not look really hard at what you are doing,but...]
Yes, that shows :-)
> Perhaps your confusion is with call-next-method. call-next-method
> in an around method will call the next-most specific around method
> (if it exists) and if it doesn't will call the most-specific before
> method (if it exists) and if that doesn't exist will call the most
> specific primary method. But it will not recall the same around
> method. So looking at your node-insert, I don't see any recursion
> happening.
The recursion happens in the primary method:
(defmethod node-insert ((sequence sequence) (node ternary-node)
[... stuff elided for sake of brevity ...]
((funcall eql obj nodedata)
(unless (funcall end sequence)
(setf (eql-node node)
(node-insert (funcall iter sequence)
(or (eql-node node)
(make-instance (type-of node)))
:eql eql :comp comp
:iter iter :end end))))
[... stuff elided for sake of brevity ...]
Actually, the recursive calls work fine, i.e. as I intended
(reinserted from my original posting):
>>USER(19): (tree-insert "bar" *t* :value 'bar)
>>Around method called with bar,#<TERNARY-DATA-NODE @ #x204fe262>
>>Around method called with ar,#<TERNARY-DATA-NODE @ #x2050175a>
>>Around method called with r,#<TERNARY-DATA-NODE @ #x20501c12>
>>r is empty, setting #<TERNARY-DATA-NODE @ #x20501c12>
These actually are the recursive calls to the around method, just as I
wanted. The problem shows up _only_ when I try to /modify/ the
results (see the trace in my orig.post).
Now, what I find really interesting, is, that at least Allegro seems
to show a machine- or os-dependent behaviour. I.e., on Linux, I get
the results shown in prior posting (i.e. the setf modifies the result
of all recursive applications, not just the most local result). But on
Solaris (ACL4.3 and ACL5.0.1), I get:
Primary method called on ins,#<TERNARY-DATA-NODE @ #x458183a>.
Around method called with ns,#<TERNARY-DATA-NODE @ #x4581c22>
Primary method called on ns,#<TERNARY-DATA-NODE @ #x4581c22>.
Around method called with s,#<TERNARY-DATA-NODE @ #x458200a>
Primary method called on s,#<TERNARY-DATA-NODE @ #x458200a>.
Leaving primary method for s,#<TERNARY-DATA-NODE @ #x458200a>.
Error: No methods applicable for generic function
#<STANDARD-GENERIC-FUNCTION (SETF TREES::NODE-VALUE)> with args
(NIL NIL) of classes (NULL NULL)
[condition type: PROGRAM-ERROR]
Restart actions (select using :continue):
0: Try calling it again
1: Return to Top Level (an "abort" restart)
2: Abort #<PROCESS Initial Lisp Listener>
[1c] USER(27): [1c] USER(27):
This is just like the trace I've shown for the Linux version with the
single exception that the setf seems to be applied to something which
is not there (and also with a value that is not there!)
[1c] USER(23): :loc
Interpreted lexical environment:
TREES::RESULT: NIL <--------- Looky here!
TREES::VALUE: NIL
TREES::COMP: #<Function CHAR<>
EQL: #<Function EQL>
TREES::NODE: #<TERNARY-DATA-NODE @ #x454a932>
TREES::OBJ: "s"
CLOS::.NEXT-METHOD.:
#<Interpreted Function (METHOD TREES::NODE-INSERT
(SEQUENCE TREES::TERNARY-NODE))>
CLOS::.NEXT-METHODS.:
(#<Interpreted Function (METHOD TREES::NODE-INSERT
(T TREES::TERNARY-NODE))>
#<Interpreted Function (METHOD TREES::NODE-INSERT (T TREES::NODE))>)
#:AMPERSAND-ARGS:
(:EQL #<Function EQL> :COMP #<Function CHAR<> :ITER
#<Interpreted Function (:INTERNAL
(CLOS:SLOT-DEFINITION-INITFUNCTION
TERNARY-SEARCH-TREE TREES::ITERATOR))
@ #x4542d6a>
:END
#<Interpreted Function (:INTERNAL
(CLOS:SLOT-DEFINITION-INITFUNCTION
TERNARY-SEARCH-TREE TREES::END))
@ #x4542dba>)
#:NODE: #<TERNARY-DATA-NODE @ #x454a932>
#:OBJ: "s"
BTW: the problem seems not to be related to :around only. The same
problem occurs when I define my :around method as an :after method
like this:
(defmethod node-insert :after ((sequence sequence) (node ternary-data-node)
&key (eql #'eql) (comp #'<)
(iter #'(lambda (seq) (subseq seq 1)))
(end #'(lambda (seq) (<= (length seq) 1)))
(value nil))
(format t ":after method called on ~A,~S.~%" sequence node)
(when (funcall end sequence)
(format t "In :after, ~A is empty, setting ~S~%" sequence node)
(setf (node-value node) value))
(format t "Leaving :after method for ~A,~S."))
I guess I am missing something about how and when return values of
next-methods are available and whether I am (dis-)allowed to modify
them in :around (etc.) methods.
> In general though, this might be less obfuscated if you just mapped
> over your sequence argument...but absent the other methods I
> shouldn't say anything really.
Actually, I will going to do something along the lines of what you're
suggesting. I intended to start out with the recursive version, as it
is fairly close to the C version given by Bentley/Sedgewick, and then
see how much optimization you get by using an iterative version.
Nethertheless, I would like to know what and why I am doing wrong.
Holger
--
--- http://www.coling.uni-freiburg.de/~schauer/ ---
Fachbegriffe der Informatik - Einfach erkl�rt
48: Nutzt die neuen M�glichkeiten von Windows'95!
Haben Sie unser anderes Update schon gekauft? (Kristian K�hntopp)
"Holger Schauer" <··············@gmx.de> wrote in message
···················@watchtower.coling.uni-freiburg.de...
> (defmethod node-insert :around ((sequence sequence) (node ternary-data-node)
> &key (eql #'eql) (comp #'<)
> (iter #'(lambda (seq) (subseq seq 1)))
> (end #'(lambda (seq) (<= (length seq) 1)))
> (value nil))
> (format t "Around method called with ~A,~S~%" sequence node)
> (let ((result (call-next-method)))
> (when (funcall end sequence)
> (format t "~A is empty, setting ~S~%" sequence result)
> (setf (node-value result) value))
> (format t "Value at ~S now: ~S~%" result (node-value result))
> result))
>
[snip]
>
> USER(19): (tree-insert "bar" *t* :value 'bar)
> Around method called with bar,#<TERNARY-DATA-NODE @ #x204fe262>
> Around method called with ar,#<TERNARY-DATA-NODE @ #x2050175a>
> Around method called with r,#<TERNARY-DATA-NODE @ #x20501c12>
> r is empty, setting #<TERNARY-DATA-NODE @ #x20501c12>
> Value at #<TERNARY-DATA-NODE @ #x20501c12> now: NIL
According to these last two lines of output, the node-value of #x20501c12 has
just been set to NIL. Is that intentional? If BAR was intended, then maybe
your recursive step isn't passing :value down?
--
Martin Simmons
······@xanalys.com
rot13 to reply
On Mon, 11 Feb 2002, Martin Simmons wrote:
> "Holger Schauer" <··············@gmx.de> wrote in message
> > (defmethod node-insert :around ((sequence sequence) (node
>> USER(19): (tree-insert "bar" *t* :value 'bar)
>> Around method called with bar,#<TERNARY-DATA-NODE @ #x204fe262>
>> Around method called with ar,#<TERNARY-DATA-NODE @ #x2050175a>
>> Around method called with r,#<TERNARY-DATA-NODE @ #x20501c12>
>> r is empty, setting #<TERNARY-DATA-NODE @ #x20501c12>
>> Value at #<TERNARY-DATA-NODE @ #x20501c12> now: NIL
>
> According to these last two lines of output, the node-value of
> #x20501c12 has just been set to NIL. Is that intentional? If BAR
> was intended, then maybe your recursive step isn't passing :value
> down?
Oh my. I just made a mess of myself on cll. Yes, that was indeed
part of the problem. There was, however, another nasty tidbit. What
was happening was a combination of two bugs: on the one hand, indeed
the :value was not passed down during the recursion (as can be seen in
yesterdays posting). The second problem was that I have another
node-insert method, which is /not/ specialized on sequences
(i.e. specializes on t). What happened then was that the presented
:around method got happily called without :value, setting indeed the
slot to nil (the default). And then at the last level, due to
call-next-method, this non-specialized method got called, which
unconditionally inserted the value at the outer-most node. This led
to the result which looked (to me) like as if the recursion would
unrole before the :around method got called.
I think, I just learned three lessons:
* That the strict congruency wrt. to required method arguments does
not carry over to keywords. I.e., that the recursive value would not
get handed down was a problem of the specialized method using one more
keyword. Would have this been required or optional arguments, CL would
have detected the incongruency of arguments, but not so here.
Actually, I was aware of the congruency implications and even tried
to make use of the fact that the number of &keys does not need to
match, but still missed this bug. (Funny enough: prior to the
presented erroneous version, I did another one which was much more
complicated and uglier but did the (apply #'node-insert ... keys).)
So, the lesson here is probably that if you're doing recursive
invocations of methods with keywords, you better use &rest keys,
&key, &allow-other-keys and then apply #'foo keys -- you never know
whether specialized methods accept further keywords (and don't
forget to ensure that your local keys are added for further
recursion).
* I should have a more careful eye on method arguments wrt. to multiple
dispatch. I was so focussed on the specialization of my node classes
that I missed which method will /really, really/ be applied by
call-next-method. And yes, I read over the part of the CLHS again
and again that says that the next specific :around method will get
called. I did not notice though that this was related to my problem.
* Standard-method combination, which seems to be an easy to grasp
concept at first sight ("well, look here, this looks like the usual
polymorphism with some nice extensions"), has some subtelities which
may result in some hard to detect bugs. I mean, the reason I made
myself look stupid, was not that I got some error messages but only
weird behaviour. This is quite contrary to the usual response of CL:
in case you're doing something wrong, you usually do get errors, and
meaningful and expressive ones, too. Not so in this case. And as I
am not an experienced CLOS programmer, I was simply thinking that I
must be overlooking some detail about the results of CNM.
Well, to sum up, a typical case of PEBKAC -- problem exists between
keyboard and chair.
Thanks for your patience, anyway.
Holger
--
--- http://www.coling.uni-freiburg.de/~schauer/ ---
"The funny thing is that expressions in a Subject Oriented language
like Smalltalk can really look like sentences:
Fernando send: aPaper about: subjectOriented to: OOPSLA"
-- Fernando Mato Mira in comp.object
"Holger Schauer" <··············@gmx.de> wrote in message
···················@sowhat.coling.uni-freiburg.de...
> On Mon, 11 Feb 2002, Martin Simmons wrote:
> > "Holger Schauer" <··············@gmx.de> wrote in message
> > > (defmethod node-insert :around ((sequence sequence) (node
> >> USER(19): (tree-insert "bar" *t* :value 'bar)
> >> Around method called with bar,#<TERNARY-DATA-NODE @ #x204fe262>
> >> Around method called with ar,#<TERNARY-DATA-NODE @ #x2050175a>
> >> Around method called with r,#<TERNARY-DATA-NODE @ #x20501c12>
> >> r is empty, setting #<TERNARY-DATA-NODE @ #x20501c12>
> >> Value at #<TERNARY-DATA-NODE @ #x20501c12> now: NIL
> >
> > According to these last two lines of output, the node-value of
> > #x20501c12 has just been set to NIL. Is that intentional? If BAR
> > was intended, then maybe your recursive step isn't passing :value
> > down?
>
> Oh my. I just made a mess of myself on cll. Yes, that was indeed
> part of the problem. There was, however, another nasty tidbit. What
> was happening was a combination of two bugs: on the one hand, indeed
> the :value was not passed down during the recursion (as can be seen in
> yesterdays posting). The second problem was that I have another
> node-insert method, which is /not/ specialized on sequences
> (i.e. specializes on t). What happened then was that the presented
> :around method got happily called without :value, setting indeed the
> slot to nil (the default). And then at the last level, due to
> call-next-method, this non-specialized method got called, which
> unconditionally inserted the value at the outer-most node.
Ah, yes, I wondered how the value got there.
>
> I think, I just learned three lessons:
>
> * That the strict congruency wrt. to required method arguments does
> not carry over to keywords. I.e., that the recursive value would not
> get handed down was a problem of the specialized method using one more
> keyword. Would have this been required or optional arguments, CL would
> have detected the incongruency of arguments, but not so here.
> Actually, I was aware of the congruency implications and even tried
> to make use of the fact that the number of &keys does not need to
> match, but still missed this bug. (Funny enough: prior to the
> presented erroneous version, I did another one which was much more
> complicated and uglier but did the (apply #'node-insert ... keys).)
> So, the lesson here is probably that if you're doing recursive
> invocations of methods with keywords, you better use &rest keys,
> &key, &allow-other-keys and then apply #'foo keys -- you never know
> whether specialized methods accept further keywords (and don't
> forget to ensure that your local keys are added for further
> recursion).
In the ternary-search-trees case, it isn't clear to me why value is a keyword.
Would you ever need to insert a node without having a value?
>
> * I should have a more careful eye on method arguments wrt. to multiple
> dispatch. I was so focussed on the specialization of my node classes
> that I missed which method will /really, really/ be applied by
> call-next-method. And yes, I read over the part of the CLHS again
> and again that says that the next specific :around method will get
> called. I did not notice though that this was related to my problem.
>
> * Standard-method combination, which seems to be an easy to grasp
> concept at first sight ("well, look here, this looks like the usual
> polymorphism with some nice extensions"), has some subtelities which
> may result in some hard to detect bugs. I mean, the reason I made
> myself look stupid, was not that I got some error messages but only
> weird behaviour. This is quite contrary to the usual response of CL:
> in case you're doing something wrong, you usually do get errors, and
> meaningful and expressive ones, too. Not so in this case. And as I
> am not an experienced CLOS programmer, I was simply thinking that I
> must be overlooking some detail about the results of CNM.
A generic-function browser can help in cases like these, allowing you to trace
all the methods and try out various combinations of argument types to see which
methods would be called.
--
Martin Simmons, Xanalys Software Tools
······@xanalys.com
rot13 to reply
On Wed, 13 Feb 2002, Martin Simmons wrote:
> "Holger Schauer" <··············@gmx.de> wrote in message
>> So, the lesson here is probably that if you're doing recursive
>> invocations of methods with keywords, you better use &rest keys,
>> &key, &allow-other-keys and then apply #'foo keys -- you never
>> know whether specialized methods accept further keywords (and
>> don't forget to ensure that your local keys are added for further
>> recursion).
> In the ternary-search-trees case, it isn't clear to me why value is
> a keyword. Would you ever need to insert a node without having a
> value?
Yes, I think so. For example, when you just used it as some kind of
quick storage for sequences.
The reason I use a keyword for value is due to the congruency of
required arguments. But I also defined a version that doesn't look as
ugly on the outside for the data-trees (and yes, I choose to call it
ref because of the recent fuzz about a general ref operator):
(defmethod tree-ref ((tree ternary-data-tree) obj)
(tree-find tree obj))
(defmethod set-tree-ref ((tree ternary-data-tree) obj value)
(tree-insert tree obj :value value))
(defsetf tree-ref set-tree-ref)
>> * I should have a more careful eye on method arguments wrt. to
>> * multiple dispatch. I was so focussed on the specialization of my
>> * node classes that I missed which method will /really, really/ be
>> * applied by call-next-method. And yes, I read over the part of
>> * the CLHS again and again that says that the next specific :around
>> * method will get called. I did not notice though that this was
>> * related to my problem.
> A generic-function browser can help in cases like these, allowing
> you to trace all the methods and try out various combinations of
> argument types to see which methods would be called.
Does it really? I.e. does it somehow distinguish the various methods?
At least for CMUCL and ACL, just using trace doesn't.
Holger
--
--- http://www.coling.uni-freiburg.de/~schauer/ ---
"It seems to me you have become addicted to binaries. You should seek
help immediately. You should contact the nearest hacker and have him
dump your system full of tarballs for you to compile until your head
explodes." -- R. L. Kleeberger on debian-user
"Holger Schauer" <··············@gmx.de> wrote in message
···················@ipanema.coling.uni-freiburg.de...
> On Wed, 13 Feb 2002, Martin Simmons wrote:
> > A generic-function browser can help in cases like these, allowing
> > you to trace all the methods and try out various combinations of
> > argument types to see which methods would be called.
>
> Does it really? I.e. does it somehow distinguish the various methods?
> At least for CMUCL and ACL, just using trace doesn't.
In LW, if you trace the method (rather than the generic-function) then the trace
output says something like
(METHOD FOO (MY-CLASS))
--
Martin Simmons, Xanalys Software Tools
······@xanalys.com
rot13 to reply