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

[Duncan Rose]

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

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

> I haven't thought long and hard about it, but in the worst case, given  
> an arbitrary duplicate-test function, isn't it the case that we can't  
> do better than linear search to check for duplicates?  I.e., we have  
> no idea how to thin the field of possible match candidates, so we  
> can't do better than check EVERY existing graph node to see if a  
> newly-added one matches.  That seems unacceptable.  Or am I  
> overlooking somethign?
>

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

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

In as far as it departs from the specification, it's a sacrifice I  
think (though probably not a substantial sacrifice). To retread old  
ground, I would personally still prefer to see these kinds of changes  
implemented outside the main codebase of McCLIM (or at least, external  
to the implementation of the functionality that is present in the  
specification). At least that way, somebody could take the McCLIM  
'extension' and drop it into LW or ACL, and have their application  
work. That said, it's not like the vendors (especially Franz) have  
adhered to the spec anyway (Franz likes to reorder argument lists which  
kind of makes more sense, and improves consistency I guess, but does  
(IMO) damage portability. I can only conclude that portability between  
CLIM implementations wasn't Franz' main concern with regards to CLIM.  
Is it ours?) so maybe this is an irrelevance.

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

Without further user feedback I fear it will be difficult to resolve  
this issue to everyones satisfaction.

-Duncan


>
> Best,
>
> Robert
>
>
> P.S.  This discussion has reminded me to add an annotation to the CLIM  
> spec to this effect.
>