ch08-async.html

<section data-type="chapter" id="chapter08">
<h1>Asynchronous processing</h1>

<p>
In this chapter, you will write an étude that uses <a href="http://clojuredocs.org/clojure.core.async"><em>core.async</em></a> to do asynchronous processing.
</p>
  
<p>
Here are two examples of using <em>core.async</em>. In the first example, Annie and Brian are going to send each other the numbers 5 down to zero, stopping at zero, in a project named <code>async1</code>. You will need to add some <code>:require</code> and <code>:require-macro</code> specifications to your namespace:
</p>

<pre data-type="programlisting" data-code-language="clojurescript">(ns ^:figwheel-always async1.core
  (:require-macros [cljs.core.async.macros :refer [go go-loop]])
    (:require [cljs.core.async
               :refer [&lt;! &gt;! timeout alts! chan close!]]))</pre>

<p>
Then, define a <em>channel</em> for both Annie and Brian:
</p>

<pre data-type="programlisting" data-code-language="clojurescript">(def annie (chan))
(def brian (chan))</pre>

<p>
Annie gets two processes: one for sending messages to Brian and another for receiving messages from him.
</p>

<pre data-type="programlisting" data-code-language="clojurescript">(defn annie-send []
  (go (loop [n 5]
           (println "Annie sends" n "t` Brian")
           (>! brian n)
           (when (pos? n) (recur (dec n))))))

(defn annie-receive []
  (go-loop []
           (let [reply (&lt;! brian)]
             (println "Annie receives" reply "from Brian")
             (if (pos? reply)
               (recur)
               (close! annie)))))</pre>

<p>
In the <code>annie-send</code> function, you see the <code>go</code> function, which asynchronously executes its body and immediately returns to the calling function. The <code>&gt;!</code> function sends data to a channel. The loop continues until <code>n</code> equals zero, at which point the function returns <code>nil</code>.
</p>

<p>
Because <code>go</code> and <code>loop</code> occur together so often, ClojureScript has the <code>go-loop</code> construct, which you see in the <code>annie-receive</code> function. That function loops (but does not need the loop variable) until it has received the zero, at which point it performs a <code>close!</code> on the channel.
</p>

<p>
A similar pair of functions <code>brian-send</code> and <code>brian-receive</code> do Brian’s sending and receiving tasks (they are not shown here). You may have noticed there’s a lot of duplication here; we’ll get rid of it in the next example.
</p>

<p>
All that remains to be done is write a function that invokes these processes:
</p>

<pre data-type="programlisting" data-code-language="clojurescript">(defn async-test []
  (do
    (println "Starting...")
    (annie-send)
    (annie-receive)
    (brian-send)
    (brian-receive)))</pre>

<p>
Here is the console log output from invoking <code>async-test</code>. You can see that this is indeed asynchronous; the sends and receives are in no particular order.
</p>

<pre>
Starting...
Annie: 5 -&gt; Brian 
Annie: 5 &lt;- Brian 
Brian: 5 -&gt; Annie 
Brian: 5 &lt;- Annie 
Annie: 4 -&gt; Brian 
Annie: 3 -&gt; Brian 
Brian: 4 -&gt; Annie 
Brian: 3 -&gt; Annie 
Annie: 4 &lt;- Brian 
Annie: 3 &lt;- Brian 
Brian: 4 &lt;- Annie 
Brian: 3 &lt;- Annie 
Annie: 2 -&gt; Brian 
Annie: 1 -&gt; Brian 
Brian: 2 -&gt; Annie 
Brian: 1 -&gt; Annie 
Annie: 2 &lt;- Brian 
Annie: 1 &lt;- Brian 
Brian: 2 &lt;- Annie 
Brian: 1 &lt;- Annie 
Annie: 0 -&gt; Brian 
Brian: 0 -&gt; Annie 
Annie: 0 &lt;- Brian 
Brian: 0 &lt;- Annie 
</pre>

<p>
You can see the entire program here: <a href="#SOLUTION08-ET00A" data-type="xref">#SOLUTION08-ET00A</a>.
</p>

<p>
The next example using <em>core.async</em>, in a project named <code>async2</code>, has processes that communicate with one another in a semi-synchronized manner. In this case, Annie will start off by sending Brian the number 8; he will send her a 7; she sends back 6, and so on, down to zero.
</p>

<p>
In this case, both people do the same thing: send the next lower number to their partner, then await the partner’s reply. Here is the function to activate the process for the two partners. The <code>from-str</code> and <code>to-str</code> parameters are used for the debug output. 
</p>

<pre data-type="programlisting" data-code-language="clojurescript">(defn decrement! [[from-str from-chan] [to-str to-chan] &amp; [start-value]]
  (go-loop [n (or start-value (dec (&lt;! from-chan)))]
           (println from-str ":" n "->" to-str)
           (>! to-chan n)
           (when-let [reply (&lt;! from-chan)]
             (println from-str ":" reply "&lt;-" to-str)
             (if (pos? reply)
               (recur (dec reply))
               (do
                 (close! from-chan)
                 (close! to-chan)
                 (println "Finished"))))))</pre>

<p>
There are several clever tricks going on in this function.  The <code>&amp; [start-value]</code> allows an optional starting value. There’s an asymmetry in the processes; Annie starts the sending, and Brian starts by receiving her data. Thus, Annie will start with 8 as her <code>start-value</code>; Brian will omit that argument. The completion of this bit of kabuki is in <code>(or&#160;start-value&#160;(dec&#160;(&lt;!&#160;from-chan)))</code>; if <code>start-value</code> is <code>nil</code> (which evaluates to false), you take one less than the received value as your starting value.
</p>

<p>
Similarly, the <code>when-let</code> clause is executed only when the reply from <code>from-chan</code> is  true (i.e., not <code>nil</code>).
</p>

<pre data-type="programlisting" data-code-language="clojurescript">(defn async-test []
  (let [annie (chan)
        brian (chan)]
    (activate ["Annie" annie] ["Brian" brian] 8)
    (activate ["Brian" brian] ["Annie" annie])))</pre>

<p>
Here is the output from invoking <code>async-test</code>.
</p>

<pre>Annie : 8 -&gt; Brian
Brian : 7 -&gt; Annie
Annie : 7 &lt;- Brian
Annie : 6 -&gt; Brian
Brian : 6 &lt;- Annie
Brian : 5 -&gt; Annie
Annie : 5 &lt;- Brian
Annie : 4 -&gt; Brian
Brian : 4 &lt;- Annie
Brian : 3 -&gt; Annie
Annie : 3 &lt;- Brian
Annie : 2 -&gt; Brian
Brian : 2 &lt;- Annie
Brian : 1 -&gt; Annie
Annie : 1 &lt;- Brian
Annie : 0 -&gt; Brian
Brian : 0 &lt;- Annie
Finished</pre>

<p>
You can see the entire program here: <a href="#SOLUTION08-ET00B" data-type="xref">#SOLUTION08-ET00B</a>.
</p>

  <section data-type="sect1" id="ETUDE08-01">
  <h1>Étude 8-1: TBD</h1>
  <p>
  In this étude, you’re going to write a program that lets the computer play the card game of "War" against itself.
  </p>
  
  <section data-type="sect2" id="war-explained">
  <h2>The Art of War</h2>
  <p>These are the rules of the game as condensed from <a href="http://en.wikipedia.org/wiki/War_%28card_game%29">Wikipedia</a>, adapted to two players, and simplified further.
  </p>

  <p>
  Two players each take 26 cards from a shuffled deck. Each person puts their top card face up on the table. Whoever has the higher value card wins that battle, takes both cards, and puts them at the bottom of her stack. What happens the if the cards have the same value? Then the players go to "war." Each person puts the next two cards from their stack face down in the pile and a third card face up. High card wins, and the winner takes all the cards for the bottom of their stack. If the cards match again, the war continues with another set of three cards from each person. If a person has fewer than three cards when a war happens, they put in all their cards.
  </p>
  
  <p>
  Repeat this entire procedure until one person has all the cards. That player wins the game. In this game, aces are considered to have the highest value, and King > Queen > Jack.
  </p>
  
  <p>
  A game can go on for a <em>very</em> long time, so I have added a new rule: if the game goes more than a pre-determined maximum number of rounds (50 in my program), stop playing. The person who has fewer cards win. If the number of cards is equal, it’s a tie.
  </p>
  </section>
  
  <section data-type="sect2" id="war-purpose">
  <h2>War: What is it good for?</h2>

  <p>
  Absolutely nothing. Well, almost nothing. War is possibly the most incredibly inane card game ever invented. It is a great way for children to spend time, and it’s perfect as an étude because
  </p>

  <ul>
    <li>it is naturally implementable as channels (players) passing information (cards)</li>
    <li>there is no strategy involved in the play, thus allowing you to concentrate on the channels and messages</li>
  </ul>
  </section>

  <section data-type="sect2" id="war-strategy">
  <h2>Pay Now or Pay Later</h2>

  <p>
  When you purchase an item, if you pay cash on the spot, you often end up paying less than if you used credit. If you are cooking a meal, getting all of the ingredients collected before you start (pay now) is often less stressful than having to stop and go to the grocery store for items you found out you didn’t have (pay later). In most cases, “pay now” ends up being less expensive than “pay later,” and that certainly applies to most programming tasks.
  </p>

  <p>
  So, before you rush off to start writing code, let me give you a word of advice: Don’t. Spend some time with paper and pencil, away from the computer, and <em>design</em> this program first. This is a non-trivial program, and the “extra” time you spend planning it (pay now) will save you a lot of time in debugging and rewriting (pay later). As someone once told me, “Hours of programming will save you minutes of planning.”
  </p>
  
  <p>
  Trust me, programs written at the keyboard look like it, and that is not meant as a compliment.
  </p>
  
  <p>
  Note: This does not mean that you should never use +erl+ or write anything at the keyboard. If you are wondering about how a specific part of Erlang works and need to write a small test program to find out, go ahead and do that right away.
  </p>
  
  <p>
  Hint: Do your design on paper. Don’t try to keep the whole thing in your head. Draw diagrams. Sometimes a picture or a storyboard of how the messages should flow will clarify your thinking. (If your parents ever asked you, “Do I have to draw you a diagram?”, you may now confidently answer “Yes. Please do that. It really helps.”)
  </p>
  </section>
  
  <section data-type="sect2" id="war-design">
  <h2>The Design</h2>

  <p>
  When I first started planning this, I was going to have just two processes communicating with one another, as it is in a real game. But let’s think about that. There is a slight asymmetry between the players. One person usually brings the cards and suggests playing the game. He shuffles the deck and deals out the cards at the beginning. Once that’s done, things even out. The game play itself proceeds almost automatically. Neither player is in control of the play, yet both of them are. It seems as if there is an implicit, almost telepathic communication between the players. Of course, there are no profound metaphysical issues here. Both players are simultaneously following the same set of rules. And that’s the point that bothered me: who makes the “decisions” in the program? I decided to sidestep the issue by introducing a third agent, the <em>dealer</em>, who is responsible for giving the cards to each player at the start of the game. The dealer then can tell each player to turn over cards, make a decision as to who won, and then tell a particular player to take cards. This simplifies the message flow considerably.
  </p>


  <p>In my code, the dealer had to keep track of:</p>

  <ul>
  <li>The players’ channels</li>
  <li>The current state of play (see the following)</li>
  <li>Cards received from player 1 for this battle</li>
  <li>Cards received from player 2 for this battle</li>
  <li>The pile of cards in the middle of the table</li>
  </ul>

   <p>
  The dealer initializes the players, and then is in one of the following states. I’m going to anthropomorphize and use “me” to represent the dealer.
  </p>
  
  <dl>
  <dt>Pre-battle</dt>
  <dd>Tell the players to send me cards. If the pile is empty, then it’s a normal battle; give me one card each. If the pile isn’t empty, then it’s a war; give me three cards.</dd>
  
  <dt>Battle</dt>
  <dd> Wait to receive the cards from the players. 
  If either player has sent me an empty list for their cards, then that player is out of cards, so the other player must be the winner. Send both players a message to quit looping for messages.
  
  <p>
  If I really have cards from both players, compare them. If one player has the high card, give that player the pile plus the cards currently in play, and go into post-battle state. Otherwise, the cards match. Add the cards currently in play to the pile, and go back to “Pre-battle” state.
  </p>
  </dd>
  
  <dt>Post-battle</dt>
  <dd>
  Wait for the person to pick up the cards sent by the dealer. If you’ve hit the maximum number of rounds, go to long-game state. Otherwise, go back to “Pre-battle” state.
  </dd>
  
  <dt>Long-game</dt>
  <dd>
  The game has taken too many moves. Ask both players for the number of cards they have, and tell them both to quit looping. The winner is the player with the smaller number of cards (or a tie if they have the same number of cards).
  </dd>
  </dl>

  <p>
  Note that this is my implementation; you may find an entirely different and better way to write the program.
  </p>
  </section>
  
  <section data-type="sect2" id="war-messages">
  <h2>Messages Are Asynchronous</h2>
  <p>
  Remember that the order in which a process receives messages may not be the same order in which they were sent. For example, if players Annie and Brian have a battle, and Annie wins, you may be tempted to send these messages:
  </p>

  <ol>
    <li>Tell Annie to pick up the two cards that were in the battle.</li>
    <li>Tell Annie to send you a card for the next battle.</li>
    <li>Tell Brian to send you a card for the next battle.</li>
   </ol>

  <p>
  This works nicely unless Annie had just thrown her last card down for that battle and message two arrives <em>before</em> message one. Annie will report that she is out of cards, thus losing the game, even though she’s really still in the game with the two cards that she hasn’t picked up yet.
  </p>
  </section>
  
  <section data-type="sect2" id="war-deck">
  <h2>Representing the Deck</h2>
  <p>
  I decided to represent the deck as a vector of the numbers 0 through 51 (inclusive); 0 through 12 are the Ace through King of clubs, 13 through 25 are diamonds, then hearts, then spades. (That is, the suits are in English alphabetical order.) You will find ClojureScript’s <code>shuffle</code> function to be quite useful. I wrote a small module in a file named <em>utils.cljs</em> for functions such as converting a card number to its suit and name and finding a card’s value. 
  </p>
  
  <p>
  If you want to make a web-based version of the game, you will find a set of SVG images of playing cards in the <em>datafiles/chapter08/images</em> directory, with names <em>0.svg</em> through <em>51.svg</em>. These file names correspond to the numbering described in the preceding paragraph. The file <em>blue_grid_back.svg</em> contains the image of the back of a playing card.
  </p>
  
  <p>
  Note: You may want to generate a small deck with, say, only four cards in two suits. If you try to play with a full deck, the game could go on for a very long time.
  </p>
  </section>

  <p>
  Here is output from a game:
  </p>
  
  <pre>Starting Player 1 with [2 0 16 13 14 18]
Starting Player 2 with [1 4 3 15 17 5]
** Starting round 1
Player 1 has [2 0 16 13 14 18] sending dealer (2)
Player 2 has [1 4 3 15 17 5] sending dealer (1)
3 of clubs vs. 2 of clubs
Player 2 receives [2 1] add to [4 3 15 17 5]
** Starting round 2
Player 1 has [0 16 13 14 18] sending dealer (0)
Player 2 has [4 3 15 17 5 2 1] sending dealer (4)
Ace of clubs vs. 5 of clubs
Player 2 receives [0 4] add to [3 15 17 5 2 1]
** Starting round 3
Player 1 has [16 13 14 18] sending dealer (16)
Player 2 has [3 15 17 5 2 1 0 4] sending dealer (3)
4 of diamonds vs. 4 of clubs
** Starting round 4
Player 2 has [15 17 5 2 1 0 4] sending dealer (15 17 5)
Player 1 has [13 14 18] sending dealer (13 14 18)
6 of diamonds vs. 6 of clubs
** Starting round 5
Player 1 has [] sending dealer ()
Player 2 has [2 1 0 4] sending dealer (2 1 0)
nil vs. Ace of clubs
Winner: Player 1</pre>

  <p>
  See a suggested solution: <a href="#SOLUTION08-ET01" data-type="xref">#SOLUTION08-ET01</a>.
  </p>

  </section>

</section>