[mcclim-devel] question about CLIM spec [format-graph-from-roots]

[Robert P. Goldman]

>>>>> "DR" == Duncan Rose <duncan at robotcat.demon.co.uk> writes:

    DR> On Thursday, July 21, 2005, at 06:55  pm, Robert P. Goldman wrote:

    >> Duncan Rose wrote:
    >> 
    >>> On Monday, July 18, 2005, at 08:13  pm, rpgoldman at real-time.com wrote:
    >>>> 
    >>>> AFAICT, the CLIM spec doesn't say anything about what are the
    >>>> acceptable values for the DUPLICATE-TEST argument to
    >>>> FORMAT-GRAPH-FROM-ROOTS (although it does specify that the default
    >>>> value is EQL).  This seems very unfortunate.  If we were to be  
    >>>> limited
    >>> It says that it is a '...function of two arguments that is used to  
    >>> compare two objects...'
    >>> I think any function of two arguments that can be used to compare two  
    >>> objects should be ok.
    >>>> to the conventional equality test values, then we would be able to  
    >>>> use
    >>>> a hash-table to store the graph nodes.  However, if the spec permits
    >>>> arbitrary functions of two arguments, that seems to make use of
    >>>> hash-tables impossible.  Am I overlooking something?  Is this a
    >>>> deficiency in the spec?
    >>> I don't understand what the benefit of using hashtables to store the  
    >>> nodes is. That said, it seems to me that whilst the spec permits  
    >>> arbitrary functions of two arguments, any specific node type will  
    >>> need a particular DUPLICATE-TEST function... or am I missing the  
    >>> point of the question totally?
    >> 
    >> Given the fact that there might be a very large number of nodes, and  
    >> that we have to check for duplicates, a hash-table providing constant  
    >> time lookup seems pretty desirable, so one could do
    >> 
    >> (make-hash-table :test duplicate-test)
    >> (gethash (funcall duplicate-key node) hash-table)
    >> 
    >> to find duplicates.
    >> 
    >> Perhaps /I'm/ missing the point --- do you have a different vision of  
    >> how the duplicate detection could be performed?
    >> 

    DR> I'm with you now; I agree that duplicate node checking would
    DR> be easier and likely quicker using hashtables. I suspect that
    DR> the original intention was that the graph be traversed to find
    DR> duplicates; as you say, a linear search (perhaps something
    DR> better could be achieved for ordered trees, but I'm not sure
    DR> that the function arguments allow such possibilities).

I think I should provide an implementation that is based on the use of
hash-tables, checking for the argument being EQ, EQL, EQUAL or EQUALP.
I can have a mixin class providing the hash table and a
find-previous-node generic function that does the lookup, and a linear
search implementation of the method for the default case.

[...snip...]

    DR> I think that the original intention was not to provide a built in  
    DR> function for drawing arbitrarily complex graphs of many nodes. Perhaps  
    DR> it was (again, it would be nice if one of the CLIM designers were  
    DR> subscribed to this list to answer such questions ;-). In the CLIM  
    DR> mailing list archive  
    DR> (ftp://ftp.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/gui/ 
    DR> clim/mail/) a lot of these kinds of questions seem to me to have been  
    DR> answered with 'if the supplied functionality doesn't meet your specific  
    DR> requirement, write something that does'. I think this may be one of  
    DR> those cases where the generalised CLIM functionality fails under  
    DR> specific usage, that either was not anticipated (in which case there's  
    DR> an argument for changing FORMAT-GRAPH-FROM-ROOTS) or that was  
    DR> anticipated and purposefully left unsupported - of course, we are only  
    DR> left to guess at which of these is correct.

This is a good point.  It's clear, for example, that
format-graph-from-roots is insufficient for a graph *editor*, since it
doesn't provide support for being able to move the graph nodes, etc.
So there's a case where one is clearly moving beyond
format-graph-from-roots.  But my case (simple dag display) seems
acceptable.


    >> Note also that since you have the freedom to define the DUPLICATE-KEY  
    >> funciton yourself, restricting the DUPLICATE-TEST values to one of the  
    >> hash-table-acceptable alternatives doesn't seem like a profound  
    >> sacrifice.
    >> 
    >> Can anyone think of a case where it would be a substantial sacrifice?

    DR> In as far as it departs from the specification, it's a
    DR> sacrifice I think (though probably not a substantial
    DR> sacrifice). To retread old ground, I would personally still
    DR> prefer to see these kinds of changes implemented outside the
    DR> main codebase of McCLIM (or at least, external to the
    DR> implementation of the functionality that is present in the
    DR> specification). At least that way, somebody could take the
    DR> McCLIM 'extension' and drop it into LW or ACL, and have their
    DR> application work. 

This seems like a good idea, but I'm skeptical that it will work in
practice.  AFAICT, the documented graph-formatting interface is simply
not sufficient to allow someone to create a portable extension.  I am
certainly finding that if I want to build onto what's there, I need to
(or at least, it's a lot easier to) do it by using stuff that is not
part of the specified API.  For example, if one wishes to add slots to
graph-output-record types, one really must take advantage of the fact
that format-graph-from-roots in McCLIM passes extra arguments to the
graph-output-record constructor, which is not (unless I missed
something) part of the graph-formatting protocol.  Similarly, the CLIM
spec does not allow for additional keyword arguments to
format-graph-from-roots, which IMHO would make the avowed intention of
providing an extensible API well-nigh impossible.  I take advantage of
the fact that McCLIM has format-graph-from-roots with &allow-other-keys.


    DR> That said, it's not like the vendors (especially Franz) have
    DR> adhered to the spec anyway (Franz likes to reorder argument
    DR> lists which kind of makes more sense, and improves consistency
    DR> I guess, but does (IMO) damage portability. I can only
    DR> conclude that portability between CLIM implementations wasn't
    DR> Franz' main concern with regards to CLIM.  Is it ours?) so
    DR> maybe this is an irrelevance.

Since I don't expect ever to be able to afford a CLIM license from a
vendor, this is not a huge concern of mine!  That's not intended to be
a slam --- CLIM seems horribly un-economical from the perspective of a
Lisp vendor, combining the bad features of hugeness and expense to
maintain with a vanishingly small user base.

    DR> In summary: I think your argument has merit, I just feel that
    DR> changing FORMAT-GRAPH-FROM-ROOTS isn't the place to rectify
    DR> the problem(s).

Granted.  I think that the hash-table can be supported using CLOS
specialization w/o violating the spec (modulo &allow-other-keys, which
seems mandatory and, in any case, isn't MY violation!), and if it can
be, should be.

I hope to provide a better patch RSN.

OPEN QUESTION:  The HASH-TABLE slot in standard-graph-output-record is
not documented as to purpose.  However, it seems to be used for
duplicate-handling in GENERATE-GRAPH-NODES.  On that basis, I'm
inclined to remove it, move it into the mixin I've proposed, and
provide something that's actually MORE standard-compliant than the
current version.

OPEN QUESTION 2: Would people who are using format-graph-from-roots be
willing to send me a test case or test cases so that I can make sure
any new version I create doesn't bust things?

Thanks,
Robert