Poslední články

Rock Paper Scissors with core.async

aneb I'll probably have to translate the whole blog, won't I?


So, you want to do asynchronous programming in Clojure. You've searched on the internet and seen lamina and pulsar, but there's still some undescribable urge to examine what is the "official" solution to all those channels and whatnot.

Let's see it then! This is going to be a primer of sorts. Not answering all the questions, but getting your feet wet.

I'm going to walk you through the exciting world of Rock Paper Scissors! We will model the situation where two players get into a game, make their moves and a judge will decide who wins.

(Disclaimer: partially inspired by Anders Janmyr.)

It's very simplistic but there's a lot of space for you to experiment further: room with many (3+) players making games randomly, tournament where players advance the bracket, games of best-of-3, etc.

So, let's dive in!


Our first struggle happens right at the project.clj.

Because core.async isn't yet pushed to clojars or some standard maven repository, you either have to install it to your own local maven repository (what? I don't even have maven installed), or let Leiningen know that you want to fetch it from some other repository. And that's what we're going to do.

(defproject events "0.1.0-SNAPSHOT"
  :dependencies [[org.clojure/clojure    "1.5.1"]
                 [org.clojure/core.async "0.1.0-SNAPSHOT"]]
  :repositories {"sonatype-oss-public"

I think it's pretty self-explanatory, if unusual. In the source code itself we import it like this:

(ns events.core
  (:require [clojure.core.async :refer :all]))
RPS logic

So, let's build the basic logic of Rock-Paper-Scissors. There's no need to dive into the impure waters of core.async yet, let's keep it clean.

(def moves [:rock :paper :scissors])

(defn make-a-move []
  (rand-nth moves))

Now we introduce how our data structures will look. I chose a hash-map. We need player ID (so we can differentiate between them) and the move itself. When we decide who wins, we return his ID.

(defn rule [{p1 :player m1 :move}
            {p2 :player m2 :move}]
  (case m1 :rock     (case m2 :rock     nil
                              :paper    p2
                              :scissors p1)
           :paper    (case m2 :rock     p1
                              :paper    nil
                              :scissors p2)
           :scissors (case m2 :rock     p2
                              :paper    p1
                              :scissors nil)))

Think of it as of switch or a big if.

(rule {:player :A :move :rock}
      {:player :B :move :paper})
;=> :B

That should be enough for now.

no core.async

Let's think about how this would look using Clojure and nothing but Clojure.

Because the only thing our player will do is tell us his ID and move (as if he wasn't interested in the result of the game!), why not just return the data structure we talked about a while ago?

(defn player []
  {:player (keyword (gensym "p"))
   :move (make-a-move)})

(That gensym is there just to make an unique number. I didn't want to bother with some counter atom or closure.)

;=> {:player :p1023 :move :scissors}

The judge is going to look at the two hands, think a bit and declare a winner.

(defn judge [hand-1 hand-2]
  (let [winner (rule hand-1 hand-2)]
    {:winner winner
     :h1 hand-1
     :h2 hand-2}))

And, finally, we plumb it all together.

(defn play []
  (let [h1 (player)
        h2 (player)
        result (judge h1 h2)]
    (println result)))

The gameplay might look like this:

;=> {:winner :p1037
;    :h1 {:player :p1033 :move :paper}
;    :h2 {:player :p1037 :move :scissors}}

Now what are the pros and cons of this approach?


  • It's dead simple. Everybody who knows a little bit of Clojure will probably understand it.


  • It's sequential and makes us define the exact order of operations. In this little example it doesn't seem that much of a fail, but it's not optimal. Also there's no immediately obvious way to make this behave concurrently. Maybe futures?

Anyways, let's see what does core.async bring to the table.

chan, >!!, <!!

Here you see the three main functions you'll use.

(chan) ; Unbuffered channel.
       ; The sender and receiver will wait (block) for each other.

(chan 5) ; Channel with 5 slots. FIFO.
         ; If empty, the receiver will block.
         ; If full, the sender will block.

(chan (buffer 5)) ; The same as above.

(chan (dropping-buffer 5)) ; If full, the new value will be ignored.
                           ; Oh, and the sender won't block.

(chan (sliding-buffer 5)) ; If full, the oldest value will be dropped.


(>!! ch :val) ; Put :val into the channel.

(<!! ch) ; Read from the channel.

If the exclamation marks confuse you, read them this way:

  • The bangs are the channel.
  • When you do >!!, you point at the channel - you're giving it something.
  • When you do <!!, it's pointing at you - it's giving you something.

Now, let's redefine the player. He finally has somebody/something to tell his decisions to! He knows he will tell it to the judge using the channel. (Think about it as a mailbox.)

(defn player [game]
  (>!! game {:player (keyword (gensym "p"))
             :move (make-a-move)}))

The only thing changing here is the argument list (game is the channel) and the >!! call.

Now, the judge. He gets the two hands from the channel and decides who wins.

(defn judge [game]
  (let [hand-1 (<!! game)
        hand-2 (<!! game)
        winner (rule hand-1 hand-2)]
    {:winner winner
     :h1 hand-1
     :h2 hand-2}))

Now he doesn't take the two hands directly but through the channel.

I want you to pause on the fact that if we run on a single thread and we call the judge before both players have made their decisions, we get into a deadlock. The judge will wait for the second hand (or both of them) and of course won't be getting it. More on that later.

(defn play []
  (let [game (chan 2)]
    (player game)
    (player game)
    (println (judge game))))

Can you see the change here? We don't plumb the players' hands to the judge - the players put their decisions to the channel and the judge gets them from it. It's their decision, not the game's (whatever that means).

We've moved the reasoning about the message-passing from the play function to the individual functions - players and the judge. The only thing we still have to think about here is giving them all the same channel ;)


  • Separation of concerns. The possibly concurrent code is in composable, linear units. You can reason about the different parts independently.


  • It's all blocking. Definitely not parallel, definitely single-threaded.
  • We have to think about the order of operations. If we call the judge before the players, we get into a deadlock. Imagine an use case where the judge would put the results back into the channel and the players would read it and say "Yay" or "Oh no!" depending on whether they won or lose. You can't do that right now.

So, we want to avoid the deadlocks. The solution is to either be able to do more things at the same time, or to be able to jump between all the different parts that are waiting for something. We will examine the first possibility first and then the other.

(thread ...) ; Executes the body in another thread and returns immediately.
             ; Much like futures, don't you say?
             ; Returns a channel which will contain the result when completed.

So, how does our usage change? It's simple, the only thing that changes is our play function. We don't call the players and judge sequentially, we put them on different threads!

(defn play []
  (let [game (chan 2)]
    (thread (player game))
    (thread (player game))
    (println (<!! (thread (judge game))))))

If you're puzzled by the <!! on the last line, remember that thread returns a channel with the result of the body passed in.

All the <!! and >!! functions are still blocking! They're just on another threads so right now it's possible to change the order of the calls. We can call the judge as the first one, and he won't deadlock us to eternity.

There's just one little problem - prints from different threads don't show in your REPL. Otherwise I'd gladly do something like this just to show you we can change the order now and not get a deadlock:

(defn play []
  (let [game (chan 2)]
    (thread (player game))
    (thread (println (judge game)))
  ; (thread (spit "log.txt" (judge game))) would work though!
    (thread (player game))))

Obviously the way we do it now (with println being on the level of the other two threads), it would block and create a deadlock, not giving the other player any chance to even start.

So, pros and cons?


  • Although <!! is still blocking, it's now on another thread. The three participants can function in parallel.


  • There's the inconvenience of other threads not printing to REPL properly.
  • If you do blocking read on a main thread, you still can get deadlocks very easily.
  • And most importantly, on JavaScript VM there's only one thread!

What to do?

go, >!, <!

Here come the green threads. In the CLJS implementation the go macro transforms your code to a freaking state machine and whenever one "thread" blocks (or, as the developers put it, "parks"), something else gets executed. (In the JVM implementation it uses thread pools.)

This creates illusion of parallelism even in JavaScript, where it's not currently possible to program on more than one thread.

Let's look at it!

(go ...) ; Must wrap every use of <! and >!.
         ; Like thread, but works in JS.
         ; Also returns a channel with the result of the body.

(>! ch :val) ; Like >!! and <!!, the only difference is:
(<! ch)      ; THEY DON'T BLOCK.

The go form doesn't span inside function calls. So if you do (go (something)) (to not block and let the other parts run too), you have to wrap the inside of (something) with (go ...) too.

(defn something []
  (go ...))

(go (something))

Let's see how our code changes.

(defn player [game]
  (go (>! game {:player (keyword (gensym "p"))
                :move (make-a-move)})))

We can change the >!! to >! here, but then we have to wrap it all in (go).

(defn judge [game]
  (<!! (go (let [hand-1 (<! game)
                 hand-2 (<! game)
                 winner (rule hand-1 hand-2)]
             {:winner winner
              :h1 hand-1
              :h2 hand-2}))))

The judge is a little bit more complicated, but it all makes sense. Let me explain:

  1. You change the <!! inside the let to <! to not block.
  2. You wrap it into (go) for the <!'s to work.
  3. But it returns a channel - so <!! from it!
(defn play []
  (let [game (chan 2)]
    (go (println (judge game)))
    (go (player game))
    (go (player game))))

The play function is pretty straightforward. We just replace every thread with go.


  • We finally don't have to think about the order!
  • Parallel when it can; on JS at least works!
  • Somehow gets printing into REPL right! ;)


  • Can't think of any.
Final discussion

Changed way of thinking

The core.async approach to all things async is not unlike Go's channels or Erlang's actor model. I can see it modelling my thinking from Clojure's more usual nouns describing the objects and verbs describing the computation to the subjects (who - player, judge).

That seems very Erlang-y to me, and I like this kind of thinking - each go block being one entity communicating via channels, if not mailboxes.

Is that just a consequence of thinking about concurrency, threads, etc.?

What are the channels?

A thing I don't know how to handle are the channels and how to think about them - or at least how to name them.

If we stick to our game of RPS, what are they? Are they the "room"? Are they some kind of "coordinator"? Or are they just "channels", really? The "bus", "wire", ... "mailbox"? Just something connecting all these otherwise independent entities?

It seems weird to me to just call them the "channel". But "game" in my examples probably wasn't the best name either. The way we name things shapes how we think about them. If there is a way that makes it all simpler and more intuitive, I'd like to hear about it!

Web scraping

aneb když to nejde po dobrém ...

(Update: there will probably be some amount of English-speaking people trying to read this article. Sorry, it's in Czech. My next programming articles will all be in English. You can start with Rock Paper Scissors with core.async!)

Challenge: dostat adresář nakladatelů Národní knihovny ČR do Excelové tabulky.

Adresář nepodporuje nějaké hromadné stažení celé databáze - stáhne jen to, co vyhledáte, a má limit 1000 záznamů na stažený soubor. Takže na to musíme nějak chytře. A abychom se neuklikali k smrti, tak si to radši zautomatizujeme.

Krok první: nějak dotazy na tu databázi pokrýt celé spektrum a všechno to stáhnout.

První pokus byl nějak šikovně zformovat URLka a nechat Bash a wget udělat všechnu tu těžkou práci za mě. Jenže adresy se mění a dělá se tam nějaká magie s cookies, není to moc předvídatelné a nedařilo se mi.

Druhý pokus byl přes Twill - pythonovou knihovnu, která imituje prohlížeč - go("http://..."), follow("Link"), get_html() atd. Jenže adresář má nějakou ochranu proti botům, kterou se mi nepovedlo obejít ani změnou User-Agenta. Takže tohle taky ne.

UPDATE: po funuse jsem našel clj-webdriver ... Damn :)

Takže třetí, finální a musím dodat nejbrutálnější pokus: Automator a AppleScript. Jde o to, že programem ovládáte Safari a klávesnici. Vypadá to nějak takhle:

on run {input, parameters}
    set theCharacters to {"a*", "b*", "c*", "d*", "e*", "f*", "g*", "h*", "i*", "j*", "k*", "l*", "m*", "n*", "o*", "p*", "q*", "r*", "s*", "t*", "u*", "v*", "w*", "x*", "y*", "z*","0*","1*","2*","3*","4*","5*","6*","7*","8*","9*"}
    repeat with theChar in theCharacters
            tell application "Safari"
                do JavaScript "window.open('http://aleph.nkp.cz/F/')" in document 1
                delay 2
                do JavaScript "document.querySelectorAll('a')[15].click()" in document 1
                delay 2
                set theJS to "document.querySelector('input[name=request]').value = '" & theChar & "'"
                do JavaScript theJS in document 1
                do JavaScript "document.querySelector('input[type=image]').click()" in document 1
                delay 2
                do JavaScript "(document.querySelector('td[class="title"]') === null) ? 1 : 0" in document 1
                if the result = 1 then
                    tell application "System Events"
                        keystroke "w" using command down
                    end tell
                    error 0
                end if
                do JavaScript "document.querySelector('td[class="title"]').innerHTML.trim().match(/\d+$/)[0].length" in document 1
                if the result > 3 then error 0
                do JavaScript "document.querySelector('a[title="Vybrat vše"]').click()" in document 1
                delay 2
                do JavaScript "document.querySelector('a[title="Uložit/odeslat"]').click()" in document 1
                delay 2
                do JavaScript "document.querySelector('input[value="ALL"]').click()" in document 1
                do JavaScript "document.querySelector('input[value="NONE"]').click()" in document 1
                do JavaScript "document.querySelector('input[alt="Uložit/odeslat"]').click()" in document 1
                delay 2
                do JavaScript "document.querySelector('a[href$=".sav"]').click()" in document 1
                delay 2
                set theURL to URL of document 1
            end tell
            tell application "System Events"
                tell application "Safari" to activate
                keystroke "w" using command down
                tell application "iTerm" to activate
                keystroke "wget -q " & theURL & " # " & theChar
                keystroke return
            end tell
        end try
    end repeat
    return input
end run

Má to pár much - když má hledání více než 1000 výsledků, musím ten dotaz rozdělit na menší části. Tedy z "a*" udělám "a*a*", "a*b*", atd. Tohle jsem tam ale už nenakódoval - v AppleScriptu si nejsem tak jistý. Jen jsem nechal AppleScript daný tab nezavřít a nechal jsem si ho na ruční posouzení později. Potom jsem to rozdělení dělal "ručně" s pomocí makra ve VIMu - udělal jsem si řádek s abcdefghijklmnopqrstuvwxyz0123456789, vybral ho a zavolal na něm:


Výsledkem je "a*a*","a*b*",...

Nechal jsem to běžet přes noc (s počítačem se totiž během toho nemůže moc věcí dělat, vyžaduje to focus toho Safari a podobně) a výsledkem je 704 souborů s celkovou velikostí okolo 50MB.

Je tam hodně duplicit - ty by se snad mohly řešit nějakým chytřejším pokládáním dotazů (adresář povoluje dělat ORy atd.) - ale už by mi to komplikovalu logiku toho AppleScriptu. Tohle je simple enough.

Krok druhý: nějak to zparsovat do CSVčka.

Pro představu, každý soubor vypadá asi takhle:

     Záznamy vyhledané v databázích NK ČR
                                    Datum: 26/08/2013

     Číslo záznamu:         1
     Název nakl.         AAA
                          ##spol. s r.o.
     Adresa               Dvojdomí 609/1, 400 01 Ústí nad Labem
     Adresa               Hálkova 4, 120 00 Praha 2
     E-mail               petr.vrzak@centrum.cz
     Identifikátor       978-80-85995
     Prof. zaměření    * Maps
     Datum aktualizace    20060905 zden
     Systém. číslo     000008082

     Číslo záznamu:         2
     Název nakl.         Aaada English School for Children
     Adresa               Hloubětínská 26, 198 00 Praha 9
     E-mail               heck@volny.cz
     Identifikátor       Neregistrován v ISBN
     Datum aktualizace    20060322 sama
     Systém. číslo     000014300

Asi by to šlo udělat AWKem, napadl mě i Haskellovský Parsec, ale protože jsem Clojure fanboy, rozhodl jsem se prozkoumat, co nabízí jeho knihovny. A narazil jsem na Instaparse. Jde o to, že mu předáte ve stringu EBNF grammar, Instaparse vytvoří funkci a té prostě už jen předáváte string s těmi daty. Vypadá to asi takhle:

(ns nakladatelstvi.core
  (:require [instaparse.core :as insta]))

(def zaznamy
   "soubor = header, {zaznam}, <whitespace>, Epsilon

    header = <whitespace>,
             'Záznamy vyhledané v databázích NK ČR',

    datum_souboru = <'Datum: '>,

    zaznam = <whitespace>,
             {(<whitespace>, adresa)
              | (<whitespace>, email)
              | (<whitespace>, isbn)
              | <(<whitespace>, odkaz)>
              | (<whitespace>, ico)
              | (<whitespace>, url)
              | (<whitespace>, prof_zamereni)
              | <(<whitespace>, aktualizace)>
              | (<whitespace>, system_cislo)},

    cislo_zaznamu = <'Číslo záznamu:'>,

    nazev = <'Název nakl.'>,
            [<whitespace>, <'##'>, sentence]

    adresa = <'Adresa'>,

    email = <'E-mail'>,

    isbn = <'Identifikátor'>,

    odkaz = <'Odkaz. forma'>,

    ico = <'IČ'>,

    url = <'URL'>,

    prof_zamereni = <'Prof. zaměření'>,

    <zamereni> = <' '?>,
               <'* '>,

    aktualizace = <'Datum aktualizace'>,

    system_cislo = <'Systém. číslo'>,

    <whitespace> = #'\s+'
    <sentence> = ('(', sentence)
               | (')', [[<' '>], sentence])
               | (word, [[<' '>], sentence])

    <word> = #'[a-zA-Z0-9ĚŠČŘŽÝÁÍÉŮÚĎŤŇÓěščřžýáíéůúďťňó*/\-_=?:.,@#!&]+'

    <isbnre> = #'(\d+-\d+(-\d+)?)|Neregistrován v ISBN'
    <number> = #'[0-9]+'"))

(def test-soubor (slurp "adr10124698.sav"))

(def parsed (zaznamy test-soubor))

No a ono to vyhodí něco jako Hiccupovský zápis XMLka (který převedeme na XML samotným Hiccupem):

  "Záznamy vyhledané v databázích NK ČR"
  [:datum_souboru "26/08/2013"]]
  [:nazev "AAA" "spol." "s" "r.o."]
  [:adresa "Dvojdomí" "609/1," "400" "01" "Ústí" "nad" "Labem"]
  [:adresa "Hálkova" "4," "120" "00" "Praha" "2"]
  [:email "petr.vrzak@centrum.cz"]
  [:isbn "978-80-85995"]
  [:prof_zamereni "Maps"]
  [:system_cislo "000008082"]]
  [:nazev "Aaada" "English" "School" "for" "Children"]
  [:adresa "Hloubětínská" "26," "198" "00" "Praha" "9"]
  [:email "heck@volny.cz"]
  [:isbn "Neregistrován v ISBN"]
  [:system_cislo "000014300"]]]

V reále to je ještě trochu složitější - musíme escapovat ampersandy, apostrofy a podobně, aby nás XML mělo rádo, přidat umlauty do podporovaných znaků a podobně - ale nakonec se přece jen povede a všechny soubory jsou přečteny. Potom se už jen sloučí jedním reduce a vyplivne se XML.

Mimochodem, je úžasné, jak jednoduše Clojure umožňuje využít více jader procesoru. Můj kód chroustal hlavně dvě věci - první bylo samozřejmě vyparsovat z toho souboru data do té hierarchické struktury - a druhý bylo "zálohování" na disk. Prvně jsem se díval, že mě to, že jedou sekvenčně po sobě, víceméně brzdí. Tak jsem to zálohování obalil do future, a bylo. Naráz oba ty úkoly jely zároveň. Žádné locky, žádné mutexy, žádné semafory ... Jedna future. Úžasné!

No, ale to XML. Do CSVčka se dá docela jednoduše převést pomocí XSLT:

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:template match="/">
    <xsl:for-each select="//zaznam">
      <xsl:value-of select="system_cislo"/>
      <xsl:text> </xsl:text>
      <xsl:value-of select="nazev"/>
      <xsl:text> </xsl:text>
      <xsl:value-of select="email"/>
      <xsl:text> </xsl:text>
      <xsl:value-of select="adresa"/>
      <xsl:text> </xsl:text>
      <xsl:value-of select="isbn"/>
      <xsl:text> </xsl:text>
      <xsl:value-of select="prof_zamereni"/>
      <xsl:text> </xsl:text>
      <xsl:value-of select="ico"/>
      <xsl:text> </xsl:text>
      <xsl:value-of select="url"/>

(Pozn.: asi by šlo použít i clojure.data.csv nebo tak něco, ale když už to Instaparse vyhazuje v Hiccup formátu a Hiccup exportuje do XML... :) )

Krok třetí: vyhodit duplicity.

Tohle je nejjednodušší: Otevřu CSV v Excelu a vyfiltruju to podle sloupce Systémové číslo.


Nejkratší matematický vtip

aneb haha, I guess?