Eric Lippert has another post up in his immutability series, this one about using immutable binary trees to represent immutable maps. (“Map” = “hash” or “dictionary”, for you perl and python folks. I understand that the technical term is “associative array.”)
I skimmed the post, said to myself “that makes sense,” then went back and stared at the code samples for a bit and said “wait a minute….” Because the map interface has methods like Add() and Remove(), and so does the tree interface. What’s immutable about that?
I was halfway through writing a comment asking Mr. Lippert what the hell was going on, when I figured it out. Yes, you can call Add() and Remove(), but those methods don’t actually modify the map (or the tree) you call them on. Instead — this is what I saw, when I looked closely — they return a new map (or tree), identical to the original apart from whatever was added or removed. Instead of mutators that change the internal state of an object, you have something much closer to a mathematical function, describing a relationship but never altering any values.
Anyway, it turns out that if I’d actually read all of Mr. Lippert’s other posts, he explains all this, specifically in post #2 of the series, “A Simple Immutable Stack.” He goes on to demonstrate how, contra most people’s first instincts including mine, immutable data structures of this kind can actually use less memory than the traditional mutable kind, because, being as all the pieces they’re built up out of are also immutable, they can safely share as much of their internal state as they have in common.
It strikes me that something like this is probably the answer to Dan‘s question about representing mutable state in functional languages. Functional expressions may not be able to modify anything, but they can always produce new results.
(The “Item 13” in the title is from Effective Java: Item 13: Favor Immutability. Since it’s the Bible, we might as well cite chapter and verse — as long as the numbers haven’t changed in the second edition.)
Comments closed due to spam.
Chrononaut 
I suppose that link to my name would make more sense if I’d actually gotten to the point of posting my question over there.
I’m fairly comfortable with the idea of immutable data structures — what I’m more curious about is how the purely functional mindset conceptualizes the aspects of system state that must change over time. I/O is the blatant example of that, but there are others under the hood[*] as well, f’rex variable reassignment. In the comments on the immutable stack link, the author illustrates typical use of the stack like so: this.s = this.s.Push(…); which still reads to me as procedural; it’s the i++ of stacks.
I admit that I haven’t read the full series yet, and it’s entirely possible that there’s a later chapter on not reusing variable names, for example. I’m just a member of the Carnegie Mellon CS Envy Club (and a junior member, at that), so any blanket statements I make should be read with question marks appended.
[*] To tie things back around to a previous post of yours here, it seems that the Actor model of concurrency is incompatible with immutability on two counts: 1) an Actor must be able to alter its future behavior in response to receiving a message, which means mutating either itself or a master “forwarding address” for its message queue, and 2) since messages are delivered asynchronously and Actor behavior may change depending on message receipts, a reply to a message cannot be treated as the evaluation of a function.
Well, yeah, I think “this.s = …” is a cop-out. But I don’t see why in principle “whatever was last output by this function” isn’t as valid a way to represent system state as a variable, if you imagine that function being called, say, at the core of an event loop.
I haven’t gone through the Actor stuff anywhere near enough to figure out how it works, but I expect (and this post, on a quick skim, hints) that it’s all done with recursion. You don’t change any state variables, you just pass the message on. Or a mutated message. Or something.
Hmm. Distractions first: the post that you link seems to imply that implementing the behavior-modification requirement of Actors involves recursively forwarding to a new Actor every time a change of state is needed, which means that every novel change of state accumulates the overhead of one forward-and-reply to your running program. That doesn’t sound great, so I must not have it right.
Deeper, though, I’m looking for a way to unpack what it means to say “was last output” or even “loop” in a functional context. Those words are deeply procedural, and although I know Haskell etc. use macros to convert those procedural conceptual handles into functional core logic, I’m curious about how that lower level bridges the gap between a timeless expression to be evaluated and the need to receive interrupts and change state. If it’s as simple as “procedurally loop the function that maps input histories to output directives until halted,” that would make sense, but in a feet-of-clay sort of way.
You’re going to make me learn all this stuff, aren’t you? 🙂
Tim Bray has this ongoing project called “Wide Finder” which is basically a simple web server log file parser-counter, only parallelized (hopefully in a way that’s scalable across a whole lot of CPUs), and people have been writing implementations in a bunch of different languages and then fighting about performance. His first couple of tries are in Erlang, which doesn’t have any mutable variables — have a look. Supposedly there are much more sophisticated versions out there by experienced Erlang programmers, but I couldn’t find them in a quick search and anyway I really should get dressed and go to Starbucks to meet Ben, or I won’t be able to give him crap for not showing up on Monday. 🙂
Oh, I also (misremembering Haskell for Erlang) just looked up a Haskell example and, if I understand the code right, it’s using a for loop and a mutable associative array. So maybe these functional programmers aren’t the magicians we’ve been imagining them to be.
…
I got nuthin’.
Thanks for entertaining the question! At some point I might lob another one your way.
Glad you enjoyed the series.
To answer Dan’s question above — purely functional languages such as Haskell represent impure, must-have-side-effects operations such as I/O with _monads_.
Monads are a bit tricky to wrap your head around at first, but once you get them, the design of LINQ in C# 3.0 becomes much clearer.