Scala vs Clojure – Round 2: Concurrency!
17Sep09
*** BLOG HAS MOVED ***
Dear visitor,
This blog has MOVED entirely to: http://blog.bestinclass.dk
This site will no longer be updated so please change your bookmarks and RSS subscriptions accordingly.
Thank you all for your time and comments,
Lau
*** BLOG HAS MOVED ***
Filed under: development | 22 Comments
Tags: actors, clojure, concurrency, scala, stm
I think your comparison suffers from having to little Scala knowledge compared to clojure knowledge.
For example if you want a more concise style with actors you can write them like this.
import scala.actors.Actor._
val world = actor {
receive {
case x => println(x)
}
}
world.start()
world ! “hello”
And if you want a no compromise functional language, just use Haskell and don’t bother with the OO baggage of the JVM
.
It’s worth noting that Clojure also has Actors, which possibly make more sense for this problem that STM.
You’re not comparing Clojure and Scala, but STM and message passing concurrency – so the tilte looks misleading.
Did you take a look at Akka?
The main difference I see is, Scala does actors in libraries (and does STM in libraries, see Akka) while Clojure does STM in the language. Doesn’t take anything away from the great job Rich did.
Otherwise very good post,
Cheers
Stephan
http://www.codemonkeyism.com
(second short remark).
Essentially this compares a drill and saw – which one is better to drive nails in a wall.
Using a hammer (Queue, Master/Worker) would be best for this problem, not a drill (STM) or a saw (message passing).
Cheers
Stephan
@mkneissl: I think a common response to all articles regarding a language is a flurry of suggestions for more concise/idiomatic examples. I opted to go with code that was official and in print, not wanting to claim to be a Scala expert.
We always come back to this one central thing: Whatever the language defaults to, is what the lowest common denominator will be. If the default is mutability, people will mutate values.
@Brett: Good observation and you’re completely right!
The reason I flaunted the STM (which is overkill) was because I wanted to show the key differences between non-distributed systems and distributed systems.
In the Clojure code, you have a lot of debug/print statements inside transactions. I believe this is a problem, because if the transaction retries, the message could print more than once.
One solution is to set up a debug-message-printing agent that just prints messages to the screen. By using the agent to print your messages, the printing is delayed until the transaction completes.
But there’s a whole other approach that is worth considering. If you look at the O’Reilly Scala example, there are also print statements for when a customer finishes his haircut. But this reveals problems due to the asynchronous nature of agents, e.g.,
[b] cutting hair of customer 1
[b] cutting hair of customer 2
[c][/c] customer 1 got a haircut
[c][/c] customer 2 got a haircut
Notice that customer 2 is reported as getting a haircut before customer 1 is reported as finished. This violates the spirit of the problem that the barber can only cut the hair of one customer at a time. I suspect that the Clojure version would be similarly flawed.
So right off the bat, you can see that actors/agents aren’t really a great solution for this problem, if one of the objectives is to make sure that at every instant the world is in a consistent state.
In Clojure you can take another approach, eschewing agents altogether. You could represent each customer as a ref containing a state (planning to go to the shop, entering the shop, sitting in a seat, getting haircut, leaving the shop). You could represent the barber as a ref containing a state (sleeping in chair, setting up for customer #n, cutting hair of customer #n). And you could represent the queue of seats as a ref (as you are currently doing). Then you could attach watchers to all these refs to print out any state changes, and handle the appropriate logic (for example, when a customer changes from planning to go to the shop to entering the shop, the logic is triggered that determines whether he sits in a seat or is forced to leave the shop). Start the simulation by starting a number of different threads responsible for waiting the appropriate time before changing the customer’s state to entering the barbershop. The simulation then flows from these state changes triggering watchers, which in turn may trigger other state changes (possibly using threads that sleep for an amount of time to delay certain state transitions).
I believe that with this ref-based approach you end up with an even more robust simulation in which consistency is guaranteed to a degree that you simply can’t achieve with agents. It’s also a great demonstration of how you can mutate a lot of different pieces of state from different threads, and keep them all carefully in sync via STM.
As an example of this approach, you can look at my ref-based implementation of the similar, but more complex, “Santa Claus problem”.
http://paste.lisp.org/display/79744
Whoops, the “customer” lines above got interpreted as a code block. Well, you get the idea.
@Mark: Awesome comment.
You are right on the money in terms of how to write a solution which is well suited this problem. Also a good catch on the debug statements. Yes on solution would be to send them to an agent, but truthfully I/O should be entirely avoided in dosyncs. You solutions looks good and the documentation is almost that of a tutorial, so it’s a recommended read!
You might also want to checkout Christophe Grand’s (legend of the legends in functional programming) revised version of my solution http://gist.github.com/189002
Thanks for stopping by!
One more point here about the ref-based approach I propose is that you could easily imagine hooking a GUI up, via watchers, to the various ref-based states. For example, one windows shows you who is sitting in what seats in the seat queue, and what the barber is doing. Another window shows you the state of all the customers. And it would all be in sync. There would be no instant where, for example, the customer thinks he is “sitting in a seat”, but the seat doesn’t yet show itself as being occupied by the customer. That’s because both these state changes would be part of the same transaction.
Mark,
I think it’s simpler to have the GUI to periodically snapshot the refs rather than to have watchers trigger GUI updates. And it’s likely to have a better behaviour under a high update rate.
Mailboxes aren’t queues, they’re blobs of pending messages which do not make delivery order guarantees. If you want guarantees they have to be made inside an actor.
I would have made the seats themselves an actor, which gets messaged a customer and makes a non-blocking accept/reject decision immediately, and the barber an actor which loops polling the seats for the next customer (using an explicit request, response protocol so it simulates blocking).
Result:
- Barber asks seats for customer. Seats set barber sleeping flag.
- 1 appears, seats forward 1 to barber and clear sleeping flag
- Barber starts cutting 1
- Customer 2, 3, 4, 5, 6 show up
- Seats accept 2, 3, 4 and turn away 5 and 6
- Barber finishes cutting 1
- Barber asks seats for customer. Seats respond immediately with 2 and will accept the next customer who arrives.
Here is an innocent Erlang try from an Erlang newbie. (I hope I get the problem described in the post right.)
shop(AvailSeats, BarberPid) ->
receive
{BarberPid, done} ->
io:format(“One seat more!~n”),
shop((AvailSeats + 1), BarberPid);
{CustomerId, seat_req} when AvailSeats > 0 ->
BarberPid ! {self(), CustomerId},
shop((AvailSeats – 1), BarberPid);
{CustomerId, seat_req} ->
io:format(“(s) turning away customer ~p~n”, [CustomerId]),
shop(AvailSeats, BarberPid)
end.
barber() ->
barber(0).
barber(HairCuts) ->
receive
{ShopPid, CustomerId} ->
timer:sleep(100 + random:uniform(200)),
io:format(“(b) cutting hair of customer ~p~n”, [CustomerId]),
ShopPid ! {self(), done},
barber(HairCuts + 1);
hair_cut_count ->
io:format(“~p hair cuts completed so far.~n”, [HairCuts]),
barber(HairCuts)
end.
customer(0, _ShopPid) ->
ok;
customer(Customers, ShopPid) ->
timer:sleep(100 + random:uniform(200)),
io:format(“(c) entering shop ~p~n”, [Customers]),
ShopPid ! {Customers, seat_req},
customer((Customers – 1), ShopPid).
main(AvailSeats, Customers, MilliSeconds) ->
BarberPid = spawn(barber, barber, []),
ShopPid = spawn(barber, shop, [AvailSeats, BarberPid]),
customer(Customers, ShopPid),
BarberPid ! hair_cut_count,
timer:sleep(MilliSeconds),
exit(ShopPid, ok),
exit(BarberPid, ok),
ok.
bug: in contrast to “<-", which is syntax, "!" and ":/" are just methods with weird names. and please don't forget it takes some time to learn _not_ to read all the () in lisp code, too.
Excellent series of articles. I fooled around some with Scala a few months back, but had some criticisms about the quality of documentation, and as you mentioned above, the syntax is quirky. If you are interested, you can view my impressions of scala here.
Anyway thanks to your posts, I’m going to have a look at Clojure. I’ve been pretty immersed in the Java and php world for too long and am really missing the clean style of lisp.
It’s also interesting to see a consultancy that only works on Clojure projects. I would be interested in seeing some case studies of different Clojure projects you have done (if your clients don’t object).
Volkan – I think there are bugs in your code. For example, you forget the initial (maximum) AvailSeats, so the value can grow with the number of completed customers (as if they each leave an extra chair in the waiting room when they leave
Mik
I have put an Erlang version here:
http://snipt.org/ngni
Mik