Statefulness and the Abstract Universe
Quite often, I hear comments from people who are trying to get a grasp on functional programming about entities which are “inherently stateful” or “intrinsically mutable” (example). The commenters often point to a disk or network to make the point. In this post, I am going to attempt to portray a slightly deeper understanding of this topic to erase the facade and bring to fruition the fact that this “inherent state” (or whatever) is in fact an illusion. This will require some thought experiment and the manipulation of some abstract entities in order to attain this insight.
I will first start off by describing the distinction between the physical universe as we observe it and the abstract universe. The physical universe is made up of matter; for example, a house, a typewriter and even a hard disk. The abstract universe is one that is, well, abstract — one that is not physical. If we consider the number 2. We call it ‘a number’, a physical entity, yet we cannot hold it in our hands or point to its physical representation. Therefore, 2 is better described as a representation of “twoness” or “the concept of two”. The symbol ‘2′ is used to denote the concept of two, among other possible representations of the same concept:
- two
- . .
- 00000010
…and so on. Anyone interested in defining the concept of two, with a bent for history, might be interested in learning about the discovery of zero.
Now, this point touches on some philosophical grounds that I’d rather not go into, so instead, I will make a note of the fact that a pure evolutionary Atheist might not accept this distinction (perhaps claiming that 2 is in fact physical as a chemical signal in the brain), while a Theologian would describe the abstract universe as your ‘Soul’ (or some such). I don’t mean to encroach on this philosophical point and I am hoping I can get away with using terminology that can be translated to the relevant philosophical view.
So, when you write a function, in any language, f(2), you’re not passing a 2 or 2 itself to that function, but instead, a representation of the concept of two to the concept of your function and nothing further. Here’s the clincher: All software exists in the abstract universe. Even your C program that does clever pointer arithmetic and your assembly program that moves the hard disk head. Yes, that FILE* is in fact, an abstraction of a pointer, not a pointer itself. None of these are physical entities, but abstractions of physical entities that manifest themselves somehow — none of these manifestations are relevant to the software author.
It’s all quite simple so far, but if you can pass ‘a representation of the concept of two’, then what is to stop you from passing ‘a representation of the concept of the file system’? or the network? Nothing, that’s what. In fact, you could quite plausibly argue that this is exactly what Haskell’s IO monad is doing — an abstraction that represents these physical entities using the expressive type system of Haskell. In exactly the same way that 2 is an abstraction that represents a physical entity i.e. it will eventually manifest itself as electrical signals in your computer hardware (or physically manifest somehow anyway).
Those of you who are concerned about passing an entire file system as a function argument and the impact on performance might be interested in delving further into a topic called Lazy Evaluation and Weak Head Normal Form (WHNF). I’d rather not reiterate the work of many others who are more dedicated, so I’ll just point out that concerns for performance are definitely valid, but the impact on performance is not there (in fact, often quite the contrary — performance improves!).
The distinction between ‘2′ and ‘the file system’ and ‘the network’ from a software developer’s perspective is entirely superficial and should be abandoned. One cannot be ‘inherently stateful’ while the other isn’t. It’s one or the other, so which is it? (hint: n**ther :))
February 22nd, 2007 at 10:40 pm
When you do this, to be honest with your inability to duplicate that resource, you also need to ensure that you don’t copy it, or refer to old versions of it. The IO monad also does that, but only by ensuring that you never actually see that resource as a programmer. Uniqueness typing does it more explicitly.
February 23rd, 2007 at 1:12 am
I really want to understand how you can get things done with a purely functional language. I believe that you can, but someone is going to have to *actually* explain monads before I can make that leap. I’ve read several attempts to explain monads of the last few weeks, but they all seem to accidentally assume the reader already knows what they are.
I’m reminded of when I first heard about lambda expressions and closures. It was this abstract weird bunch of jargon explained by even more jargon and I couldn’t make heads or tails of it. With some digging, I found the right explanation, the one that made me think, “Oh, that’s IT? Why didn’t they just SAY so?”.
I’m sure there’s an article out there about monads that would cut to the chase like that, but I haven’t found it yet.
February 23rd, 2007 at 10:20 am
I can’t make heads nor tails of this post. Of course I can have an abstraction of a network or a hard disk. But interactions with that abstraction have real-world consequences. This necessarily implies that you must treat those abstractions differently than you do the “number 2″. That’s why Haskell has the IO Monad. On Reddit, you said: “The critical question is, what’s the difference between f(2) and g(fileSystem)? Absolutely nothing, that’s what.” If that was true then there would be no need for the IO Monad. The difference between f(2) and g(fileSystem) is that there is nothing that f can do to “2″ that can cause people to die. There may be things that g can do to “fileSystem” that can cause people to die (whether due to software error or to correctly sending an email that launches a war). That’s a difference that matters.
February 23rd, 2007 at 11:56 am
Paul: “The difference between f(2) and g(fileSystem) is that there is nothing that f can do to “2″ that can cause people to die. There may be things that g can do to “fileSystem” that can cause people to die (whether due to software error or to correctly sending an email that launches a war).”
February 23rd, 2007 at 12:45 pm
My comment got cut off, trying again.
Paul said: “The difference between f(2) and g(fileSystem) is that there is nothing that f can do to “2″ that can cause people to die. There may be things that g can do to “fileSystem” that can cause people to die (whether due to software error or to correctly sending an email that launches a war).”
This is not a valid comment to make. What’s to say that the function f(2) isn’t a single line function that erases everything on your hard drive, without seeing the contents of that function you can’t know that. Even if you can see the function’s contents and it doesn’t seem to be doing that some error in the function could cause it to do that elsewhere.
Secondly when you were comparing abstractions and their “contents” or “real world representations” you’ve made a huge mistake. Interacting with the contents of a hard drive is akin to interacting with the contents of the “number two” which has drastic real world consequences. Think about it, since you were knee high to a grasshopper you’ve known what 2 means, it’s an abstraction with static contents that we as a society all agree on for ease of communication. If you change the contents of that abstraction (change the “meaning” behind the “number two”) even just within the scope of your system, think about the consequences.
This post isn’t changing the world as you know it, it’s merely looking at it from a different angle and questioning things you (and I) have taken for granted since the infant stage of programming and probably since the beginning of our interaction with a computer of any kind.
February 23rd, 2007 at 1:54 pm
@p: here is an attempt at a short but explanatory explanation. the first thing monads are for is garanteeing that some expressions are evalutated in a certian order.
Do you know what a data dependency is? It’s part of compiler implementation practise. Basically when a variable gets it value from somewhere it’s said to depend on where it got it from. In other words, in order for a function to use the value it must first evaluate the place it gets its value from first. In theory as long as you evaluate things depended on before you evaluate things that use that thing, your program should produce the same results no matter what order things are evaluated in.
But io doesn’t work like this, at least not in mainstream languages. So if change the order of evaluation of statements that do io, you’ll produce different results. So how does haskell fix this? By making things that must be evaluated in a certain order have data dependencies between each other. So now haskell can evaluate things in any way it wants, the way functional programming is supposed to work, so long as it respects the data dependencies. How does it acheive this? By making the result of a function use the result of previous functions.
This function is called bind, and in haskell is written >>=. It takes two functions as arguments. The first produces a result and the second takes a result and produces another one. Bind takes these two functions and joins them together.
A not entirely correct analogy, is that in many mainstream languages, arguments must be evaluated before being passed into a function. So if we have that rule and we want certain things to be done in a certain order we can make a function that does the last thing and pass it the result of doing to the next to last thing as an argument. Since arguments will be evaluated before the function they’re being passed to, the next-to-last function call will be evaluated before the last one. So basically bind takes two functions, which it names second (char second(int) {…}) and first (int first () {…}), and rewrites them so we have second(first). Does that kind of make sense?
See my next post for mutation vs functional
February 23rd, 2007 at 2:09 pm
This is an attempt to say what Tony is saying in a different way.
Basically you don’t need mutation to have things that change. A state is a mapping of identifiers to values, that is a state is really just an enviroment.
Env { foo = 2,
baz = “boo”}
and an enviroment is really just a data structure.
To produce a change in an eviroment we take an old one and produce a new one. So
// Env now is same as above
foo ++; // the enviroment is being passed to foo implicitly
// foo has returned a new enviroment Env {foo = 3, baz = “boo”}
Since nobody is using the old enviroment it can be garbage collected. Better yet the old enviroment can be recylced. Notice how we are still using mutation but we are not using it directly. This is just like garbage collection vs memory management. In both cases memory is being managed but in the garbage collection case a correct program is being produced faster with less effort, because the computer is taking care of our memory for us.
In general we can represent time varying quantities by using sequences instead of mutation. So instead of using a loop to increment a value we write a pure function which takes the current state and produces the next state.
for (i=0; i [0, 1, 2, 3, 4, 5, 6........]
take 11 $ iterate foo 0 => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
I hope that was clear, though I’m not sure it was