Java Has Type Inference and Refinement Types (But With Strange Restrictions)

When enthusiasts talk about Scala they frequently start with "it's a lot like Java but with all this other cool stuff like type inference and structural types and..." I guess it's okay to introduce Scala that way. I've done it myself. But it does give the impression that Scala has somehow heaped complexity onto the Java. Oddly enough, it hasn't, at least not in the areas of type inference and structural types. Java has both. Sorta. They're just not very useful.

In this short article I'm going to try to show that while type inference and structural types appear to be additions to Scala over and above Java, they can also be explained as the removal of peculiar restrictions from Java. The goal is not just to illustrate these two points, but to make a broad statement: Scala isn't a just bunch of features heaped on top of Java. To a significant degree it's a generalization of things already found in Java. The result is that many aspects of Scala are both simpler and more regular than Java.

Type Inference

Java folk get excited about Scala's type inference. Usually positively, but sometimes negatively. But here's the thing: every practical statically typed language has some type inference. Every one. Even Java has type inference. It's just very limited. Let me show you by starting with a simple class

class Foo {
  public Foo bar() { return this; }
  public String toString() { return "Foo!"; }
}

With that I can write

System.out.println(new Foo().bar().bar().bar());

It's silly code but it illustrates my point. Java doesn't need me to explicitly annotate the return type of each call to bar(). Java infers the type resulting from new Foo().bar() as being a Foo, which in turn can be sent a bar() message resulting in a Foo, etc. If I change things just a little the type system complains

System.out.println(new Foo().bar().bar().baz()); // bzzt error!

In Java I "only" have to annotate types when I want to assign to a variable or return from a method. Which, come to think of it, is an odd restriction. The compiler obviously knows the type, so why do I have to tell it yet again?

Foo f = new Foo().bar().bar().bar();

Thus, rather than saying Scala adds type inference we can equally well say that it removes a silly restriction from Java's type inference[1].

Structural Refinement Types

The fact that you don't have to annotate types when building expressions in Java is well known even if people don't usually call it type inference. What's not as well known is that Java has refinement types. So I'll have to explain, this time starting with Scala.

In Scala you can say method doSomething takes any object with a bar method, like so

def doSomething(x : {def bar : Unit}) = ...

That's called structural typing - the doSomething method puts a constraint on the structure of objects that may be passed to it. But actually, in Scala, that's just shorthand for the following refinement type

def doSomething(x : AnyRef {def bar : Unit}) = ...

That says that x must be a subtype of AnyRef and must have a bar method. The type of x is a "refinement" of AnyRef with an additional structural constraint. Scala's refinement types aren't limited to just refining AnyRef, but that's really not important to my point here. My point is that Java has refinement types, too.

If you're a Java programmer, you're probably scratching your head thinking I've lost my sanity. But I promise I haven't. I ask you, in Java what exactly is the type of this expression?

new Object() { 
  public void bar() {
     System.out.println("bar!"); 
  } 
}

If you said "Object!" think again. In Java it's actually something more sophisticated. Go paste this into your favorite Java IDE and run it. I'll wait

public class Test {
  public static void main(String[] args) {
    (new Object() { 
      public void bar() { 
        System.out.println("bar!"); 
     } 
    }).bar();
  }
}

Surprised? Remember my point about limited type inference above? Here, Java has clearly inferred that the result of the expression is an Object refined with a bar method[2]. And so it lets you send a bar() message to the object. Rename either the method or the call to "baz" and you get a type error. But if you want to do anything interesting with the (new Object {public void bar() {...}};) object, like assign it to a variable, return it from a method, or apply it as an argument to a method then Java has a problem. It has no way to denote the refinement. So the refinement gets "lost" from the static type system. Poof. Gone. It's part of the object, you can find it via reflection, but the static type system won't let you get at it. The static type system only lets you get at a refinement "immediately" in a surrounding expression. Which is pretty close to useless. When you look at it that way, Scala hasn't so much added refinement types as removed another silly Java restriction.

Conclusion

When Java people first start looking into Scala it's common to think of Scala as being some complicated mishmash. In large part, evangelists (including me) are to blame. It's surprisingly hard to convey a nice feature of language A to users of language B without making it sound like something totally new, hence something that will complicate their lives. Hopefully this article has helped illustrate that in a very real sense some of the things that appear to be "new" in Scala are really "old" but generalized to be made more useful.

So this article is a call to all Scala pundits out there: when comparing Scala to another language, especially Java, go ahead and get excited about a "new" feature...but then see if you can't explain it as a generalization of an "old" one. You might be surprised how often you can and your audience might come away less intimidated.

Foot Notes

1. Technically, Scala's type inference is quite a bit more sophisticated than Java's. But I won't let inconvenient facts like that get in the way of making a good point.
2. Technically, I think the Java spec says that the type isn't structural, but some anonymous nominative type that the compiler can infer and use over a very limited scope. Then again, maybe not. I'm too lazy to go re-read the spec. Also, as already established, I won't let inconvenient facts like that get in the way of making a good point.

Erlang Style Actors Are All About Locking

I managed to offend a few Erlangers by talking about actors as being shared stateful objects a couple of articles back. Now I'm going to continue the tradition by talking about the actor locking model. And I'm not just talking about Erlang, but any of the libraries that have sprung up for other languages to support actor style concurrency. Let me emphasize again that I like both Erlang and actors. But I dislike the number of times I read from enthusiasts that you "can't have deadlocks in Erlang because it doesn't have any locks." Of course you can because it does. This article will explain.

Locks

There are all manner of locks in the world: mutexes, monitors, synchronization barriers, read/write locks etc., etc., yada yada yada. All of them boil down to a spot in the program where if conditions aren't good-to-go the currently executing thread stops executing until some other thread (or threads) change the condition the lock is waiting on[1]. Erlang has a locking primitive, too. It stops the execution of the current thread and waits for the right conditions to move on. The primitive is called (drum roll please)...'receive'.

"But, but, 'receive' receives messages - it's not a lock." Sure, it receives messages. True. But it also brings the currently running thread to a screeching halt until it receives a message it wants to handle. "receive foo -> doSomething()" waits until the atom "foo" is at the front of the current process's mailbox - any other message gets thrown to the back of a "this receive can't handle that message" queue for processing by some other receive. In other words "receive foo ->" is a lock that waits for the condition "foo at head of mailbox queue" before it unlocks.

Deadlocks

A deadlock is when there's a cycle in the locking dependencies of 2 or more threads. Thread 1 is locked waiting for condition 1 after which it will set condition 2, Thread 2 is waiting for condition 2 after which it will set condition 3, etc until you get Thread n which is waiting for condition n after which it will set condition 1. Everybody's waiting on somebody else to go first so nobody can go.

Based on this, a deadlock in Erlang is easy to create. Just spawn two actors that are each waiting for a message from the other

Foo = spawn(fun() -> receive 
  {From, foo} -> 
    From ! {self(), bar}, 
    io:format("foo done~n") 
  end 
end).
Bar = spawn(fun() -> receive 
  {From, bar} -> 
    From ! {self(), foo}, 
    io:format("bar done~n") 
  end 
end).

If a running system doesn't have any other actors that will send Foo or Bar the right message then they are deadlocked until some poor sleepy eyed admin comes along to break the deadlock with "Foo ! {Bar, foo}". Now, in this case the deadlock is not a big deal. The resources these actors consume are pretty tiny and they don't really do anything useful even when they unlock. But if these actors were meant to do something actually useful such a deadlock could seriously impair the functionality of a system.

This was a toy example, of course. It's easy to see the deadlock. In a "real world" large scale application it might not be so obvious where the deadlocks lurk. Actor's can end up in very complicated, dynamically changing relationships. Couple that with the possibility for race conditions and you'll see that deadlock is a real concern. Erlang style actors make concurrency much easier to deal with, but they don't remove the need for careful design and testing.

That's pretty much all I really wanted to say in this article, but I can't feel my work here is done until I've committed further atrocities against Erlang.

Perverting Erlang

A couple of posts ago I had a problem with race conditions on a shared stateful actor. Here's what it looked like.

1> c(sockmachine).
{ok,sockmachine}
2> Machine = sockmachine:start().
<0.38.0>
3> sockmachine:test(Machine, 2).
all test processes launched
[2] BONUS COIN!
[1] BONUS COIN!
ok
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!

etc.

While there are many good solutions, one evil solution is to use a mutex. You see, one well known aspect of concurrent programming is that once you have one locking primitive, many others are pretty easy to build. To the perversion mobile!

-module(mutex).
-export([create/0, lock/1, unlock/1]).

create() -> spawn(fun() -> unlocked() end).

lock(Mutex) -> 
   Mutex ! {lock, self()},
   receive ok -> ok end.

unlock(Lock) -> Lock ! {unlock, self()}.

unlocked() -> 
   receive {lock, LockedBy} ->
      LockedBy ! ok, 
      locked(LockedBy, 1) 
   end.

locked(LockedBy, Count) -> 
  receive 
     {unlock, LockedBy} -> 
       if Count == 1 -> unlocked();
       true -> locked(LockedBy, Count - 1)
       end;
     {lock, LockedBy} -> 
       LockedBy ! ok,
       locked(LockedBy, Count + 1)
  end.

When a Mutex actor is the unlocked state then any actor can tell it to lock. Once in the locked state it won't unlock until the first actor tells it to. [2] The counting business is so that one process can lock a mutex several times and then must unlock the mutex the same number of times before it is considered unlocked.

And now a bit of test code. I've modified the original sockmachine test code so that before inserting coins and pushing buttons a testloop must acquire the lock on a mutex and once done must release it.

-module(mutextest).
-export([test/3]).

test(Machine, Mutex, Processes) -> 
  if 
    Processes > 0 ->
       spawn(fun() -> testloop(Processes, Machine, Mutex, 10) end),
       test(Machine, Mutex, Processes - 1);
    true -> io:format("all test processes launched~n")
  end.       

testloop(Process, Machine, Mutex, Count) ->
   if 
     Count > 0 -> 
       mutex:lock(Mutex),
       testzerocoins(Process, Machine),
       mutex:unlock(Mutex),
       testloop(Process, Machine, Mutex, Count - 1);
     true -> io:format("[~w] testing completed~n", [Process])
   end.

testzerocoins(Process, Machine) ->
  case sockmachine:insertcoin(Machine) of
    {nothing} -> testonecoin(Process, Machine);
    {coin} -> 
       io:format("[~w] BONUS COIN!~n", [Process]),
       testtwocoins(Process, Machine)
   end.

testonecoin(Process, Machine) ->
  case sockmachine:insertcoin(Machine) of
    {nothing} -> testtwocoins(Process, Machine);
    {coin} ->
       io:format("[~w] BONUS COIN!~n", [Process]),
       testtwocoins(Process, Machine)
  end.

testtwocoins(Process, Machine) ->
  case sockmachine:pushbutton(Machine) of
    {tubeofsocks} -> io:format("[~w] Got my socks.~n", [Process]);
    {nothing} -> io:format("[~w] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH~n", [Process])
  end.

And here's what it looks like when I run all this

4> c(mutex).
{ok,mutex}
5> c(mutextest).
{ok,mutextest}
6> Mutex = mutex:create().
<0.53.0>
7> mutextest:test(Machine, Mutex, 2).
all test processes launched
ok
[2] Got my socks.
[1] Got my socks.
[2] Got my socks.
[1] Got my socks.
[2] Got my socks.
[1] Got my socks.
[2] Got my socks.
[1] Got my socks.
[2] Got my socks.
[1] Got my socks.
[2] Got my socks.
[1] Got my socks.
[2] Got my socks.
[1] Got my socks.
[2] Got my socks.
[1] Got my socks.
[2] Got my socks.
[1] Got my socks.
[2] Got my socks.
[2] testing completed
[1] Got my socks.
[1] testing completed

Ta da! Fixed my problem!

Kids, Don't Try This At Home

There are better ways to solve this kind of problem with actors. Seriously. Why use a custom mutex when Erlang has a lock built in as described above? Just change the sock machine to not be so stateful, i.e. make it take one message "{From, coin, coin, pushbutton}" and do all the work necessary before returning the tube of socks. Particularly nasty about this manual mutex code is that it's hard to ensure that all code paths will unlock a mutex. If my test code had thrown an exception at the wrong point then the mutex would be left locked. So don't do this. Unless you're evil. Like me.

Conclusions

Erlang's a great language. Actors are a great model. But they are neither race nor deadlock free. That's because, fundamentally, they're all about shared mutable state and locking. If after all of these articles you still don't believe me or you think I'm using the words wrong then please send your comments to dev/null.

In my next article I'll try to pervert Erlang for good rather than for evil and maybe try to explain the frequent observation that "yeah, races and deadlocks can happen with Erlang, but it seems less common than with more traditional shared memory/manual locking mechanisms."

Footnotes

1. Erlangers use the word "process" because of the memory isolation enforced between different actors. I'm using "thread" here to avoid confusion with OS processes. But even here there's confusion because I mean logical threads which may or may not be the same as hardware threads. I've seen a few libraries call this concept "sparks."
2. Or until some third actor spoofs an unlock message from the locking actor.

But, But...You Didn't Mutate Any Variables

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
end

If 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
end

Internally, 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 - 2

This 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 loop

As 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

1. 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.
2. 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.
3. Some people equate state with data, but that's just as bad. Code is data so all code must be stateful - another useless conclusion.

Erlang Style Actors Are All About Shared State

Actors have become quite the popular topic. Besides Erlang, there's a famous library implementation in Scala and at least 3 for Java. But the "no shared state" propaganda is setting people up for failure. In last week's exciting episode I defined both what state is and what it isn't. It is the fact that something responds differently to the same inputs over time. It is not the details of how that is represented. Based on that I can now show why saying that Erlang style actors don't share state is totally wrong headed - that, in fact, if you don't want to share state the actor model is a very clunky way of doing things.

Before I go on, let me emphasize that I like Erlang. I like actors, too. It's a very nifty model. But it's not a stateless model. Let me show what I'm ranting against:

• "The actor model consists of a few key principles: No shared state"
• "Erlang is an inherently stateless system."
• "Erlang does not have [...] 'mutable state'"

The problem is that Erlang style actors can have shared, mutable (changeable), state. The model is all about shared state. If you didn't need to share mutable state then there are better alternatives than actors. And, importantly, even when you are using actors well you must think about all of the problems of shared mutable state. All of them. People who believe the propaganda are in for rude shocks.

The Situation

Last time I described a simple sock tube dispensing machine. Insert two coins, press the button, get a tube of socks. Insert too many coins and you get the extra coins returned. Push the button before you've inserted enough coins and you get nothing. Here's the diagram.

Imagine that Alice and Bob work at Crap Corp. ("Making High Quality Crap Since 1913"). Once a day they each like to saunter down to the break room and purchase a nice warm tube of socks. But, this is Crap Corp. and the machines don't take regular coins but Crap Corp. Coins instead. Each CCC weighs 40 pounds (very roughly 18.1436948 kilograms).

Naturally, Alice and Bob don't want to carry 80 pounds of crappy tokens around with them so they each laboriously drag a token down to a machine, insert it, walk back to their cubicle, grab another and repeat. Now, if Alice and Bob take their sock breaks at very different times that's probably going to work fine. But if they tend to overlap bad things happen. It's possible for Alice to insert her first coin, Bob to insert his first coin, Alice to insert her second coin and get an coin back (BONUS! she cries happily, experiencing the greatest joy she's ever experienced at Crap Corp.) So Alice pushes the button, gets her tube of socks, and merrily skips back to her cube. Well, maybe not skip exactly, but whatever you do when you're ecstatically happy while carrying 40 pounds of crap.

Then Bob shows up, inserts his second coin, eagerly smashes the button to get his well deserved tube of socks and ... gets nothing. Feeling cheated he pounds on the machine, kicks it, shakes it, and rocks it back and forth. Inevitably, the machine tips over, falls on Bob, and crushes him with all the tons of Crap Corp. Coins that have been inserted over the weeks. A tragic ending for somebody who just wanted some socks.

Now, that outcome isn't guaranteed even if Bob and Alice start about the same time. On the way to inserting her first coin Alice could be waylaid by the boss looking for his TPS report. As Alice patiently explains that a) TPS reports were never her job and b) they were discontinued three years ago and c) her eyes are on her face not her chest, Bob could have merrily taken the two coin trips and safely received a tube of socks without ever knowing the mortal injury he narrowly avoided.

Finally, Some Damn Code

Any time something unwanted can happen as the result of unpredictable delays, scheduler priorities, workload, etc you have a race condition. What could be more unwanted than being crushed by a vending machine? And what could be more unpredictable than a pointy haired boss? We can write this up exactly in Erlang.

In a file called sockmachine.erl. First, a little standard module definition and export business.

-module(sockmachine).
-export([start/0, insertcoin/1, pushbutton/1, test/2]).

Here are the guts of the machine. zerocoins(), onecoin(), and twocoins() are the states of the machine. When one is called it blocks, waiting for an message in its inbox. Based on the message it gets it responds with {nothing} if nothing happens, {coin} if it needs to return a coin, or {tubeofsocks} for the win. It also then calls the appropriate function for the next state - which might be the same state. These are all private functions not exported by the module. Note, there are more clever ways to write this - but for explanatory purposes I like this.

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.

Start spawns a new sock machine actor in the zerocoins state

start() -> spawn(fun() -> zerocoins() end).

insertcoin and pushbutton are rpc style convenience functions that insert a coin or push the button. Or did I get that backwards? Well, whichever, they each return whatever they recieve as a message back from the machine.

insertcoin(Machine) -> 
   Machine ! {coin, self()},
   receive X -> X
end.

pushbutton(Machine) -> 
   Machine ! {button, self()},
   receive X -> X
end.

Test spawns as many concurrent test loops as requested to simultaneously pound one machine.

test(Machine, Processes) -> 
  if 
    Processes > 0 ->
       spawn(fun() -> testloop(Machine, 100) end),
       test(Machine, Processes - 1);
    true ->
       io:format("all test processes launched~n")
  end.       

Testloop repeatedly walks through the cycle of inserting 2 coins and pushing the button. It calls helper functions that mirror the state of the sock machine to show what it expects to happen at each step, complaining when things don't go well.

testloop(Process, Machine, Count) ->
   if 
     Count > 0 -> testzerocoins(Process, Machine,Count);
     true -> io:format("[~w] testing completed~n", [Process])
   end.

testzerocoins(Process, Machine, Count) ->
  case insertcoin(Machine) of
    {nothing} -> testonecoin(Process, Machine,Count);
    {coin} -> 
       io:format("[~w] BONUS COIN!~n", [Process]),
       testtwocoins(Process, Machine,Count)
   end.

testonecoin(Process, Machine, Count) ->
  case insertcoin(Machine) of
    {nothing} -> testtwocoins(Process, Machine,Count);
    {coin} ->
       io:format("[~w] BONUS COIN!~n", [Process]),
       testtwocoins(Process, Machine,Count)
  end.

testtwocoins(Process, Machine, Count) ->
  case pushbutton(Machine) of
    {tubeofsocks} -> io:format("[~w] Got my socks.~n", [Process]);
    {nothing} -> io:format("[~w] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH~n", [Process])
  end,
  testloop(Process, Machine, Count - 1).

Now fire up erl, compile, start a machine, and test it with only 1 running test loop

1> c(sockmachine).
{ok,sockmachine}
2> Machine = sockmachine:start().
<0.38.0>
3> sockmachine:test(Machine,1).
all test processes launched
ok
[1] Got my socks.
[1] Got my socks.
[1] Got my socks.
[1] Got my socks.
[1] Got my socks.
[1] Got my socks.
[1] Got my socks.
[1] Got my socks.
[1] Got my socks.
[1] Got my socks.
[1] testing completed

Ah, sweet, sweet success! But now run another test with 2 concurrent test loops. 1 = Bob, 2 = Alice...or was that the other way around?.

4> sockmachine:test(Machine,2).
all test processes launched
[2] BONUS COIN!
[1] BONUS COIN!
ok
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] BONUS COIN!
[1] BONUS COIN!
[2] Got my socks.
[1] Blasted machine ate my money! Give it to me!  Rattle, rattle, ARRRGGHGHHRHRHGH
[2] testing completed
[1] testing completed

It's a litany of socks, bonus coins and crushed intestines. On my machine it's an oddly predictable litany, but in a real, distributed Erlang app it would be much more interesting and random litany as network delays would emulate pointy haired bosses even better than Erlang's scheduler.

Some Last Notes

With Erlang style programming, actors are the central unit of statefulness. Multiple actors can share access to one stateful actor. Hence shared state, race conditions, and ruptured spleens. Am I saying that Erlang or actors are bad? No, in fact I quite like them. What the Erlang model does very nicely is separate that which must be stateful because it is concurrent from that which is more pure computation. By making state so much more painful to write than "foo.x = foo.x + 1" the actor model encourages you to think about the consequences of sharing it. It also cleanly mirrors the mechanics of distributed computing and asynchronous IO. It's nice, but it's not stateless.

One last note. I started with "actors are all about shared state." Naturally one might ask "well, what about stateless actors - actors that don't change state or depend on state via IO?" Certainly those are viable uses of actors. But that's no longer concurrency, that's parallelism and IMHO futures, data flow variables, and Haskell's data parallelism are all cleaner ways to deal with parallelism. Someday soon I hope to write about them. In the meantime, the whole point of having the complexity of message passing instead of those simpler mechanisms is precisely to deal with the complexity of concurrent state.

One really last note. Sadly, simple straight up actors don't automatically compose very well. You can design a set of actors that interact correctly for one use case but that don't interact at all well when plugged into a different system. This is another aspect that actors share with traditional manual locks and shared mutable memory. To date the best known way to deal with composable state is transactions (optimistic, pessimistic, distributed, compensating, software, hardware, database, whatever). There are very nice transactional capabilities available for Erlang, but this is yet another area where the "no shared state" mantra can lead people to think that actors are the entire answer without needing anything else.

Try not to get crushed and good luck with your socks!

Postscript

It has been suggested in the comments that when people say that Erlang style actors don't share state they mean it doesn't share memory. First, I clearly defined state in the previous article as being different from its representation. But, just as importantly, I think that saying "we don't share memory" is a distinction without much relevance. It's mostly an implementor's point of view that doesn't reflect how a user must think about actors.

Here's some Erlang code for simple shared mutable variables. This isn't recommended Erlang usage, but it doesn't break the model in any way.

-module(variable).
-export([malloc/0, fetch/1, store/2]).

malloc() -> spawn(fun() -> loop(0) end).

loop(Value) ->
   receive
       {fetch, From} ->
           From ! Value,
           loop(Value);
       {store, NewValue} ->
           loop(NewValue)
   end.

fetch(Variable) -> 
   Variable ! {fetch, self()},
   receive X -> X end.


store(Variable, Value) -> 
   Variable ! {store, Value}.

And here's me using it.

1> c(variable).
{ok,variable}
2> X = variable:malloc().
<0.38.0>
3> variable:store(X,42).
{store,42}
4> variable:fetch(X).
42
5> variable:store(X, variable:fetch(X) + 1).
{store,43}
6> variable:fetch(X).
43

And, since these variables are actors they are just as easy to share as my sock machine example.

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.

The Door to User Interface Design

A common tenet in user interface design is to be consistent, especially to be consistent with de facto standards. It's certainly a good goal, but I think that kind of consistency can be pushed too far. I recently thought of some real world examples: humble, ordinary, every day doors.

Doors share a common functional requirement: be closed sometimes and be open others. That leaves a lot of room for design though, like what color should it be? Or, more importantly, which way should it open?

The De Facto Standard

Doors in offices, bedrooms, bathrooms, etc. tend to open inwards. Why? Because a bathroom door opening outwards could suddenly thrust a large solid object into a public walkway. Black eyes, broken noses, and other hilarity ensue.

The Exception

There's a major exception to this rule. Public places where there are likely to be crowds like stores tend to have doors that open outwards. Why? Because a dangerous fire is far more likely to occur inside than outside, and if one did occur then a rushing crowd could jam an inward opening door closed. Panic, trampling, and other hilarity ensue.

The Exception to the Exception

There's a major exception to the exception to the rule. An airliner is certainly a crowded public place where you would want to quickly get people out in an emergency. Yet the door opens inwards. Why? Because at altitude the airplane will be pressurized. The inside pressure will be significantly higher than the outside and must be contained. The doorway is a significant weakening in that containment, but a door that opens inwards works just like a drain plug. The pressure difference keeps it firmly sealed and in place. A door that opened outward would be very likely to, um, open outward. Ejected flight attendants, hypoxia, and other hilarity ensue.

The Take Away

De facto standards are good and often have good reason to exist. But they don't always apply. Exceptions and exceptions to exceptions sometimes make more sense. Following a standard is no substitute for doing actual design.