This post is an inquiry into CL style. I program primarily in C++ and
am interested in learning about how, or even whether to, adapt a
specific idiom to CL.
I am writing a program involving simple graph traversal, in which I
must walk the same graph for several different purposes at different
stages of the program. In C++ we have the Boost Graph Library�, which
separates graph structure and traversal algorithms using generic
programming techniques. The BGL favors compile-time binding with
templates over run-time binding with virtual functions.
BGL provides a depth-firth search algorithm� that makes callbacks on a
provided visitor object. As mentioned, BGL eschews virtual interfaces,
so no "depth first visitor" base class interface exists. Rather, the
interface is emergent from the set of valid expressions expected of a
provided visitor type. This imposition of interface, often called a
"concept,"� is typical in C++ template-based generic programming.
My question concerns how to express a function such as
depth_first_search requiring a callback type made up of several
functions. In C++, one simply accepts a single argument (here of
template type DFSVisitor) and calls each of the required functions on
it. The compiler ensures that this DFSVisitor type provides an
implementation of each function. How does one do this in CL?
So far, I have tried two approaches. The first is to explode the
callback interface, accepting a separate argument for each callback
function:
,----
| (defun dfs (g &optional v
| on-discover-vertex
| on-examine-edge
| on-tree-edge
| on-back-edge
| on-forward-or-cross-edge
| on-finish-vertex)
| ; ...
| )
`----
Within function dfs or some callee, I dispatch these callbacks like
so:
,----
| (if on-tree-edge
| (funcall on-tree-edge tgt g))
`----
The arguments are optional because a caller rarely needs to use all of
the callback events. Perhaps making these functions keyword arguments
would allow a caller to more easily specify which subset of functions
to provide.
My second approach is to use a single callback function, passing a tag
as an extra argument to distinguish which event is being reported. The
BGL has some adapter classes that transform the former style interface
into the latter.
Neither of these two approaches feel "right," for they are convenient
for neither the algorithm author nor the caller. I have never used
defgeneric or defmethod in CL. Preliminary reading of the Hyperspec
documentation shows me that these facilities may help emulate C++'s
generic programming style (write functions that uses unspecified types
in specified ways), but I'm not sure if they could help with the
grouping or clustering of related callback functions. Would one define
a set of generic functions (e.g. discover-vertex, examine-edge), and
expect a caller to specialize these functions for a given visitor
type?
I don't want to cut against the CL grain, so any suggestions on how to
find it and follow it would be most appreciated.
Footnotes:
� http://www.boost.org/libs/graph/doc/index.html
� http://www.boost.org/libs/graph/doc/depth_first_search.html
� http://www.boost.org/libs/graph/doc/DFSVisitor.html
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
Steven E. Harris wrote:
> My question concerns how to express a function such as
> depth_first_search requiring a callback type made up of several
> functions. In C++, one simply accepts a single argument (here of
> template type DFSVisitor) and calls each of the required functions on
> it. The compiler ensures that this DFSVisitor type provides an
> implementation of each function. How does one do this in CL?
You could do the same in CL, but to check at compile-time that all
methods have been supplied you would have to write a macro which expands
into a defclass and all the method definitions, then check there that
each method is defined. But later you wrote:
> The arguments are optional because a caller rarely needs to use all of
> the callback events. Perhaps making these functions keyword arguments
> would allow a caller to more easily specify which subset of functions
> to provide.
...so I am confused. :) Anyway, in CL it is "against the grain" to
especially want the compiler to find bugs. (Not that it does not save me
from many of them in its own way.)
> My second approach is to use a single callback function, passing a tag
> as an extra argument to distinguish which event is being reported.
Nothing wrong with that. Keeps all the handling in one place so there is
no need to track down a bunch of methods.
> Neither of these two approaches feel "right," for they are convenient
> for neither the algorithm author nor the caller.
For my money, I would not want to have to subclass DFSVisitor just to
kick off a search. I would prefer to supply (possibly) anonymous
handlers with access to their spawning lexical scope:
(defun look-for-weird-case (tree thing)
(tree-search thing
:on-edge (lambda (node)
(weird-relationship-p node thing))
:on-entry #'trace-node)
ie, tree-search (and any other searchers if you have a family) accepts
the optional handlers. You could also do
(tree-search thing (make-instance 'dfsvisitor :on-edge (lambda....
...but then you have to make a CLOS instance.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Cells let us walk, talk, think, make love and realize
the bath water is cold." -- Lorraine Lee Cudmore
Kenny Tilton <·······@nyc.rr.com> writes:
> I am confused. :) Anyway, in CL it is "against the grain" to
> especially want the compiler to find bugs.
Sorry, my question was poorly stated. I wasn't asking how to get the
compiler to verify that these functions are implemented, but rather
how to emulate the C++ idiom of passing an instance of some type to a
function or service and having that service call back various
functions on the provided instance.
In C++, we can use compile-time binding with templates or run-time
binding with virtual functions; in both cases, one defines a struct or
class, implements the interface functions, and passes an instance of
that type to the function or service�. Since member functions or
methods are not so directly associated with type in CL, I'm not sure
how to to translate these interface ideas into CL.
> For my money, I would not want to have to subclass DFSVisitor just
> to kick off a search. I would prefer to supply (possibly) anonymous
> handlers with access to their spawning lexical scope:
>
> (defun look-for-weird-case (tree thing)
> (tree-search thing
> :on-edge (lambda (node)
> (weird-relationship-p node thing))
> :on-entry #'trace-node)
>
> ie, tree-search (and any other searchers if you have a family)
> accepts the optional handlers.
Yes, using closures here allows us to capture any necessary context --
which the visitor instance usually provides.
> You could also do
>
> (tree-search thing (make-instance 'dfsvisitor :on-edge (lambda....
>
> ...but then you have to make a CLOS instance.
This would require a different tree-search that knows how to extract
the functions from the CLOS instance, right?
Footnotes:
� With templates, creating an instance isn't always necessary if the
functions don't depend upon instance-level data. The Policy idiom,
often related to the Traits idiom, is an example.
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
From: Joe Marshall
Subject: Re: Expressing a callback interface - CL style
Date:
Message-ID: <u1g1vv11.fsf@ccs.neu.edu>
Steven E. Harris <········@raytheon.com> writes:
> Sorry, my question was poorly stated. I wasn't asking how to get the
> compiler to verify that these functions are implemented, but rather
> how to emulate the C++ idiom of passing an instance of some type to a
> function or service and having that service call back various
> functions on the provided instance.
>
> In C++, we can use compile-time binding with templates or run-time
> binding with virtual functions; in both cases, one defines a struct or
> class, implements the interface functions, and passes an instance of
> that type to the function or service�. Since member functions or
> methods are not so directly associated with type in CL, I'm not sure
> how to to translate these interface ideas into CL.
One can do the same thing in CL. CL doesn't cast anything in stone,
so there is no difference between compile-time or run-time binding.
Bindings can be changed at any time.
An `interface' is simply a set of generic functions. CL doesn't
bundle them in any way. So just create a class and define methods for
the appropriate generic functions.
> Footnotes:
> � With templates, creating an instance isn't always necessary if the
> functions don't depend upon instance-level data. The Policy idiom,
> often related to the Traits idiom, is an example.
Again, you can mimic this in CLOS by either creating a class with no
slots, using an EQL specializer, or just calling a function.
However, many of these `patterns' and `idioms' that are in C++ arise
because the language is severely impoverished. There are no anonymous
functions, so rather than calling MAP on a sequence, you are expected
to bundle the traversal state of MAP along with the sequence in a
third object that MAP understands.
Because there is no type inference or polymorphism, you are also
expected to bundle your function in yet another object....
Steven E. Harris wrote:
> Since member functions or
> methods are not so directly associated with type in CL, I'm not sure
> how to to translate these interface ideas into CL.
Well, CLOS in this sense is a superset of what you are after. So just do it:
(defclass xxx ()())
(defmethod do-it ((this xxx) &rest mo-better-args)
...)
(defclass yyy ()())
(defmethod do-it ((this yyy) &rest mo-better-args)
...)
ie, pretend multi-dispatch does not exist. Hell, 90% of Cello (my
current project) methods look like:
(defmethod what-ever ((self IXText) yada1 yada2) ...)
In short, I wager your C++ visitor code translates to Lisp/CLOS directly.
>>For my money, I would not want to have to subclass DFSVisitor just
>>to kick off a search. I would prefer to supply (possibly) anonymous
>>handlers with access to their spawning lexical scope:
>>
......
> Yes, using closures here allows us to capture any necessary context --
> which the visitor instance usually provides.
Not good enough for a Lisper. "fast and loose" is our motto. There I am
coding away great guns at 3am and I need to write a function which takes
an argument and then kicks off a search with a callback closed over that
argument and you want me to what? Stop. Define a class with a slot for
that argument. Define a constructor that takes that slot as an argument
so i can construct an instance of that class just to do what the Lisp
programmer finished in-line five minutes ago without even reaching for
the coffee? Nahhhh...
>
>
>>You could also do
>>
>> (tree-search thing (make-instance 'dfsvisitor :on-edge (lambda....
>>
>>...but then you have to make a CLOS instance.
>
>
> This would require a different tree-search that knows how to extract
> the functions from the CLOS instance, right?
"different tree search"? Not sure what other one we're talking about. If
we are talking about a Visitor instance, I gather the search code does
something like (guessing at C++) at some poinbt:
v->enterNode( node );
With my instance-based example you would (simplified vastly):
(defun search-list (list v)
(dolist (node list)
(funcall (enterNode v) node)))
A class-based approach would be like the C++:
(defclass v1 (visitor)())
(defmethod enterNode ((this v1) node)
...etc...
With my tree function keyword arg suggestion you would
(defun search-list (list &key enterNode ....others...)
(dolist (node list)
(when enterNode
(funcall enter-node node))
I like the latter because, as i said before, it lends itself to
fast-n-loose.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Cells let us walk, talk, think, make love and realize
the bath water is cold." -- Lorraine Lee Cudmore
Kenny Tilton <·······@nyc.rr.com> writes:
>> Yes, using closures here allows us to capture any necessary context --
>> which the visitor instance usually provides.
>
> Not good enough for a Lisper. "fast and loose" is our motto. There I
> am coding away great guns at 3am and I need to write a function which
> takes an argument and then kicks off a search with a callback closed
> over that argument and you want me to what?
[...]
I think you read the opposite meaning from my comment. I too was
advocating that a closure can provide all the context one needs,
without bothering with the class instance required in other
languages. We agree here.
> "different tree search"? Not sure what other one we're talking
> about.
You showed two examples; the first took functions as keyword
arguments, the second took a single CLOS instance. By "different" I
meant that you would need two tree search functions, one that operates
on functions from keyword arguments and one that calls upon a CLOS
instance.
> If we are talking about a Visitor instance, I gather the search code
> does something like (guessing at C++) at some poinbt:
>
> v->enterNode( node );
>
> With my instance-based example you would (simplified vastly):
>
> (defun search-list (list v)
> (dolist (node list)
> (funcall (enterNode v) node)))
That last line throws me. Is that saying to extract the "enterNode"
function from instance "v" and call it, passing "node" as a single
argument? If so, it's not the same as the C++ example, because in C++
the object gets passed as an implicit first argument to its member
functions. That first argument provides context. In your example
above, I'm not sure what kind of function would be returned from the
form (enterNode v). Would it be a closure over v to retain context?
> A class-based approach would be like the C++:
>
> (defclass v1 (visitor)())
> (defmethod enterNode ((this v1) node)
I don't see how the "this" argument is provided in your search-list
function above.
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
Steven E. Harris wrote:
> That last line throws me. ...
I was bouncing around from approach-to-approach in the same sentence.
Mistakes were made because when I floated the idea of creating an
instance with callbacks as slot data, I was not thinking the instance
also carried state around (good idea) so when I mimicked C++ the second
time I did not think to pass the visitor instance.
Anyway, we agree, yechh. To me something like:
(defun gen-wicked-callback (arg1 arg2)
(lambda (node)
(wicked-analysis node arg2 arg1)))
...goes to Lisp's code-data equivalency thang. The data arguments to
gen-wicked-callback become code in the lambda. Indeed, when I later code:
(mapcar (gen-wicked-callback :deep #'>) list)
...I actually am mentally in coding mode when I type the seeming data
:deep and #'>, so Lisp is doing a cool job of translating the dynamic
data :deep and #'> into not just code but more elaborate code, as
amplified by the callback generating code.
C++ don't play dat, we agree. it can't go straight from runtime data to
callback, so it has to stop off to make a data instance in which to
stash the context.
Lisp just treats the lexical view as an information atmosphere to be
drawn on randomly, while passing dynamic information statically (thru
static (lexical) structure (lambda lists)) from lexical view to view.
Lexical-dynamic tunneling brought to you by special variables.
I need another pint.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Cells let us walk, talk, think, make love and realize
the bath water is cold." -- Lorraine Lee Cudmore
Steven E. Harris <········@raytheon.com> writes:
...
> BGL provides a depth-firth search algorithm� that makes callbacks on a
> provided visitor object. As mentioned, BGL eschews virtual interfaces,
> so no "depth first visitor" base class interface exists. Rather, the
> interface is emergent from the set of valid expressions expected of a
> provided visitor type. This imposition of interface, often called a
> "concept,"� is typical in C++ template-based generic programming.
>
> My question concerns how to express a function such as
> depth_first_search requiring a callback type made up of several
> functions. In C++, one simply accepts a single argument (here of
> template type DFSVisitor) and calls each of the required functions on
> it. The compiler ensures that this DFSVisitor type provides an
> implementation of each function. How does one do this in CL?
You don't do it at compile time in Common Lisp...
>
> So far, I have tried two approaches. The first is to explode the
> callback interface, accepting a separate argument for each callback
> function:
>
> ,----
> | (defun dfs (g &optional v
> | on-discover-vertex
> | on-examine-edge
> | on-tree-edge
> | on-back-edge
> | on-forward-or-cross-edge
> | on-finish-vertex)
> | ; ...
> | )
> `----
>
> Within function dfs or some callee, I dispatch these callbacks like
> so:
>
> ,----
> | (if on-tree-edge
> | (funcall on-tree-edge tgt g))
> `----
>
> The arguments are optional because a caller rarely needs to use all of
> the callback events. Perhaps making these functions keyword arguments
> would allow a caller to more easily specify which subset of functions
> to provide.
Yes, it would.
...
> Neither of these two approaches feel "right," for they are convenient
> for neither the algorithm author nor the caller. I have never used
> defgeneric or defmethod in CL. Preliminary reading of the Hyperspec
> documentation shows me that these facilities may help emulate C++'s
> generic programming style (write functions that uses unspecified types
> in specified ways), but I'm not sure if they could help with the
> grouping or clustering of related callback functions. Would one define
> a set of generic functions (e.g. discover-vertex, examine-edge), and
> expect a caller to specialize these functions for a given visitor
> type?
That's exactly what I'd do. You can either define reasonable default
methods (methods with arguments specialized on t) or don't and let a
no-applicable-method error be signalled. You could require that classes
for which your "callback" methods are implemented inherit from e.g., a
"node-mixin", but that's not really necessary. Common Lisp is more
about protocols than class relationships.
Tim
·····@bricoworks.com writes:
> That's exactly what I'd do. You can either define reasonable default
> methods (methods with arguments specialized on t) or don't and let a
> no-applicable-method error be signalled.
I'd probably do the former, assuming that most traversals ignore all
but one or two events.
> You could require that classes for which your "callback" methods are
> implemented inherit from e.g., a "node-mixin", but that's not really
> necessary.
Yes, even before posting, I suspected that this kind of root class
definition is not appropriate in CL.
> Common Lisp is more about protocols than class relationships.
I will take this to heart. But I don't see how protocols emerge as
first-class ideas in CL. At the single function level, a signature
provides the protocol. In my graph traversal example, how does one
document that, say, dfs will call certain methods upon the visitor? If
I present the function as
,----
| (defun dfs (g visitor &optional start-vertex)
| ; ...
| )
`----
how do I inform callers what is expected of the visitor argument? Kaz
Kylheku posted some examples of the associated method definitions. We
know that these methods are related because of our discussion
here. Does the CL programmer use comments to make the association
between a set of methods? I imagine something like
,----
| Function /dfs/ calls the following methods, using the provided
| /g/ and /visitor/ arguments in each call:
|
| o initialize-vertex (visitor vertex g)
| Invoked on every vertex of the graph before the start of the
| graph search.
| o start-vertex (visitor vertex g)
| Invoked on the source vertex once before the start of the
| search.
| o discover-vertex (visitor vertex g)
| Invoked when a vertex is encountered for the first time.
| o examine-edge (visitor edge g)
| Invoked on every out-ege of each vertex after it is
| discovered.
| o on-tree-edge (visitor edge g)
| Invoked on each edge as it becomes a member of the edges that
| form the search tree.
| ...
`----
That's just prose. Is that enough of a protocol?
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
Steven E. Harris <········@raytheon.com> wrote in message news:<··············@harris.sdo.us.ray.com>...
> This post is an inquiry into CL style. I program primarily in C++ and
> am interested in learning about how, or even whether to, adapt a
> specific idiom to CL.
>
> I am writing a program involving simple graph traversal, in which I
> must walk the same graph for several different purposes at different
> stages of the program. In C++ we have the Boost Graph Library�, which
> separates graph structure and traversal algorithms using generic
> programming techniques. The BGL favors compile-time binding with
> templates over run-time binding with virtual functions.
Lisp favors run-time binding in its object system.
> BGL provides a depth-firth search algorithm� that makes callbacks on a
> provided visitor object. As mentioned, BGL eschews virtual interfaces,
> so no "depth first visitor" base class interface exists.
There are no such things as interfaces or abstract base classes in the
Common Lisp Object System. Two types are substitutable with respect to
a set of generic functions if specializations (methods) exist to
handle them. No inheritance is required.
In fact you can make the built-in types obey the same protocol as some
class object of yours, if you are so inclined. Define some generic
functions that constitute an interface, and then specialize them to
whatever types, be they classes that you defined, or things like
conses or integers.
CLOS can even dispatch on integer values and symbols, so you can
specialize a method parameter to the symbol FOO, or to the value 42.
And of course CLOS methods are dynamically specialized on all
parameters (a.k.a. multiple dispatch). So you don't need design
patterns like Visitor which emulate double dispatch.
> Rather, the
> interface is emergent from the set of valid expressions expected of a
> provided visitor type.
This is closer to Lisp than inheriting from a common base, but it's
achieved at the expense of compile-time bloat.
In Lisp, we can say this: ``the interface is emergent from the set of
generic functions for which specializations are expected over the
provided visitor type''.
> This imposition of interface, often called a
> "concept,"� is typical in C++ template-based generic programming.
Hehehehe.
> My question concerns how to express a function such as
> depth_first_search requiring a callback type made up of several
> functions. In C++, one simply accepts a single argument (here of
> template type DFSVisitor) and calls each of the required functions on
> it. The compiler ensures that this DFSVisitor type provides an
> implementation of each function. How does one do this in CL?
>
> So far, I have tried two approaches. The first is to explode the
> callback interface, accepting a separate argument for each callback
> function:
>
> ,----
> | (defun dfs (g &optional v
> | on-discover-vertex
> | on-examine-edge
> | on-tree-edge
> | on-back-edge
> | on-forward-or-cross-edge
> | on-finish-vertex)
> | ; ...
> | )
> `----
Here it seems that you are not takign advantage of the object system.
DFS is an ordinary function rather than a method. I take it that the
on-* handlers are also ordinary functions/closures. (Though in Lisp
you *can* use a generic function in place of an ordinary function, by
the way).
This seems quite clumsy; ideally you should just pass the object. The
functions on-discover-vertex and so forth should be one-parameter
generic functions for which you can define methods that take a given
visitor type.
> Within function dfs or some callee, I dispatch these callbacks like
> so:
>
> ,----
> | (if on-tree-edge
> | (funcall on-tree-edge tgt g))
> `----
I see, you want to test whether a method exists, and the use it or not
use it.
There are better ways to do this.
If you use CLOS, the above becomes simply:
(on-tree-edge visitor target graph)
You can write methods to specialize the code for any combinations of
visitors, targets and graphs. If you want to use a string as a
visitor, no problem:
(defmethod on-tree-edge ((visitor string) target graph)
...)
the absence of a type specification means that the type defaults to T,
which means match any type.
Now this brings us to the point of how does the writer of the visitor
type assert that the on-tree-edge method does not exist? What he can
do is write one that does nothing. Or better yet, you can provide a
catch-all handler, so that people don't have to worry about it: they
simply don't bother implementing the method and it silently does
nothing:
;;; default on-tree-edge, called when no other specialization for
given
;;; visitor exists.
(defmethod on-tree-edge ((visitor t) target graph)
(declare (ignore visitor target graph))
(values))
The (visitor t) notation is the same as just writing visitor, but it
emphasizes that visitors that have no other specialization are being
caught. We kind of care more about the left argument in this design,
because we are reusing some ideas from a single-dispatch object
system.
> I don't want to cut against the CL grain, so any suggestions on how to
> find it and follow it would be most appreciated.
I think that your original approach also has its merits. By passing
the functions down, you can easily use lambda expressions, and over
top of that write a macro called DO-DFS that turns DFS into a seamless
language feature, whose use looks like this:
(defun count-vertices (graph)
(let ((count 0))
(do-dfs (graph count) ;; second arg is return value of form
:on-discover-vertex (v) (incf count))))
You can still use the object system, you just write your own dispatch.
That is if you want to call a generic function in respnose to
on-discover-vertex, nothing stops you from manually inserting the
right call. You can easily make a function which will adapt the
closure-based DFS to the object oriented approach:
(defun dfs-oo (graph visitor)
(do-dfs (graph)
:on-discover-vertex (target)
(on-discover-vertex visitor target graph)
:on-... (...)
(on-... )
...))
The various clauses of the DO-DFS macro keyed by keywords are compiled
by the macro into LAMBDA expressions, which are then passed to your
original DFS. As you can see, you lose no flexibility at all; the
entire CLOS based approach as I described it can still be employed,
completely hidden behind DFS-OO. Lastly, we can make DFS-OO into a
method, so you can specialize its behavior to different graph-like
things and visitors:
(defgeneric dfs-oo (graph visitor)
;; default implementation for (T T), as above
...)
Hope this helps.
From: Marco Antoniotti
Subject: Re: Expressing a callback interface - CL style
Date:
Message-ID: <3E2EBB8B.5010204@cs.nyu.edu>
Hi
One thing to note is that things like the GOF Visitor pattern are a
neccessary kludge in C++ style languages. In CL you would use
multi-method dispatch to achieve the same effects in an easier and
cleaner way. I.e. you would write a "generic function"
(defgeneric visit (container item))
and provide appropriate methods for it. The multi-method dispatching
rule (which is more flexible than argument overloading) will take care
of things for you.
E.g.
(defmethod visit ((g graph) (i node)) ...)
(defmethod visit ((g graph) (e edge)) ...)
(defmethod visit ((g graph) (fe forward-edge)) ...)
etc etc (not correct, but it is just to illustrate the idea). If you
want to do something after you have visited a note you just do
(defmethod visit :after ((g graph) (i node)) ...)
Everything incrementally and flexibly.
Of course that does not guarantee you that the compiler will issu
warnings about "unimplemented" methods. But that solution is just a few
macros away.
Cheers
Steven E. Harris wrote:
> This post is an inquiry into CL style. I program primarily in C++ and
> am interested in learning about how, or even whether to, adapt a
> specific idiom to CL.
>
> I am writing a program involving simple graph traversal, in which I
> must walk the same graph for several different purposes at different
> stages of the program. In C++ we have the Boost Graph Library�, which
> separates graph structure and traversal algorithms using generic
> programming techniques. The BGL favors compile-time binding with
> templates over run-time binding with virtual functions.
>
> BGL provides a depth-firth search algorithm� that makes callbacks on a
> provided visitor object. As mentioned, BGL eschews virtual interfaces,
> so no "depth first visitor" base class interface exists. Rather, the
> interface is emergent from the set of valid expressions expected of a
> provided visitor type. This imposition of interface, often called a
> "concept,"� is typical in C++ template-based generic programming.
>
> My question concerns how to express a function such as
> depth_first_search requiring a callback type made up of several
> functions. In C++, one simply accepts a single argument (here of
> template type DFSVisitor) and calls each of the required functions on
> it. The compiler ensures that this DFSVisitor type provides an
> implementation of each function. How does one do this in CL?
>
> So far, I have tried two approaches. The first is to explode the
> callback interface, accepting a separate argument for each callback
> function:
>
> ,----
> | (defun dfs (g &optional v
> | on-discover-vertex
> | on-examine-edge
> | on-tree-edge
> | on-back-edge
> | on-forward-or-cross-edge
> | on-finish-vertex)
> | ; ...
> | )
> `----
>
> Within function dfs or some callee, I dispatch these callbacks like
> so:
>
> ,----
> | (if on-tree-edge
> | (funcall on-tree-edge tgt g))
> `----
>
> The arguments are optional because a caller rarely needs to use all of
> the callback events. Perhaps making these functions keyword arguments
> would allow a caller to more easily specify which subset of functions
> to provide.
>
> My second approach is to use a single callback function, passing a tag
> as an extra argument to distinguish which event is being reported. The
> BGL has some adapter classes that transform the former style interface
> into the latter.
>
> Neither of these two approaches feel "right," for they are convenient
> for neither the algorithm author nor the caller. I have never used
> defgeneric or defmethod in CL. Preliminary reading of the Hyperspec
> documentation shows me that these facilities may help emulate C++'s
> generic programming style (write functions that uses unspecified types
> in specified ways), but I'm not sure if they could help with the
> grouping or clustering of related callback functions. Would one define
> a set of generic functions (e.g. discover-vertex, examine-edge), and
> expect a caller to specialize these functions for a given visitor
> type?
>
> I don't want to cut against the CL grain, so any suggestions on how to
> find it and follow it would be most appreciated.
>
>
> Footnotes:
> � http://www.boost.org/libs/graph/doc/index.html
> � http://www.boost.org/libs/graph/doc/depth_first_search.html
> � http://www.boost.org/libs/graph/doc/DFSVisitor.html
>
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
715 Broadway 10th Floor fax +1 - 212 - 998 3484
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
Marco Antoniotti <·······@cs.nyu.edu> writes:
> One thing to note is that things like the GOF Visitor pattern are a
> neccessary kludge in C++ style languages.
While doing research before posting, I came across many discussions
about the Visitor pattern being unnecessary in CL because it has
muti-argument dispatch. I understand that point, but my question was
more about callback interfaces with several functions than about
dispatching on type.
It's easy to find CL examples that pass a single function or closure
as an argument, but I couldn't find examples that correspond to the
abstract handler idiom, where the called function or service will in
turn call several related functions upon a single entity.
> In CL you would use multi-method dispatch to achieve the same
> effects in an easier and cleaner way. I.e. you would write a
> "generic function"
>
> (defgeneric visit (container item))
>
> and provide appropriate methods for it.
Wouldn't we need a third argument -- the actual visitor? I may not
care what type of graph I'm using, but want to handle a particular
item or event (such as tree-edge) for a /particular/ visitor.
> (defmethod visit ((g graph) (i node)) ...)
> (defmethod visit ((g graph) (e edge)) ...)
> (defmethod visit ((g graph) (fe forward-edge)) ...)
I know you're just sketching a solution, but I want to make sure I
understand what these methods provide. These define behavior for
interaction between a graph instance and some particular item
instance, but don't specialize on a given visitor type. Wouldn't that
mean that every traversal of some graph would behave the same way?
What if one wanted to perform different sets of actions in repeated
traversals of the same graph? You didn't show a signature for a
top-level traversal function like dfs, but it looks like you're
suggesting that no visitor instance need be provided.
> Everything incrementally and flexibly.
So much choice can be overwhelming, in a delightful way.
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
Marco Antoniotti <·······@cs.nyu.edu> wrote in message news:<················@cs.nyu.edu>...
> Hi
>
> One thing to note is that things like the GOF Visitor pattern are a
> neccessary kludge in C++ style languages. In CL you would use
> multi-method dispatch to achieve the same effects in an easier and
> cleaner way. I.e. you would write a "generic function"
>
> (defgeneric visit (container item))
>
> and provide appropriate methods for it. The multi-method dispatching
> rule (which is more flexible than argument overloading) will take care
> of things for you.
Not quite! Firstly the term VISIT is no longer applicable when you use
CLOS, because you no longer have a visitor object. That non-essential
glue object is at the heart of the visitor pattern; without it, there
is no need for the visitation terminology.
It has just occured to me in a flash of insight that a visitor object
encapsulates a generic function object. How you use the visitor
pattern in C++ is that you have some abstract visitor base class, and
you derive that into specific kinds of visitors that represent
algorithms to be done over the elements of some structure.
For example, given an expression tree, one kind of visitor might
perform pretty printing for every node. Another might do some kind of
evaluation. And so on. So a visitor *class* in fact corresponds to a
*generic function*.
But in your example above, you have just one generic function with the
anonymous name visit. That is wrong; there has to be more than one
generic function, and it should be named after the specific visitation
algorithm that is done. The accept and visit methods in the Visitor
Pattern are just fluff; we don't retain them in transforming the
solution to CLOS.
So you have:
(defgeneric dump-info-about-node (node))
(defgeneric transform-node-in-some-way (node))
and others.
Notice that the visitation functions just take one argument. It's not
in fact multiple dispatch at all.
Yes, there are two levels of indirection, but it's not double
dispatch. Rather, it's the indirect selection of a generic function
followed by single dispatch.
Imagine that you have this function for processing the graph:
(defun map-graph (visitor-generic-function graph)
...)
At the heart of this function you would have:
(funcall visitor-generic-function graph)
Then given the generic functions we proposed previously, you could
call MAP-GRAPH like this:
(map-graph #'dump-info-about-node graph)
(map-graph #'transform-node-in-some-way graph)
And, of course, using a regular closure:
(map-graph #'(lambda (node) ...) graph)
The generic function *is* the visitor, dispatched indirectly by
funcall, and dynamically over the node.
The visitor pattern is not about making up for the lack of multiple
dispatch; the issue being overcome is deeper than that. It's a feeble
attempt to do the equivalent of Lisp's function applicative operators
(FUNCALL, MAPCAR, ...) combined with generic functions---the fact that
we can treat a generic function as an object to indirect upon it.
A visitor is therefore nothing more than a polymorphic functor. The
big clue that an object is a functor is when there is just one
function (or multiple functions with the same name, but overloaded),
and that function is named after the class. Whenever you have some
class called foobar whose only member function is foobar, you might as
well conclude that it's the ``function'' class whose job is to
``function''; in other words a functor. The function might as well be
anonymous; its name is redundant, since the class name, actually a
verb, already indicates that the job is to do the foobar action.
Getting back to the original topic, the traversal callback is not
exactly a visitor. Firstly, the callback object is not functor,
because it has various methods. There is more of a protocol between
the callback and the traversal algorithm; a node is not just visited,
but a certain set of handlers fire in some expected order. There is
not necessarily any dynamic dispatch on the node type; rather you have
specific handlers for various elements of the graph being traversed:
we are going down an edge, up the edge, visiting the node, etc. Now in
Lisp we can make these handlers generic functions, which gives us a
kind of super-Visitor-pattern. There is a whole bunch of visitors
being used all at once in a single traversal to implement a complex
visitation protocol. To do that in C++ using the Visitor pattern, you
would have to create half a dozen classes to encapsulate the action
for each handler, and in each one you would have to specialize the
overloads for each node type. Ugh.
From: Joe Marshall
Subject: Re: Expressing a callback interface - CL style
Date:
Message-ID: <of69vuq7.fsf@ccs.neu.edu>
···@ashi.footprints.net (Kaz Kylheku) writes:
> The visitor pattern is not about making up for the lack of multiple
> dispatch; the issue being overcome is deeper than that. It's a feeble
> attempt to do the equivalent of Lisp's function applicative operators
> (FUNCALL, MAPCAR, ...) combined with generic functions---the fact that
> we can treat a generic function as an object to indirect upon it.
>
> A visitor is therefore nothing more than a polymorphic functor. The
> big clue that an object is a functor is when there is just one
> function (or multiple functions with the same name, but overloaded),
> and that function is named after the class.
Henry Baker wrote about this in:
@article{ jr93iterators,
author = "${}^{\clubsuit}$Henry G. {Baker, Jr.}",
title = "Iterators: Signs of Weakness in Object-Oriented Languages",
journal = "{ACM} {OOPS} Messenger",
volume = "4",
number = "3",
pages = "18--25",
year = "1993",
url = "citeseer.nj.nec.com/55669.html" }
> Getting back to the original topic, the traversal callback is not
> exactly a visitor. Firstly, the callback object is not functor,
> because it has various methods. There is more of a protocol between
> the callback and the traversal algorithm; a node is not just visited,
> but a certain set of handlers fire in some expected order. There is
> not necessarily any dynamic dispatch on the node type; rather you have
> specific handlers for various elements of the graph being traversed:
> we are going down an edge, up the edge, visiting the node, etc. Now in
> Lisp we can make these handlers generic functions, which gives us a
> kind of super-Visitor-pattern. There is a whole bunch of visitors
> being used all at once in a single traversal to implement a complex
> visitation protocol. To do that in C++ using the Visitor pattern, you
> would have to create half a dozen classes to encapsulate the action
> for each handler, and in each one you would have to specialize the
> overloads for each node type. Ugh.
I bet there is a template hacker already drooling over this.
Kaz Kylheku wrote:
... lots of interesting stuff.
Well thanks. I had not really thought of it in that way. But you are
right.
Cheers
--
Marco Antoniotti
Marco Antoniotti <·······@cs.nyu.edu> wrote in message news:<·················@typhoon.nyu.edu>...
> Kaz Kylheku wrote:
>
> ... lots of interesting stuff.
>
> Well thanks. I had not really thought of it in that way.
Neither had I! :)