Why Charcoal?

... in 100 lines or less ... or more

[tl;dr]

Existing frameworks for writing interactive software (event dispatchers, {preemptive, cooperative} threads, coroutines, processes) have problems that make it easy to write unmaintainable, unreliable and/or inefficient code. I am exploring a new approach called pseudo-preemptive threads (or activities, for those who prefer fewer syllables).

Under the hood activities look just like cooperative threads, but the language definition includes frequent implicit yields, which make activities feel more preemptive (thus "pseudo-preemptive"). A simple synchronization primitive called unyielding makes it relatively easy to avoid atomicity violations, the bane of multithreaded software.

[slightly longer tl;dr]

Color code:

Good
Pretty good
Okay
Pretty bad
Bad
Threads Events Coop Threads Coroutines Activities
Atomicity Data races Trivial within a single handler; totally up to the application for tasks that span multiple handlers Will that procedure Joe wrote invoke yield? Who knows! Wheee Pretty much the same issue as events (s/handler/non-async-procedure/) unyielding: Like synchronized in Java, but way better
Starvation/{Dead,Live}lock/Progress Unsynchronized threads never block each other, but then you need all that synchronization to avoid atomicity violations So easy for a handler to take an unexpected path and run way too long There's almost certainly some long-running (or blocking) path somewhere that you forgot to put a yield in Pretty much the same issue as events, but a little easier to fix Just don't wrap long-running blocks in unyielding and you're golden
Memory scalability All those nasty stacks So pleasantly simple Most implementations are like normal threads; can be implemented like coroutines, but most aren't Only need a single frame (not a whole stack) for each coroutine (aka "async" procedure call) Just like coroutines, but with fewer annotations
Overhead (spawn, context switch, etc.) Have to enter the kernel to do most things So pleasantly cheap Generally don't need to get the kernel involved, but still closer to threads than events Generally a bit more expensive than events, but not by much Just like coroutines
Modularity/Composability See Composable Memory Transactions by Harris, Marlow, Peyton-Jones and Herlihy There's a whole domain devoted to it: http://callbackhell.com/; also "stack ripping" Will that library function invoke yield? Who knows! Wheee More explicit than coop threads, but you're kind of stuck if a library doesn't provide an async version See note below about foreign/legacy code, but otherwise free of the other frameworks' problems
Parallelism Finally, threads win something No one's crazy enough to even try "Observationally cooperative multithreading". Color me skeptical See events See coop threads

There are at least three families of concurrency/interactivity frameworks that I haven't included here: processes (i.e. no shared memory by default), functional reactive programming (FRP), and threads plus transactional memory (TM).

Shared memory is so useful for the kinds of applications I'm interested in, I'm not even considering frameworks that don't support it well. You're welcome to try to convince me that it's a good idea to write GUI applications where each widget is its own process, but I'm extremely skeptical.

FRP has been a reasonably active research topic since at least 1997 (Functional Reactive Animation by Elliott and Hudak). I am aware of zero large-scale applications that make significant use of it. I don't know if FRP will ever go mainstream, but I'm interested in improving the state of interactive software in a way that can integrate more easily with current tools and practices.

My reason for ignoring TM is similar to FRP. The software industry got really excited about TM in the early to mid aughts. Several of the biggest companies devoted some of their best engineers to implementing TM systems. So far it's been a complete bust. Most of the teams are now disbanded. (Haskell's STM is beautiful, but Haskell is used by 0.0% of the world's professional developers (to a first approximation).)

It's too early to declare TM dead, but I'd bet a large pile of money that it won't be ready for widespread use for at least a decade or two. On a more philosophical note, I'm not that into TM because it's an attempt to do both parallelism and interactivity; I think those should really be handled by two different frameworks.

Finally, a couple of notes under the No Free Lunch banner. Integrating activity code with foreign/legacy code is a little bit tricky (as one should expect from any concurrency framework). I think I have a pretty reasonable interop story, but it's not trivial.

Charcoal code runs in one of two modes: unyielding or might-yield. In unyielding mode, it runs as quickly/efficiently as equivalent C code. However, in might-yield mode things slow down quite a bit. It's not hard to tune CPU-bound code to be in unyielding mode most of the time, but it does take some effort. This is never catastrophic, it just means that untuned CPU-bound code is somewhat less efficient than it should be.

[narrative version]

Once upon a time, all software was functions. By once upon a time I mean around the dawn of modern computing in the 30s, 40s and 50s. By functions I mean that the interface between a program and its environment was very much like a mathematical function:

  1. the environment provides an input;
  2. the program runs;
  3. if it finishes it provides an output to the environment.
This pattern is also called batch or procedural software. As early as the 1960s, interactive software was being developed (for example, Ivan Sutherland's Sketchpad). Interactive software has a dramatically different interface with its environment. Interactive software can:

Interactive software is generally considered harder to write and maintain than procedural software, so software engineers have gone to great lengths to make large-scale software "mostly procedural", with interactivity carefully sequestered in as small a corner of the code as possible. Much to the chagrin of the programmers who prefer thinking procedurally, the relative importance of interactivity in mainstream software has increased in recent years. This increase can primarily be chalked up to three trends:

The two dominant abstractions for interactive software are event handlers and threads. Both have serious drawbacks (the linked documents have good summaries of events & threads, if you're not already familiar):

My one sentence summary of these arguments: Event handlers are great for simple interaction patterns, but scale very badly as program logic becomes more complex ("callback hell"). Threads allow complex interaction patterns to be programmed in a natural style, but make it extremely hard to avoid nasty concurrency bugs (data races, deadlocks, and atomicity violations, oh my).

Most modern software uses both event handlers and threads. Popular graphical user interface frameworks use event handlers almost exclusively for things like mouse clicks and keyboard presses. Yet almost all modern desktop and mobile software has anywhere from a few to several dozen threads at any given time. These threads exist primarily to handle long-running and complex asynchronous tasks like database transactions and communicating with servers over the internet.

An aside about parallelism. A major difference between event handlers and threads is that threads can run in parallel on separate processors, whereas event handlers cannot. While this is difference is significant in general, from the perspective of interactivity it is mostly irrelevant. Interactivity and parallelism are completely different topics, so the fact that threads can be run in parallel is beside the point when we are talking about how to write interactive software.

The main idea(!): If event handlers and threads both have such serious problems, why are they used so heavily in modern software? Quite simply, it's because nothing better exists yet. This project is an attempt to create a new primitive (called an activity) that combines the advantages and mitigates the disadvantages of event handlers and threads for programming interactive software.

On the way to explaining what activities are, we are going to take a brief detour through cooperative threads. Cooperative threads are like conventional (a.k.a. preemptive) threads, except only one is allowed to run at a time and the active cooperative thread must explicitly invoke a yield primitive to give the system the option of switching to a peer cooperative thread. The nicest feature of cooperative threads is that between yield invocations threads cannot interrupt each other, which makes avoiding concurrency bugs easier.

Cooperative threads are a kind of compromise between event handlers and threads, and they do combine some of the advantages of both. Unfortunately, cooperative threads come with their own nasty drawback: applications are responsible for getting yield invocations in just the right places. If a cooperative thread doesn't yield frequently enough it can starve other threads of processor time and make the whole application unresponsive. If a programmer throws in yields blithely in an attempt to avoid starvation they can violate atomicity assumptions, creating potentially catastrophic concurrency bugs.

The "Goldilocks" yield frequency is especially hard to maintain when a program is composed of multiple libraries and frameworks (as most modern applications are). What assumptions did the authors of the various components make about whether code in other components will yield or not? Answering this question is important and extremely hard in general. This problem has limited the adoption of cooperative threading to the margins of the software industry. However, in the name of making interactive programming easier (especially for applications that run across the internet), cooperative threads (and their cousins, coroutines) have started showing up in some mainstream software (Python, Lua, Ruby, .NET, etc.)

Activities are a hybrid of cooperative and preemptive threads, that I believe neatly captures the advantages of both. From a runtime system perspective, activities are exactly cooperative threads. However, languages that support activities (like Charcoal) are defined to implicitly insert yield invocations very frequently (as a first approximation, think every iteration of every loop). This means that from the perspective of high-level application design, activities behave more like preemptive threads. The system still has to wait for a yield to switch between activities, but in non-buggy Charcoal code it should never have to wait very long. Because of this I sometimes call activities pseudo-preemptive threads.

These frequent yields could easily reintroduce the concurrency bugs that bedevil multithreaded software. The primary tool to prevent this is the ability to declare any procedure or block of code unyielding. Within the dynamic scope of an unyielding block the current activity cannot be interrupted.

Frequent yields could also become a substantial drag on performance, so one of the most important implementation challenges in Charcoal is keeping the yield overhead extremely low and offering a convenient way for the programmer to suppress yield insertion in tight performance-critical loops.

Summary

Relative to conventional threads, the advantages of activities are:

Relative to cooperative threads, the advantages of activities are:

I believe activities inhabit an interesting new part of the universe of interactive software primitives. In particular I aim to show that multi-activity software can be:

If this sounds intriguing please explore the rest of this site, which includes several examples, ruminations on concurrency in general, detailed discussions of existing approaches to concurrent programming, and information about implementing activities (and some day an actual working implementation).

An aside about shared memory versus message passing. Some people (e.g. the designers of Go) believe that writing concurrent software (including interactive software) can be made doable by a strong focus on memory isolation between threads/​processes and rich message passing primitives. While minimizing shared memory is an excellent rule of thumb, there are applications for which shared memory is quite clear, safe and efficient. In other words, I do not believe that banning (or very strongly discouraging) the use of shared memory is the solution to the interactive software challenge. Charcoal and its core library have rich support for both shared memory and message passing (a la CML), because I think they are both useful.


Creative Commons License
Charcoal Programming Language by Benjamin Ylvisaker is licensed under a Creative Commons Attribution 4.0 International License