One of Smalltalk’s most unique and powerful features is also one of the least known outside the Smalltalk community. It’s a little method called become: .
What become: does is swap the identities of its receiver and its argument. That is, after
a become: b
all references to the object denoted by a before the call point refer to the object that was denoted by b, and vice versa.
Take a minute to internalize this; you might misunderstand it as something trivial. This is not about swapping two variables - it is literally about one object becoming another. I am not aware of any other language that has this feature. It is a feature of enormous power - and danger.
Consider the task of extending your language to support persistent objects. Say you want to load an object from disk, but don’t want to load all the objects it refers to transitively (otherwise, it’s just plain object deserialization). So you load the object itself, but instead of loading its direct references, you replace them with husk objects.
The husks stand in for the real data on secondary storage. That data is loaded lazily. When you actually need to invoke a method on a husk, its doesNotUnderstand: method loads the corresponding data object from disk (but again, not transitively).
Then, it does a become:, replacing all references to the husk with references to the newly loaded object, and retries the call.
Some persistence engines have done this sort of thing for decades - but they usually relied on low level access to the representation. Become: lets you do this at the source code level.
Now go do this in Java. Or even in another dynamic language. You will recognize that you can do a general form of futures this way, and hence laziness. All without privileged access to the workings of the implementation. It’s also useful for schema evolution - when you add an instance variable to a class, for example. You can “reshape” all the instances as needed.
Of course, you shouldn’t use become: casually. It comes at a cost, which may be prohibitive in many implementations. In early Smalltalks, become: was cheap, because all objects were referenced indirectly by means of an object table. In the absence of an object table, become: traverses the heap in a manner similar to a garbage collector. The more memory you have, the more expensive become: becomes.
Having an object table takes up storage and slows down access; but it does buy you a great deal of flexibility. Hardware support could ease the performance penalty. The advantage is that many hard problems become quite tractable if you are willing to pay the cost of indirection via an object table up front. Remember: every problem in computer science can be solved with extra levels of indirection. Alex Warth has some very interesting work that fits in this category, for example.
Become: has several variations - one way become: changes the identity of an object A to that of another object B, so that references to A now point at B; references to B remain unchanged. It is often useful to do become: in bulk - transmuting the identities of all objects in an array (either unidirectionally or bidirectionally). A group become: which does it magic atomically is great for implementing reflective updates to a system, for example. You can change a whole set of classes and their instances in one go.
You can even conceive of type safe become: . Two way become: is only type safe if the type of A is identical to that of B, but one way become: only requires that the new object be a subtype of the old one.
It may be time to reconsider whether having an object table is actually a good thing.
A place to be (re)educated in Newspeak
Thursday, July 30, 2009
Subscribe to:
Post Comments (Atom)
40 comments:
In the last paragraph, you allude to a type-safe become:. This is in fact monotonic reclassification, or, we we call it in a recent paper, Object Evolution.
Object Evolution can be used by having the object move down the pre-defined inheritance tree (I-Evolution), or by applying a mixin to the object's dynamic type (M-Evolution), or by applying a shakin to same (S-Evolution).
As we show in the paper, Object Evolution using shakins is in fact strong enough to support dynamic aspects, for those of us that believe AOP has merit.
On a related note, the GoF describe the State design pattern as "[allowing] an object to alter its behavior when its internal state changes. The object will appear to change its class". Obviously, reclassification (using become:, or using Object Evolution) renders the pattern obsolete.
Common Lisp has no direct BECOME function, but:
Common Lisp allows you to change the class of an object and it allows you to change objects for class updates (schema changes, etc).
On a class redefinition, existing objects will be updated lazily.
If assigment is harmfull, this is wicked!
In a language like Java, you would use a proxy object instead.
A similar but less, well, crazy model is transparent forwarders, which gives you a proxy that behaves exactly like the object it's pointing to and that only the creator, or whoever the creator decides to pass the capability on to, can update.
Full 'become:' is a more powerful model but sometimes you can have too much power.
Well, it actually makes sense when you think about it!
RT
www.anon-web-tools.tk
I think we can avoid an object table for the sole purpose of become: by replacing the receiver of become: with a forwarding pointer ("broken heart") to the argument. The GC can then resolve this indirection lazily next time it scans the heap. Advantage: no explicit traversal needed, no space for an object table needed.
Perl and python have this to some degree. In both languages you can change the class and property dictionary of an object at any point. I used it in Perl long ago to do exactly the lazy database loading you describe.
The "to some degree" comes from the fact that perl and python both have special data types are different, e.g. in python you could not turn an integer or a string into something else, their __class__ attributes are readonly. In perl its even worse as you have scalars, arrays, hashes etc etc. You can turn one hash based object into another but you could not turn a hash based object into an array based one for example.
Tal: thanks for the pointer to your paper.
michaelw: Yes, you can combine transparent forwarding with GC to implement become: w/o an object table and w/o a full heap scan. It's a nice trade off.
Christian: Nice to hear from you! Forwarding by itself has the downside that these proxies pile up and introduce overhead.
Finally: a common thread in many comments is that changing the class or behavior of an object is possible in many other systems. However, become: is unique, because one can eliminate the overhead of the proxies.
Yes, it seems crazy, but it's all good stuff.
Proxies don't have to pile up. If there's a way for the owner to mark a proxy as frozen when it has been given its final value then the GC is free to replace proxy pointers with direct references and collect the proxy objects.
Gilad said: "a common thread in many comments is that changing the class or behavior of an object is possible in many other systems. However, become: is unique, because one can eliminate the overhead of the proxies."
No, in perl and python there are no proxies, it is exactly as become, just not built in. Here is become in python... bah blogger's comment box destroys my python formatting (which matters for python) so here is a demo of become in python. The only limitation is that you can't swap builtins like integers, floats and strings.
Going way back.
The initial main usage of become: was to allow collection instances to grow when needed. In fact this is the sole usage I can find in the blue book (p 247)
This was necessary to allow Collection classes to use indexed instance variables to reference their elements.
IIRC, some implementations (Smalltalk/V as I recall was one), tended to replace this implementation for many collection classes to use a separate contents array which could simply be replaced and the old one GCed. obviating the need to do the become:
"Remember: every problem in computer science can be solved with extra levels of indirection."
Wasn't it Kevlin Henney who said "except for the problem of too many levels of indirection"?
Fergal: Thanks for the code.
One concern: it is often important that the entire process be atomic. I should write a post on atomic install of reflective changes. With atomic install and the ability to change the class of an individual object , you can implement become: (and vice versa). How useful that is depends on how efficient it is.
Security is another concern: containing this magic power to suspends the natural laws of the universe in a capability is crucial.
Rick: you're right on the history. Of course, this is overkill. Strongtalk is an example where collections were implemented using standard data structures.
Due to python's global lock, become() could be made atomic by implementing it as a function in C.
Anyway, I think anyone using it in python is probably misguided. I suppose it's not so bad if the object you're becoming has never been seen before e.g. you just created it from the DB and call become() immediately.
I've never seen anyone use this technique in python it and anyone I've spoken to has looked at me in horror!
(from Travis Griggs using his wife's account)
Become: does not require an object table. It does require a structured model of memory. VisualAge does not use an object table. I could have sworn, that original versions of Squeak used direct pointers, rather than an Object Table, I have no idea what the current status is. But both still support become:.
It seems many of the comments are confusing the value/use of become: for that of changeClassTo:/adoptInstance:. If I read the responses correctly, it sounds like python and LISP may have these, rather than a become: equivalent.
I try to explain become: as a system wide version of swapping two variables.
it's like
tmp = a;
a = b;
b = tmp;
But applied to your entire memory heap in one atomic go.
Travis,
I'm afraid I don't understand the practical difference between smalltalk's become and the python I wrote. As far as I can tell they are identical for all practical purposes.
In the python every reference to a gets the same class and data as b had and every reference to b gets the same class and data as a had. The effect is global and if I had written it as a C extension it would have been atomic.
That is why c, in my code (which was assigned from a before the become), behaves like b after the become.
It doesn't involve scanning the heap because python effectively has an object table - it just spreads it throughout the heap. Since every object in python is just a struct with 2 mutable entries, class and data, it has the same degree of indirectness. An object has an address and at that address we find pointers to the actual contents of the object. Updating these pointers is exactly equivalent to updating an entry in the smalltalk object table, except that there are 2 pointers to twiddle.
One interesting difference between python or object-table-smalltalk vs heap-scanning-smalltalk is with C extensions. With an object table, as long as the C extensions hold onto the index into the object table, they will also see the effects of become. With heap-scanning you would have to find and update references held in C-structs which seems quite a dangerous operation if you don't have intimate knowledge of those C-structs.
Fergal:
I'd hasten to add that exporting object references to C is problematic regardless of whether you use direct pointers or not, because of GC. So data passed into C should be copied unless it is an immutable value.
Re: garbage collection and C.
Perl has only ref counted garbage collection and the API for dealing with perl data in C respects the ref count. So this should be entirely safe but still has the problems of refcount-only GC.
Python has ref counts but also has a more general GC system that can detect unreferenced circular data. I'm pretty sure it's possible for a C module to hold the sole reference to some python object and not have it prematurely collected by the cycle-detector (otherwise C modules would be essentially unusable). So while I had no clue how, I claim that the orphaned cycle detector will not incorrectly claim data held solely by C extensions.
Shameless plug: My PhD was about improving become: (in a sense). See the software evolution section of my research page, specifically the papers about transmigration of object identity, dynamic object replacement, and the comparand pattern.
Hi Pascal,
Thanks for the pointers.
Altogether, this has been a nice discussion that actually sheds light rather than heat.
I used to have lots of fun evaluating code like: "true become: false", that crashes any Smalltalk VM. Just tested it on latest Squeak, doesn't crash but hangs with 100% CPU usage. Well, hats off to a language that tries so hard to do anything I demand, however absurd. ;-)
Now seriously, the absence of this feature in virtually all languages can be understood as evidence that it didn't stand to the test of time. For tricks like smart replacement of proxies there are modern alternatives, like AOP engines or ad-hoc bytecode transformations, e.g. see what Hibernate does with CGLIB. Yeah these things are harder and less elegant than #become, but that's OK for stuff you only need to do in a few infrastructure/middleware libs. I don't see a case for wide use of #become in app-level code. And when you need it, AOP/etc. are much more powerful.
#become is too expensive even w/o a object table, because you have to force a GC-like scan of the entire live heap. This can be optimized with tricks like type-based seggregation, but you don't want to have the tail wagging the dog - heap management these days is a big issue and I don't want to force some big design option just because #become needs it.
Remember that our heaps are now measured in Gigabytes, and we make tremendous efforts, with sophisticated concurrent / incremental / parallel / realtime collectors, to NEVER do a "full GC" if possible. So, the old argument that you can "just advance the next GC and piggy-back on it" is not valid anymore.
Osvaldo,
Thanks for writing! Of course I completely disagree.
1. Heap scanning is problematic. Yes - thanks for affirming my post, which says : "The more memory you have, the more expensive become: becomes". Did you have something to add? The point is that there are multiple implementation strategies. I suggested object tables, and others have had constructive suggestions, like implementing become: in terms of changing the class of an instance rather than vice versa. This can be done lazily. Each has a place.
2. false become: true. Isn't that the essence of Newspeak? Anyway, again, I'm glad you agree with me - become: "is a feature of enormous power - and danger". You've kindly provided a spectacular example. GIGO - people can do inane things in any language. If you really want to embarrass Smalltalk, do a become: on self.
3. AOP. I have never made it a secret that I don't believe in that stuff. It's been beaten to death in the literature as well. Someday I might be bored enough to discuss it in detail.
Ultimately, I think that elegant solutions are better than clunky ones. We all pay the price for clunkiness in the core infrastructure.
Neal,
1- I want to agree with you, I'm just skeptic... don't know what technique can give us a cheap #become - in particular, zero cost when you don't use the feature. Lazy techniques often demand support from object encoding (header or pointer bits). I would be glad to be proven wrong; but Cohen's paper (section 5) doesn't give any hope if this represents the state of the art.
Perhaps dynamic compilation can help; I can envision a VM that would patch code as necessary to add the overhead in demand and only where necessary (particular objects, classes or vars).
2- Right about GIGO, but do you agree that #become is one feature that makes Smalltalk a non-managed language (IMHO even a type-safe variant would do that)? You could sandbox/manage this feature, but in that case, it would be restricted to core and middleware.
3- I'm also not a fan of AOP :) at least not the whole thing. AOP is being widely used by things like JavaEE app servers, that also adopt other complicated stuff like OSGi microkernels. But I don't see any business app using AOP, not even with very mature tools like AspectJ/AJDT.
Osvaldo,
(1) I can imagine a slightly different lazy implementation scheme than Tal's, to avoid the extra word in the object header (though consider that every nested class in Java carries an extra word, and that is the least of one's worries; of course, we don't do that in Newspeak).
For example, one can change the class pointer of the object, and have the new class methods consult a side table for the new object. When GC does happen, one can clean up.
(2) Of course free access to become: destroys any and all security properties. But so does the ability to modify classes on the fly, and so do many other
things.
In Newspeak, the plan is to control everything via capabilities. These can be fine tuned (e.g, you can reflect on your classes but not mine etc.).
Gilad,
That extra ptr is just for non-static nested classes, and there are even higher costs for full closures; still I was/am a big backer of the BGGA proposal. But normal classes/objects don't have these costs. If we can implement "A #become B" (or anything else) with the same pay-as-you-go philosophy, I'm all for it.
Header rewriting can help. But instead of forwarding, you could use that to trap all attempts to send msgs to A firing a handler that inspects the caller's stack to find the ->A ref and replace it with ->B; so you immediately remove the overhead for that reference. This is easy if stacks are annotated with info to locate the source field/var of each send, at least in the cases where this is not trivial to discover from the send code stream due to optimizations.
Also, thinking again... in incremental heap organizations that never need full GC, like Sun's G1, I guess the problem is much more tractable. You already pay a higher cost of more abundant/precise remsets so you can collect heap blocks individually; so, these remsets serve as a pretty good replacement for ol' good Object Table. I propose the following algorithm:
0) Let H(x) be the heap block containing object x; R(x) the remset for that block; and R->x the entry in that remset pointing to x if that entry exists;
1) If R(A)->A exists, patch R(A)->A so it points to B!
1.1) If H(A) != H(B), the remset must support forwarding to point to another region's remset entry, so this step actually does R(A)->A=>R(B)->B. If this kind of forwarding will complicate the remset structure, just use a separate remset, which is usually empty for all blocks (no pending #become's or other operations requiring forwarding), so the added overhead for normal GC operations remains zero.
2) Force a local-GC of H(A), so all internal references to A are replaced to references to B.
Osvaldo,
Neat! A clever guy can always find a way. You've already found two new ways.
Re: nested classes. Yes, I should have said "inner classes". Of course, static inner classes are an aberration anyway.
Gilad,
Re: nested things, am I the only one who misses Pascal's nested functions/methods? :-)
Tal,
Closures and object literals subsume those nicely,I think.
To whoever bumps into this: 'around' advice and 'become' can be implemented in terms of each other when we focus on function values and assume pointcuts are based on references (as opposed to, say, type signatures).
In essence, 'become' is AOP for dynamic languages. Suggested usage is an entirely different matter.
Check out Leo's post on this at
http://lmeyerov.blogspot.com/2010/01/become-operator-advice-and-javascript.html
I think your demands for typesafety are too stringent. Since a subclass need not duplicate the behavior of the superclass I assume your suggestion is meant to preserve a formal notion of typesafety not some informal attempt to ensure become doesn't screw things up. Of course that demand doesn't really make sense in smalltalk so I'll assume that we've added some kind of limited strong typing to the language. Now your suggestion is surely sufficient for type safety but it is overly restrictive.
Consider the case where B and C are subclasses of A. Now suppose O is an object of class B but all references to O are typed as A references. O could become an object of type C without breaking any type discipline.
One might, for instance, assign each object location a type (in addition to the type of the object at that location) and references to that location could only have types weaker than the location type. Then the object at that location could safely become any other object compatible with the location type.
Not, however, the concern about type safety is not unique to become but arises whenever you dynamically change an objects class. Even simply changing a method's signature by dynamically replacing/overriding the method has the potential to break type guarantees, at least if your type system cares about return/argument types. I don't see any solution but to assign to each cell a type that any object stored in that cell must implement and forcing all refernces not to insist on any more narrow type.
-----
I think someone already pointed this out but a good implementation of become should impose zero cost when unused.
Remember smalltalk is a dynamic language so every method call (and that is all there is) requires we check the type pointer and (if the PIC or other caches don't include an appropriate entry) use the type to resolve the method call. One could easily have a special type that escapes into the runtime on any message at which point the runtime replaces the reference the message call was dispatch on with the new location and retries the call. Indeed, any modern GC has to have some way of doing indirection like this so the heap can be compacted.
Hi TruePath,
your suggestion "Remember smalltalk is a dynamic language so every method call (and that is all there is) requires we check the type pointer and (if the PIC or other caches don't include an appropriate entry) use the type to resolve the method call. One could easily have a special type that escapes into the runtime on any message at which point the runtime replaces the reference the message call was dispatch on with the new location and retries the call. Indeed, any modern GC has to have some way of doing indirection like this so the heap can be compacted." is exactly the approach I need to implement an efficient pinning GC for Squeak. I can do a become on byte data that turns the corpse into an "escape into the run-time" object with a forwarding pointer to the now-pinned copy. Subsequent sends to the corpse will be forwarded to the new copy and, either before or at the next GC all references to the corpse will be replaced/forwarded to the pinned object.
If you feel like discussing this further, please don't hesitate to send me an email (eliot.miranda@gmail.com).
Do you have any references or pointers to implementations on this approach?
thanks again
Eliot
Hi True Path,
damn , I edited too quickly. I had edited out a bit. n Newspeak, yes, all there is is message sends. Alas, in classical Smalltalk there are also direct inst var accesses. So in classical the corpse forwarding technique only works without additional effort on byte data which doesn't contain direct inst vars. Of course one can scan just activations, since these are the only places where such references can exist, but that could be a large search space. Of course, an optimizing Newspeak or Self (or JavaScript) implementation will likely attempt to inline inst var accessors with less overhead than an inline cache test and hence some form of this search may be necessary anyway.
Someone on reddit.com has said that swap(*a,*b) achieves the same thing as a become: b.
What is the difference between the two?
Answering my own question about differences between swap(*a,*b) and a become: b....
become: is used in the MessageCapture class which I use to create animations of arrays.
MessageCapture interceptFrom: anObject forwardTo: aReceivingObject
In my case, I created a visualization object that will take messages sent to any array and illustrate what happens to a normal array. In principle, you could work with any array used in any aspect of Squeak to show what is going on live during, say, some kind of IPC using sockets.
More generically, you could animate the activity of nearly ANY object type in squeak, using the same general strategy. Doing this with C++ would be rather more difficult, because you can't do swap() on an instance of an array and an instance of a window.
http://www.youtube.com/watch?v=QAA0mGRAQwY&list=PL6601A198DF14788D&index=49&feature=plpp_video
I'm amazed that this thread has woken up. I don't know who is listening but a few comments on old posts.
Kerrin said...
"Become: does not require an object table. It does require a structured model of memory. VisualAge does not use an object table. I could have sworn, that original versions of Squeak used direct pointers, rather than an Object Table, I have no idea what the current status is. But both still support become:"
I believe that object table implementations fell out of favor by the time most commercial Smalltalk implementations came out. I don't know how long ParcPlace continued to use it, I'm pretty sure Smalltalk/V used direct pointers from the get go, as did the OTI provided VM for VisualAge. Probably the same holds for Squeak.
Implementations with a direct pointer object model tend to use one way become. Also since those pointers tend to point to an object header, things like flag bits can be used to lazily forward/swap references.
Then Eliot Miranda said...
"Newspeak, yes, all there is is message sends. Alas, in classical Smalltalk there are also direct inst var accesses."
Smalltalk is dynamically typed on the outside of objects, but strongly typed on the inside, in that methods are compiled knowing the layout of instances. When you change the list of instance variables in a class, all of the methods of that class and any of it's subclasses need to be recompiled.
I remember that one of Dave Ungar's favorite pastimes was to crash different Smalltalk implementations by adding an instance variable to Object.
Newspeak, like Self, dynamically binds instance variable names.
The same goes for Ruby, which doesn't have static declarations of instance variables, each instance acquires instance variables dynamically as the are referenced in executed methods. The original MRI implementation of Ruby used a Hash (Dictionary in Smalltalk lingo) in each object to map IV names to values. Later implementations have made various speed/space tradeoffs, but the semantics remain unchanged. This was one of the differences between Smalltalk and Ruby which posed a challenge to the MagLev team.
I'm amazed that this thread has woken up. I don't know who is listening but a few comments on old posts.
Kerrin said...
"Become: does not require an object table. It does require a structured model of memory. VisualAge does not use an object table. I could have sworn, that original versions of Squeak used direct pointers, rather than an Object Table, I have no idea what the current status is. But both still support become:"
I believe that object table implementations fell out of favor by the time most commercial Smalltalk implementations came out. I don't know how long ParcPlace continued to use it, I'm pretty sure Smalltalk/V used direct pointers from the get go, as did the OTI provided VM for VisualAge. Probably the same holds for Squeak.
Implementations with a direct pointer object model tend to use one way become. Also since those pointers tend to point to an object header, things like flag bits can be used to lazily forward/swap references.
Then Eliot Miranda said...
"Newspeak, yes, all there is is message sends. Alas, in classical Smalltalk there are also direct inst var accesses."
Smalltalk is dynamically typed on the outside of objects, but strongly typed on the inside, in that methods are compiled knowing the layout of instances. When you change the list of instance variables in a class, all of the methods of that class and any of it's subclasses need to be recompiled.
I remember that one of Dave Ungar's favorite pastimes was to crash different Smalltalk implementations by adding an instance variable to Object.
Newspeak, like Self, dynamically binds instance variable names.
The same goes for Ruby, which doesn't have static declarations of instance variables, each instance acquires instance variables dynamically as the are referenced in executed methods. The original MRI implementation of Ruby used a Hash (Dictionary in Smalltalk lingo) in each object to map IV names to values. Later implementations have made various speed/space tradeoffs, but the semantics remain unchanged. This was one of the differences between Smalltalk and Ruby which posed a challenge to the MagLev team.
Rick:
Good comments.
One difference between Newspeak and Ruby is that typos do not introduce variables. Another is that instance variables can be replaced by methods etc. So the late binding in the two languages is not at all the same.
Lawson: Re pointer swapping: as noted, the (quasi)-strong typing of C++ gets in the way. This makes sense, because of the problem of what happens when the sizes of the objects differ - you may be treading on other memory.
Osvaldo:
You don't HAVE to do a whole-heap scan, though. If your system supports transparent forwarding, it needs to do a check on every* message send anyway. If that system is good, it's optimizing so that the check is cheap if there's no forwarding to be done. If there is forwarding, cheap #become: semantics can be achieved by implementing the message-forwarding as changing the source pointer inline and retrying the message send. That will even free reference-counted forwarded objects eventually.
*for given values of every that don't include things like JIT devirtualizations known to be safe even in the presence of multi-threaded code, etc.
Post a Comment