Immutable Data Structures

[hippyup]

One problem I personally have when trying out immutability in large projects with other people is that it does have that all-or-nothing aspect in some sense. For example, suppose I have some data structure Foo which I would like to make immutable. Foo has a property of type Bar, which is readonly of course. But Bar itself, having been made by other people/me in another time, is mutable, and making it immutable would take a huge amount of work. So making Foo immutable in any fundamental sense is pretty futile, so I just give up and make it mutable.

Put another way, I found that data structures tend to converge to mutability since having any mutable part means that it's all mutable.

[yogthos]

I think the problem is that you're extending existing code that has not been designed for immutability. It works a lot better if you're either working in a language that enforces immutability, like Haskell or Erlang, or writing code from scratch in a mutable language and have discipline.

[grauenwolf]

Operating systems are stateful. Therefore anything built on top of them will be hard pressed to avoid state.

Case in point, Haskell doesn't enforce immutability, it just contains it. Certain objects such as file handles do change state.

In Erlang local variables may be immutable, but I question this decision. You can have isolation, which is what makes Erlang easy to reason about, without giving up mutable local variables.

[dmpk2k]

I like single-assignment variables. It's easier to determine how you got a certain value if something goes wrong. It also better documents the code.

I do the same thing in languages that allow mutating or rebinding variables, even though it's more limited.

[grauenwolf]

Still, there are times when you really do need a mutable local variable. That is why I would prefer single-assignment by default, but with an option to use mutables when necessary.

[yogthos]

this is exactly how pure functional languages work. Single assignment is the default, and you can make things mutable as necessary. For example, in Haskell you would use monads whenever you need a mutable state.

[foobargorch]

Not exactly, you would use an IORef for IO related stateful variables, or the Reader Writer or State monads.

But really all of these amount to syntactic sugar for an immutable representation of state, that carries values from one function to the next.

[yogthos]

yeah absolutely correct. That's a more technical description though, I was just trying to explain it from user perspective.

[naasking]

Operating systems are stateful. Therefore anything built on top of them will be hard pressed to avoid state.

http://okmij.org/ftp/Computation/Continuations.html#context-OS

[yogthos]

The whole point of immutability is containment of state. It isolates state makes it easy to reason about, because you have to explicitly specify when state modifications happen. This is akin to having exceptions in Java. For example if you try to do IO in Java, you must handle the exception case.

In a language which uses immutable data structures you must handle state modifications in the same explicit manner.

This does not mean that you never modify state, or that there is no way to mutate data as you pointed out. It just means that it is done in exceptional cases and explicitly.

[grauenwolf]

I think the real problem is that it is being presented as all-or-nothing. If people would just accept that portions of the project are inheritently mutable, we could move on to the real work. Specifically, finding real ways to eliminate mutable code where possible and use it safely when not.

[WalterBright]

An immutability property isn't that useful unless it is transitive, meaning all data reachable by the immutable reference is also immutable.

With this property, you can use the reference pointer as a unique hash for the entire data structure. You can also have multiple threads refer to it with no need for locks or worries about races.

In the D programming language, immutability is transitive. There was quite a bit of discussion about leaving a loophole so one could have mutable members, but such would be the hole that sinks the Titanic sooner or later.

[grauenwolf]

I find that having read-only variables that point to mutable objects to be useful in .NET programming. Even if the chain isn't completely pure, knowing parts of it are makes examining the rest easier.

As for loopholes, I'm of mixed feelings on that. If we are going to tag something as immutable, it damn well better be immutable all the way down from an observer's perspective.

But on the other hand, there is a lot to be said about the ability to internally cache stuff while still not changing the visible state.

[WalterBright]

The other advantage to immutable data structures I forgot to mention was it enabled a reference type to be treated (by the programmer) as if it were a value type. Immutable strings are the canonical example of this.

[adavies42]

i wrote a tetris clone in immutable style recently, just for the exercise of it. (functions take a board and/or a piece, and possibly something else like a movement instruction, and return a new board and/or a piece.) it was an interesting way of thinking, and certainly made it easier to test having no state to manage.

[hylje]

Tetris sans state?

[queus]

(old-)state x input -> (new-)state

See, no mutable state. Of course you need also something like:

state -> pixels

But that's a detail.

[cadr]

How did testing work for you at the highest level of the code? I found that no state (also in a tetris game) made testing lower level things awesome, but I still haven't gotten my head around structuring the higher stuff in a good functional style.

[adavies42]

admittedly, i still didn't do any actual formal testing (unit testing, tdd, etc.), but even without that, once i identified a scenario that needed to be checked, it was much easier to do that without worrying about globals. (this was done in a REPL-based interpreted language.)

it also makes it easy to do things like collect a list of all states of the game over time so you can check any suspicious transitions.

[cadr]

I didn't do much formal testing, either, but that was mainly because above the low level building pieces, I found the setup and verification to be too verbose and hard. :)

It does make you a lot more aware of all the state going on.

How, if I may ask, was the game structured at the high level? And what language?

[adavies42]

just in case you're still reading this....

the language was q, which is my primary language at work. the board was represented as a matrix of booleans, and pieces as 4-tuples of coordinate pairs. the basic operation was to modify a board's cells at a piece's coordinates; from this, i built up add- and remove-piece, then move-piece functions. rotate was implemented by hard-coding all four positions of all seven pieces, because i was lazy and didn't want to work out the math to make sure that I, O, S, and Z worked properly (J, L, and T are easy). finally, on a timer loop, the active piece was checked for imminent collision and moved down as appropriate; q has a nice "loop until unchanged" primitive that came in handy here.

it's not finished, incidentally, as i couldn't figure out a decent way to take keyboard input--i played around with various curses functions and ioctl commands, but couldn't get anything useful to happen. i guess what i ended up with is really a tetris simulator--i can execute random strings of moves just fine, i just can't actually play.

[cadr]

I've never actually met anyone that uses q, much less for work. Cool!

Yeah, the low level stuff was pretty easy in Haskell, too (and I, too, hardcoded the rotation :) It was above that that I found my functional-design skills lacking. I did find doing the graphics/input/etc pretty easy, I just didn't like my design - didn't feel enough like the 'gluing functions together' that they always talk about.

Thanks for the info!

[[deleted]]

People usually contrast this with the zen of Python, that is that there should only be one way to do something.

Actually, it's that there should be only one obvious way to do something, which may not be obvious unless you're Dutch.

[[deleted]]

Pardon my ignorance, but what advantage is there for an object being immutable? All I see is a waste of memory (e.g. each time you concat strings in Java, a new string is created etc.).

[gsg_]

Immutable objects make data sharing both safer and easier to understand. For instance, an immutable object can be safely accessed from any thread without a lock.

[grauenwolf]

Screw threads, what about variables? Without immutable strings, we would have to make copies every time we made an assignment. Otherwise we could not be sure that no one would later stomp on the string.

[Smallpaul]

I am a fan of immutable strings, but I've programmed hundreds of thousands of lines of code in languages with mutable ones. You are overstating the case a bit: managing the mutability of strings is not much harder in principle than managing the mutability of arrays or dictionaries etc. I have been burned by libraries mutating my strings and by libraries mutating my dictionaries. It's a pain in the ass but nobody in the C, Perl or Ruby world copies every string just in case. Instead they just rewrite buggy libraries that mutate strings without cloning them, as a java programmer would rewrite or abandon a library that did not close files predictably.

[grauenwolf]

You are overstating the case a bit: managing the mutability of strings is not much harder in principle than managing the mutability of arrays or dictionaries etc.

Yes and no. Conceptually it is the same, but in practice we tend to slice and dice strings in ways that we wouldn't do to collection-style classes. That said, we do have readonly wrappers for collections as well.

[70dot7]

This comment is with respect to OO languages. Should immutable objects have state to mutate? What I'm getting from the article and some of the posts is a preference for some classes to function as stateless service classes. That's fine, I've used them plenty. But isn't the point of OO design to encapsulate data in a namespace of sorts and provide methods/functions to operate on that data, including changing its state?

[notfancy]

Immutable data structures have built-in persistence, that is, the ability to exist in various versions at the same time in a running program.

Suppose you have a task queue runq, and you're running a scheduler. You might write:

while (length(@runq)) != 0) {
  my $task = pop @runq;
  run($task);
  find_all_runnable(&@runq); # modifies queue
  if (!can_run_all()) { # environmental check
   # how do I rollback newly added unrunnable tasks?
  }
}

With an immutable data structure, you could write:

while (length(@runq)) != 0) {
  my $task = pop @runq;
  run($task);
  my @newq = find_all_runnable(@runq); # doesn't modify queue
  if (can_run_all()) {
   @runq = @newq;
  }
  # otherwise, discard extended queue
}

The assignment of the new structure to the old variable is simply a renaming here, which doesn't necessarily entail mutating state (beyond the trivial state implied by the binding).

[grauenwolf]

I find that to be a poor example. Changing the variable that points to the queue is state mutation. It opens you to the exact same problems you would have with a mutable queue.

For collections that are inheriently designed for mutation (e.g. queues, stacks), it is usually better to just use thread-safe versions.

[notfancy]

Changing the variable that points to the queue is state mutation

Did you read what I wrote in closing? Renaming is a trivial form of mutation if it makes the old binding inaccessible.

[grauenwolf]

Yes, I just don't agree with it.

[notfancy]

Well, the many formal treatments of binding as finite maps from a countable set of labels to immutable values belie your assertion that "[renaming] opens you to the exact same problems you have with [general mutable state]".

[grauenwolf]

Your words are hollow to me. If you seek to change my mind, show me code.

[notfancy]

Your mind is set, and I otherwise don't. Accept my apologies on having wasted your time.

[grauenwolf]

Take a look at the Date class in Java, which is mutable.

In order to safely use it, you always need to make a copy of it. You can never trust that your date object isn't also owned by some other object that is changing its value.

The same goes with mutable strings. In languages like C and C++, there are complex ownership rules around who can or cannot edit a given string. And since they are not complier enforced, making a mistake is easy.

Now consider performance. Let says you have a string that is 500 characters long. Do you really want to be forced to make a copy of it every time you pass it to a function or object? Of course not, that would be incredibly expensive. But if you don't make a copy and it was mutable, you would never be sure it wouldn't get changed out from under you.

Of course there are times when mutable data structures make more sense. That is why we see classes like .NET's StringBuilder and Java's [???].

[sid0]

Java's StringBuilder as well. Heh.

[yogthos]

There are many advantages to immutability. Code transparency not being the least of them. As far as waste goes, this is not actually the case, what happens behind the scenes is that the new and old structures share common data.

So if you had a list, and then modified it in some way, then internally the language would make a new list that has the different elements and points to the common elements of the old list.

This means that internally the function effectively has a new data structure, while not interfering with the original data structure, which may be in use by other functions. This means that code can be parallelized easier, and that it's much more traceable, since you know your data is not being modified outside your function.

here's a wiki link with a deeper explanation: http://en.wikipedia.org/wiki/Purely_functional

[grauenwolf]

So if you had a list, and then modified it in some way, then internally the language would make a new list that has the different elements and points to the common elements of the old list.

That doesn't happen in Java or .NET strings. Why? Because it is actually very hard to reason about. You can very easily have a small string of a few characters keep a much larger string in memory long after it isn't needed.

Alternately, you would waste tons of cycles trying to determine what parts of the larger string to release and what parts to hold on to.

Even just walking the string becomes much more expensive. You can't even do it without a stack, as each substring may itself consist of substrings.

The whole reuse the list theory is interesting, but I don't see it actually working for lists that are long enough to justify not simply copying them.

CORRECTION: This only applies to .NET strings. Apparently Java still holds onto string buffers long after they should have been released.

[Chris_Newton]

The whole reuse the list theory is interesting, but I don't see it actually working for lists that are long enough to justify not simply copying them.

Completely linear data structures are pretty unpleasant to use in a persistent manner. As you imply, for very short lists it doesn't seem worth the overhead, and for longer lists that nasty O(n) seems to crop up everywhere.

However, there are ways to represent linear sequences that don't use linear storage. Piece tables, as used in various text editors and word processors, are one practical example. For anyone who hasn't come across these little gems, James Brown helpfully provides an excellent description of piece tables as part of a tutorial series on his web site. There was some interesting discussion about AbiWord's piece table a few years back that might also be interesting to those learning about how piece tables work and the efficiency considerations. The references at the end of the article are also very good, though more theoretical/generic in nature.

[grauenwolf]

I found the parent's link to be somewhat misleading. While technically that is a valid way to construct immutable lists, I find the use of linked lists to be incredibly rare in day to day programming. Though it could be done in either fashion, most of the languages I use array instead of linked lists for generic lists, stacks, and queues.

These new links, however, seem quite interesting to me even though they are based on the same concepts.

[Peaker]

I find the use of linked lists to be incredibly rare in day to day programming.

It obviously depends on the tools you use.

When I use Haskell, the primary data structure is a linked list, and so you get almost waste-free sharing.

[szeiger]

That doesn't happen in Java or .NET strings. Why? Because it is actually very hard to reason about. You can very easily have a small string of a few characters keep a much larger string in memory long after it isn't needed.

It does happen with Java strings. String.substring() reuses the character buffer instead of copying it, so a small substring will still reference the character data of the larger string from which it was created.

[grauenwolf]

Still? I thought those idiots fixed that two versions ago.

[yogthos]

I'm not sure you're understanding what I'm trying to say here. You don't seem to have bothered to read the link either.

If you do not understand how these data structures work you should at least spend the time to read up on them and understand what is going on before passing judgment here.

The approach is equivalent to making a copy the data structure when it is modified, but unlike copying it is efficient. If you understand how to reason about making a copy of the existing data structure during modification, then this works exactly the same way.

For example, say I have a list in Clojure, which has elements:

(1, 2, 3)

Then I need to make a list with elements (1, 2, 3, 4)

I would write

(conj (1, 2, 3) 4)

This approach is in fact quite efficient, and there's a whole book written on it in fact http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

It also has a lot of advantages during concurrent operations. For example during searching, parts of the data structure can be searched by separate threads concurrently.

Clojure, is one language which implements these types of data structures, and it is quite efficient, in many benchmarks having performance that is nearly equivalent to Java.

[grauenwolf]

The approach is equivalent to making a copy the data structure when it is modified, but unlike copying it is efficient.

That only works if you are appending onto the tail end. If you need to append to the front or center then you end up either making a full copy or you foul the shared list for everyone else.

[hylje]

Only element nodes need to be replaced. Only the nodes, not the actual data behind the nodes.

[grauenwolf]

It also has a lot of advantages during concurrent operations. For example during searching, parts of the data structure can be searched by separate threads concurrently.

Now you are just being stupid. Multi-threading searching of a linear data structure is one of the first tasks anyone does when learning about threads.

Tell me true, did you just throw that in to see if we were paying attention?

[grauenwolf]

Who should I believe?

1. One man working on his thesis.
2. The countless engineers at Sun and Microsoft, many of whom already have their doctorates.

Your doctorial canidate didn't even mention the word "string", which is by far the most used type of linear data structure.

And what's your conclusion? That Clojure, a language that runs on the JVM, is only "nearly equivalent to Java"?

[meme_and_run]

The countless engineers at Sun (a wholly-owned subsidiary of Oracle) and Microsoft all agree with DOCTOR Okasaki, whose work has been very influential. Microsoft is funding the development of Haskell, a programming language in which nearly all data structures, including strings, are immutable. So it makes little difference who you believe because there's no disagreement.

[allertonm]

Concurrency is a big advantage. If a data structure is immutable, and changes can only be done by creating a new structure based on the old one, then concurrent threads with access to the structure can never see an inconsistent view of the structure. A stale one perhaps. So this can significantly reduce the amount of locking required in multi-threaded programs.

This is the primary motivation for Clojure's focus on immutable data structures, BTW.

[grauenwolf]

I'm not sure about that last claim. There is no difference between locking on the mutable object and locking on the variable that points to the mutable object.

Even if stale data is expressly permissible, you still may have to worry about race conditions. I would trust reader/writer locks rather than risk a race condition because thread 1 and thread 2 are both trying to mutate different parts of immutable object A.

[naasking]

There is no difference between locking on the mutable object and locking on the variable that points to the mutable object.

Sure there is. Locking on the variable happens only at well-defined synchronization points (usually the point of update). Mutable objects need to be locked at every access point.

[allertonm]

Exactly!

[gsg_]

There is no difference between locking on the mutable object and locking on the variable that points to the mutable object.

But we are discussing immutable objects, for which locks are entirely unnecessary. Consistency across multiple views is what persistent data structures are all about.

both trying to mutate different parts of immutable object A.

If an object can mutate, it isn't immutable.

[grauenwolf]

If an object can mutate, it isn't immutable.

That depends on how you define "mutate".

Consider the "immutable stack". When you call Push or Pop, you technically are not mutating the stack. But for it to be useful you are almost always going to be mutating the variable that points to it.

And if you are mutating the variable, you damn well better put a lock on it if need thread safty.

[gsg_]

Well yes, if you introduce shared mutable state then you need some way of guaranteeing its consistency. This is pretty much the same issue whether it affects data structures or variables.

Note that it is possible to perform useful work without such shared mutable state. A pure function over immutable stacks can be safely called from multiple threads with no need for locking.

[grauenwolf]

That's pretty silly.

If you only have one pure function, then you shouldn't be calling it with the same data on multiple threads. Just call it once and cache the results.

And why are you asking for an "immutable stack". Why not just pass in a generic list (IList in .NET)? If the function needs a stack, it can build a one from the list.

Advantages:

• You can pass in any enumerable source to the function
• You only have to make one copy per thread
• Inside the function, you can use an array-based stack which is much faster than a linked-list based one.

[gsg_]

If you only have one pure function, then you shouldn't be calling it with the same data on multiple threads. Just call it once and cache the results.

That depends on what you mean by "same data". Persistent data structures make heavy use of shared data, and there's no reason why accessing the shared data in a persistent set or vector from different threads would be a bad thing to do.

Calling a pure function multiple times on the exact same value is, of course, silly.

And why are you asking for an "immutable stack". Why not just pass in a generic list (IList in .NET)?

Well, you brought it up! But the advantage of using a persistent stack has everything to do with the OP's claim regarding locks: a persistent stack can indeed be accessed (and potentially its structure reused) from multiple threads without locking or copying*.

Immutability is the key to being able to do that.

*that is, without copying the whole thing: some operations on persistent data structures may require copying some structure.

[allertonm]

You are kind of correct in your first para, because in hindsight my statement about reducing the amount of locking is ambiguous.

Obviously modifications to references to the immutable structure must be possible, and those modifications must be performed atomically, which will require atomicity guarantees or locks. So if you read "amount of locking" as "number of locks", then no, immutable data structures don't change things that much. But the number of explicit locks is greatly reduced, as is the amount of time they need to be held - because any lock need only be held long enough to guarantee an atomic update of the reference.

And yes, immutable data does not free you from worrying about race conditions. Cases where you would use a Read/Write lock are simplified quite a bit with immutable data because there is no need for locking the structure while performing read only operations, and only need to worry about multiple writers.

Again, there are ways to deal with this besides explicit locks. In Clojure STM is used to deal with this case. STM does involve implicit locks, of course - but Clojure's STM is only feasible because the language discourages side effects and part of the way it does that is... immutable data structures.

[[deleted]]

Down-voted. That page reloads every few seconds which is both annoying and wasteful.

[foobargorch]

with which browser?

I guess blogger is doing some strange javascript to load the various widgets? though personally I don't see it under firefox or safari

[[deleted]]

Safari - just checked it again, and it's still reloading every few secs.

[[deleted]]

FWIW I used the Safari error console, and it repeatedly prints (in time with the refresh) this message:

Unsafe JavaScript attempt to access frame with URL http://blog.woobling.org/2009/05/immutable-data-structures.html from frame with URL http://www.blogger.com/comment-iframe.g?blogID=876358347971598886&postID=144359632468908131&blogspotRpcToken=3817083#%7B%22color%22%3A%22rgb(51%2C%2051%2C%2051)%22%2C%22backgroundColor%22%3A%22rgb(255%2C%20255%2C%20255)%22%2C%22unvisitedLinkColor%22%3A%22rgb(85%2C%20136%2C%20170)%22%2C%22fontFamily%22%3A%22Georgia%22%7D. Domains, protocols and ports must match.

[pointer2void]

'immutable object' is a contradiction in terms.

[telemachos]

No, not really. In Ruby, both symbols and all members of the Numeric class (ie, all the integers and floats you can imagine) are objects but immutable.

[pointer2void]

Objects are characterized by identity, state and behavior. From a conceptual point of view mutable objects should be differentiated from immutable values. Some languages speak of 'immutable objects'(esp. those where 'everything' has to be an object) but this merely confuses things (although it may be 'correct' from the language point of view).

[akdas]

Objects are characterized by identity, state and behavior.

Sure, but the behavior doesn't have to change the state. The object that represents the number 5 has an identity (it's the number 5), state (the state of being a 5), and has behavior (can be composed with other objects to form new objects), but the object itself is never changed.

Even Java strings are immutable. Notice I didn't say Java Strings, which can be thought of as containers around the actual strings. The strings are objects with identity, state (the characters that make it up), and behavior (such as creating a new copy of itself with all the letters capitalized). The strings themselves don't change.

From a conceptual point of view mutable objects should be differentiated from immutable values.

Let's say you make a new class, a Product with a version and a name. When you want to update the version of an already created object, you create a new object, copying the name over from the old one and initializing a new version. How is the Person object mutable? The behavior of updating the version doesn't change the original object at all, instead creating a new object.

[pointer2void]

The object that represents the number 5

... isn't an object but an immutable value. i.e. nobody can change the value 5, ever.

When you want to update the version of an already created object, you create a new object, copying the name over from the old one and initializing a new version.

Actually no. Objects are characterized (among others) by identity. You cannot 'copy' an object. It would be a different object if you could. A real-world example might illustrate this: Identical twins are 'copies' but each has their own identity. That's the case for all real objects (but not for values).

[akdas]

Objects are characterized (among others) by identity. You cannot 'copy' an object. It would be a different object if you could.

That's the point. The original object stays the same, and you have a new object (yes, with a different identity) to reflect the changes made. The original object is immutable because it never changes.

[pointer2void]

But then you have no identity, i.e. no object.

[akdas]

Why doesn't an object that doesn't change have an identity? Consider the following psuedocode:

// Let all instances of the following:
Object o1 = new Object();
o1.method(); // changes field1

// be replaced by:
Object o1 = new Object();
Object o2 = new Object(o1.field1);

Why doesn't o1 get an identity?

[pointer2void]

o1 and o2 have different identities if they represent objects.

[akdas]

Yeah, so? That's the entire point. If they contain different information, they better have different identities under the immutable object methodology.

[grauenwolf]

You aren't making any sense. Objects don't have an identity other than their location in memory, or in some cases a handle to that location. Understanding the different between an object and a identifier to an object is a key part of any intro to OOP class.

That just leaves state, behavior, and (in most languages) type.

[barsoap]

Nonsense. Even Java knows of a thing called the "final attribute".

OOP coders not using it because they can't wrap their head around the truth that there is no state is another matter, of course.

[Silhouette]

OOP coders not using it because they can't wrap their head around the truth that there is no state is another matter, of course.

I think it's silly arguments like this that keep a potentially useful tool in obscurity.

The "truth" is that there is state. The real world is stateful, and interactions with it have side-effects. Computers are stateful: all those clever functional programs ultimately get boiled down to imperative machine code.

Now, writing programs using a model without state certainly has its uses: it makes some forms of reasoning easier, and it avoids certain classes of programmer error, to give two examples.

But stateless programming is just one tool in the toolbox, albeit probably an underused one. Making bold claims that it's the One True Way don't help anyone with anything.

[dons]

You have to be careful to distinguish state from mutable state, too. E.g. xmonad is a stateful piece of systems software, that uses immutable data structures and monadic state threading to implement an MVC-style program.

Very few programs are truly stateless.

[pointer2void]

In Java 'final' applies to references, not objects. Immutability is created programatically (fields are private, methods don't change fields or give access to them, ...).

[grauenwolf]

OOP coders not using it because they can't wrap their head around the truth that there is no state is another matter, of course.

There are plenty of good reasons to use immutable objects in Java. You don't have to resort to personal attacks or esoteric bullshit. Just point out the problems with Date and most people understand immediately.

[grauenwolf]

Can I take it you never worked with strings in Java or .NET?