To: squeak-dev at lists squeakfoundation org From: Richard A. O'Keefe <ok at cs otago ac nz> Subject: Design Patterns and Collection Classes Date: Thu Aug 29 02:50:01 CEST 2002 "David Griswold" <David.Griswold at acm org> wrote: So if there is any overall message here, it is: be very careful with code in classes like this, and show great restraint by making changes as minimal as possible. The code in Collection is simple, but not simple-minded. Don't underestimate the subtlety of why these simple-seeming methods are the way they are. In another context, Brian Foote and Joseph Yoder wrote [http://www.laputan.org/mud/mud.html capitals are theirs and were links]: ... when you are prototyping a system, you are not usually concerned with how elegant or efficient your code is. You know that you will only use it to prove a concept. Once the prototype is done, the code will be thrown away and written properly. As the time nears to demonstrate the prototype, the temptation to load it with impressive but utterly inefficient realizations of the system's expected eventual functionality can be hard to resist. Sometimes, this strategy can be a bit too successful. ... Does this sound a bit like the history of Smalltalk? It should. A whole new language every two years. A research goal that was not "how do we build ideal collection classes" but "how do we take the idea of object orientation and build a language and system around it that can be understood ("Personal Mastery") and used in powerful ways, how can we develop a whole new approach to programming?" ... Time, or a lack thereof, is frequently the decisive force that drives programmers to write THROWAWAY CODE. Taking the time to write a proper, well thought out, well documented program might take more time than is available to solve a problem, or more time than the problem merits. Often, the programmer will make a frantic dash to construct a minimally functional program, all the while promising him- or herself that a better factored, more elegant version will follow thereafter. They may know full well that building a reusable system will make it easier to solve similar problems in the future, and that a more polished architecture would result in a system that was easier to maintain and extended. Quick-and-dirty coding is often rationalized as being a stopgap measure. All too often, time is never found for this follow-up work. The code languishes, while the program flourishes. THEREFORE [and this is their recommendation], produce, by any means available, simple, expedient, disposable code that adequately addresses just the problem at hand. ... while this approach [that is, the approach used in a particular example, not throwaway code as such] is, in general, a lousy way to address this [particular example's] problem, it is perfectly satisfactory within the confines of the particular purpose for which [it] has ever actually been used. Such practical constraints are typical of THROWAWAY CODE, and are more often than not undocumented. For that matter, everything about THROWAWAY CODE is more often than not undocumented. When documentation exists, it is frequently not current, and often not accurate. Does this sound like #removeAll: and #addAll:? It should! ... [Two example] systems might be good candidates for RECONSTRUCTION, were the resources, interest, and audience present to justify such an undertaking. In the mean time, these [particular] systems, which are still sufficiently well suited to the particular tasks for which they were built, remain in service. Keeping them on the air takes far less energy than rewriting them. They continue to evolve, in a PIECEMEAL fashion, a little at a time. Doesn't this sound like everything about Squeak? From the core classes to Morphic? Isn't piecemeal (community) improvement part of the point of Squeak? So David Griswold claims that the Collection classes are subtle, simple but not simple-minded, and that the methods (including the ones I claim are broken) are the way they are for excellent reason and should not be altered without great [indeed, to my thinking, extreme] restraint, while I claim that the Collection classes are a "Ball of Mud" where most methods are the simplest thing that could possibly work, except they don't. Obviously, eyewitness testimony from the original developers could settle this. Except that it couldn't; it could only tell us how they remember what they thought they were doing. We need some more objective criterion to help us decide what kind of code we are dealing with here. If we are dealing with entire and perfect chrysolite, what we need is documentation. If we are dealing with mud, we need documentation and repairs. So let's look away from #removeAll: and #addAll:. Let's even look away from #union:, #intersection:, and #difference:, enchanting though their perversity may be. ---------------------------------------------------------------- A Design Principle. ---------------------------------------------------------------- Every class should have a class invariant. It does not need to be expressed as code, but it needs to be thought about and written down. Initialisation methods have the obligation of setting up an object's state so that its class invariant is true. Other (externally accessible) methods get to assume that the invariant is true and have the obligation to ensure that it is still true when they complete. If you cannot rely on sufficient knowledge about the object's state at the beginning of a method, the only thing you can do to restore the invariant is reinitialise. If the invariant of a class depends on the state of a mutable object, and that object is accessible outside this class, then you DON'T have an invariant and you cannot expect your methods to work. So the design principle is: a class's invariant should depend only on the values of its instance variables and the states of such objects as are immutable or are not shared with other objects. ---------------------------------------------------------------- The Collection Classes ---------------------------------------------------------------- Do the collection classes heed this warning? Many of them do. OrderedCollection, for example, never hands out its array, and does not provide any non-private methods for changing its instance variables. (At least, by putting methods in the 'private' category it is warning "don't call these lest the heavens fall".) Set, for another example, depends on the exact state of its array, but never hands out access to that array. but it also depends on the state of the elements; it requires that the hash code of an element not change. Oddly enough, it does provide a repair procedure that can be called. You could mutate the elements of a Set, taking care that the Set itself was not used while this was happening, and then invoke the #rehash method. Except that #rehash is private. With the exception of numbers and symbols, there are no immutable values that one might use as keys. There is no equivalent of OPAL's InvariantArray, for example. (I'm trying to write one and it's a nightmare. Array has so many methods that think it's OK to smash, even when they are making copies.) But what about Dictionary? Dictionary cannot make up its mind whether it's about Sets of Associations or keyed collections of values, and tries to be both. Considered as a keyed collection of values, a Dictionary's Associations are part of its private internal structure. Dictionary's invariant concerns the structure of its hash table, which depends on the state of these Associations. Yet it is perfectly happy to hand those Associations out to anyone who asks. Consider d := Dictionary new. d at: #red put: Color red. d associationsDo: [:each | each key: #green]. d inspect ==> (shows #green -> nil) d at: #green ==> (Error: key not found) d at: #red ==> (Error: key not found) Had Dictionary been designed with class invariants in mind, it could still have looked much the way it does now, but the Associations it hands out would be InvariantKeyAssociations, where Association subclass: #InvariantKeyAssociation instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'Collections-Support' "private methods" pvtKey: k value: v key := k. value := v. "accessing methods" key: k self shouldNotImplement "class instance creation methods" key: k value: v ^self new pvtKey: k value: v Except that this won't work; practically the only time I ever really need 'pvt' methods is so that a class can initialise a new instance without the initialisation method being exposed to another class, but the 'pvt' machinery will not let you do this: "private messages may only be sent to self". If only there were a category of private messages that a class could send to 'self new'. So the method really has to be called #privateKey:value: and we just have to hope that no outsider will use it. So much for private methods. It's all very well to say that competent programmers wouldn't even try to change the key of an association that came from a dictionary, but if there are two things that the last fifty years of programming and the recent history of the Internet have taught us, they are - everyone makes mistakes - some people deliberately try to break other people's programs. Oh yes, what if no Association is changed, but a key is? Just like Set, Dictionary could let you make a series of changes to keys (as long as no previously unequal keys became equal) and then repair the state of the dictionary using #rehash, except that #rehash is a private method. (Which means you can do this, but you shouldn't.) #rehash depends on a rather weaker invariant: it requires that keys still be non-nil and unequal, but it doesn't require that their values or hashes be unchanged. Is there another Collection class that exposes its internal structure? Yes, MappedCollection. MappedCollection collection: c map: m in effect constructs the composition of two tabulated functions: (MappedCollection collection: c map: m) at: index = c at: (m at: index) The base collection c and the map m are not copied when you do this. Indeed, that's the point. But it leads to some very odd consequences. For example, i ~= j and: [ (mc at: j) ~= 0 and: [ mc at: i put: 0. mc at: j = 0]] can come out true. For every other keyed collection, setting the element at one key doesn't alter any elements at other keys. So don't try to sort a MappedCollection! It's also the only Collection class I can find in Squeak 3.2 where (coll contents) is not the receiver but a copy with different properties. One of the nasty things about the fact that the collection and mapping are shared with unknown numbers of other objects is that foo: aCollection bar: aBlock |index value| index := aCollection size. value := aBlock value: (aCollection at: index). aCollection at: index put: value may fail, even though aBlock value: ... doesn't send any messages whatsoever to aCollection. How? aBlock could make the mapping smaller, or alter its last element so that it is no longer a valid key for the other collection, or could alter the other collection so that the key disappears, &c. Oh yes, imagine the fun when you do a := #(3 1 4 1) copy. m := MappedCollection collection: a map: a. m ==> a MappedCollection(4 3 1 3) m at: 2 put: 2. m ==> a MappedCollection(1 2 1 2) m at: 3 put: 3 m ==> a MappedCollection(1 2 3 4) a ==> #(2 1 4 3) MappedCollection tacitly assumes that the collection and mapping are different objects or that neither will be changed, but it does not say this anywhere. At the very least the class comment for MappedCollection should be changed from I represent an access mechanism for a sequenceable collection re-ordering or filtering its elements. (which is quite untrue because it doesn't in the least depend on the collections being sequenceable) to I represent the composition of two collection. (MappedCollection collection: c map: m) at: index is always the same as c at: (map at: index). The collection and map could be any combination of sequenceable collections and dictionaries as long as the elements of m all are (and remain) acceptable keys for c. My instances are sequenceable precisely when their maps are sequenceable. If you plan to use #at:put: with one of my instances, the collection c and map m should be different objects. Note that the collection c and map m arenotcopied, but are shared. If you change them, the mapped collection you made from them will also change. Changes to the elements of the collection are normally safe; changes to the key space of the collection or the elements of the map may make the mapped collection invalid. Do not change the map while you are iterating over the map or the mapped collection. Hey, there's another oversight, found while writing that new class comment. There's a missing method: "in category 'testing'" isSequenceable ^map isSequenceable Alternatively, if the (otherwise pointless and unnecessary) restriction to sequenceable collections is to be preserved, then #setCollection:map: should be setCollection: aCollection map: aDictionary self assert: [aCollection isCollection]. self assert: [aDictionary isSequenceable]. domain := aCollection. map := aDictionary except that the names of the method parameters (which I have not changed) strongly suggest that the map should be allowed to be a dictionary, which is not sequenceable. But the instance creation method calls the very same parameter aSequenceableCollection. Whatever this code may be, it is not 'subtle'. It's confused and confusing. Are there any other collection classes that violate this design principle? Yes, there is one that doesn't so much violate it as cut its breast off and eat half of one of its kidneys: LinkedList. Most container libraries regard a linked list as a container for general objects, with the link nodes being part of the private structure of the list. From the outside, it should not matter whether the nodes are allocated one at a time, or in chunks (a good way to combine the flexibility of lists with the space efficiency of arrays is to have a linked collection of arrays; the well known "piece table" representation used in some editors is related to this). However, Smalltalk LinkedLists are very different: all their elements must be Link nodes. This makes them utterly unlike arrays; any number of arrays may refer to the same object as an element, and an array may include an object as element any number of times. Not so LinkedLists: each Link may be an element of at most one LinkedList, and then at most once. In other words, LinkedList does not encapsulate. Serious weirdness can result. Consider c1 add: c2 first. where c1 and c2 are separate collections sharing no objects at all before this message is sent. If c1 is any other kind of collection that can support #add:, this is fine. Now c1 and c2 have a common element. But if c1 and c2 are both LinkedLists, now a node is shared between the two lists. While #add: is defined to be #addLast:, it need not actually true that c2 first is now the last element of c1! (Because c2 might have had more than one element.) I could multiply examples of how easy it is to break LinkedLists without exploiting (initial) aliasing, but the main consequence is that Smalltalk programmers should never ever use LinkedList, not even after making their own subclasses of Link. Arguably, LinkedList should be outside the Collection hierarchy. (As noted in an earlier message, LinkedList is amongst the SequenceableCollections, but does not support #at:, surely a defining characteristic of such collections.) Make no mistake: - I am not saying Smalltalk is unusable. - I am not saying the Collection classes are unusable. - I am not saying that the Smalltalk designers are culpable. What I am saying is that the Smalltalk designers weren't trying to produce highly polished code but were engaged in research of a completely different kind, so that they produced 'good enough for the immediate task' code which after 20-odd years outside the lab is overdue for an overhaul. The Collection classes are a means to an end, not Holy Writ, and mortals may dare to criticise and revise them.