Asynchronous programs are hard to reason about. But is this intrinsic to asynchrony? Or might we be using the wrong paradigms?
Behavioral programming is a programming paradigm that aims to make asynchronous, event-driven systems both simple and easy by using a system centered on behavioral threads (bthreads). In my previous article, I introduced the idea of behavioral programming in Clojure.
In this article, we dive deeper. I hope to convince you that, compared to the alternatives:
- Bthreads decouple complex (and stateful!) application behaviors,
- Bthreads are more natural to reason about
Bthreads are both simple and easy. The simplicity is evident. Bthreads define isolated stateful application behaviors that communicate by requesting or blocking events.
Tic Tac Toe Example
To see why bthreads are easy, we will consider an example: programming a tic tac toe game. Programming games involves rules that can come into conflict (and hence need prioritization). In addition to rules (what must occur), there are strategies (what a rational player should do). Some events in tic tac toe originate from a human player. Other events are generated from the program, such as wins, draws, and computer moves.
Teaching a bprogram
Behavioral programming is performed by “teaching” the computer in a way similar to how we would teach a human. We might start teaching a person by saying “tic tac toe is a turn-based game, first player x goes; then, player y.” We teach our program in a similar fashion.
(require '[tech.thomascothran.pavlov.bthread :as bthread])
(defn make-enforce-turn-bthreads
[]
(let [moves (for [x-coord [0 1 2]
y-coord [0 1 2]
player [:x :o]]
[x-coord y-coord player])
x-moves
(into #{}
(comp (filter (comp (partial = :x) last)))
moves)
o-moves
(into #{}
(comp (filter (comp (partial = :o) last)))
moves)]
(bthread/seq
(interleave (repeat {:wait-on x-moves
:block o-moves})
(repeat {:wait-on o-moves
:block x-moves})))))
We use pavlov’s seq function, which creates a bthread from a sequence. Each map is a bid, which blocks all of one player’s possible moves until the other player moves.
{:wait-on x-moves
:block o-moves}
This can be read as: “block all of o’s moves until x makes a move”. When x makes a move, the bid is accepted, and the bthread makes its next bid:
{:wait-on o-moves
:block x-moves}
This is read as: “block all of player x’s moves until player o moves”.
We represent each move as [x-coordinate, y-coordinate, player].
Only one player per square
In Monopoly, two players can be on the same square at the same time. However, in tic tac toe, a square can only belong to one player.
(defn make-no-double-placement-bthreads
"You can't pick another player's square!"
[]
(for [x-coordinate [0 1 2]
y-coordinate [0 1 2]
player [:x :o]]
(bthread/seq
[{:wait-on #{[x-coordinate y-coordinate player]}}
{:block #{[x-coordinate y-coordinate :x]
[x-coordinate y-coordinate :o]}}])))
The sequence consists of only two events. First, our bthread waits on a move to be made:
{:wait-on #{[x-coordinate y-coordinate player]}}
This can be read as: “when this move occurs, make the next bid”. And the next bid simply blocks any further moves in that square:
{:block #{[x-coordinate y-coordinate :x]
[x-coordinate y-coordinate :o]}}
This bthread does not listen for any other events. It does not have a :request or :wait-on key. As a result, it blocks until the bprogram exits.
Bthread reducers
So far we have used seq to create bthreads. Sometimes this isn’t enough. We can also use bthread/reduce to construct a bthread.
The reduce function is used here to accumulate state across multiple iterations of event processing. Reduce takes up to three arguments:
(bthread/reduce reducing-fn
initial-value
options)
Let’s take a very straightforward example:
(def bthread
(b/reduce (fn [{:keys [times-called] :as _accumulated-value} _event]
(when-not (= times-called 3)
{:request #{:more}
:times-called (inc times-called)}))
{:times-called 0}))
We initialize the accumulated value as {:times-called 0}. The accumulated value passed to our reducing function is its previous bid. Because bids are just maps, we can add additional data to them.
We take advantage of this to track the number of times the bthread has executed. When it has executed three times previously, it returns nil. A bthread that returns nil is removed from the bprogram.
How to win
Let’s create a bthread for each winning path. Each move is represented as [x-coordinate, y-coordinate, player]. For example, [0 0 :x].
An example of a winning path would be #{[0 0 :x] [1 0 :x] [2 0 :x]}. We’ll pass this into make-winning-bthread:
(defn make-winning-bthread
"for a winning path (e.g., three diagonal squares
selected by the same player), emit a win event
and terminate the program."
[winning-paths]
(bthread/reduce
(fn [{:keys [remaining-events] :as acc} event]
(if event ;; event is nil on bprogram initialization
(let [event-type (event/type event)]
(if (= remaining-events #{event-type})
{:request #{{:type [(last event-type) :wins]
:terminal true}}
:remaining-events #{}}
(update acc :remaining-events disj event-type)))
acc))
;; Initial value
{:remaining-events (set winning-paths)
:wait-on (into #{}
(map (fn [event] {:type event}))
winning-paths)}
{:priority 100})) ;; overrides other bids
Just as we kept times-called as an accumulated value, so we keep the remaining-events. We can visualize how this changes in a table:
| Iteration | Event | New remaining-paths |
|---|---|---|
| 0 | nil |
#{[0 0 :x] [1 0 :x] [2 0 :x]} |
| 1 | [1 0 :x] |
#{[0 0 :x] [2 0 :x]} |
| 2 | [0 0 :x] |
#{[2 0 :x]} |
| 3 | [2 0 :x] |
#{} |
Whenever an event from winning-paths occurs, the reduce function iterates and returns the next bid.
Priorities
Notice that we do provide bthread/reduce with an optional argument that sets its priority to 1. Why do we need to prioritize bthreads?
Multiple bthreads will be notified of an event, and each will produce a bid. But only one requested event can be selected. The bid with the highest priority wins. In pavlov, by default the priority is 0. But this could result in, for example, a bid for a computer move being selected even though the player has just won.
For example, suppose our tic tac toe game looks like this:
[x _ o
x _ _
x _ o]
And we have the following bids:
| bthread | request | wait-on | block | priority |
|---|---|---|---|---|
| detect-wins | #{[:win :x]} |
0 | ||
| computer-moves | #{[2 1 :o]} |
0 |
What should happen? X should win. However, if the detect-wins thread has the same priority as computer-moves, then the choice between competing bids is non-deterministic.
If we set the priority of the detect-wins bthread higher than computer-moves, then the selected event will be [:win x]
Computer moves
It’s no fun to play tic tac toe against ourselves. We want the computer to play us. Let’s suppose we will be X, and the computer O.
It’s important to know what we do not have to do.
We do not have to figure out which squares are open. A standard approach might involve a function a bit like this:
(defn next-move
"Without worrying about strategy, let's pick a square"
[{:keys [board]} player]
(-> (remove occupied? board)
first
(make-move player))
next-move has no strategy; it simply selects the next unoccupied square. This conflates two concerns: enforcing the rule that a square can only be chosen once and determining the next move.
The equivalent bthread could be:
(defn make-computer-picks-bthreads
"Without worrying about strategy, let's pick a square"
[player]
(bthread/seq
(for [x-coordinate [0 1 2], y-coordinate [0 1 2]]
{:request #{{:type [x-coordinate y-coordinate player]}}})))
But wait – we are requesting all the squares on the board. Don’t we have to remember to block the occupied squares? Don’t we have to retract our bid if the game is over? Do we need to retract our bid if the game is over? Do we need to ensure that the computer waits for the player to take their turn? The answer to these questions is no. These concerns have already been handled by the specific bthreads designed for them.
Testing
One of the most useful aspects of behavioral programming is how easy testing isolated behaviors becomes.
Suppose we want to test the bthread that detects wins. Here’s what it looks like:
(deftest test-winning-bthreads
(testing "Given a bthread that watches a crossing win pattern for player x
When that crossing pattern is filled in by player x
Then the bthread requests a win event"
(let [bthread (make-winning-bthread
#{[0 0 :x] [2 2 :x] [1 1 :x]})
bid1 (bthread/bid bthread {:type [1 1 :x]})
bid2 (bthread/bid bthread {:type [2 2 :x]})
bid3 (bthread/bid bthread {:type [0 0 :x]})]
(is (= #{[0 0 :x] [2 2 :x]} (:remaining-events bid1))
"Track which events are left to reach a win for x after the first move")
(is (= #{[0 0 :x]} (:remaining-events bid2))
"Track which events are left to reach a win for x after the second move")
(is (= #{{:type [:x :wins] :terminal true}} (:request bid3))
"Request a win when all the winning moves have been made"))))
Of course, in a real game it is not possible for one player to move three times in a row. But that rule differs from the rules about winning. Testing is the best way we have to quickly verify we are properly separating concerns.
Representation
Rather than sharing a central representation, each bthread contains its own independent view of the world.
Most tic-tac-toe implementations would represent the board with something like this vector:
[nil :o nil
nil :x nil
nil nil :x]
Then we define operations performed against that representation. For example:
(defn draw?
"useful when determining whether a draw has occurred"
[board]
(and (nil? (winner board))
(every? keyword? board)
But our bthread implementation above:
- Has no shared representation of the board, and
- Never represents the board as a whole.
Nothing about behavioral programming prevents us from creating a bthread that maintains its data structure representing the entire board. A bthread could maintain its own representation of the board as a vector. But this representation is derived from the events and isolated to the bthread.
Conclusion
My purpose in this post is to show, by example, how programs can be “taught” incrementally using a similar progression to the way we would teach a human being. Arguably this can be a more natural way of thinking about how a program behaves. This ease is not purchased at the price of simplicity. Rather, it results from the strict separation of behaviors into bthreads, as well as the constrained semantics of behavioral programming (i.e, ask, refuse, wait).
This paradigm is flexible enough for various applications, such as stream processing (using Kafka or Kinesis) and managing complex UIs, and it includes established patterns for distributed systems. Hopefully this post inspires some glimmer of the possible applications of behavioral programming.