Recursive methods with :around's and call-next-method results 
Author Message
 Recursive methods with :around's and call-next-method results

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)








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:










What am I missing? Which piece in the CLHS?

Holger

--
---           http://www.*-*-*.com/ ~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



Fri, 30 Jul 2004 00:07:25 GMT  
 Recursive methods with :around's and call-next-method results


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



Fri, 30 Jul 2004 05:11:22 GMT  
 Recursive methods with :around's and call-next-method results

Quote:


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

Quote:
>>(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 :-)

Quote:
> 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):

Quote:
>>USER(19): (tree-insert "bar" *t* :value 'bar)





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:







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

    :END
    #<Interpreted Function (:INTERNAL
                            (CLOS:SLOT-DEFINITION-INITFUNCTION
                              TERNARY-SEARCH-TREE TREES::END))


#: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.

Quote:
> 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)



Fri, 30 Jul 2004 18:34:39 GMT  
 Recursive methods with :around's and call-next-method results

 > (defmethod node-insert :around ((sequence sequence) (node ternary-data-node)

Quote:
> &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)






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

rot13 to reply


Fri, 30 Jul 2004 22:50:39 GMT  
 Recursive methods with :around's and call-next-method results

Quote:


> >  > (defmethod node-insert :around ((sequence sequence) (node
> >> USER(19): (tree-insert "bar" *t* :value 'bar)





> > 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 {*filter*} 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.

- Show quoted text -

Quote:

> 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?

- Show quoted text -

Quote:

> * 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

rot13 to reply


Sun, 01 Aug 2004 20:08:37 GMT  
 Recursive methods with :around's and call-next-method results

Quote:


>>   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)

Quote:
>> * 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.*-*-*.com/ ~schauer/            ---
"It seems to me you have become {*filter*}ed 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



Sun, 01 Aug 2004 21:57:40 GMT  
 Recursive methods with :around's and call-next-method results

Quote:

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

rot13 to reply



Mon, 02 Aug 2004 03:42:19 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. call-next-next-method

2. around methods and shadowed methods

3. multiple calls to CALL-NEXT-METHOD

4. SCOOPS method calls (tail-recursive?)

5. CALL-NEXT-METHOD with changed parameters

6. Call-next-method extent and usage

7. call-next-method questions

8. Question about defmethod, call-next-method, and declarations

9. CALL-NEXT-METHOD behavior

10. condition system handler-bind analogy to call-next-method or compute-restarts

11. How do I call a method from another method within the same class

12. calling original method in overrided method?

 

 
Powered by phpBB® Forum Software