Polymorphic replacement

Is there any language out there that can handle polymorphic replacement? First, to define replacement: If I replace A with B, all references/pointers to A now in fact reference/point to B. In C/C++, this is possible if A and B are the same concrete type. Either A can just be made equivalent to B, or B can be copied over into the same memory location as A. Either way pointers/references will now point to B. But what if B is a subclass of A? It may have added members. So simply assigning A to B won't work. Replacing B in A's space won't work either, because B may not fit, possibly forcing lots of stuff in memory after A to be moved, which would be pretty expensive.

The most obvious solution that comes to mind is copying all of B's parent class members into A's space, and then setting up a pointer to point to where the rest of B's members could be found. There would be some additional memory overhead, because every object would need to have space allocated for this pointer. Member accesses would check if the pointer was not NULL, and if so correctly setup indirect accesses (so there'd also be a slight performance cost when replacement occurred). This also of course introduces fragmentation issues. But the pointer would not have to be used in every case -- only when there was no space after As original spot.

In case anyone is wondering under what context I started thinking about this: language level support for undo. A convenient and easy to setup way of performing undo is to simply make a copy of an object as a backup, manipulate the original, and then if the user clicks cancel, set the original to the backup. This by itself doesn't necessitate replacing -- but it would be convenient for instances where user manipulations entail _creating a new object_. For example, a plot program has the option to plot data in 2D or 3D. Because the rendering of the two is so different and involves caching different data, the 2D plots and 3D plots are separate types that subclass from a master Plot type. When the user opens the plot's properties, they can click a checkbox to change between the 2D and 3D plots. If they switch from say a 2D plot to a 3D plot, assigning the original to the backup won't necessarily work because they may not be the same type anymore. So it'd be nicer if the backup could _replace_ the manipulated original. (This isn't necessarily the best design example, maybe someone can utilize their imagination to come up with a better one...)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


This doesn't seem like as big of a problem as you are making it. The Memento design pattern calls for the originator to be an object which creates its own memento objects as well as taking them back from its caretaker to handle its own rollbacks. An object that handles its own rollbacks may internally keep instances of classes that may need to change, but a memento object would have all the information needed to recreate an object from scratch, and since the originator provides all the means to externally access this object that needs to be of a different class anyway, there is no real hassle doing any necessary rewiring internally. This seems a pretty elegant solution, considering the apparent complexity of the task.

I realize I am sidestepping your question. I apologize. However, languages that support so-called "duck typing," such as Ruby, could fit your description easily, though I am sure it's not the only way.


I'm familiar with Python which is fairly equivalent to Ruby and I don't see how it could solve this problem. I think it'd be _harder_, in that you can't rely on replacing the same area of memory.

Writing code for handling rollbacks is bug prone compared to just making a copy, I wouldn't really consider that a solution. The Memento pattern is going to require you to write a wrapper class that contains references to all of the different types you want it to be able to "become." Continuing the original example it would need to hold a 2D plot and a 3D plot reference. More boilerplate.

Just assign the variable

Just assign the variable containing A with B, and it should just work. I don't see why you need to get into the memory details.

I don't think writing rollback code should count as boilerplate, as there are many ways to go about it. Generate from scratch, store changes only, store entire object heirarchies, etc. Seriously, if you want to implement something like undo, simple object replacement isn't all you have to do anyway.

Regardless, I seem to be misunderstanding the question, so I think I should leave it alone for now.

That's not how assignment works in Python

a = Dog()
b = Cat()
c = b
b = a

The type of c is Cat, not Dog. That's not a replacement. Now that I think about it, I think you could hack it with something like:

for member in dir(b): del member

# syntax probably slightly wrong
for member in dir(a): setattr(b, member, a.member)

The key distinction between replacement and assignment would be that with replacement, all references in the program to original now refer to the replacement. Assignment doesn't do that.

A way to do it in Python

I can think of two basic approaches to the problem in Python, none of which deal gracefully with extention types. Here's one of them:

Look at the built-in gc module, specifically the get_referrers() function. You can use this to get a list of objects which refer to a given object and then make those objects refer to something else. This requires implementing reference replacement explicitly for lists, tuples and dictionaries at the very least. If you end up having to perform a reference replacement within a tuple you have to replace the entire tuple rather than just mutate one of its slots. This requires recursively replacing all references to the old tuple with references to the new tuple.

It's not robust in every possible scenario, but it can be made to work well enough in practice. Using the gc module in this way is of course an ugly and immoral hack but I thought I'd at least bring it to your attention.

The only way to do what you

The only way to do what you want is to add another layer of indirection. One pointer isn't enough. In C++, either you need to use a handle (a pointer to a pointer) explicitly or implicitly (with a smart pointer class). In Python, you need to write a reference object that either explicitly or implicitly (using __getattr__ and __setattr__) redirects attribute access. Actually mutating an object into an arbitrarily different object is possible in some languages (including Python, for most objects), but it's ugly and certainly a case where the cure is worse than the disease.


You might think about immutable datatypes or object prototypes which will never be changed. Instead a mutation creates a new object that refers to the prototype recursively. Therefore all state changes are preserved. If you want to set global checkpoints you might store references to objects in a separate stack. If the user wants to time-travel back to a previous system state ( associated uniquely with pushing a reference on the stack ) you just have to delete all objects which are subsequent to this state.

In message-passing languages...

you could just have the behavior of A change so that all it does is forward any messages sent to it on to A instead. IIRC, Objective-C had this as a system-provided method, something like [A delegateTo: B]. Now since Objective-C wasn't a pure message-passing language, this wouldn't make A completely equivalent to B: since == isnt' a method call, A==B would still be false. Otherwise, it would seem to be basically what you're looking for.

Squeak, Chicken

IIRC, Squeak has this feature, where it is called "become", although I'm having a hard time finding a link. Chicken Scheme has the same functionality under the name object-become!.

"Become" in Smalltalk

'Become' is a fairly essential feature of Smalltalk, which is not Squeak-specific. According to Back to the Future (The Story of Squeak), implementing 'become' in Squeak was more difficult because Squeak didn't have the extra indirection of an object table (which would allow 'become' to be implemented by simply swapping pointers, in effect).

Other tricks

In systems like Squeak where you have an object-based virtual memory, another trick is deferring the pointer replacement inside out-of-core objects until the time when those objects are paged in. When your working set is small compared to the size of the total image this can lead to significant savings: not only does it amortize the cost (a good thing) but the replacement becomes virtually free since you already have the object in the L1 cache when you're paging it in from disk.

Yet another trick is to force a GC whenever you do a "become": the cost of a GC is completely dominated by cache misses and page faults, so while you are traversing the object graph you might as well get your money's worth.

Common Lisp

I think that Common Lisp's objects permit what you want. The relevant line in the specification is

Note that changing the class of an instance may cause slots to be added or deleted. Changing the class of an instance does not change its identity as defined by the eq function.

Here is an example. First define two classes.

CL-USER> (defclass 2d ()
           ((x :accessor x :initarg :x)
            (y :accessor y :initarg :y)))

CL-USER> (defclass 3d (2d)
           ((z :accessor z :initarg :z)))
The 3d class gets its x and y slots by inheritance.

Next define two overwrite methods. They use change-class to adjust the objects prior to copying the data. That way object identity is preserved.

CL-USER> (defmethod overwrite ((to 2d)(from 3d))
           (change-class to '3d 
                         :x (x from)
                         :y (y from)
                         :z (z from)))

CL-USER> (defmethod overwrite ((to 3d)(from 2d))
           (change-class to '2d
                         :x (x from)
                         :y (y from)))
Let us create some original data and some new data, so that we can undo back to the original data.
CL-USER> (defparameter original (list (make-instance '2d :x 1 :y 2)
                                      (make-instance '3d :x 3 :y 4 :z 5)))

CL-USER> (defparameter new (list (make-instance '3d :x 6 :y 7 :z 8)
                                 (make-instance '2d :x 9 :y 10)))
It would be nice to have some funky methods for print-object so that 2d and 3d print very differently.
CL-USER> (defmethod print-object ((o 2d) stream)
           (format stream "[~D,~D]" (x o)(y o)))

CL-USER> (defmethod print-object ((o 3d) stream)
           (format stream "(|~R:~R:~R|)" (x o)(y o)(z o)))
Now we can check that our two variables, original and new, contain suitable test data
CL-USER> original
([1,2] (|three:four:five|))

CL-USER> new
((|six:seven:eight|) [9,10])
that looks OK, but the point of the original question was about getting all the pointers in the data structures in the program to respect the replacement. Let us have a vector containing both our new objects.
CL-USER> (defparameter elsewhere (vector (first new) (second new)))

CL-USER> elsewhere
#((|six:seven:eight|) [9,10])
Now we map our OVERWRITE function over the lists, to change the new objects back to their original values
CL-USER> (mapc (function overwrite) new original)
([1,2] (|three:four:five|))
and, as promised, the pointers coming into the objects from elsewhere respect the change
CL-USER> elsewhere
#([1,2] (|three:four:five|))