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