Let's Talk Concurrency with Sir Tony Hoare | Hacker News Reader

Let's Talk Concurrency with Sir Tony Hoare

erlang-solutions.com

189 pointsdavidw27 comments

Sir Tony Hoare is a legend! Personally one of my favorite concurrency constructs that he invented, but aren't mentioned in the interview, are conditional critical regions. A very simple abstraction that helps you write concurrent code that's maintainable and easy to read. Plus, from my experience, they provide a much more elegant way to solve various concurrency problems.

Only possible drawback is that they might perform worse than the alternative, at least in some cases.

I haven’t heard about conditional critical regions before - here’s a interesting set of slides for others: http://www-ist.massey.ac.nz/csnotes/355/lectures/monitors.pd... .

Seems very closely related to condition variables - except you specify the condition at the lock site rather than via a “trigger” before an unlock. I think Google’s internal Mutex class had a LockWhen(callback) which is a pleasure to work with. Definitely an awesome concept.

IIRC there was at least one language that implemented CCRs natively in its syntax. I want to say it's Ada but I could be wrong. If anyone else knows about it please correct me.

To understand it better here's the solution to the producer/consumer problem (from wikipedia), using mutexes and semaphores:

  mtx buffer_mutex;
  sem fillCount = 0;
  sem emptyCount = BUFFER_SIZE;
  
  procedure producer() 
  {
      while (true) 
      {
          item = produceItem();
          down(emptyCount);
          down(buffer_mutex);
          putItemIntoBuffer(item);
          up(buffer_mutex);
          up(fillCount);
      }
  }
  
  procedure consumer() 
  {
      while (true) 
      {
          down(fillCount);
          down(buffer_mutex);
          item = removeItemFromBuffer();
          up(buffer_mutex);
          up(emptyCount);
          consumeItem(item);
      }
  }

and the same problem solved using CCRs:

  int avl = 0;
  
  procedure producer() 
  {
      while (true) 
      {
          item = produceItem();
          region R when (avl < BUFFER_SIZE)
          {
              putItemIntoBuffer(item);
              avl++;
          }
      }
  }
  
  procedure consumer() 
  {
     while (true) 
     {
         region R when (avl > 0)
         {
             item = removeItemFromBuffer();
             avl--;
         }
         consumeItem(item);
     }
  }

The most important thing about CCRs is that they are supposed to guarantee fairness, along with mutual exclusion. A well-designed solution uses two binary semaphore queues to achieve this.

If anyone wants to see what an implementation looks like here's a small C library I wrote a while ago, to use for some of my own personal projects, and to solve some homework for Uni https://github.com/Gikoskos/libccr

> I want to say it's Ada but I could be wrong.

Yes, entry barriers: http://www.ada-auth.org/standards/12rm/html/RM-9-5-2.html#S0...

The consumer/producer routines (entries) conceptually belong to the object/resource that is operated on (protected object) but are executed by the calling task.

Yes, conditional critical regions can be slower because conditions can be redundantly tested.

Below is an Actor implementation of a read priority solution to the readers writers problem:

  ReadPriority[aDatabase:*ReadersWriter*]:*ReadersWriterManager*
       //  Invariant: **Nonempty** #writing# ⇨ **IsEmpty** #reading#
   **Locals**(Queue(#writersQ#, #readersQ#),
              Crowd(#reading#),
              AtMostOne(#writing#)),
   **Handlers**( 
       ⟦scheduler⟧ ↦ **As** myScheduler, // myScheduler facet of this manager
       upgrade[newVersion] ↦ 
            (**CancellAll**  #readersQ# **and** #writersQ# **and** #reading# **and** #writing#
                  **for** **Become** newVersion)
   myScheduler **implements** *ReadersWriter* **Handlers**( 
      read[aQuery] ↦ 
         **Enqueue** #readersQ# **when** **Nonempty** #writing# **or** #writersQ# **or** #readersQ# 
             **for** aDatabase.read[aQuery] **thru** #reading#
                    **permit** #readersQ#
                       **afterward** **Permit** #writersQ# **when** **IsEmpty** #reading#
                                                **else** #readersQ# **when** **IsEmpty** #writersQ#,
      write[anUpdate] ↦    
         **Enqueue** #writersQ# **when** **Nonempty** #reading# **or** #readersQ# **or** #writing# **or** #writersQ#  
              **for** aDatabase.write[anUpdate] **thru** #writing#
                   **afterward** **Permit** #readersQ# **else** #writersQ#)▮

Hi everyone, a note to say this is the first of four videos we plan on releasing. The next one (this week) will be Joe Armstrong, followed by Carl Hewitt next week. The videos will follow with a one hour panel discussion which I moderate where they talk about the past, present and future of concurrency models. Stay tuned!!!

Very cool! I'm reading through "Seven Concurrency Models in Seven Weeks" by Paul Butcher at the moment, which discusses different types of concurrency models.

If I might try to elucidate what Butcher explained, the Actor model used by Erlang/Elixir was supposed to be a "purer" object-oriented programming model that defined how objects passed information between each other rather than the state and attributes of an object, and it worked well concurrently because objects don't share state outside of messages. However, actors are expensive because they tightly couple an object (the transport object) with a process (the mode of communication) unnecessarily.

CSP improves on this model by decoupling objects and processes. It eliminates the need for a process and defines a "routine" instead as a state machine for an imperative code segment, and in doing so creates a one-to-many relationship between a given routine and the hardware-defined threadpool. Buffer objects on a given routine and only exlicitly block when you need to. When an imperative segment of code is blocked in a routine, the routine relinquishes control of the underlying thread while managing state, and when it is unblocked, can begin executing on perhaps another thread with the given state. So it's easier to make imperative code concurrent. State machines are also much cheaper to create than an actual process. CSP is highly effective running concurrent tasks that may have lots of blocking events, such as tasks issued through network, which may be why a lot of the newer network-centric libraries like Kubernetes are written in a CSP-first language like Golang.

I'd definitely buy the book, I've learned a lot (never understood why Golang was so popular until now): https://pragprog.com/book/pb7con/seven-concurrency-models-in...

Your description of both models is way off.

Actors are always cheaper and faster than CSP processes with channels or "transport objects" as you call them. In a way actors can be described as cancellable asynchronously programmable channels in CSP. Asynchrony is key for implementations to achieve high performance and cancellation together with asynchrony are keys to model unbounded nondeterminism of the real world. Synchronous semantics greatly limit achievable performance and lack of cancellation limits usefulness. Hence no language exists where CSP actually works acceptably well (even Go struggles with it since the beginning, but they still refuse to admit that it was an awful choice).

Yes, Actors are faster than CSP processes with channels because there is no required overhead in communications passing through channels.

In fact, if a channel is desired it can be efficiently implemented as an Actor with put and get messages.

Strictly speaking an Actor is not a CSP process, because an Actor does not have its own stack and does not have its own program counter that moves sequentially through a program.

>[Dahl and Nygaard] had a concept of timing which was implemented as a simulated time train in the way that is completely standard nowadays. That gives a framework within which one could explore the meaning of real concurrency.

Could anyone comment on what that framework is in current terms? Googling 'simulated time train' doesn't really help. Thanks!

Not sure what he means by "train", but Simula 67 included a module for performing "simulations", which was the original point of the language (Simula 1 was a simulation-specific language; Simula 67 was a general-purpose language with simulation in the standard library.)

The simulation module was a framework for defining parallel processes that worked with discrete, scheduled events, a bit like actors. This was intended to model real-world problems such as traffic systems or factories, that complex interactions and dependencies. A simulation had a time axis, so it ran the processes in simulated time, instead of real time. This may be what Hoare was referring to.

Further reading:

http://simula67.at.ifi.uio.no/Archive/Intro-simula/intro.pdf

http://heim.ifi.uio.no/~steinkr/papers/HiNC1-webversion-simu...

Wow that is really neat. Thank you!

Simulated time is not the basis of real concurrency.

Simula-67 (Dahl and Nyaaard) used co-routines in which there was no parallel execution.

I found the CSP paper a bit too dense. Could someone suggest a beginner friendly introduction to CSP ?

An Actor is not a sequential process because it does not have a program counter that moves sequentially through a program.

You might find Actors more intuitive. For example, see the following video by Hewitt, Meijer and Szyperski: The Actor Model (everything you wanted to know, but were afraid to ask)

https://channel9.msdn.com/Shows/Going+Deep/Hewitt-Meijer-and...

Hoare notation literally made formally verified programs possible. The man is a great.

Induction is the most important principle for proving properties of programs.

The principle of Actor induction is:

   1. Suppose that an Actor x has property P when it is created.

   2. Further suppose that if x has property P when it receives a communication, 
      then it has property P when it has processed the communication.

   3. Then x always has the property P.

Somewhat unrelated: I've always heard of him being referred to as "C. A. R. Hoare"; this is the first time I've come across "Tony Hoare". Does anyone have any idea if he prefers one or the other?

What that before he was knighted? A knight bachelor wouldn't normally abbreviate their first name.

Don't be such a greyface.

As far as I know he has been known and referred to as Tony Hoare since long before most HNers were born (even me and I'm 63)

lol

No idea but I would put my money on "Tony", given that in the video he introduces himself by "Hello, I’m Tony Hoare".

Sir Charles Antony Richard Hoare.

I assume he's C. A. R. Hoare in publications, because that's how you write your name in publications, but Tony in person, because people mostly don't call each other by their initials [1]. Which is used in text like this would depend on how formal the writer wants to be.

[1] Unless you have cool initials.

Hi,I asked how he wanted to be introduced before starting the panel discussion. He said Tony Hoare, but changed that to Prof. Hoare when he heard I was going to be more formal with Dr. Joe Armstrong and Prof. Carl Hewitt. My understanding is that he prefers Tony Hoare if being informal (e.g. amongst friends or acquaintances) or Prof. Hoare in more formal settings. Indeed, I started off being formal when introducing the panel, and moved on to first names soon after.

Reply on news.ycombinator.com