Immutable Data Structures in C#

In the post on Path Finding using A*, Eric Lippert, programmer in the Visual C# team, writes that immutable data structures are the way of the future in C#. As immutable data structures have been a frequent posting topic of mine, I am really happy about this direction towards immutable data and functional programming that C# is taking. My only quibble is that the last two words, "in C#," are not really necessary.

The frequent complaint of functional programming is that it is slower than procedural programming. However, I discovered something else: As you know, the immutable data structures for maps may be slower for some operations than their imperative cousins, but the running times for all the operations are typically acceptable and well-balanced. (Even then, I did bring up in a recent post a version of persistent hash-tables and array used by COQ that offers nearly identical performance). Plus, these data structures are very flexible--able to be used freely anywhere with no constraints.

Most of my data structures in NStatic and elsewhere are immutable. In my data structures, the equality and the copy operation are constant-time, even for large object trees. The immutability and balanced performance allows many otherwise exponential algorithms to be done efficiently. A good example is the use of dynamic programming in which function values are "memoized" (sic); this technique is absolutely essential for natural language parsing.

Wes Dyer, another developer in the C# team, wrote early this year that "imperative programming is sometimes reminiscent of a Rube Goldberg machine. Both require meticulous thought to ensure that a process works correctly despite a myriad of state transitions and interdependencies. It is amazing these complicated programs work at all." Hmm... could he be referring to any popular application software that we know of?

That Microsoft and the rest of the world programs imperatively and suffers the consequence of their decisions is the main reason that I can even consider developing the software that may indirectly compete with their own.

Comments

[damien morton]

It would be nice if immutable data was supported in the C# language and the CLR.

[Patrick Smacchia]

Well done Wes, I also think that Immutable classes are a powerful tool that very few developers use. I'll certainly blog about it in the future.

Notice that I introduced the Keyword IsImmutable in CQL a few monthes ago that allows to constraint classes to be immutable with constraints like:

WARN IF Count != 1 IN SELECT TYPES WHERE !IsImmutable AND FullNameIs "MyClassThatShouldbeImmutable"

More info here:
http://s3.amazonaws.com/NDependOnlineDemos/NDependMultiThreadedApp_viewlet_swf.html

[Patrick Smacchia]

Oups, of course I meant:

WARN IF Count != 1 IN SELECT TYPES WHERE IsImmutable AND FullNameIs "MyClassThatShouldbeImmutable"

[Patrick Smacchia]

Oups, of course I meant:

WARN IF Count != 1 IN SELECT TYPES WHERE IsImmutable AND FullNameIs "MyClassThatShouldbeImmutable"

[Wesner Moise]

Cool, Patrick, your tool does awesome things.