In a private email, somebody asked of my previous article "Okay, I can see that there must be state since you've created a state machine. But you aren't mutating any variables so where does the state come from?" It's a good question. If you feel you "got it" then skip this article. But if you're still hesitant or think I'm misusing the word "state" please read on.
First, let me remind that I contend that state is 1) something responding to the same inputs differently over time as far as another observer is concerned and 2) an abstraction and not the representation. None-the-less, state always ends up with some representation. For instance, files can represent state. And even users of programs can hold state (quick, I'm in a drunken state and I plan to write a long rant, who am I?).
I want to ignore all but memory based state and show that, ultimately, even the Erlang code must manipulate mutable memory and that message sending effective leaks a little bit of that detail. Now, on Reddit an offended Erlanger called me a Java fanboy. As any of my loyal readers know, it is true that I think Java is the most incredibly awesome language EVER and I can hardly stop writing glowing things about it. But for this article I'll struggle against my natural instincts and use Ruby, Haskell, assembly, and Erlang.
I'll use Ruby to illustrate some points about state and representation. First the tired old state diagram and then some Ruby
class SockMachineSimple
def initialize
@state = :zerocoins
end
def insertcoin
case @state
when :zerocoins
@state = :onecoin
:nothing
when :onecoin
@state = :twocoins
:nothing
when :twocoins
:coin
end
end
def pushbutton
if @state == :twocoins
@state = :zerocoins
:tubeofsocks
else
:nothing
end
end
endIf you don't read Ruby then Ruby control flow structures generally result in the value of their last contained expression so explicit returns aren't needed. :foo is a symbol (kinda like a string). @state declares a field (which is private) named state. I called it state because it so clearly matches to the state space specified by the diagram. But here's another way to write SockMachine with a completely different representation
class SockMachineComplex
def initialize
@count = 0
end
def insertcoin
if @count % 3 == 2
:coin
else
@count = @count + 1
:nothing
end
end
def pushbutton
if @count % 3 == 2
@count = @count + 1
:tubeofsocks
else
:nothing
end
end
end Instances of this class keep track of the total number of coins or button pushes ever accepted and use the modulus operator to decide what to do about it. The representation is quite different from that of SockMachineSimple, but to anybody using this class the difference is mostly irrelevant - it still conforms to the same state diagram. Internally it has a very large number of states but externally it still has the same three. And here's one last stateful machine
class SockMachineDelegated
def initialize
@machine = SockMachineComplex.new
end
def insertcoin
@machine.insertcoin
end
def pushbutton
@machine.pushbutton
end
end By looking at the source it would appear that this version never mutate any variables after being initialized, but of course it does by calling methods on SockMachineComplex. Hiding the manipulation of representation is not the same thing as making something stateless. And now one last example, one that is totally different because it is not stateful.
class SockMachineStateless
def pushbutton
machine = SockMachineComplex.new
machine.insertcoin
machine.insertcoin
machine.pushbutton
end
endInternally, pushbutton uses a stateful machine but externally it is not stateful. Short of using a debugger you can't observe the state changes in SockMachineStateless's internal machine. Actually, I guess you could monkey patch SockMachineComplex to do some kind of IO or callback to expose the workings so maybe I shouldn't have used Ruby to illustrate my OO points. Too late now.
Hiding State
Okay, but that's OO stuff. Erlang is a functional language and the code never appeared to have any mutable variables or nested mutable objects. So what gives? Well, to illustrate Erlang I'm going to use Haskell, another functional language. Haskell's great advantage to this exposition is that it's really, really easy to get at some nice clean assembly.
So here's a very silly Haskell function for determining if a positive Int is even or odd. Its implementation is silly, but it allows me to make a point.
flurb :: Int -> String
flurb n = if n == 0 then "even"
else if n == 1 then "odd"
else flurb $ n - 2This is a pure function - it mutates nothing. Yet when compiled with ghc -S -O to get AT&T syntax assembly, the function looks like this
Main_zdwflurb_info: movl (%ebp),%eax cmpl $1,%eax jl .Lczq cmpl $1,%eax jne .Lczo movl $rxA_closure,%esi addl $4,%ebp andl $-4,%esi jmp *(%esi) .Lczo: addl $-2,%eax movl %eax,(%ebp) jmp Main_zdwflurb_info .Lczq: testl %eax,%eax jne .Lczo movl $rxy_closure,%esi addl $4,%ebp andl $-4,%esi jmp *(%esi)
GHC has compiled the flurb function down to a loop and the immutable n variable is represented with the mutable eax register [1]. Some pseudo Haskell/assembly mix might help illustrate
flurb n =
movl n, eax -- copy n into the eax register
Main_zdwflurb_info:
if eax == 0 then "even"
else if eax == 1 then "odd"
else
addl $-2, eax -- decrement eax by 2
jmp Main_zdwflurb_info -- jump to the top of the loopAs you can see, the Haskell code does use mutable "variables" at runtime. This is a common optimization technique in functional languages for dealing with direct tail recursion. But all that machinery is hidden from you as a programmer so just like SockMachineStateless the end result is stateless unless you peel back the covers with a debugger.
Finally, Some Damn Erlang
All right, I've written Ruby and Haskell, generated some assembly, and then written in an impossible chimeric language. But my original question was about Erlang. Here's a simple Erlang counter actor
-module(counter).
-export([create/0, increment/1]).
create() -> spawn(fun() -> loop(0) end).
increment(I) ->
I ! self(),
receive X -> X end.
loop(N) ->
receive From ->
From ! N,
loop(N + 1)
end.Again, no variables are mutated. But if I assume that Erlang does the same kind of direct tail call optimization that Haskell does, the pseudo Erlang/Assembly loop looks like this
loop(N) ->
movl N, eax % copy n into the eax register
.looptop:
receive From ->
From ! eax, % send the current value in eax back to the original sender
inc eax % increment eax by 1
jmp .looptop % jump back to the top of the loop
end.It's still a loop like the Haskell one, but there's an important difference. Each message receive sends back the current value of the mutable eax register then mutates it. So this behaves a bit like SockMachineDelegated - the original code didn't appear directly manipulate any mutable variables, but there was mutation under the covers and unlike SockMachineStateless but like SockMachineDelegated this change of state is visible beyond the local confines. [2]
Now, there are other ways to deal with recursion. I don't know Erlang's implementation, but it doesn't matter. Something is being mutated somewhere and that change is being made visible by messages being sent back. Typically non tail calls mutate the stack pointer so that it points to new stack frames that hold the current value of arguments, or then again some arguments might stay in registers. Tail calls that aren't direct tail recursion might mutate the stack region pointed to by an unchanging stack pointer. Whatever, it always involves mutation, and it's always hidden from the programmer when using pure functions. But actor loops are not pure functions. The sends and receives are side effects that can allow a little tiny bit of the mutable machine representation to be mapped to state that an observer can witness.
But Really Where Are The Mutable Variables?
So all that's fine, but it doesn't really show where the state is in my original Erlang code. The code didn't have an N to stick in a mutable register or a mutable stack frame. Here's the core of it.
zerocoins() ->
receive
{coin, From} ->
From ! nothing,
onecoin();
{button, From} ->
From ! nothing,
zerocoins()
end.
onecoin() ->
receive
{coin, From} ->
From ! nothing,
twocoins();
{button, From} ->
From ! nothing,
onecoin()
end.
twocoins() ->
receive
{coin, From} ->
From ! coin,
twocoins();
{button, From} ->
From ! tubeofsocks,
zerocoins()
end.For this final answer I'm afraid I have to do a bit of hand waving. The explanation is even more abstract than the mutable variable as register/stack local explanation. You see, no matter what, your code always mutates one register: the instruction pointer. Its job is to point to the next instruction to be executed. As the CPU executes instructions the IP moves around, typically just being bumped up a bit for everything but jumps which move it more substantially.
In purely functional code the IP moves around but these moves can't be observed by other parts of the program as they are happening. In other words, in purely functional code, the changing IP is invisible. It's a completely black box unless you use a low level debugger. It's very much like SockMachineStateless where the internals were mutable but invisible to the outside world.
But with message receives the IP can be induced to move around based on things communicated from outside the function. The IPs current instruction can then define in large part what a message received by a process will do. If the IP points at the receive in the "zerocoins()" function then that's one behavior and if it it points to the receive in the "twocoins()" function then that's another. The different behaviors can be observed by other actors via messages sent back to them. When an actor sends a SockMachine a coin or buttonpress message it may indirectly be causing the IP to be mutated. And when it gets back nothing, coin, or tubeofsocks it's really being told, in a very indirect way, something about the value of the IP.
Conclusion
State is not the same thing as representation. None-the-less, with an omniscient view of things you can always find the representation of state. It might be in bits stored on a drive, it might be in neurons in a user's head, or it might be in a computer's memory and registers. The representation might not be directly visible in the source you're looking at but hidden in low level machinery. It might just be the instruction pointer pointing at different parts of your code base.
If you equate state with representation you end up with the very un-useful property that everything is stateful since at some level of representation every bit of executing code on your computer involves stateful processes. This view robs you of the ability to think about high level languages, especially purely functional ones like Haskell, at an appropriate level of abstraction.[3]
Purely functional code ensures that that the state represented by registers and stack pointers and instruction pointers is kept local. But side effects like message sends and receives allow that low level machinery to be used as the representation of shared mutable state even if you don't see it in your code.
In the end, it's far more useful in most cases to think of state from the point of view of an observer than the point of view of its implementation. The SockMachine actor was stateful regardless of how that state was represented simply because other actors could observe it changing state. Digging down into how send and receive allow a modicum of access to the instruction pointer just isn't a useful model for thinking about stateful actors normally. So the short answer to the original question is "Who cares how the state was represented? It was shared mutable state."
Foot notes
- Actually, it appears to be moving n back and forth between memory pointed to by eap and eax, which seems oddly wasteful given that it never branches out of this function. It also does 3 tests when only 2 should be necessary.
- Technically the Erlang code probably can't keep the current value of N in a register when calling receive since receive may cause a task switch to another process, so assume that receive copies registers out to memory before executing then swaps them back in when its done.
- Some people equate state with data, but that's just as bad. Code is data so all code must be stateful - another useless conclusion.
