From: <web...@ih...> - 2004-04-21 00:36:08
|
Hi David, I have been doing more work on [arraylist] == [dict] and discovered a whole lot of interesting stuff - some of it curly. So I am rewriting my comments on the dict definition. There are a lot of points in what I have sent you, but what I have sent you is not worth circulating as it is. I shall probably write up a comprehensive [arraylist] webpage at webscool.org Regards, Paul Nash |
From: Donal K. F. <don...@ma...> - 2006-06-01 09:07:13
|
web...@ih... wrote: > I am interested in the dict command. I have been playing around with > similar kinds of structures in various applications, particularly > when generalising protperties of the Tk resource database, and also > html/script option/values and even mapping the resource database into > html/script properties. So I am interested in these dict objects > nested (lets call is a dict-tree) and mapping from one dict-tree to > another. I'm going to repeat this below, but I need you to explain in detail what semantics you are interpreting a 'dict-tree' to have. I know *precisely* what the semantics of dicts themselves are, but some of the things you say about dict-trees confuse me. > The simplest way to deal with dicts is to treat them as functions > over a finite domain similar to arrays. But when the value is itself > a finite function, things get murky. Then we have a dict which maps > onto a crossbreed range - simple values in some cases, and finite > functions in others. This is like having an array as the value of an > array element where other elements have simple values. I have never > seen this construct used in Tcl. It used to be possible to mangle the core so that you could put arrays inside of arrays, but it was a gross hack that was never supposed to work. It was removed in 8.0, according to this 'changes' file entry: 9/17/96 (bug fix) Using "upvar" it was possible to turn an array element into an array itself. Changed to disallow this; it was quirky and didn't really work correctly anyway. (JO) By contrast, dictionaries are purely values, and can indeed be thought of as lists with special conditions imposed (including a set of manipulation functions that don't maintain the order of the elements). As they are purely values, they can be nested arbitrarily (though finitely, since the code doesn't let you build reference loops, but that is a general restriction/property of our copy-on-write reference semantics anyway) and complex trees of dicts are trivial to build. You can even use dicts as keys in other dicts, though I don't know why you'd want to do that given that they're not order-preserving and the key comparisons are conceptually done on the string representation. :-) > This is the area where I have come unstuck. I suspect that these are > two different kinds of object. In other words, you cant just have a > dict within another dict. To handle it properly you have to convert > them to dict-trees. Unary functions in the dict-tree are represented > by a {{} value} pair. These form the leaves of the dict-tree. I don't understand this paragraph. Please explain more. > I would be very interested in working with your tcl implementation of > dict and exploring ideas a bit further. I am interested in isolating > the primitive operations on dict objects and dict-trees. There's five primitive operations on dict objects (which can be considered for this exercise to be general value->value partial function, i.e., if k->v is a member of the dict, there is no k'->v' in the dict where k eq k' and v ne v'). They are: EXISTS: dict * value -> boolean Returns whether the dictionary, D, has any mapping at all for the key, k, i.e. is there any value, v, s.t. k->v is a member of D. LOOKUP: dict * value -> value Returns the value, v, for the key, k, such that the mapping k->v is a member of the dictionary. UPDATE: dict * value * value -> dict Given a dictionary, D, a key, k, and a value, v, returns a dictionary, D', such that the following is true: k->v is a member of D', and for all k' ne k, k'->v' in D <=> k'->v' in D' REMOVE: dict * value -> dict Given a dictionary, D, and a key, k, returns a dictionary, D', such that the following is true: there is no v such that k->v is a member of D', and for all k' ne k, k'->v' in D <=> k'->v' in D' ITERATE: dict -> iterator(value->value) Returns an iterator that lists all the k->v mappings in the dictionary. Order is arbitrary. I suppose you could in theory omit the first two operations for ITERATE, but that'd suck. :-) The other thing to note is that none of the above operations really change a dictionary; they return new ones. *Everything* else is derived from those operations (and the fact that dictionaries are inherently values; it's a full IS_A relationship) plus normal Tcl semantics. There's also a bunch of rules for how to convert between a string representation and a dictionary representation, but they probably don't matter for this discussion. I've yet to completely understand what you regard dict-trees to be. I suspect that you're labouring under the illusion that there is some magical way to determine if a value is a dictionary or not, which there isn't really (just as you can't determine if a value is a list, just if it looks like one, flies like one, and quacks like one). Donal. |