『Programming Clojure』を読んでいます. 第二版の邦訳が出る前に英語版買ってしまったけど, 買い直すのももったいないので英語で頑張る. 第五章が面白かったのでメモる.

プログラミングClojure 第2版

プログラミングClojure 第2版 [単行本(ソフトカバー)]

あと最近 オブジェクト指向をちゃんと知った上でオブジェクト指向はクソだと声高に主張する人があと100人は必要 このへんの話題を読んで, ちょうど興味が高まっていたというのもある.


プログラミングと時間/状態

現実世界を見ると, identityのvalueが変化したからといって過去のvalueが消えるわけではない(ある人の年齢が20歳になったからといって, 19歳であった事実は消えない). だがtraditionalなlock-basedアプローチの言語では, それをうまく反映できていなかった.

hoge = 123
hoge = 789

とすると, hogeという変数が123を指し示していた事実は消え去ってしまう.
でも, それじゃだめなのか? プログラミングが現実を反映していないからといって何が問題なのだろう? ...どうやらこの種の特性は, concurrent & parallelなプログラムを書く時に厄介な問題を引き起こすらしい.

concurrent/parallel プログラミング

調べて理解した限りの Concurrent programming についての情報を書くが, 間違っている可能性も高い(理解が間違っている箇所が判明すれば適宜直します).
そもそもConcurrent/Parallelなプログラムを書きたい理由としては, 近年はCPUそのものの性能向上よりもマルチコアを活用したプログラム実行がパフォーマンス向上に大きく影響している他, 論理的にindependentなoperationは実装しやすいという事情もあるらしい. 

まずConcurrent とは, 2つ以上の処理が同時に進んでいるように見える状態. forkして別スレッドでプログラムを実行させれば一番簡単なConcurrentの例になる.

Concurrent computing is a form of computing in which programs are designed as collections of interacting computational processes that may be executed in parallel.[1] Concurrent programs (processes or threads) can be executed on a single processor by interleaving the execution steps of each in a time-slicing way, or can be executed in parallel by assigning each computational process to one of a set of processors that may be close or distributed across a network.
Concurrent conputing - Wikipedia 


食事で例えるとこんな感じだろうか.

  • 非Concurrent「おかずをすべて食べたあとご飯に着手する」
  • Concurrent「おかずとご飯を交互に食べる」
同時に進んでいるように「見える」と書いたのは, おかずとご飯を交互に食べている状態でも, ある一瞬を切り出すとおかずだけあるいはご飯だけしか食べていないためである. 
一方 Parallel は「見える」だけでなく, 実際に並行して処理が進んでいる. 2人でひとつの皿を食べるとParallelになる. 

そもそもCPUが処理を行う基本動作もConcurrentと行っていいのだろうか. iTuneでBGMを流しながらブラウザとエディタをたちあげて作業していると同時に処理が進んでいるように見えるが, 実際CPUは複数の処理を少しずつ進めている(1.7GHzなら1秒間に1700000000回の命令が実行できるので人間が気づく前に色々同時にできる)

英単語的な意味では Concurrent は Parallelを包括するが, 研究分野としてのConcurrent conputingとParallel computingは集合関係にはなく直行する概念である(たとえばParallel computingの例であるHadoop研究も, その挙動を見ればConcurrentに動作していると言えるが, 研究の主眼はConcurrent性ではなくParallel性に置かれている)らしい(参考: concurrentとparallelの違い説明会 - Togetter


Concurrent programにおいては複数のobserver(例: thread)がdataを見ている. 複数のobserverがdataを参照したり変更したりするので, 同じコードを実行しても結果が異なる場合が出て来て, 困る. 

広く使われているMutableなlanguage(CとかJavaとかRubyとか)はlocking/defensive-copyingという手法でconcurrencyの問題に立ち向かってきた. たとえば "Java Concurrency in Practive [Goe06]" はこのテーマに関する良書だそうだ. 邦訳書はこれかな.

Java並行処理プログラミング ―その「基盤」と「最新API」を究める―
Java並行処理プログラミング ―その「基盤」と「最新API」を究める― [単行本]
 

Clojureのアプローチ


ClojureはMutable languagesとは別のアプローチを採る. これはClojureの大きな特徴の一つであるらしい.
 

Clojure's reference model is the most innovative part of the language.
p. 141 



Clojureは時間の経過と状態の共有(shared state)を扱う仕組みを用意している. 具体的には以下の4種のreference modelsを提供し, この中からexplicitに自分の使うモデルを選択する.

  • Refs: manage coordinated, synchronous changes to shared state.
  • Atoms: manage uncoordinated,  synchronous changes to shared state.
  • Agents: manage asynchronous changes to shared state.
  • Vars: manage thread-local state.

これによってprogramを

  • functional layer (immutable)
  • reference layer (mutable)

の2つに分離することができるという. 言語がよしなにやってくれるわけではなく, どんな性質のプログラムを書くかを考慮して自覚的に選択する必要があるのか. ちょっと難しそう(ここでは素人が何も考えずに使える類ではない, 程度の意図)だなという印象を受けた.


概論

 

clojure reference model cleary separate identities from values


clojureではほとんどすべてが変化しないvalueであり, reference modelは"変化する"部分として切り離している.

a "value" is an immutable and persistemt data structure.
A "stete" is the value of an identity at a point in time.

a valueは不変で具体的なただひとつの値である. "an identity"の持つvalueはどんどん変わっていくが, その1つの瞬間を捉えて"state"と称する. こんな感じ.


state


ライブラリや書き方, データベースでカバーしていた内容を言語自体に組み込んだと考えていいのかな. そういえばErlangでは変数への再代入を禁止していたが, それもこの種の問題への対処であったのかもしれない.



Ref


まずは reference modelsの第一, Ref. Refはref関数によって生成する. refは初期値を引数に取る. (doc ref)で参照すると

user=> (doc ref)
-------------------------
clojure.core/ref
([x] [x & options])
  Creates and returns a Ref with an initial value of x and zero or
  more options (in any order):

  :meta metadata-map

  :validator validate-fn

  :min-history (default 0)
  :max-history (default 10)

  If metadata-map is supplied, it will become the metadata on the
  ref. validate-fn must be nil or a side-effect-free fn of one
  argument, which will be passed the intended new state on any state
  change. If the new state is unacceptable, the validate-fn should
  return false or throw an exception. validate-fn will be called on
  transaction commit, when all refs have their final values.

  Normally refs accumulate history dynamically as needed to deal with
  read demands. If you know in advance you will need history you can
  set :min-history to ensure it will be available when first needed (instead
  of after a read fault). History is limited, and the limit can be set
  with :max-history.

optionにmin/max-historyがあって興味を惹かれる. 時間に応じて変化するvalueを記録していく機能を持つためか.

定義と参照. 前述のように (ref initial-value) で定義してderefか@で参照する.

user=> (def my-ref (ref 15))
#'user/my-ref
user=> (deref my-ref)
15
user=> @my-ref
15


Refを変更するのはref-setだが, これをそのまま使おうとすると,

user=> (ref-set my-ref 16)
IllegalStateException No transaction running  clojure.lang.LockingTransaction.getEx (LockingTransaction.java:208)

エラーが発生する.


refの立ち位置を思い出すと "manage coordinated, synchronous changes to shared state." であった. valueを変更する際は, 周囲にお伺いを立てながらじゃないとvalueを変更することが出来ない. お伺いを立てるマクロはdosyncである. dosync内で評価された式はsynchronous(他のobserverから変更が行われないことを)に変更が行われることが保証される.

user=> (dosync (ref-set my-ref 16))
16

このようなtransactionalな処理は "Software Transactional Memory (STM)" を使って行われる. STMとはなんだろう.


STMとACIDについて

Software Transaction Memory は並列計算を行う際の共有メモリへのアクセス方法であり, "ロック"の代替戦略である. "ロック"は「いまからこのデータ触らないでね」とデータを専有する方法で, データを参照する他の処理がストップするし, デッドロックや予期せぬバグなどの難しい問題を引き起こす. 一方STMは楽観的な手法であり, プログラマはより抽象化されたレイヤーの思考に集中できる. 多くの言語ではライブラリとして実装されているが, ClojureやHaskellでは言語自体にSTMが組み込まれている.
STMは, トランザクションシステムのACID特性のうちA, C, I を保証してくれる.

  • atomic: dosyncで囲った中で複数のref更新を行うと, すべてが1度に起こる. dosync内に一緒に入れたref更新は "coordinated(協調的に)" 起こることが保証される.
  • consistent: validationに失敗したときはvalueの変更が発生しない(注: 個々のrefにはメタデータとしてvalidation関数を定義することが出来る)
  • isorated: 成功するか失敗するかのどちらかで, 中途半端な状態はない

メモリ内のtransactionなので, ACIDのD(durable)がない. durableなtransactionが欲しいならDBを使うべし, とのこと.

STM最強!というわけではなく, dosyncでのwriteに不整合が発生するとトランザクションの最初からやりなおすので, writeが多いところで使うとパフォーマンスが落ちるというデメリットもあるらしい.
STMについての説明はこのスライドがわかりやすかった -> ClojureではじめるSTM入門 - SlideShare 

Atom

reference modelsの2個目はAtom. 定義, 参照方法はRefと変わらない.

user=> (def current-track (atom "Venus, Bringer of Pease"))
#'user/current-track
user=> @current-track
"Venus, Bringer of Pease"

更新にdosyncが必要ないことがAtom特徴であり, Refとの違い.

user=> (reset! current-track "Resetval")
"Resetval"

Refはcoordinate, Atomはuncoordinateな変更を扱う(復習). 複数のreferenceをまとめて変更したいならRef, 複数のreferenceをまとめて扱う必要がなければAtom... という使い分けをするのだろうか.

ここまでだとAtomはRefの劣化版に見えるが, Atomのswap!はRefができないこと, つまりreferenceのvalueを部分的に変更することができる. ←間違い. alterを使えばRefにも任意の関数を適用出来る.
たとえばAtomのvalueとしてmapが入っておりその一部を更新したいとする. Atomのswap!は任意の関数を適用出来るので, valueのsetではなくその場変更を行える.

user=> (def my-track (atom {:title "Credo" :composer "Byrd"}))
user=> (swap! my-track assoc :title "Sancte Deus")
{:title "Sancte Deus", :composer "Byrd"}
user=> @my-track
{:title "Sancte Deus", :composer "Byrd"}

swap!のdocも貼っておく. 上の例だとassocがapplyするfunctionにあたる.

user=> (doc swap!)
-------------------------
clojure.core/swap!
([atom f] [atom f x] [atom f x y] [atom f x y & args])
  Atomically swaps the value of atom to be:
  (apply f current-value-of-atom args). Note that f may be called
  multiple times, and thus should be free of side effects.  Returns
  the value that was swapped in.

Agent

Agentは非同期のvalue更新を行う. 参照はRef/Atomと同じくderefか@.

Agentにはsendという関数があり, swap!の時のAtomのようにupdate functionによるagentのvalue更新を別threadで行なってくれる.

user=> (def counter (agent 0))
#'user/counter
user=> (send counter inc)
#<Agent@3a21fa7: 1>
user=> (send counter inc)
#<Agent@3a21fa7: 2>

sendは更新後の値ではなくAgent自体を返しているが, これは更新が非同期に起こるのでRefやAtomのように更新後の値が即座に帰ってこないため.

Var

varはスレッドローカルな変数を扱うという. スレッドローカルな変数とはどういうことか. おもむろにbindingの説明が始まる. bindingは基本的にletと同じ構文だが, 以下の様な違いがある.

(def ^:dynamic foo 10)
(let [foo 9999] (println foo)) ;;=> 9999
(binding [foo 9999] (println foo)) ;;=> 9999

(defn print-foo [] (println foo))
(let [foo 9999] (print-foo)) ;;=> 10
(binding [foo 9999] (print-foo)) ;;=> 9999

驚いたことにbindingは関数による束縛スコープを上書きする. ちなみにふつうにdefするとdynamic varじゃないので以下のように怒られる.

user=> (def foo 10)
user=> (binding [foo 9999] (print-foo))
IllegalStateException Can't dynamically bind non-dynamic var: user/foo  clojure.lang.Var.pushThreadBindings (Var.java:353)

クロージャ(clojureではなくclosureを指してる)の束縛を上書きすることで何が嬉しくなるんだろうか. 不要な複雑さではないか? とつぶやいたらねこはるさんからよくある使い方を教えてもらった.


なるほど. 本文の続きを読むと 

dynamic binding has great power. But...(ry Functions that use dynamic bindings are not pure functions and can quickly lose the benefits of Clojure's functional style. (p.130)

と書いてるし, 危険性理解して使えよという感じなのかな. Haskellほど純粋さにこだわっていないClojureさん.