Friday, April 3, 2009

The State of Sock Tubes

Oddly, given that state is such a central notion to so much programming, it's awfully misunderstood. How do I know? Because OO programmers think they can make it private and Erlang programmers think they don't share it. If you agree with either of those statements then this article is for you.

I want to start with a simple, hypothetical vending machines. It dispenses socks in a tube, which is cool, because "tube of socks" is a huge Internet meme. Well, not yet, but will be when this article makes the front of Reddit, Digg, Hacker News, and CosmoGirl.

So, anyway, the machine has a coin slot, a button, and a dispensing tray. If you put in two coins one after the other and press the button you get a tube of socks. If you insert two coins and then insert a third you get your coin back. Same with fourth, fifth, etc. Pressing the button after putting only one coin or no coins at all results in nothing happening. It's a simple machine, but it's enough to illustrate all my points. A diagram sums it up nicely.

This is, you guessed it, a diagram of a state machine. In particular this one is a finite state machine, but that's not important to this article. So I'm wasting time by mentioning it. And more time by explaining that I'm wasting time. The diagram shows 3 states labeled 0 coins, 1 coin, and 2 coins. Between the states are arrows labeled with an action you would take to cause the machine to move from one state to another. Some of the transitions also have an action that the machine takes during that transition like dispensing foot warmers or returning a coin. The diagram assumes an infinite supply of socks. And tubes. Got it? Good. Patent pending. Onward.

Hypothetical

Imagine I locked you in the room with a bag of coins and that machine. The machine is a sealed, glossy black, and glows with a malevolent sock tube evil. Imagine there's no way for you to see what's inside, no way to know how the machine actually works. Assignment: figure out as much about its internals as you can.

Even with these restrictions, I'd bet that with only a small amount of experimenting you could easily draw something like the diagram above. I mean, if I unlocked the room long enough for you to get a pen and paper you could draw it.

True, you'd never be certain you knew all the details. It could be that after dispensing 1,000,000,000,000 pairs of socks it would reward you with a unicorn instead. You also wouldn't know if the machine was written in Ruby or Java. Er, integrated chips or discrete components. So many details could still be hidden. But you would certainly know that the machine had state and that the state changed based on actions you took.

You Can't Make State Private

So, point #1) you can't make state private. You can hide the details of how the state is represented and you can carefully control the valid state transitions and you can control who has access to change the state, but you can't make the state private. State is the fact that something reacts differently to the same inputs at different times. Sometimes putting a coin in and pushing the button does nothing but sometimes it results in a cool tube of socks. That's state. The gears and transistors are hidden, but the state is observable. If your favorite OO object has all private data but one single method does something different based on changing values in that hidden, private, super secret data then by definition state has been exposed to anything with access to that method or anything that has access to anything that has access to that method or anything that has access to anything that...etc.

Now, hypothetically the tube sock machine could have some internal counter that counts the total number of coins that has ever been inserted. But if that counter is strictly internal and can never be observed then it's not private state, it's just dead code ... er useless machinery. Make sense? Good. Patent pending. Onward.

How You Can Make State Private

Having just explained that you can't make state private, I will now explain how you can make state private. Imagine if our sock machine were sealed inside another machine which has a single button and a single dispenser tray. Further, imagine the outer machine has an infinite supply of coins in its guts. Pushing the button on the outer machine causes it to insert two coins into the inner machine, push the inner button, and then dispense the resulting tube of socks. If you were locked into the room with this machine you would never know that inside lives a Rube Goldberg state machine. You would just know that pushing the button gives you socks, every time, no ifs, ands, or buts. To an outside observer this machine is stateless. Only by ripping opens its guts would you know the awful truth.

The moral is that you can't make state private with a "private" keyword, but you can make it local. In programming world that means you can implement something stateless using "local" mutable variables. State is relative to an observer. If you can't observe it changing, then it's not state as far as you're concerned. That's why it's perfectly valid to say that the pure parts of Haskell programs are done without state even though thunks are memoized. If that was gibberish to you, I apologize, it was gibberish to me too.

The End, Or Is It?

This long ass article was really just a prequel to the real article coming soon which will explain why Erlang style actor "shared nothing" message passing concurrency is all about shared state. Shocked? Good. Patent pending.

8 comments:

  1. Hiding the fact that there is state isn't the point of OO as you imply; it's hiding the way that that state is stored internally. Even immutable languages have the concept of state, even if it is the execution stack at some point of its execution. In fact, the only time you don't know is in your last example where everything is in a single call - but then you have to appeal to an infinite amount of money and an infinite supply of socks for your argument of "there is no state" to hold. And if you'd done that, I'd just prefer the infinite amount ok money, thanks. Or have you been speaking to the G20?

    ReplyDelete
  2. @AlBlue,

    I never implied that hiding state is the point of OO. In fact, I explicitly state that that you can't except by hiding all its effects. Now, hiding representation is a point of OO, but a) representation and state are two different things and b) there are certainly other ways to do it.

    Pure functional programming doesn't have state in the execution stack except to an observer capable of observing the stack - i.e. a debugger. From inside a purely functional program the stack cannot be observed. In fact, even the time taken by the program cannot be observed by the pure part.

    Thinking about pure functional code as if it were the same thing as imperative code but with state in the stack is an implementation point of view that ignores the value of the abstraction offered. Kinda like thinking about object oriented dispatch as just an extra level of pointer indirection - useful in some contexts, but not an every day way of looking at that world.

    Anyway, purely declarative coding is all quite fascinating and liberating but irrelevant to the point of this article. Or is it?

    ReplyDelete
  3. "...is all quite fascinating and liberating but irrelevant to the point of this article. Or is it?"

    Ok, so what is the point? If most programmers misunderstand the differences between state and the internal representation of that state, where does that cause a problem for them? Why does understanding The State of Sock Tubes help?

    I need something more pragmatic.

    ReplyDelete
  4. @Jack,

    >I need something more pragmatic.

    The sequel Jack, the sequel!

    ReplyDelete
  5. >Shocked? Good. Patent pending.

    I'm not shocked, I'm socked!

    Good article btw, trying to hide obvious state is just silly.

    ReplyDelete
  6. Hmm. My initial reaction is "So What?" My slightly later reaction is still nearly the same. However, being drawn in to the slightly pointless debate, you have given a very simple example. There are many more complex objects that would take a mathematical genius, a huge amount of horsepower or a quantum computer, such as the state within public/private key encryption objects.

    ReplyDelete
  7. As stated on twitter - and I there weren't any IMHO good answers there - what I think is a nice problem to solve:

    - 3 actors sell socks
    - there is a limited amount of socks available
    - if socks are still availble, people should be able to buy them

    Implement this without a SPoF or a Amdahl bottleneck.

    Cheers
    Stephan

    ReplyDelete
  8. > Erlang's a great language. Actors are a great model. But they are neither race nor deadlock free.Yes but no. Strictly speaking this is true only of Erlang without OTP, but very few people use Erlang that way. Erlang/OTP deals with deadlocks (and other errors) with supervisor tasks, which detect deadlock as non-responsive tasks. A supervisor then logs the error and restarts the task. Erlang/OTP doesn't have deadlocks, because the system isn't dead or locked, after OTP restarts the task it's alive and processing input.

    Talking about Erlang without OTP is pretty misleading. Much of the power and beauty of Erlang rests in OTP -- the power to detect and work-around errors (what would be deadlock otherwise). This is a viable solution because Erlang can reliably restart tasks without data loss or corruption. Deadlock is just one example of bugs Erlang programs can survive and continue operating with.

    If you still insist the Erlang/OTP has deadlock, recode your example as a proper Erlang service and which your task escape deadlock. If you're evaluating Erlang without understanding OTP, then you missing most of the point of the language.

    ReplyDelete