Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm developing a GUI application, heavily working with graphics - you can think about it as a vector editor, for the sake of the example. It is very tempting to make all data structures immutable - so I could get undo/redo, copy/paste, and many other things almost without effort.

Fot the sake of simplicity, I will use the following example - application is used to edit polygonal shapes, so I have "Polygon" object, which is simply list of immutable points:

Scene -> Polygon -> Point

And so I have only one mutable variable in my program - the one which holds current Scene object. The problem which I have starts when I try to implement point dragging - in mutable version, I simply grab a Point object and start modifying its coordinates. In immutable version - I am stuck. I could have stored indices of Polygon in current Scene, index of dragged point in Polygon, and replace it every time. But this approach does not scale - when composition levels go to 5 and further, boilerplate would become unbearable.

I'm sure this problem can be solved - after all, there is Haskell with completely immutable structures and IO monad. But I just cannot find how.

Can you give me a hint?

share|improve this question
    
@Job - that is how it works right now, and it gives me many pains. So I am looking for alternative approaches - and immutability seems perfect for this application structure, at least before we add user interaction to it :) –  Rogach Dec 7 '11 at 3:36
    
@Rogach: Can you explain more about your boilerplate code? –  rwong Dec 7 '11 at 6:07
add comment

2 Answers

up vote 9 down vote accepted

I have worked on exactly the same problem (but only with 3 composition levels). The basic idea is to clone, then modify. In immutable programming style, the cloning and modification has to happen together, which becomes command object.

Note that in mutable programming style, cloning would have been necessary anyway:

  • To allow undo/redo
  • The display system may need to simultaneously display the "before edit" and "during edit" model, overlapped (as ghost lines), so that the user can see the changes.

In mutable programming style,

  • The existing structure is deep-cloned
  • The changes are made in the cloned copy
  • The display engine is told to render the old structure in ghost-lines, and the cloned/modified structure in color.

In immutable programming style,

  • Each user action that results in data modification is mapped to a sequence of "commands".
  • A command object encapsulates exactly what modification is to be applied, and a reference to the original structure.
    • In my case, my command object only remembers the point index that needs to be changed, and the new coordinates. (i.e. very lightweight, as I'm not strictly following immutable style.)
  • When a command object is executed, it creates a modified deep-copy of the structure, making the modification permanent in the new copy.
  • As user makes more edits, more command objects will be created.
share|improve this answer
add comment

Deeply-immutable objects have the advantage that deep-cloning something simply requires copying a reference. They have the disadvantage that making even a small change to a deeply-nested object requires constructing a new instance of every object within which it is nested. Mutable objects have the advantage that changing an object is easy--just do it--but deep-cloning an object requires constructing a new object which contains a deep clone of every nested object. Worse, if one wants to clone an object and make a change, clone that object, make another change, etc. then no matter how big or small the changes are one has to keep a copy of the entire hierarchy for every saved version of the object's state. Nasty.

An approach that might be worth considering would be to define an abstract "maybeMutable" type with mutable and deeply-immutable derivative types. All such types would feature an AsImmutable method; calling that method on a deeply-immutable instance of an object would simply return that instance. Calling it on a mutable instance would return a deeply-immutable instance whose properties were deeply-immutable snapshots of their equivalents in the original. Immutable types with mutable equivalents would sport an AsMutable method, which would construct a mutable instance whose properties matched those of the original.

Changing a nested object in a deeply-immutable object would require first replacing the outer immutable object with a mutable one, then replacing the property containing the thing to be changed with a mutable one, etc. but making repeated changes to the same aspect of the overall object would not require making any additional objects until such time as an attempt was made to call AsImmutable on a mutable object (which would leave the mutable objects mutable, but return immutable objects holding the same data).

As simple but significant optimizations, each mutable object could hold a cached reference to an object of its associated immutable type, and each immutable type should cache its GetHashCode value. When calling AsImmutable on a mutable object, before returning a new immutable object, check it would match the cached reference. If so, return the cached reference (abandoning the new immutable object). Otherwise update the cached reference to hold the new object and return that. If this is done, repeated calls to AsImmutable without any intervening mutations will yield the same object references. Even if one doesn't save the cost of constructing the new instances, one will avoid the memory cost of keeping them. Further, equality comparisons between the immutable objects may be greatly expedited if in most cases the items being compared are reference-equal or have different hash codes.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.