2013-12-14

生まれて約三時間目のHashlog

これはClojure Advent Calendar 14日目のエントリです。


(最近自作したライブラリ、Hashlogについて書きます。)


複雑な難しいプログラムを書くのはつらくとも面白いけど、煩雑なプログラムを書くのはつまらないです。

煩雑
事柄がこみいっていてまとまりがつかず,わずらわしいこと(さま)。

例えばこんなコードを読んだことが有ります(実物じゃないですよ)。

// 擬似コードです
function calc($value1,$value2,$value3,$flag)
{
  if($value1>0) {
    if($value1>=5)
      return  5;
    elseif($flag===true)
      return 4;
  }
  elseif($value2>0)
    return 3;
  elseif($value3>0)
    return 2;
  else
    return 1;
}


ある計算をする関数なんですが、if-ifelse、ifのネストで返り値を決めています。
これコード自体は「まぁしゃーない」で済ませられると思います。
しかしこの関数が30箇所にベタ書きで書いてあって、微妙な違い($value5まである/$value2までしかない、$flag2がある)があったらどうでしょう。
さらに30のなかの5個ぐらいはまったく違う引数を取って、別々の数式で返り値を計算している。

ビルの屋上で「F****CK!」と叫びたくなってきます。



if-elseif、ifのネストの何がダメなのか


5個のまったく違うロジックは置いといて、25個の微妙に違うをロジックを共通化できないか、私は考えました。

私の好きな言語はClojureです。Clojureは関数型プログラミングの考え方を取り入れており、そのスタイルに慣れると小さな関数を組合せてコーディングする考え方が身につきます。

「関数的に書き直せば共通化できるんじゃないか」と思って試してみました。

  • 入力値($value1、$flag等)を連想配列にまとめる
  • 連想配列を受け取って連想配列を返す関数群を定義する。
  • その関数を一列に並べて、連想配列をバケツリレー的に渡して更新していく。

こんなイメージでコードを書きました。



なんかしっくりこない。よくよくテストするとうまくいかないケースが出てくる。
上記の試作コードだと条件分岐を書くことが自然にできない。できるけど複雑になりすぎる感じがする。


最初のコードのif-elseif、ifのネストの何がダメなのかよく考えると、その処理フローのなかに状態を隠しているからではないかと思いつきました。

if(X)
  hoge();
elseif(Y)
  fuga();

elseif(Y)は条件Yだけでなく条件Xがfalseであるという結果も絡まっている。
試作コードのイメージで連想配列の受け渡しに変換しようとすると、hoge()、fuga()を単体の関数にすることが出来なくて、「状態」という別要素を組み込まないといけなくなる。

「状態かぁ。どんどんシンプルから離れていく感じがする」というのがこれに気づいた時の感想。




Rich Hickeyのスピーチ「シンプルさの必要性」


シンプルさの必要性 | eed3si9n

そんなときにこの記事のことを思い出しました。Rich HickeyさんはClojureの作者です。Clojure/Conjのキーノートスピーチを聞いてもシンプルさ・良いアイデアを考えることについて強い意志をもっていることが読み取れます。

Hammock Driven Development - Rich Hickey - YouTube
Hammock Driven Development Cheat Sheet | Data Sorcery with Clojure


僕たちは、今書いているプログラムと全く同一のものを、劇的にシンプルなものを使って作ることができます。
劇的にシンプルな言語、ツール、テクニック、方法論などです。もっと過激にシンプルなものです。例えば、Ruby と比べてより過激にシンプルなものを使うことができます。何故そうしないのでしょうか?

シンプルさの必要性 | eed3si9n



「最初の試作コード、なんだか難しく考えすぎてたんではないか」。
状態、順序、シンプルさ。いろんな要素が頭のなかでぐつぐつ煮える日々が過ぎました。
(ちなみに計算ロジックのリファクタリングは業務の片手間でやってたので時間はわりかしありました)

すごくシンプルに考えてみよう。入力値を連想配列にするのは良いことだ。けっきょくやってるのは連想配列を書き換えることだ。
私がプログラミングしてて難しいところを考えるときは図を描くのですが、そのとき頭に浮かんでたのはこんな図でした。





連想配列を見て「条件」に合致しているか判定して、指定した「キー」と「値」を更新するようなイメージです。

「これって宣言的に書けるんじゃないか、Prologっぽい感じで」

ちょうどClojureハッカソンであるTokyo.clj#17が11月30日にあったので、そのときに書いてみました。(ちなみに次回は来年1月
それがHashlogです(HashMap + Prologの造語です)。

Github - deltam/hashlog



Hashlog DSLの書き方


core.cljにcommentでサンプルを書きましたが、Hashlog DSLはこんなかんじです。
マクロは使ってません。ただのvectorとHashMapの組合せです。

(def hashlog-dsl
  [{:cond (exists :key1)     ; 入力HashMapの条件
    :key :output             ; 値を追加するキー
    :val (multiply :key1 10) ; キーに対応する値
    }
    ...
    ])

実行する場合は、DSLと入力HashMapを渡して更新されていくHashMapのシーケンスを取得します。
更新された結果に変化が無かったらそれ以上のシーケンスはdropします(無限ループを避けるため)。
queryを使うとシーケンスのHashMapを検索して最初に追加されたキーの値を返します。

(use 'hashlog.core)

(def hs (hash-seq {:key1 100, :key2 200} hashlog-dsl))

(query hs :outpu)
;=> 1000

core.cljのサンプルには、リンゴとオレンジしかない果物屋さんの料金計算の例を書いてみました。値引きクーポンを発行する場合も通常の料金計算に追加するかたちでロジック変更ができます。


(def fruits-price
  [
   {:cond (exists :apple)
    :key :priceOfApple
    :val (multiply :apple 100)
    }
   {:cond (exists :orange)
    :key :priceOfOrange
    :val (multiply :orange 80)
    }
   {:cond (every [(exists :priceOfApple) (exists :priceOfOrange)])
    :key :price
    :val (sum [:priceOfApple :priceOfOrange])
    }
    ;; 値引きクーポン
   {:cond (every [(exists :price) (is :hasCoupon true)])
    :key :discountPrice
    :val (multiply :price 0.9)
    }
   {:cond (every [(exists :price) (is :hasCoupon false)])
    :key :discountPrice
    :val (value :price)
    }
   ]
)

;; 通常の料金計算
(query (hash-seq {:apple 1, :orange 2, :hasCoupon true} fruits-price) :price)
;=> 260

;; 値引きクーポン有りの料金計算
(query (hash-seq {:apple 1, :orange 2, :hasCoupon true} fruits-price) :discountPrice)
;=> 234.0


Hashlogは使えるのか?


最初に手を付けたのは2週間ほど前ですが、Githubに上げたのは3時間ぐらい前です。
私は最初の書いた煩雑な計算ロジックをリファクタリングするために使うつもりです。

最初のプログラムがPHPだったのでPHP版も作ってます。実はPHP版を最初に書いたんですが、関数的書き方が使いにくかったので、まずClojureでプロトを作っていろいろ実験してる、という状態です。

Hashlogの仕様、DSLの書き方は今後どうなるか分かりません。でも基本的なアイデアは変わらないと思います。
HashMapを宣言的に書き換えることで計算ロジックを組み立てる」というアイデアは言語を問わず使えます。

Hashlogはまだ煮詰まってません。なにかアイデアがあったら教えて下さい。
「これってXXXと同じものじゃないの?」みたいなのも教えてくれると助かります。作ってる間、なにかを再発明してるんじゃないかという思いは常にあったので。
お気軽に@deltamまで話しかけてくださーい。




次回、Clojure Advent Calendar 15日目はathosさんです。

2013-12-11

core.unify - 単一化をサポートするClojureライブラリ

(この記事はClojure Contrib Library Advent Calendar 2013の11日目の記事です)


概要

core.unifyは「単一化」をClojureで扱うためのライブラリです。作者は『Joy of Clojure』の著者の一人、Fogusさんです。

単一化はPrologなど論理プログラミングなどで使われる処理で、与えられた条件から未知の値を推論する仕組みです。単一化自体について詳しく説明するのは私には難しいので、詳しくはWikipedia等で調べて下さい;−)

ユニフィケーション - Wikipedia

抽象度が高いライブラリなので利点が分かりにくいですが、同じくFogusさんの作ったcore.constractsで使われているそうです。

fogus: Using unification to write readable Clojure macros?



Clojure Contirib Libraryにはcore.logicという論理プログラミングをするためのライブラリがあり、そちらでも単一化の機能は提供してます。ではなんでcore.unifyがあるんでしょう?
READMEを読むとcore.logicとの違いについて次のように書いてあります。

Differences from core.logic
===========================

core.unify provides a la carte unification facilities that are not deeply tied into the operation of a logic engine. While core.logic does provide a similar simple unifier interface with support for specifying fine-grained constraints, if you have no need for a logic programming system, core.unify may be a better fit.

core.unifyは、論理プログラミングをバリバリ使いたい人ではなく、単一化の機能だけを使いたい人を対象に作られてるようですね。

core.unifyは次の機能を提供します
  • 単一化の束縛を作る、置き換え、単一化を行なう関数のファクトリー関数(occur-check有り/無し)
  • 上記の処理をパッケージ化し、"?"が接頭辞になるシンボルを置き換え用の値として解釈するしくみ
※occur-checkは後述


インストール

現在の最新安定版は0.5.5です。

leiningenを使う場合は:dependenciesに以下を追加してください。

[org.clojure/core.unify "0.5.5"]

今後の最新情報&Mavenでのインストールは公式のREADME.mdを参照して下さい。


使い方

core.cljは240行程度がライブラリ本体で、あとは使用例がcommentマクロで書いてあります。

core.unify/src/main/clojure/clojure/core/unify.clj at master · clojure/core.unify

"PUBLIC API"というコメント文の下に幾つか関数が並んでますが、基本的には次の3+2個の関数を知ってればOKのようです。

  • unify, unify-
  • subst
  • unifier, unifier- 

substはsubstitute(置き換え)の略。
unify-,unifier-については後述します。


まずは単純な例から。

(require '[clojure.core.unify :as uf])

;; ?から始まるシンボルを単一化の対象として、置き換え用のマップを返す
(uf/unify '(?a ?b) '(1 2))
;=> {?b 2, ?a 1}

(uf/unify '(?a ?b) '([1 2 3] [4 5 6]))
;=> {?b [4 5 6], ?a [1 2 3]}

;; 単一化結果の置き換えマップを引数で指定することも可能
(uf/unify '(?a ?b) '(1 ?b) {'?b 9})
;=> {?a 1, ?b 9}


;; unifyで返される形式のマップで第一引数の式を置き換える
(uf/subst '(?a ?b) {'?a 1, '?b 2})
;=> (1 2)

;; 置き換え後に未知の値があったら可能な限り置き換える
(uf/subst '(?a ?b) {'?a 2, '?b '(+ 3 ?a)})
;=> (2 (+ 3 2))


;; 式の未確定の値を第二引数から単一化して置き換えたものを返す
(uf/unifier '(?a ?b) '(1 2))
;=> (1 2)

(uf/unifier '(?a ?b) '([1 2 3] [4 5 6]))
;=> ([1 2 3] [4 5 6])

(uf/unifier '(?a ?b) '(1 ?b) {'?b 9}) ; 置き換えマップを指定
;=> (1 9)

これだけだと「これ知ってる、パターンマッチングってやつじゃね?」となりそうなのでちょっと違う例を出してみます。

(uf/unify '(?a ?b) '(1 ?a))
;=> {?b 1, ?a 1}

ちゃんと「?aと?bは同じ」という単一化をしてくれてますね。 パターンマッチングとの違いについては作者Fogusさんのこのブログ記事が詳しいです。

fogus: Unification versus Pattern Matching… to the death!



「単一化ってのはなんとなく分かったけど、なんか嫌な予感がする」とおもう人もいるでしょう。その予感は正しいです。上記のように値が確定するまで推論を展開していくのなら、つぎのコードはどうなってしまうでしょう?

(uf/unify '(?a ?b) '([?a 2 3] [4 5 6]))


まず{?a [?a 2 3]}と単一化されますが、そのさきの?aをいくら単一化しても無限ループに入ってしまいます。なので実行すると「循環がありますよ」という例外が発生します。

(uf/unify '(?a ?b) '([?a 2 3] [4 5 6]))
;=> IllegalStateException Cycle found in the path [?a 2 3]  clojure.core.unify/var-unify (unify.clj:95)

この「単一化したあとにも?aのような未知な値が残っているか」というチェックをoccur-checkと呼んでいるみたいです。


しかし途中まででいいから単一化した結果が欲しい場合もあるでしょう。そういう場合には"without occur-check"な関数である"unify-","unifier-"を使います。

(uf/unify- '(?a ?b) '([?a 2 3] [4 5 6]))
;=> {?b [4 5 6], ?a [?a 2 3]}

(uf/unifier- '(?a ?b) '([?a 2 3] [4 5 6]))
;=> StackOverflowError   clojure.lang.AFn.applyToHelper (AFn.java:155)


あれれ? "unifier-"なら"([?a 2 3] [4 5 6])"を返してくれると思ったんですが、そうなりませんね。
正しい挙動なのか良くわからないので、気になる人はコードを追ってみてください。





unifyを使って簡単なデータベースを作ってみます。

(def database [[:Superman :is :ClarkKent]
               [:Batman :is :BruceWayne]
               [:Conan :is :Shinichi]
               [:AnpanMan :is :AnpanMan]
               [:Batman :fought :Joker]
               [:AnpanMan :fought :BaikinMan]])

(defn query [q]
  (filter (fn [m] (not (nil? m)))
          (map #(uf/unify % q) database)))

;; バットマンの正体は誰?
(query '[:Batman :is ?who])
;=> ({?who :BruceWayne})

;; ヒーロー名と正体が同じ人は?
(query '[?who :is ?who])
;=> ({?who :AnpanMan})

;; ヒーローの敵はだれ?
(query '[_ :fought ?enemy])
;=> ({?enemy :Joker} {?enemy :BaikinMan})

;; コナンは(略
(query '[:Conan :is ?who])
;=> ({?who :Shinichi})

いまいち単一化が必要な例じゃないですが、まぁこんな感じでも使えます。

もう少し実用的なのはこちらのFogusさんの記事を見て下さい。core.constracts内で、substを簡易マクロのように使ってるみたいです。



まとめ

  • 単一化の処理を提供するcore.unifyライブラリを紹介しました
  • unify、subst、unifierを知っておけば大丈夫
  • 単一化は循環する場合があるから気をつけてね
    • その場合はunify-,unifier-(?)を使ってね
  • 実用的な例を作りたかったけど思いつかなかった(´・ω・`)


次回12日の発表者はまだ決まってないようです athosさんです。

カレンダーはまだ何日か空いてるようなので誰か書いてみませんか?(個人的にはcore.unifyつながりでcore.constractsが気になるなぁ)

Clojure Contrib Library Advent Calendar 2013 - connpass