Does side-effect-free programming with persistent data-structures on share-nothing, actor-based architecture, in other words Erlang is qualified to be lock-free?
It seems that Haskell also doesn't exist.)
It seems that Haskell also doesn't exist.)
%Here is a function that rather idiotically takes a process
%id, a message, and just sends the message to the process,
%in Erlang, and then returns the atom 'ok'.
send_message(Pid, Message) ->
Pid ! Message,
ok.
But obviously that is not the case; we are expecting the process that Pid corresponds to to receive that message, and to do something with it.
The very act of sending a message is a side effect.
On the other hand, non-networking procedures in Erlang are pure functions, so they could be safely evaluated in parallel. Its spawned processes are isolated, they share nothing, not even a common stack, so they could fail and being restarted without affecting any other code or data.
It is much better to read Armstrong's thesis where he gives outline of the design of Erlang, hows and whys. It might has a bit ugly syntax, but semantics are fine.
But being lock-free doesn't necessarily mean better or even faster.
Even working with persistent data structures as in Clojure is not usually considered to be lock-free (even though there are no locks involved, no mutation is taking place). But Clojure does support lock-free programming, for example with atoms.
According to classic maxima, the way you structure your data influences the shape of your procedures, that is why list procedures are naturally recursive.
Similarly, if you have no destructive operations, you could partition your data any way you wish, and process the parts in parallel, this is, for example, how make -j4 works. As long as your obj files share nothing they could be build in any order and in parallel.
The idea is that parallelism begins from how you structure your data, and hardware primitives are of much less importance. 10 threads updating one global variable is a disaster no matter what.
Sure, but again, you're talking high-level. At a low-enough level, every operation is destructive, because that's how our machines work. If you're using immutable data-structures, then you're allocating memory, so you are bumping (destructively) some heap pointer. Even if that pointer is thread-local, sooner or later some garbage collection will take place, which requires some form of synchronization.
The idea is that somewhere in your software stack, be it the OS or the JVM or whatever, there will be shared mutable state, and that's where lock-free data structures are handy. Some high-level languages abstract that away from you so you don't have to deal with this stuff.
Also, parallelism is only part of the story. Parallelism, or data parallelism, divides the data so that it can be processed cooperatively in parallel, but that's not always what you have. Lock-free data structures are useful when doing concurrency rather than parallelism, i.e. lots of different computations (rather than one), competing for (rather than cooperatively sharing) limited resources.
Erlang is certainly not lock free - I'll use a Scala/Akka example since I know it better than Erlang:
class DiningPhilosopher(leftForkHolder: Actor, rightForkHolder: Actor) extends Actor {
leftForkHolder ! ForkRequest
def receive = {
case ForkFromLeft => {rightForkHolder ! ForkRequest; ...}
}
}
I think stream based programming without loops (i.e., the stream processes form a digraph) will generally be lock free.
http://james-iry.blogspot.de/2009/04/erlang-style-actors-are...