Polymorphic Typist: Erlang

Showing posts with label Erlang. Show all posts

Tuesday, March 26, 2013

The Case for a Concurrency-oriented VM

In the following, I’ll describe the background for my current long-running project - why I believe it to be a worthwhile endeavour.

The overall line of thought goes like this: concurrency and concurrency-oriented languages are important; we have such languages, but they are few and far between; there exists a non-CO ecosystem (the one around the JVM) which has spawned dozens of languages and allows those languages to cooperate and prosper; which factors have been significant in creating this ecosystem, and how can they be harnessed to improve conditions for concurrency-oriented languages?

We begin at concurrency and how programming languages deal with it.

Concurrency and languages

A fair number of the programs we use every day are doing more than one thing at a time. Every web server, smartphone app, GUI application, operating system, chat server, VoIP system, game server, music player, video player, etc. that you’re using are concurrent programs - either in the sense that they are serving multiple users at once, or in the sense that they have multiple asynchronous event sources they have to react to in a timely manner.

Yet most programming languages - and about all mainstream languages - aren’t very well geared towards making concurrent applications. The programming paradigms one hears most about these days are the Object-oriented and the Functional paradigm. Ever heard of Concurrency-oriented languages? They exist, but there aren’t very many of them - and they are not mainstream but something you have to actively seek out.

What do I mean by being concurrency-oriented, or "geared towards concurrent applications"? (I’ve touched upon this question earlier.)

A number of languages with concurrency support are not much more than a sequential language with threads and locks added. This is not enough to qualify for being a concurrency-oriented language; to be that, you have to take the issues of concurrency seriously. If you take a convential imperative language and add threads, you’d have to subtract something as well.

A typical example of a language-with-threads is Java. Java is an object-oriented language first and a concurrency-supporting language second, at best. Like most languages-with-threads, concurrency support mainly comes as an addition, an afterthought, with a library-ish feel. Sure, the Java syntax contains concurrency-related things - mainly synchronized and volatile - but nothing forces you to use them. You can write a program embodying all of the concurrency pitfalls known to man, and neither compiler nor runtime will object in the slightest.

There are rules about when the concurrency primitives are used safely. They come in the form of the Java Memory Model and Thread Specification, which states what the guarantees are and how to avoid »Surprising behaviours«.^[1]

To be sure, explicitly stated guarantees is a Good Thing. But consider a world in which the type safety of Java amounted to a document stating how to avoid type errors. No static checking, no run-time checking, just rules about when you’re safe…

Smells a lot like C, right? Replace type errors, initialization errors, and memory mismanagement faults with data races and deadlocks - and lack-of-strong-typing becomes lack-of-proper-concurrency-support. Except that whereas the former kind of bugs are more or less deterministic, the latter kind seldom is. Which means that a) it is harder to debug, b) it can not be guarded against by unit tests, and c) the place where you’re likely to discover it is in production.

And just like we’re much better off with the enforced type safety of Java (nobody misses the segmentation faults which are common when developing C or C++ programs), so we’re better off when the language provides some actual guarantees in the face of concurrent activities.

And languages can do that. A language like Erlang, for example, is concurrency-oriented first and functional second - and it shows. Other examples include Oz, CML, Rust, and Clojure (Haskell probably also qualifies these days); each solves the problem of providing safe concurrency in its own way.^[2]

But these languages are each isolated efforts, and they are not mainstream. Which means that they each must struggle on many fronts: evolving syntactically and semantically; keeping up with hardware and OS evolution; providing libraries for the expected functionality of the changing times; and fighting for developer mindshare.

The success of the JVM

Which brings us to the happy ecosystem centered around the JVM.

The Java Virtual Machine is thriving - to the point where it might outlive the language it was originally created for; while Java the language is evolving only slowly, - the JVM is the center (qua facilitator) of a wholly different level of evolution: a multitude of languages of all sorts of paradigms, domains, typing strategies and syntactic styles are targeting the JVM.

Though the VM was originally designed for just one language - Java - it has proven so convenient to generate code for that many language implementers have chosen to do just that. (I’ve done it myself on more than one occasion.)

Why is that?

For one thing, the JVM is well-specified. Its specification is public and the rules are clear and make sense. Second, part of those rules are embodied in the bytecode verifier - a validation step performed on code when it is loaded into the JVM. Thirdly, the existence of the public specification has meant that the Java language and the JVM implementation(s) have been decoupled (more or less) with respect to their evolution. Java the language has been able to evolve quite a bit without the VM spec changing much (The addition of generics being one example), and the VM on its part has been able to evolve quite much performance-wise. (Besides, several competing VM implementations have come to exist.)

And the HotSpot implementation of Java is a solid piece of software engineering which has put to shame the "interpreted languages must be slow" prejudice, making it a thing of the last century.

What does these things mean for compiler writers targeting the JVM?

Targeting a statically checked bytecode format is a blessing, because many of the most difficult-to-debug kinds of error are revealed at load time, instead of resulting in mysterious memory corruptions. Bytecode verification enforces some useful invariants, reducing debugging time.

Targeting a mature VM yields performance and portability benefits - "write once, run anywhere" is attractive for language implementers as well as application developers.

Consider all the languages which run on the JVM, some of them available only on that platform.
Without that virtual machine, or something else playing the same role, would we have had so many new implementations of such a variety of languages, of such a level of maturity, performance and portability? And provided with such a wide range of libraries?

Most probably not.

The task of implementing a native code generator for just a single platform, along with runtime libraries and a decently performing general-purpose garbage collector, is not trivial.^[3] The number of man-hours which could have gone to debugging segmentation fault and similar mysteries, and to implement just the basic libraries for the new languages, but which have instead been channeled to progress in other areas, are significant. Small wonder that Microsoft chose to copy Java and make their own common cross-language platform (.NET).

Finally, apart from development of compilers, the well-defined-ness of the Java bytecode format has meant that a number of other byte-code processing tools have come to exist: tools for analysis, transformation and instrumentation of Java bytecode.

In summary: The JVM has been, and is, a great facilitator; this is especially due to its general usability, public specification, fine performance (especially after HotSpot), and - not least - bytecode verification following well-defined and well-understood rules.

The shortcomings of the JVM

But the JVM design has drawbacks as well. Some are general nuisances, some are just annoying to compiler implementers targeting the JVM, and some cause it to be less than ideal for languages belonging to certain paradigms. Some are visible to Java developers, others are purely technical.

Issues for language implementers

First of all, the JVM smells of Java.
In a number of ways, the design of the virtual machine would have been different if Java - especially the early versions of Java - had been different.

The JVM is quite class-centric, for instance - the unit of loading and verification is the class. The only kind of type definition is the class. For language implementers, this is a source of mild annoyance: translating most kinds of simple code is simple, but the moment the code uses a new record type, or variant type, or function object, or a function needs to return multiple values - it translates into adding a new separate class file to the compiler output.

The JVM is statically typed - but has no parametrized types. Therefore, type safety breaks slightly every time one of the common container classes from e.g. java.util is used, so runtime checks must be performed. This is because Java prior to 1.5 (where generics where introduced) was poor on this point.
Furthermore, the JVM instruction set has a type check instruction and a type cast instruction - but no "check-and-cast" instruction. I can only assume that this is because Java doesn’t have a language construction such as "type case", but only the combining idiom "if (x instanceof T) {T y = (T) x; …}". Presumably, this pattern is recognized and simplified internally in the common JVM implementations.

JVM methods are limited to 64KB worth of bytecode. While this is rarely a limitation for hand-written Java code, it is occassionally a problem for machine-generated code. (In Erjang, for example, we hit the limit for one version of the interpreter, and also (if memory serves) when compiling one particular Erlang module into Java bytecode.)

A special case of this is that large literals simply can’t be used, because in the Java class file format, a literal value are represented as the sequence of instructions it takes to build the value. Try compiling a literal array of, say, 12,000 elements - at four instructions per array slot, this exceeds the method-length limit, and the compiler quits with the message "code too large".^[4] Certain table-driven algorithms would therefore also be hit by the limit.

The implications for language implementers are that a) one likely kind of candidate for hitting the method-length limit is interpreter loops, and b) compilers to JVM bytecode should know about and handle the limit — which gives rise to a tough implementation decision: just detecting when the limit is overrun and aborting the compilation is an honest, but abstraction-breaking solution; working around the limit in general is presumably possible, but introduces undesired (and seldomly needed) complexity.^[5]^[6]

Issues related to concurrency

A related problem is JVM’s bad immutability guarantees. Specifically, there is no such thing as an immutable array. If a part of your code is given an array, or provides public access to one it its arrays, then it can’t assume that other code parts won’t modify the contents of the array at a later point.
Literal arrays are no exception: a VM implementation can’t perform constant folding of lookups into a literal array until it’s proven that that array can’t be leaked to somewhere where it might be mutated; a property which can only be established by inspecting the entire scope of the variable.

The JVM’s support for (shallowly) immutable variables comes in the form of the final field modifier. The intuition of this modifier is simple enough: a final field can be set only once, and must be set before its first use, so it should have the same value throughtout its lifetime.

But in reality, things are a bit more complex - the field modifier has its warts:

Certain final fields may be inlined at compile time - even across classes, which has the potential for causing surprising inconsistencies.
Even fields declared final can be modified though reflection(!) - which, of course, doesn’t affect those accesses which have been inlined at compile-time (I believe you could call this a surprise within a surprise).

There’s another case where the "final fields always have the same value" rule is broken: Final fields can be observed before they gain their value.
That abstraction breakage is demonstrated in the following program:

public class JavaFinal {
    final static Object x = JavaFinalHelper.create();
    public static void main(String[] args) {
        System.err.println("Main: x = "+x);
    }
}

class JavaFinalHelper {
    static {
        System.err.println("Helper: x = "+JavaFinal.x);
    }
    public static Object create() {return new Object();}
}

Here, the helper class’s static initializer is run before JavaFinal.x has been set - exposing the null value that field has before it is initialized.

Thus, certain should-be-invariants aren’t.

Finally, and most importantly in this context, there are the shortcomings in the concurrency department.

The JVM provides no checking of the sanity of concurrent access patterns. Java’s static type system which is the basis of the bytecode verification is static in more than one sense: It doesn’t take time into account. If you ever get hands on a reference to an object, then you can at any later point call any (visible) method.

In concurrent systems, concepts like life cycle, ownership, sharing and thread safety become important. The JVM doesn’t provide much support for dealing with these. For that matter, attention to these concepts is important in general for defining library boundaries - which assumptions the library and the library client can make about values passed to and from the library. Quite often, thread safety and access timing questions aren’t addressed by Java libraries' API documentations; Javadoc makes it easy to document the static types involved, but certain questions about the dynamics are not often answered.

From an Erlang point of view, such a thing as thread-local garbage collection is also desirable. I have a hypothesis that no sanely structured concurrent programs genuinely need a globally-GC’ed heap. Whether that is true or not, for global GC you either pay the price of occasional slow major garbage collections - which cost in latency - or, if your garbage collector is sufficiently advanced to do its work incrementally or concurrently with the mutating threads, pay the price of inter-thread synchronization necessary for this to work - which costs in throughput.

For the matter of this text, the verification aspects are the central points.

To sum up: The JVM lacks verification support for such things as sanity of concurrent accesses and immutability/read-only access privileges. As far as concurrency-orientation is concerned, these areas present room for improvement.
And I am not aware of any other generally targetable VMs which fare better in these respects.

The shortcomings of the BEAM

The primary contender for the title of Concurrency-orientated VM is probably the one for Erlang, which is called BEAM. The flavour of concurrency-orientation provided by BEAM includes immutable data structures, shared-nothing actor-based concurrency, light-weight processes, and process-local GC - and a few specific forms of destructive updates.

In some ways, it is very much like the Java VM: It has a mature implementation, was originally intended for just one language, comes from industry (as opposed to academia), and started out as purely interpreted but later grew optional native compilation.

But in other respects, it is very different:
While the JVM has had a public specification at least since 1999, BEAM hasn’t got a complete specification - public or not.^[7]

The most complete instruction set reference I know of is this historical paper, written in 1997 but first released 2012 (prompted, I think, by the 2012 mailing list discussion). And that one only documents the internal representation, not the (somewhat different) instruction set used in BEAM files.

This lack of a specification has consequences:

As for BEAM code producers: While other languages than Erlang have been developed for BEAM, none produce BEAM code directly - instead, they target an intermediate representation of the Erlang compiler and use that compiler’s backend for producing actual BEAM code.
As for BEAM consumers: Until fairly recently, no other BEAM VM implementations existed but the official one from Ericsson.

The consumer situation has changed a bit; people have begun making other implementations such as Erjang, Browserl and Ling (which run on, respectively, JVM, Javascript, and bare metal).

But the lack of a specification - a clear definition of what is and what isn’t allowed - means that there are differences in what the implementations can run.

At least two example of this are known to me:

Erjang assumes that exception handlers are set up in a execution path independent manner. While this is presumably true for code generated by the Erlang compiler, I can imagine BEAM code in which this isn’t the case, and which the official BEAM implementation will run cheerfully, while Erjang will balk at it.
There is a gotcha hidden in the external instruction set - there are nine instructions for calling functions: three for local calls (call, call_last, call_only - depending on whether it’s a tail call, and whether there’s a stackframe to deallocate); three for external calls (call_ext, call_ext_last, call_ext_only); two for calls with dynamic module and/or function name (apply, apply_last); and one for calling function objects (call_fun).

Can you guess what the trap is?

Erlang is a language with guaranteed proper tail recursion, but the only instruction for calling function objects is a non-tail-call.
How can that work??

By cheating. The official BEAM rewrites the instruction set used in BEAM files into a richer instruction set used internally. The rewriting rules contain a rule which recognizes the instruction sequence "call_fun; deallocate; return" and rewrite it into the internal tail-call version of call_fun.

The Erlang compiler, obviously, is in on the joke, and generates code accordingly.

This call_fun gotcha was one that both Erjang and Browserl missed. I only discovered it accidentally, and fixed it in Erjang, but as far as I can tell, Browserl doesn’t handle that corner case (yet).

So: a clear, public specification does matter. A specification backed by a formal checking mechanism such as a bytecode verifier is even better.^[8]

From a "multiple different languages on one VM" viewpoint, there are of course other issues as well - for instance, the BEAM is rather Erlang-centered.

No in-process destructive updates are supported - even where it would be safe.
Only the concurrency primitives needed by Erlang are present - and the form in which they are present is so high-level that there is very little flexibility for other languages to be very non-Erlang. A process can’t have more than one inbox; the set of supported transactions on tables are fixed; binaries support efficient appending but not prepending; and so on.

In summary: The BEAM is a mature, well-tuned, and actively evolving VM for running Erlang programs, but lacks probably the flexibility and (as things stand) certainly the well-defined-ness necessary for it to be viewed as a general platform for concurrency-orientated languages.

What would a concurrency-oriented VM look like?

If the JVM isn’t it, and the BEAM isn’t it, what would a concurrency-oriented VM then look like?

The BEAM offers concurrency safety, in that it does not allow^[9] shared mutable state without clearly defined transactions; this is a property we want.

The JVM guarantees the absence of certain kinds of errors, because its rules make the necessary invariants locally verifiable. We also want that. More specifically, the rule should guarantee against not only type errors, but also concurrency-related errors (data race conditions).

The JVM also enforces these invariants by verifying code at load time - rather than trust the compiler to generate only valid code. We want that, too - because we intend for there to be more than one compiler, for more than one language.

Both the JVM and the BEAM support "native functions" - functions implemented in C or similar - e.g. for interfacing with third-party libraries or for performance-sensitive parts of a program. It would be foolish to constrain the applications of a new VM by not supporting this. However, the aim should be to encourage as much as possible to be written in a concurrency-safe language - i.e. while library integration would be a good reason for using native functions, performance shouldn’t be; there should not be things which are inherently slow to implement on the VM.^[10]

Thus, while the rule "all data structures are immutable" (as known from Erlang) makes it easy to guarantee against data races, it is not good enough - it either makes it impossible to implement certain things efficiently, or encourages diving into a lower-level language to escape the rules. We want a bit more generality than that, also for the sake of supporting other paradigms than Erlang’s - mutating operations should be supported as long as they are safe and can be proven (reasonably easily) to be so.

For example, one step up, we have the rule "all data structures which are ever visible by more than one process/thread to another must be immutable", which is much more flexible yet also guarantees against data races (and can be made locally verifiable). Even higher up that ladder, shared mutable data are allowed, as long as proper synchonization is in place.

The design I have in mind is based on the concept of linear types, which appear to be a good match, in that they make it possible to capture lifecycles of objects in the type system - which goes a long way towards making certain concurrency-related guarantees locally verifiable (because half of concurrency is timing).

I plan to elaborate on linear types and their use as basis for a VM in future posts.

Acknowledgements

I would like to thank Peter Mechlenborg and Thomas In Sook Holmen for their help with forming this text.

[1] This is the place where you learn that if you have one thread writing a long or double value, and another thread reading it, the JVM implementation is allowed to let the reading thread see half-updates - where the two words of the read values come from different writes.

[2] Go and CML do allow shared mutable memory and thus are not strictly data-race safe; they do, however, encourage communication to be done in other, safer ways.

[3] Admittedly, LLVM has come along in the meantime, promising to relieve some of that burden.

[4] Technically, the compiler could handle large literals by splitting the initialization into two methods, or - for integers - maybe even initialize the array based on a string constant. But apparently the Java compiler has been taught no such trick.

[5] The Scala compiler (as of version 2.9.1) handles large literals in the same way as Java - except that it does not detect when the resulting method is too long; the resulting class file is rejected by the JVM at load time.

[6] When developing Erjang, we ran into the limit both when writing the (machine-generated) interpreter and when compiling an Erlang module containing a particularly complex function.

[7] The question of the BEAM spec has come up multiple time on the Erlang mailing lists, for instance in 2003, in 2007 and in 2012 - see erlang.org/pipermail/erlang-questions/2012-May/066628.html.

[8] The Erlang compiler has a verifier in its backend, which does certain sanity checks on the generated code - but it is not complete, nor is it meant to be.

[9] Except through the use of native functions (NIFs) or similar.

[10] For preference, there should be a rather small trusted kernel written in C or similar. The official BEAM implementation is around 140K lines of C code for the emulator proper; I hope that less than that would be necessary.

Tuesday, October 25, 2011

The Impossible Isolates

…in which I continue to expound on the vast superiority of the Erlang Way, this time with the young and innocent Dart on the receiving end (but don't worry, Dart can handle multiple of those. The problem is that it must).

Google recently published a "technical preview" of the Dart language. It contains a notion of “isolates” — described by the language specification as "actor-like entities" — which serve partly as sandboxes, partly as "unit[s] of concurrency".

In the following, I intend to demonstrate that though the Dart isolates are presented as “inspired by Erlang [processes]”, there is much to be gained by taking a few more pages out of Erlang's book.

What's Impossible in Your Favorite Language?

When programming languages are discussed, focus tends to be on the things that are possible in a given language.
But what's at least as important — if you're doing anything beyond toy programs and obfuscation contests — are the things that are impossible in the language. What can't happen?

Impossibilities are very useful. They can be a great help when reasoning about programs — and when constructing programs which lend themselves to reasoning.
The impossible helps isolate relevant effect from irrelevant cause.

It's the same in real life: we do a lot of optimizations based on what we know can't happen; being able to make assumptions about the world is what lets us do, well, anything complex at all.

Gravity is quite reliable, for instance. I rarely bother to strap things to my desk these days, but rely on plain old gravity to keep them where I put them.

If I place something on my desk, then come back later to find that thing lying on the floor, and wonder how that came to be — then I may suspect a number things, but gravity outage isn't even considered a candidate explanation.
That's the difference between unlikely and impossible.

(With the different large-ish systems I've been working on for the past few years, unlikely happens all the time. And implausible (though not impossible) happens about once every 1–2 years (these events often involve virtualization).)

Narrowing down the "what may happen / what may have happened" scope is a crucial part of program debugging, understanding and maintenance, and hence of developing.

The blessings of Erlang

One of the critical things that Erlang provides, and a major reason why I like it, is the way its semantics and building blocks prevent surprises.
Two processes can't interfere with each others' state; they can't affect each others' control flow except through message passing; and if a process goes down, it disappears completely, without leaking resources.

The great thing about Erlang is not in itself that it allows you to do many things simultaneously, but that at the same time it lets you focus on one thing at a time. It is just as much about being able to think non-concurrently, as it's about concurrency. That's the way that complexity is handled: by isolation, through focus on the task at hand.
Much of the time, the result is that concerns separate nicely.

The three pillars of sound state

As Kresten Krab Thorup points out in his posting “Dart: An Erlanger's Reflections”, the three major features of Erlang which enable such focus on one task are isolation, sequencing, and fault handling.

These features consist of four (1+1+2) properties which can be summed up as, respectively,

Other processes cannot interfere with a process's state (except through message passing)
A process cannot interfere with its own state (but has a single, predictable control flow)
A process which fails cannot continue to run after the failure (with a possibly corrupt state)
When a process fails, and thus ceases to run, entities dependent on that process will be notified of its demise in a timely manner.

(Or, more consisely: “Others won't interfere”, “I myself won't interfere”, “Failure will not linger”, and “Failure will not go unnoticed”.)

Of these, I will in the following focus on the first three — the ones which are, incidentally, stated as impossibilities of the aforementioned kind.
The absense of either of these properties would destroy locality in reasoning.

One consequence of this set of properties is related to the famous "Let it crash" philosophy of the Erlang tradition: that even error handling is done only by the survivors — those processes with a “good” (non-corrupted) state.

The state of Dart (and stacklessness of its isolates)

The reason I write about all of this just now is related to Google's recently-published language “Dart” (released as an early preview; the spec is not final yet).

Dart introduces a notion of isolates — like Erlang's light-weight processes, isolates have separate heaps. Unlike Erlang processes, however, isolates don't have separate stacks, but are activated on an empty stack each time, through callbacks which process the incoming messages on a FIFO basis.

And as far as I can tell from the specification, nothing particular happens to an isolate if one of its callbacks terminate abnormally.
[Actually, I am told that as it is now, that will cause the Dart VM to crash. I will assume that this behaviour is not intended.]

Indeed, isolates appear to be more passive than active objects -- as far as I can tell, their life spans are determined, not explicitly and from within like Erlang processes' life spans, but implicitly and from without, by reachability, like OOP objects.

And that difference is a significant one: it breaks two of the three “pillars of sound state”: an isolate can surprise itself by handling an unrelated event when it perhaps shouldn't, and an event handler crashing within an isolate can leave the state in an inconsistent state without any consequences for the isolate's lifecycle.

Basically, what this means is that the invariants of an isolate's state most be reestablished by all of its event handlers, always, regardless of whether and how they terminate abnormally. This may just be par for the course in the eyes of many programmers, of course, but from an Erlang developer's perspective it's very much a “close but no cigar” situation.

The state-space explosion that commonly happens when a state machine must be able to handle every kind of events in every state is exactly one of the things that drove the development of Erlang in the first place (and led to the “selective receive” feature).

Case in point: Synchronous calls

An example of a common pattern where this matters is as follows: One actor needs, during the processing of a message, to contact another actor for information necessary to complete the processing. This is a situation that commonly occurs in Erlang programs, and in Erlang, the typical solution would be to make a synchronous call to the other actor: send a request, then wait for a response before continuing execution. (In most cases, a timeout would be set as well, to ensure that execution will in fact continue.)

This send-request, wait-for-response operation pair can be put together in a function, so that the invocation of another actor looks just like a normal function invocation — the communication can be encapsulated; in fact, the send/receive code is rarely actually spelled out, because it is already provided by the standard library.

In Dart, the situation is somewhat different: to do a synchronous call to another actor, you'd create a Promise (a one-shot message queue), and send the send-end + the request to the actor in question. That actor would then put the result to the Promise. But the caller cannot just explicitly wait for the response; instead, it must register a response handler on the Promise. The handler would typically be a closure which carries whatever state is needed to complete the processing.

All of these operation complete right away — execution continues immediately. This means that the remote call cannot be encapsulated and treated like a normal function call; modularity suffers. In Erlang, it is easy to change whether, how and to which other actor to make asynchronous calls — it's a local change, completely transparent to the call site; in Dart it looks like it wouldn't be so simple a matter.

If you were to approach the Erlang way in Dart, you'd have to write in continuation passing style (CPS), so that the call would always happen on a nearly empty stack — so that returning from a function means returning from the event handler; this means that the current constraints — that event handling always begins and ends with an empty stack — wouldn't matter, because the real stack would be in the continuation.
When using CPS, calling another actor could indeed be made to look just like another function call.

Except that it wouldn't behave like an ordinary function call, because other incoming messages could be processed between the call request and the call response — leading to the problems mentioned above with self-interference.

The funny thing about this CPS-based approach, by the way, is that this attempt to buy back the between-events stack that is necessary for encapsulation of calls, essentially overdoes it: what you get is not one call stack, but a number of simultaneous call stacks (disguised as response handler continuations), all ready to continue execution as responses become ready. A multitude of threads of execution which can trip each other up and cause all sorts of nondeterminism-induced problems.

If the intention of the single-threaded isolates is to reduce the complexity of developing concurrent systems, then this would not be a particularly good outcome.
No stack is too little; a multitude of stacks is too many. One is the number we want, the one we can reason about.

Please animate the isolates!

The above describes the present situation, as I read the Dart specification (which I must admit I haven't done end-to-end; I've mainly been focusing on the isolate- and exception-related parts).

Since the Dart language is still in development, and Google is requesting input to the development process, these things may of course change.

My input to the process, then, is this:

Give the isolates an explicit life cycle — just isolating the heap, thus ensuring sequential heap access, is a good first step, but to fully simplify matters and keep invariants local, an isolate must be in control of its own lifecycle, including which types of events it will be ready to process at any given moment.
In short, give them liberty and give them death! (to paraphrase Patrick Henry rather freely).

Monday, October 10, 2011

Dynamic Selective Receive — an Erlang hack

Erlang is a language which is dynamic in many aspects.
One of the things that are resolved statically, however, is pattern matching; the decision trees used for branching in function clauses, case statements, and receive statements are constructed on compile time.

For instance, a set of patterns like

[X] when X==0 orelse X==100
[H|T]
[]

is translated by the Erlang compiler into the following decision tree:

is_nonempty_list(B)?
+-Y-> [H|T] = B
|     is_nil(T)?
|     +-Y-> H == 0?
|     |     +-Y-> case 1
|     |     |     ^
|     |     |     |
|     |     |     Y
|     |     |     |
|     |     +-N-> H == 100?
|     |           |
|     |           N
|     |           |
|     |           v
|     +---------> case 2
|
+-N-> is_nil(B)?
      +-Y-> case 3
      +-N-> No match.

The Erlang compiler is quite good at constructing such decision trees, which is good, because it's critical to the performance of typical Erlang programs.
(Actually, if the compiler was poor at that job, “typical Erlang programs” would probably often look different, because developers would be more inclined to write their own decision trees. Compilers form developers, to some extent.)

If you want to construct a predicate dynamically, you can do that, using function composition or an interpreter function — that is for instance how the Eshell is implemented. For instance, the first pattern above can be described as

{is_pair,
 {'or', {is_eq, 0}, {is_eq, 100}},
  is_nil}

which can be interpreted by a predicate evaluator like:

eval(is_nil, []) -> true;
eval({is_pair, HP, TP}, [H|T]) -> eval(HP,H) andalso eval(TP,T);
eval({is_eq, V}, V) -> true;
eval({'or', P1,P2}, V) -> eval(P1,V) orelse eval(P2,V);
eval(P, V) when is_function(P,1) -> P(V);
eval(_, _) -> false.

However, you can't do a selective receive using such a predicate, because one of those statically-constructed decision trees is always used for selecting which message to extract from the inbox; and once it's taken out of the inbox it cannot be put back again. Only after a message is extracted from the inbox can more general code be applied to it.

When is this a problem?
Well, the Erlang shell is one example; here, dynamic selective receive will have to be faked: buffering is needed, and in fact the timeout mechanism of the Erlang receive construct is (last I checked, which is a few years ago) emulated only incompletely. I know that I filed a bug report about that issue, but I can't find it now.

Also, it's an issue that may sometimes arise when you're trying to combine two concerns in one process, and each of the concerns communicate with other processes; in such cases, it would sometimes be convenient to have parameterizable selective receive.

Solutions

For this problem, I've found a solution which looks promising.

The solution is sufficiently cheaty, however, that I should probably first mention a couple of more “in the spirit” solutions; all three solutions can be considered to be cheating, but at least I can offer different flavours of unrulyness.

Construct, dynamically, a module which implements a function which does the selective receive. Constructing and compiling modules dynamically is relatively easy in Erlang. Calling a function in a runtime-specified module is just everyday Erlang; it's Erlang primary kind of polymorhism.

You wouldn't want to do this module construction business for something that needs to be done a million times, but it's probably a good exercise.
Take as a parameter a predicate function which is to be used for selecting the message. Access the process's inbox through the backdoor: process_info(self(), messages), and apply the predicate to each message in turn until an acceptable one is found (or the end of the list is reached, in which case you wait a bit and retry). Now you know exactly which message you want to extract, and that's straightforward to do (the decision tree for that is static).

I can only recommend this approach if you don't care about performance or ugly hacks. Also, there's no really good way of handling the no-such-message-yet case, as far as I can see.
Take advantage of the fact that what is possible in Beam — the VM's instruction set — is a superset of what's possible in Erlang. In particular with respect to the receive construct. This is the solution that I will describe below.

The following module is a quite general solution which uses a matchspec as a predicate. It is written in Erlang assembly, because at this level this hack becomes possible:

%% File: dyn_sel_recv.S
{module, dyn_sel_recv}.  %% version = 0
{exports, [{match_spec_receive,2}]}.
{labels, 5}.

{function,match_spec_receive,2,2}.
  {label,1}.
    {func_info,{atom,match_spec_magic},{atom,match_spec_receive},2}.
  {label,2}.
    {allocate,2,2}.
    {move,{x,1},{y,0}}.
    {move,{x,0},{y,1}}.
  {label,3}.
    {loop_rec,{f,5},{x,0}}.
    %% x0 = Msg, y0 = Timeout, y1 = CMS
    {test_heap,2,2}.
    {put_list,{x,0},nil,{x,0}}.
    %% x0 = [Msg]
    {move,{y,1},{x,1}}.
    %% x1 = CMS
    {call_ext,2,{extfunc,ets,match_spec_run,2}}.
    %% x0 = [] | [Res]
    {test,is_nonempty_list,{f,4},[{x,0}]}.
    {get_list,{x,0},{x,1},{x,2}}.
    {move,{x,1},{x,0}}.
    %% x0 = Res
    remove_message.
    {deallocate,2}.
    return.
  {label,4}.
    {loop_rec_end,{f,3}}.
  {label,5}.
    {wait_timeout,{f,3},{y,0}}.
    timeout.
    {move,{atom,timeout},{x,0}}.
    {deallocate,2}.
    return.

To test it, we have this module:

%% File: dyn_recv_test.erl
-module(dyn_recv_test).
-include_lib(“stdlib/include/ms_transform.hrl”).
-export([test/0]).

test() ->
    %% The pattern (and what it should result in):
    MS = ets:fun2ms(fun({ping, X}) -> {pong,X} end),

%% Compile the pattern:
    CMS = ets:match_spec_compile(MS),

%% Perform a selective receive based on the pattern:
    dyn_sel_recv:match_spec_receive(CMS, 1000).

A sample interaction, with comment marked with "#" and "%":

# Compile the code:
$ erlc dyn_recv_test.erl dyn_sel_recv.S

# Then start an Erlang shell:
$ erl
Erlang R14B (erts-5.8.1) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.8.1  (abort with ^G)
1> dyn_recv_test:test(). % No appropriate messages - times out
timeout
% Fill the inbox with test data:
2> self() ! 'before'.
before
3> self() ! {ping, 144}.
{ping,144}
4> self() ! {ping, 1234}.
{ping,1234}
5> self() ! 'after'.
'after'
6> process_info(self(), messages). % There are four messages in the inbox now
{messages,[before,{ping,144},{ping,1234},'after']}
7> dyn_recv_test:test(). % Receive first ping message
{pong,144}
8> dyn_recv_test:test(). % Receive second ping message
{pong,1234}
9> dyn_recv_test:test(). % Times out again - no more ping messages
timeout
10> process_info(self(), messages). % Now, only the non-pings are left.
{messages,[before,'after']}

Discussion

Why restrict ourselves to matchspecs?

In principle you could instead construct a receive function which accepts a general predicate function, but that would be risky — while I'm reasonably confident that the matchspec hack works (no guarantees though!), I'm fairly certain that the Erlang VM would take offense if such a predicate were to e.g. do any receiving of its own, or throw exceptions.

Matchspecs, on the other hand, can do just that which is possible to do in a regular pattern matching construct in Erlang — in particular, no side effects are allowed.

And matchspecs can be preprocessed (“compiled”) into a form which is interpreted efficiently; yet their source form can be constructed with relative ease at runtime. Finally, matchspecs have the nice thing about them that even though they are represented as ordinary Erlang terms, and as such may be a somewhat hard to read (and write) if they are complex, there is a parse-tree transformation which makes it possible to write them just as ordinary Erlang patterns and conditions — this is demonstrated in the above.

Now, I haven't yet had the chance to use this hack in a real context, but here it is. If nothing else, I suppose it demonstrates that it is quite possible to allow matchspecs in Erlang's pattern-matching constructs — at least that there does not seem to be any VM-level reason against it. I think that might be an interesting language extension; then again, there are plenty of other language extension discussions, and this suggestion would probably not get high priority.

Monday, August 15, 2011

An Erlang-Java Interop Demo

Erlang is designed and used for distributed systems. As such, it is quite good at talking to itself. And as I'll show in the following, it is — at least in some cases — reasonably good at talking to other languages as well.

When would you want to do this?

(You can skip this section if you know.)

Interoperability between languages is useful when there's value to be had in the software in both ends. You might prefer to keep some functionality in Erlang because it's already written in that language; because it has better libraries for the task; or simply because the language supports that task better. The same goes for the other language: there are C libraries around for almost anything (and plenty of C/C++ legacy code), and for GUIs you might prefer e.g Java.

Or you have the same functionality implemented in both languages, and wish to do comparison tests on the two implementations.

Or the architecture is inherently distributed — e.g. a client-server configuration — so that there is no advantage to be had in building the two parts using the same language anyway.

In the following demonstration, we have a Java side with some freshly written software with interesting bugs, and an Erlang side with an interesting tool for discovering bugs and a nice-ish language for specifying tests.

The demo

What I intend to do:

Define an interface;
Write a Java function;
Make it accessible from Erlang;
Test it using Erlang.

Sounds like a lot of work? It needn't be. Not for you, anyway; most of the heavy lifting has already been done.

(If you don't care about exposition, and are just interested in the technical end result, here is the executable summary.)

An interface

First, we'll need to define an interface. For this, we use the IDL — Interface Description Language:

// File "foo.idl"
interface Foo {
  string quuxinate(in string s);
};

We translate this into Java using the Erlang compiler:

erlc '+{be,java}' foo.idl

This results in a Java interface in Foo.java, as well as some stub code we'll be using.

A function in Java

For an implementation, let's say that quuxinate() is to reverse the string. To add a twist, let's say that it breaks down under some rare, complex-ish circumstances, such as when there's a letter which occurs thrice in the input string — that'll be a bug we can find later, when we start testing it:

// File "FooImpl.java"
public class FooImpl extends _FooImplBase /* which implements Foo */ {
  public String quuxinate(String s) {
    int[] stats = new int[256];
    for (int i=0; i<s.length(); i++) {
      char c =  s.charAt(i);
      if (c<255 && ++stats[c] >= 3) throw new RuntimeException("WTF");
    }
    return new StringBuilder(s).reverse().toString();
  }
}

Making the function accessible from Erlang

You may have noticed that we don't implement Foo directly, but rather extend an stub class which implements it. This means that the class already knows how to talk to Erlang — specifically, it knows how to handle requests like a gen_server.

What is left is to establish connection to an Erlang node. There are two frameworks for this: CORBA and Erlang inter-node communication. CORBA is, I believe, the heavy-weight option, and I haven't worked with it; in the following, we'll use Erlang inter-node communication.

A runnning Erlang program (OS-level process) is often referred to as a 'node', because Erlang is designed for having multiple such programs be connected, in what is known as a 'cluster' of nodes.

It's not an exclusive club, either: nodes can be, and usually are, Erlang nodes, but other kinds can enter the mix — a C or Java node, for instance.

A bit of code is needed to run a Java program as a node; don't worry though, this is the only lengthy bit, and it can be generalized so that it doesn't have to refer to Foo:

// File "FooServer.java"
public class FooServer {
  // The following is based on the program in lib/ic/examples/java-client-server/server.java
  static java.lang.String snode = "javaserver";
  static java.lang.String cookie = "xyz";

  public static void main(String[] args) throws java.io.IOException, com.ericsson.otp.erlang.OtpAuthException {

    com.ericsson.otp.erlang.OtpServer self = new com.ericsson.otp.erlang.OtpServer(snode, cookie);

    System.err.print("Registering with EPMD...");
    boolean res = self.publishPort();
    if (!res) throw new RuntimeException("Node name was already taken.");
    System.err.println("done");

    do {
      try {
        com.ericsson.otp.erlang.OtpConnection connection = self.accept();
        System.err.println("Incoming connection.");
        try {
          handleConnection(connection);
        } catch (Exception e) {
          System.err.println("Server terminated: "+e);
        } finally {
          connection.close();
          System.err.println("Connection terminated.");
        }
      } catch (Exception e) {
        System.err.println("Error accepting connection: "+e);
      }
    } while (true);
  }

  static void handleConnection(com.ericsson.otp.erlang.OtpConnection connection) throws Exception {
    while (connection.isConnected() == true) {
      FooImpl srv = new FooImpl();
      com.ericsson.otp.erlang.OtpInputStream request= connection.receiveBuf();
      try {
        com.ericsson.otp.erlang.OtpOutputStream reply = srv.invoke(request);
        if (reply != null) {
          connection.sendBuf(srv.__getCallerPid(), reply);
        }
      } catch (Exception e) {
        System.err.println("Server exception: "+e);
        e.printStackTrace(System.err);
        handleException(e, connection, null);
      }
    }
  }

  static void handleException(Exception e, com.ericsson.otp.erlang.OtpConnection connection, com.ericsson.otp.ic.Environment env) throws Exception {
    // We'll improve on this later...
    throw e;
  }
}

Time to build and try out:

ERL_ROOT=`erl -noshell -eval 'io:format("~s\n", [code:root_dir()]), init:stop().'` # Or simply where Erlang is.
IC_JAR=`ls -1 $ERL_ROOT/lib/ic-*/priv/ic.jar`
JI_JAR=`ls -1 $ERL_ROOT/lib/jinterface-*/priv/OtpErlang.jar`
CLASSPATH=".:$IC_JAR:$JI_JAR"
javac -classpath "$CLASSPATH" *.java

epmd # Start Erlang port mapper daemon if it isn't already.
java -classpath "$CLASSPATH" FooServer

The Java node should now be running and registered as javaserver — ready to accept connections with the right cookie.

Let's test that:

erl -sname tester -setcookie xyz
> {ok,Host}=inet:gethostname().
> JavaServer = {dummy, list_to_atom("javaserver@"++Host)}.
> gen_server:call(JavaServer, {quuxinate, "Testing, 1-2-3"}).

The reply should be the reverse string:

"3-2-1 ,gnitseT"

And the bug we put there is working too:

> gen_server:call(JavaServer, {quuxinate, "Testing, 1 2 3"}).
** exception exit: {{nodedown,javaserver@flitwick},
                    {gen_server,call,
                                [{dummy,javaserver@flitwick},
                                 {quuxinate,"Testing, 1 2 3"}]}}
     in function  gen_server:call/2

Property testing of Java code

Now then, what can we do with this setup?

One interesting thing that we can do is to apply one of the property-based testing tools to our Java function. In the following, I'll be using Triq, but Quviq QuickCheck or PropEr could be substituted with only minor changes. First, assuming that you haven't got Triq, but have git:

git clone git://github.com/krestenkrab/triq.git
(cd triq && ./rebar compile)

Then we are ready to write our test — namely, that given any (ASCII) string, quuxinate() should return the reverse string:

// File "test.erl"
-module(test).
-include_lib("triq/include/triq.hrl").
-export([main/0]).

prop_reverse(JavaServer) ->                  % The property
  ?FORALL(S, ascii_string(),
      gen_server:call(JavaServer, {quuxinate, S})
      == lists:reverse(S)).

ascii_string() ->                            % A data generator
  list(choose(0,127)).

main() ->
  {ok,Host}=inet:gethostname(),
  JavaServer = {dummy, list_to_atom("javaserver@"++Host)},

  triq:check(prop_reverse(JavaServer), 100), % Do the magic
  init:stop().                               % Shut down cleanly

Compile and run the test:

erlc -I triq/include -pa triq/ebin test.erl

erl -noshell -sname tester -setcookie xyz -pa triq/ebin -run test main

Triq will now generate a hundred random test cases, and verify the property for each case. After a dozen such tests, the bug is triggered:

...........Failed with: {exit,
                 {{nodedown,javaserver@flitwick},
                  {gen_server,call,
                      [{dummy,javaserver@flitwick},
                       {quuxinate,
                           [79,84,75,110,3,42,73,14,1,53,76,42,126,40,118,122,
                            74,2,58,34,42,98]}]}},
                 [{gen_server,call,2},
                  {test,'-prop_reverse/1-fun-0-',2},
                  {triq,check_input,4},
                  {triq,check_forall,6},
                  {triq,check,3},
                  {test,main,0},
                  {init,start_it,1},
                  {init,start_em,1}]}

Failed after 12 tests with {'EXIT',
                            {{nodedown,javaserver@flitwick},
                             {gen_server,call,
                              [{dummy,javaserver@flitwick},
                               {quuxinate,
                                [79,84,75,110,3,42,73,14,1,53,76,42,126,40,
                                 118,122,74,2,58,34,42,98]}]}}}

The 22-character string has three '*'s (ascii value 42) in it, which was what triggered the bug.

Triq then proceeds to simplify the test case:

Simplified:
        S = [33,33,33]

concluding that the string "!!!" is a locally-minimal failing test case.

Quite useful, isn't it? — and the amount of non-reusable code has been quite manageable (3 lines of IDL, 14 lines of implementation, 14 lines of test code, 1 line of Foo-specific code in FooServer).
(Speaking of which: you're free to use these snippets as you see fit; provided as-is and with no guarantees of anything, of course.)

I should mention at this point that property testing tools exist within the Java world as well — there exists at least one for Scala. I didn't find it particularly satifying to use, though, although I may have been unlucky; in any case, this is an alternative.

Erlang, IDL and exceptions

The Guide (that is, the Erlang IC (IDL compiler) User Guide) has this to say about handling of Java exceptions:

While exception mapping is not implemented, the stubs will generate some Java exceptions in case of operation failure. No exceptions are propagated through the communication.

Which means that, out of the box, these are our options for handling Java-side exceptions:

Convert exceptions into values within quuxinate().
Return no result on exceptions — in which case the Erlang-side call will time out (after, as a default, 5 seconds).
Close the connection — in which case the Erlang-side call will receive an error result immediately.

None of these options are especially satisfying.

So let's look at how to do this:

Report exceptions to the caller as an {error, Reason} reply.

It's not too difficult. What we need to do (according to the gen_server call protocol) is send a {RequestRef, Reply} tuple to the caller, where RequestRef is a reference which was included in the request and must be included in the response as well.

The main difficulty is one of access: at the point of error handling, we will need access to (1) the caller's PID and (2) the request reference. I'd like to keep FooImpl and the connection-managing FooServer separate, so we need to add an accessor:

// File "FooImpl.java"
public class FooImpl extends _FooImplBase /* which implements Foo */ {
  ...
  /** The request environment is exposed for error handling reasons. */
  public com.ericsson.otp.ic.Environment getEnv() {
     return _env;
  }
}

That's it. We could instead have added one accessor for the caller PID and one for the request reference, but let's keep the complexity in the server class.

In the server class, instead of throwing an exception which causes the connection to be terminated, we will build and send an error reply:

// File "FooServer.java"
public class FooServer {
  ...
// in handleConnection(), replace
        // handleException(e, connection, null);
// with:
        handleException(e, connection, srv.getEnv());
  ...
// and replace handleException() with:
  static void handleException(Exception e, com.ericsson.otp.erlang.OtpConnection connection, com.ericsson.otp.ic.Environment env) throws Exception {
    // Write exception reply:
    com.ericsson.otp.erlang.OtpOutputStream err_reply = new com.ericsson.otp.erlang.OtpOutputStream();
    err_reply.write_tuple_head(2);
    err_reply.write_any(env.getSref());
    err_reply.write_tuple_head(2);  // Construct return value {error, ErrorText}
    err_reply.write_atom("error");
    err_reply.write_string(e.toString());
    connection.sendBuf(env.getScaller(), err_reply);
  }
}

There; that's all.

If we test it again, we get a nicer behaviour:

> gen_server:call(JavaServer, {quuxinate, "Testing, 1 2 3"}).
{error,"java.lang.RuntimeException: WTF"}

Disclaimer

I ought to mention that I have only just discovered this interoperability option (two days ago, in fact, when I stumbled upon this article); it is only a few months ago that I wrote a custom socket server test program in Java, and corresponding driver code in Erlang, just to achieve what could be had far more easily using Erlang's IDL compiler. It may therefore not be so easy to use in practice as the above make it seem. (For one thing, the only type that I've used is string.)

Even so, I hope to have inspired others to try this out.
One way to do so is to have a look at the executable summary referred to earlier; it is the demo as a shell script.

Happy inter-language hacking!

Further technical notes (and speculation)

The IDL compiler supports generating code for Java, C and Erlang. Here is its documentation.

If you're writing Erlang port programs (like an Erlang driver, but running in a separate process), but have an interface which is evolving quicḱly enough, or you yourself are lazy enough, that writing and maiintaining the serialization and deserialization code has quite lost its attraction, then it might be tempting to look into using IDL for that interface, and have the boring bits code-generated for you.

The IDL compiler and the code it generates does not seem to have been designed for this, but as far as I can tell it appears to be achieveable.

Monday, May 23, 2011

On concurrency issues

Concurrency issues — race conditions and the like — are the worst category of bugs. These are the bugs that cannot well be proven absent by unit tests; these are the kind of bugs that hide away, biding their time until the most inopportune moment, then rearing their ugly, non-deterministic head on your production system when it is at its busiest. And even then, they can continue to exist unlocated for quite a while, despite many hours being put into tracking them down. Elusive, hardly reproducible, yet ultimately expensive; I've seen it happen more than once.

What follows is some thoughts on the basis of the typical issues.

Your basic multi-threading bug
As any course on multi-threaded programming will tell you, when multiple threads of execution are to run concurrently, care needs to be taken or there will be a risk of data corruption and/or unintended results.

More specifially, the threat (a "race condition" or "data race") is present when:

one thread modifies the state of an object
at the same time as
another thread accesses the object.

That is: it takes a coincidence, a conjunction of three conditions.
Let's analyze it...:

Analysis

Another way of stating the above is obtained by reversing the statement:
We can avoid concurrency issues by always making sure that any object either

is never modified; or
is never accessed by two threads simultaneously (or stronger: never written to while accessed otherwise); or
can only ever be accessed by one thread.

Such objects are known as, respectively,

Immutable objects.
Objects with state protected by a mutex (synchronization lock; monitor)

and the one used less often:

Single-thread objects — or even stronger: objects of linear type.

The first two options are well-known; personally, I'm increasingly coming to consider the strong third option — objects with enforced linear lifecycle — to be rather overlooked, language design space-wise.

"Concurrency-ready" metric
One possible metric for how well a programming language is designed to express complex concurrent systems is, then, how easy it is to enforce that all objects fall into one of the three categories.

Languages and concurrency

Let's apply this view to a few programming languages. The two languages I've used most recently are Java and Erlang:

Erlang

In Erlang, there are the following kinds of objects: terms, message queues, process dictionaries and other process metadata, ETS tables, ports (files and drivers).

Terms are immutable values. They may contains handles of other kinds of objects, but the handles themselves are also immutable.
Certain objects — private ETS tables, and to some extent ports — are single-thread objects.
The rest — message queues, public ETS tables, process metadata etc. — are mutex-protected.

Single-thread objects are enforced not to be used by other threads than the owning one.
In Erlang, low-level data races only occur if there's a bug in the Erlang run-time system, or if you write your own driver and include one.

Java

In Java, you could argue both that there are fewer kinds of object — just one, really, the class-file defined kind — and that there is a much wider range of object kinds.There are certainly thousands of classes, defined by one well-defined scheme, which includes just a few mechanisms relevant to concurrency.
But the problem here is the number of classes — because it is at the class level that it is ensured that the corresponding objects will be thread-safe. A well-designed and -implemented class may be thread-safe, in that it is either immutable or uses appropriate inter-thread synchronization (and encapsulation) to ensure thread-safety. A less well-written class may rely implicitly on details of the context in which it is used, and really be single-thread-use only, or multi-thread usable only in certain unstated conditions.

Java is one of the few languages actually designed for portable multi-threaded programs; in particular, it has explicitly stated semantics wrt. multi-threaded execution. However, as the above comparison is one indication of, it has its shortcomings. For a language to claim good concurrency support, it should provide mechanisms for good, usable guarantees to be derived from local context (e.g. "we know that this-and-this property always holds, because these few lines here ensure that it does").
I've expounded earlier on the importance of supporting local reasoning. As it happens, Java did also then get some criticism (sorry, Java, but you're the modern main-stream language I happen to know the best...).

A Java exercise

Imagine that you have in front of you the source code of a Java class.
A quick inspection reveals that all methods are declared "synchronized".
What kinds of thread-safety issues might the class yet have? Try to list at least three ways in which the class may be non-thread-safe.

I'll present my list at the end of this article.

Does it matter?

But building security against these issues into a language is not exactly trivial, you might argue. Is stricter language rules, additional compiler analysis, and/or costly run-time support just for preventing concurrency issues not just overkill?
Sure, the trend is towards increasing parallellism and so on, but we have done quite fine without such extra measures so far, haven't we?
And bondage-and-discipline languages have been out of fashion for a while. Dynamically typed languages are as popular as ever!

The difference is this:

You can easily live and work with the relative uncertainties of dynamic typing — but then, you can unit test and get some confidence that the types match. If something is broken, or breaks later, then there's a good chance it'll be caught.
For many concurrency issues, unit tests are not likely to catch any errors. Furthermore, the necessary invariants aren't local — they are often widely dispersed in the code. To convince yourself that the code is correct, you more or less need to keep it all in your head at once. That, combined with missing language support for documenting and/or enforcing vital non-local invariants, means that they will perhaps not be communicated to whoever makes the next change in the code, who will therefore not have the full picture necessary to keep things correct.

Rather than being caught at the next full test suite run, or at least quite soon after the rubber hits the road, here's what happens to a race-condition bug:

The program may appear to work most of the time.
The issue will tend to manifest itself at the most inopportune moment: Not during development or testing (unless explicit and considerable effort is taken to stress-test against such issues), but in production, when your servers are at their busiest, or on the desktop of your busiest client.
Often, what clues you have amount to little besides "There almost certainly is an issue, it presumably is a software bug, the issue is probably in our code — and it occurs seldomly, so it's likely to be a concurrency issue of some kind."
Replicating the issue may be difficult; under the exact same circumstances, the program may run just fine.
Indeed, if the problem does manifest itself during development, it'll appear to have gone at the next run.
The issue may even be technically impossible to reproduce on some machine architectures, because it requires multiple physical processors of the right kinds to manifest itself (and your servers or other production environment is less likely than the development machines to be thus bug-resistant).
Eliminating a tricky concurrency bug can be a drawn-out experience in all phases — detecting it, reproducing it, tracking down its root cause, verifying that it has gone — all steps tend to be markedly more difficult than for deterministic bugs.
With any kind of bug, tracking it down once is one thing; there may be even be a feeling of gratification once you've done it. Tracking the same bug down twice is another matter — it is deeply frustrating to realize that there's a reason for your feeling of déja-vu. This is one of the reasons for regression testing: bug hunting may be stimulating in its own way, but it'd better lead to a different bug each time.
This goes doubly (well, even more than that) for the elusive non-deterministic bugs.
Sadly, because of their nature it is at best difficult, and often near impossible, to write regression tests for these kinds of issues.

Conclusion

Languages differ in concurrency support. Nothing new about that, of course, but I think it likely that many developers using one of the mainstream languages which have a relatively good level of support in that area may not know that there are alternatives which are significantly more concurrency-ready.
In the beginning of this text, the prerequisites for a race condition were broken down and three kinds of conditions for avoiding race condition were derived; based on this I suggested a qualitative metric for a language's level of support for concurrent programming. I hope to have demonstrated that it may be a useful way of looking at both languages and concrete programs or program designs.

In the absence of a programming language providing strong, local guarantees with respect to thread-safety, as a developer you need to be alert whenever there's a chance that two threads may be executing your code concurrently. The best way of doing this is probably through discipline — for instance, by clearly constructing each class so that it falls into one of the above categories: Immutable, thread-safe through synchronization, or single-thread use only — and then using them strictly according to this. That is one way of trying to restore local reasoning.

Do you write programs involving multiple threads? If so, are you familiar with which consistency guarantees your platform actually provides (e.g, the Java Memory Model)?
Do you regularly stress-test your program on a system with multiple physical processors? I hope you do.
Dealing with concurrent programs in general requires good global, combinatorial-temporal reasoning abilities. Probably not your best-developed cognitive mode... :-)
The solution? Keep things as simple as possible. Find rules that work, and follow them. Encapsulate the issues, so that you can deal with just one question at a time. If possible, let the rules be checked mechanically.

Answer to Java exercise
Some ways in which a Java class may be unsafe even though all methods are declared "synchronized":

A field is public, and either

Non-final (and non-volatile) or
Referring to a non-thread-safe object.

The superclass is non-thread-safe, and the current class does not or can not override the causes.
An instance method modifies the value of a a static variable without proper synchronization.
An instance method reads the value of a a static variable which is also modified by a static method, without proper synchronization.
A method exposes a reference to a non-thread-safe object referred to directly or indirectly by the current object.
1. By returning such a reference.
2. By passing such a reference to some method which stores the reference somewhere accessible to another thread.
3. By starting a new thread and giving it such a reference.
(I.e., a non-thread-safe object becomes shared.)
A field (which may be private) refers to a non-thread-safe object which may be shared because

It originated as (or was extracted from) a parameter to a constructor
It originated as (or was extracted from) a parameter to a method
It was returned from a call

An inner class accesses an instance variable of the surrounding class, but fails to synchronize on the right this.
An instance method locks on another object which may be of the same class (this may result in a deadlock)
1. Implicitly, by calling a (synchronized) method on the other object
2. Explicitly, using "synchronized"
(A plausible example of this is a synchronized equals() method.)
A constructor leaks this to some place where it can be accessed by another thread, and the object has at least one (final) variable which is accessed without synchronization.
(This is because the special rule for final fields, which allows them to be accessed without synchronization, only applies after the constructor has completed.)
A method exposes a reference to a thread-safe object referred to directly or indirectly by the current object, and that thread-safe object allows mutation (of itself or of a contained object) in a way that the current class is not prepared for.

This list is quite likely not complete; it is not the result of a systematic analysis of the matter.

Friday, September 18, 2009

Programming Languages and Local Reasoning

Through time, there have been two interesting trends in programming languages: towards better guarantees and later binding.

With "guarantees", I mean facts and invariants which the language rules permit us to conclude from the code. Such as the following - you may or may not recognize them (and the language features which give rise to them):

"The value in this variable is of this type."
"The value in this variable can only come from one of these expressions."
"The value of this object field can not be changed once the object has been constructed."
"This variable can only be accessed from one thread."
"This method can not be redefined in subclasses."
"This process will always be notified when this other process disappears."
"If this code point is reached, then this other code point will eventually be reached."

The two trends, better guarantees and later binding, correspond to two desirable properties of software: the ability to reason about the behaviour of software, and flexibility.

Introduction

About me:

I have a background in theoretical computer science (Master's degree from University of Aarhus). I currently work as a software developer (developing in Erlang, Scala, and the odd Bash, Perl and C++).

I've been involved - briefly - in many software projects; as bug reporter, coder, translator, or level designer. You could call me a hit-and-run contributor.
The reason: I tend to have too many ideas of my own to explore to hang around any particular project for long. Perhaps not ideal, but that's how it's turned out.

My main interests are programming languages and their implementations. That means primarily compilers, but also interpreters and runtime systems.