Jeremy W. Sherman

stay a while, and listen

Behavioral Programming

I recently read an exciting article on by Harel et al. on behavioral programming.

The basic idea of behavior programming is to compose a bunch of simultaneously executing state machines. Each machine represents a behavior.

But you don’t use the plain event in/event out state chart to define these machines. Instead, you add modal operators to specify what must/may/mustn’t happen next:

  • must: Please carry out this action.
  • may: Please let me know when this happens.
  • mustn’t: No matter who tells you to do this, don’t; if it does happen, abend.

These operators represent a synchronization point between behaviors. Once all behavioral threads, or “bthreads” for short, have blocked expressing a modal preference, the executive picks a must-event that’s not blocked by a mustn’t operator, carries out the event, and notifies any bthread that had that event listed as a must or may event. Execution then continues till every bthread blocks again by specifying a modal operator.

I like this model because it’s a thin but powerful layer over existing models. You can implement it with pthreads and synchronous pub/sub, which could be as simple as a group of pthread conditions.

The development approach you end up with differs markedly from the model you build your bthread framework in.

Here’s the powerful part of the bthread layer: Decomposing your problem into bthreads frees you up to pick a set of coordinating events, then start coding scenarios around those events. Fire up your program, see how it does, and then fix any bugs that testing/simulation/model checking shows up and go again.

The state machine ness also lets you react to entire event traces in order to handle things like a “win rather than defend” strategy in tic-tac-toe, which is one of the basic examples given in the article.

There’s room for plenty of cleverness in how the executive selects the next event and how to test and check bthread programs, but the core idea is elegant and exciting. The full article is worth a read.

David Harel, Assaf Marron, Gera Weiss. Behavioral Programming. Communications of the ACM, Vol. 55 No. 7, Pages 90-100. doi 10.1145/2209249.2209270. Retrieved 2012-07-23.