Mutable Tcl objects

What is a mutable object ?

In the context of Tcl objects I am going to define a mutable object as being one which you can change even while it is shared. The standard Tcl object types are not mutable because they use copy-on-write semantics. This requires that a shared object must not be modified, instead a copy of it is taken which is modified instead.

While copy-on-write allows enormous benefits in terms of performance and memory usage over using strings it does have one big limitation which is its inability to efficiently create and manipulate container objects and more complicated data structures built on top of them.

Take for instance a tree structure built using a Tcl list which has the following format.

name	Description
name	Name of node.
left	Left node (optional).
right	Right node (optional).

So to encode the following tree

     +
  *     5
2   3

you would do

set tree [list + [list * [list 2] [list 3]] [list 5]]

If I wanted to change the left node of the tree so it looked like:

     +
  -     5
2   3

I would have to do something like:

set tree [lreplace $tree 1 1 [list - [list 2] [list 3]]]

In other words I have to make a new copy of the list which has been slightly modified. In this case it is rather trivial but it very quickly gets very complicated and inefficient, especially when you consider that most of the old copies would be thrown away anyway.

Contrast this with the following pseudo code

# Create a tree made up of node objects.
set tree [node create + [node create - 2 3] [node create 5]]

# Change the 'name' of the left node of the tree to -.
node set [node get $tree left] name -

which requires no copying and is therefore much faster and efficient.

How do I implement a mutable object type ?

The problem with doing this is that Tcl objects are designed to support copy-on-write semantics and therefore you have to be very careful what you do.

The major rule that you must not break when it comes to shared objects is that you must not change the string representation. You can change the internal representation as much as you like, convert it to other types but the string representation is invariant.

As a mutable object's internal representation can be changed even when the object is shared there cannot be a direct relationship between that and the string representation; otherwise we would violate the above rule; by direct I mean using only the contents of the string representation and not using some sort of context to map from the string representation to the internal representation.

It would be nice if we could ignore the mapping from string representation to a mutable object's internal representation but too much of Tcl still works on string representations only.

The solution is to treat the string representation as an opaque representation; or in other words a handle. (All mutable objects need to be opaque but not all opaque objects are mutable.) However unlike other handles in Tcl such as for a channel, or an interpreter the handle should not have to be freed explicitly, rather it should be freed when the internal representation is freed. The extra code necessary to track and free all of the handles explicitly would make the objects almost unusable. Therefore the mapping must only exist for as long as the internal representation exists.

This can however cause problems, take the following code:

% button .b -label button -command [list foo [list 1 2 3]]
.b
% .b cget -command
foo {1 2 3}

The -command option does not support Tcl objects, instead it works with strings. In the above code it takes a copy of the list object's string representation and when the [button] command returns the list objects are freed because there are no other references to them. In this case this is not a problem because if foo treats its argument as a list the internal representation of the list can be recreated directly from the string representation. Obviously it is less efficient than if the Tcl object was used but at least the program still works as expected.

However if an opaque object (with no other references) was used instead of [list 1 2 3] then the program would not work because the destruction of the object would remove the mapping from the string representation to the internal representation.

The only way to prevent this from happening is to create another reference to the opaque object so that neither the object nor the internal representation is freed. This can be done either by storing a reference in a variable or by explicitly increasing the reference count. Obviously this extra reference would need to be explicitly cleaned up when the object was no longer required.

Ideally an opaque object's should have a totally unique string representation; that is it should not be the same as any other object's in the current process; to eliminate any possibility of the wrong object being found when looking up a handle. Obviously this cannot be achieved in general but the chances of it accidentally matching another string should be reduced by choosing a format which is not likely to be replicated. However every opaque object can and should have a different string representation from every other opaque object.

Opaque objects have to be explicitly created, as conversion from another type would also require modification of the string representation which is not allowed.

Similarly opaque object's string representations have no real meaning except as a handle for the object so should not be converted to another type. However it is not possible to enforce this as it requires the cooperation of the other types.

Care must be taken when using mutable objects as it is possible to create self referential structures which can not be cleaned up properly by using reference counts. As Tcl does not support garbage collection applications will have to be very careful to clean up after themselves.

[email protected]