Poslední články

Co je čitelnější?

aneb překvapivé pojítko mezi matematikou a LISPem

Na VŠ jsme nedávno v hodinách topologie probírali vnitřek množiny, vnějšek množiny a podobné věci. Snažil jsem se udělat si v tom v hlavě pořádek, protože definice vnitřku je:

"Vnitřek množiny X je sjednocení všech otevřených podmnožin množiny X."

Hodně mi to připomíná LISPovou syntaxi:

(defn vnitrek [x]
  (sjednoceni
    (filter otevrena?
      (podmnoziny x))))

Člověk to musí číst odprostřed (od "konce") - je to prefixová notace. Chápu, proč ji používají matematici ve svých slovních definicích - chtějí, aby to bylo čím jak nejkratší, aby tam nebylo nic zbytečného, atd. - ale mně by k pochopení víc pomohlo, kdyby to rozvedli třeba takhle:

"Vnitřek množiny X získáš tak, že ji vezmeš, najdeš všechny její podmnožiny, z nich vybereš všechny, co jsou otevřené, a uděláš nad nimi sjednocení."

Neboli:

(defn vnitrek [x]
  (->> x
       podmnoziny
       (filter otevrena?)
       sjednoceni))

Když to vidím rozepsané takhle, dovedu si lépe představit, co se s tím, co mám zrovna v ruce děje, jak se to mění. V bakalářce by to asi neobstálo, ale pro čtenáře to je přístupnější :)

Nutno dodat, že u programování je čitelnost a pochopitelnost programu podstatně důležitější. Možná proto se mi to ->> makro tak líbí? :)

Snídaně

aneb vita vita vita!

Na začátku roku jsme s Tomem a Milanem drželi půst za ClicKostel (pro osvětlení, o co zhruba jde → sem).

Dokud žiješ pod mojí střechou!

Po čtyřdenním úplném půstu (voda a nic než voda) jsem zkusil pokračovat "Danielovým půstem" (viz Daniel 1 nebo Daniel 5) - víceméně se ze mě stal asi na týden vitarián. Tedy, ovoce, zelenina, ořechy a podobně.

Půst sám o sobě (z duchovního hlediska) byl zajímavá zkušenost, ale o tom se rozepíšu snad někdy později. K čemu se chci dostat dneska: některé věci mi v jídelníčku už zůstaly asi nadobro. Asi vás překvapí, jaká dobrota je třeba tahle snídaně: (post mortem sepsáno, co jsem bez většího přemýšlení narychlo splácal dohromady)


  • 3 jablka
  • 4 mrkve
  • 50g rozinek
  • 100g slunečnicových jader
  • 1 vrchovatá lžíce medu
  • 1 lžíce olivového oleje
  • (ještě bych tam přidal trochu citronové šťávy, kdyby mi na ni v tu chvíli padl zrak)

Rozmixovat → do talíře → posypat strouhaným kokosem, skořicí a vanilkovým cukrem.


Je toho jeden plný hluboký talíř, a ... tohle opravdu asi nic nepřekoná. Něco jako mrkvový salát od mamky, akorát ... s variacemi. Yum!

Rock Paper Scissors with core.async

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

Introduction

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!

project.clj

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"
                 "https://oss.sonatype.org/content/groups/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)
;=> {: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:

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

Now what are the pros and cons of this approach?

Wins

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

Fails

  • 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 ;)

Wins

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

Fails

  • 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.
thread

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?

Wins

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

Fails

  • 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.

Wins

  • 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! ;)

Fails

  • 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!