進捗報告
(このエントリは 進捗Advent Calendar 6日目の記事です)
進捗どうですか?
ダメです,とまではいいませんが,良いとも言い切れません。ギリギリの自転車操業な感じです。
Clojure Contrib Library Advent Calendar
元凶はなんといっても Clojure Contrib Library AC ですな。ClojureのContribライブラリというものを1つずつ紹介していくアドベントカレンダーですが,「空いてる枠,全部埋めるわー」と言ったわりに,人はなかなか集まらないし,使ったことないライブラリ多いしでなかなか辛いですね。それぞれのライブラリについて実際に使ってみつつ,コード読みつつ,参考文献あたったりしつつしてると平日の空き時間なんかでは全然回りませんぬぅぅ。そもそも,年に数回しかブログを更新しないような人間がそんな筆まめなわけがなかろう。
Lisp Advent Calendar
Lisp ACは明後日12/8に担当が割り当たっていますが,こっちは昨日今日に仕事中にネタの実装がほぼ終わってどうにかなりそうな目処が立ちました。進捗イイです( ・∀・)イイ!!
NGK2013B発表準備 & Clojure Advent Calendar
来週12/14のNGK2013B(名古屋合同懇親会)のLTも割り当たってますが,これは壊滅的にヤバイです。実装が半分以上終わってないので,当日までに形になることが期待できません。同じネタで書こうと思ってたClojure ACもヤバイです。が,まぁ構想だけでもネタにはなるので,両方ともそれでしのごうかなぁと思ってます。
おわりに
そんなわけで,進捗報告に見せかけたアドベントカレンダーたちの宣伝でした。まだまだ枠が空いているものもあるので(特にContrib Library AC),気になったアドベントカレンダーがあればいますぐ参加登録をしましょう。あ,進捗アドベントカレンダーも24日空いてるみたいですよ?
明日は(全部俺)のアドベントカレンダーで有名なeseharaさんです。進捗どうですか?
data.jsonでJSONの読み書き
(このエントリは Clojure Contrib Library Advent Calendar 3日目の記事です。)
はじめに
3日目の今日はdata.jsonについてです。
data.jsonは名前が示すとおり,JSON形式の読み書きをするために使います。以前はclojure.contrib.jsonという名前でした。
ひと昔前は,ClojureでJSONというと,clojure-jsonやclj-json,cheshireなどいろいろなライブラリが競合していました。現在では,data.jsonがデファクトスタンダード的な位置にあり,Web関連のアプリケーションを中心に広く使われています。初日の記事の Clojure Contrib ライブラリとは に記載したランキングを見ても,data.jsonがよく使われていることが分かります。
このエントリでは,data.jsonの使い方を説明し,その後で実用例としてGitHub APIからリポジトリの情報を取得する例を見てみます。
インストール
Leiningenを使用している場合は,project.cljの:dependenciesに
[org.clojure/data.json "0.2.3"]
と追加するだけで使えます。2013年12月現在では,0.2.3が最新の安定版です。
以下はproject.cljのサンプルです。
(defproject test-json "0.1.0-SNAPSHOT" :description "test project for data.json" :url "http://example.com/test-json" :license {:name "Eclipse Public License" :url "http://www.eclipse.org/legal/epl-v10.html"} :dependencies [[org.clojure/clojure "1.5.1"] [org.clojure/data.json "0.2.3"]])
使い方
data.jsonは非常にシンプルなライブラリで,提供する関数は以下の5つのみです*1。
- read:ReaderからJSONデータをClojureのオブジェクトとして読み込む
- read-str:文字列からJSONデータを読み込む
- write:WriterにClojureのオブジェクトをJSONとして書き出す
- write-str:文字列に書き出す
- pprint:JSONをプリティプリントした結果を標準出力(*out*)に書き出す
なお,これらの関数を使う場合には,名前空間clojure.data.jsonをrequireする必要があります。
(require '[clojure.data.json :as json])
ここでは,readとwriteについて詳しく説明します。その他の関数について,詳細は公式ドキュメントを参照して下さい。
(read reader & options)
readはReader(java.io.Reader)と0個以上のオプションを引数にとります。提供されているオプションは次の5つです:
- :eof-error?:trueを指定すると,EOFを読み込んだ場合に例外を投げます(デフォルトはtrue)
- :eof-value::eof-error?がfalseでEOFを読み込んだ場合に返す値を指定します(デフォルトはnil)
- :bigdec:trueを指定すると,小数値を読み込んだ場合に(Doubleでなく)BigDecimalに変換します
- :key-fn:オブジェクトのキーを変換する際に使用する関数を指定します
- :value-fn:オブジェクトの値を変換する際に使用する関数を指定します
以下は入力例です*2:
; :eof-error?を指定しないでEOFを読み込んだ場合は例外が投げられます user=> (with-in-str "" (json/read *in*)) EOFException JSON error (end-of-file) clojure.data.json/-read (json.clj:180) ; :eof-error?にfalseを指定すると,EOFを読み込んだ場合にデフォルトではnilが返ります user=> (with-in-str "" (json/read *in* :eof-error? false)) nil ; :eof-valueでEOFを読み込んだ場合に返す値を指定できます user=> (with-in-str "" (json/read *in* :eof-error? false :eof-value 'nothing)) nothing ; :bigdecを指定しないで小数値を読み込んだ場合はDoubleに変換されます user=> (with-in-str "1.0" (json/read *in*)) 1.0 user=> (class *1) java.lang.Double ; :bigdecにtrueを指定すると,小数値を読み込んだ場合にBigDecimalに変換されます user=> (with-in-str "1.0" (json/read *in* :bigdec true)) 1.0M user=> (class *1) java.math.BigDecimal ; :key-fnを指定しないでオブジェクトを読み込んだ場合,オブジェクトのキーはそのまま文字列になります user=> (with-in-str "{\"a\" 1, \"b\" 2}" (json/read *in*)) {"a" 1, "b" 2} ; :key-fnにkeyword関数を指定すると,オブジェクトのキーはキーワードに変換されます user=> (with-in-str "{\"a\" 1, \"b\" 2}" (json/read *in* :key-fn keyword)) {:a 1, :b 2} ; もちろんkeyword関数以外も指定できます user=> (with-in-str "{\"a\" 1, \"b\" 2}" (json/read *in* :key-fn symbol)) {a 1, b 2} ; :value-fnに関数を指定すると,その関数がオブジェクトの値を変換するのに使用されます ; :value-fnに指定する関数は2引数関数で,第1引数としてキー,第2引数として値がそれぞれ渡されます user=> (with-in-str "{\"a\" 1, \"b\" 2}" (json/read *in* :value-fn (fn [k v] [k v]))) {"a" ["a" 1], "b" ["b" 2]} user=>
(write x writer & options)
writeはJSONとして書き出すオブジェクトとWriter(java.io.Writer),0個以上のオプションを引数にとります。提供されているオプションは次の5つです:
- :escape-unicode:trueを指定すると,非ASCII文字を\uXXXXという表記へエスケープします(デフォルトはtrue)
- :escape-js-separators:trueを指定すると,U+2028およびU+2029というユニコード文字を(:escape-unicodeがfalseの場合でも)\u2028および\u2029へエスケープします(デフォルトはtrue)
- :escape-slash:trueを指定すると,スラッシュ(/)を\/へエスケープします
- :key-fn:オブジェクトのキーを変換する際に使用する関数を指定します
- :value-fn:オブジェクトの値を変換する際に使用する関数を指定します
以下は入力例です*3:
; :escape-unicodeを指定しないと,非ASCII文字が\uXXXXへエスケープされます user=> (with-out-str (json/write {"question" "進捗どうですか?", "answer" "進捗ダメです"} *out*)) "{\"question\":\"\\u9032\\u6357\\u3069\\u3046\\u3067\\u3059\\u304b\\uff1f\",\"answer\":\"\\u9032\\u6357\\u30c0\\u30e1\\u3067\\u3059\"}" ; :escape-unicodeにfalseを指定すると,非ASCII文字もエスケープされずそのまま出力されます user=> (with-out-str (json/write {"question" "進捗どうですか?", "answer" "進捗ダメです"} *out* :escape-unicode false)) "{\"question\":\"進捗どうですか?\",\"answer\":\"進捗ダメです\"}" ; writeに渡すオブジェクトのキーは,:key-fnに渡す関数によって変換することができます user=> (with-out-str (json/write {:a 1, :b 2} *out* :key-fn name)) "{\"a\":1,\"b\":2}" ; ただし,オブジェクトのキーがキーワードやシンボルの場合は自動的に文字列に変換されるので,:key-fnを指定する必要はありません user=> (with-out-str (json/write {:a 1, :b 2} *out*)) "{\"a\":1,\"b\":2}" user=> (with-out-str (json/write '{a 1, b 2} *out*)) "{\"a\":1,\"b\":2}" ; :value-fnでオブジェクトの値を変換することもできます user=> (with-out-str (json/write {:a 1, :b 2} *out* :value-fn (fn [k v] [k v]))) "{\"a\":[\"a\",1],\"b\":[\"b\",2]}" user=>
例
さて,それではdata.jsonの実用的な例として,GitHub APIからリポジトリの情報を取得する例を見てみます。
GitHub APIは,レスポンスがJSON形式で返ってくるので,readでClojureのマップとして読み込んだ後に,必要なキーだけを選択するようにします。
(ns contrib-calendar.data.json (:require [clojure.data.json :as json] [clojure.java.io :as io]) (:import java.net.URL)) (def ^:const ^:private %github-api-base-uri "https://api.github.com/repos") (defn retrieve-repo-info [owner repo] (let [url (URL. (str %github-api-base-uri "/" owner "/" repo))] (with-open [r (io/reader (.openStream url))] (-> (json/read r :key-fn keyword) (select-keys [:size :stargazers_count :watchers_count])))))
以下の実行例では,ClojureのGitHubリポジトリ(https://github.com/clojure/clojure)の情報を取得しています。
user=> (use 'contrib-calendar.data.json) nil user=> (retrieve-repo-info "clojure" "clojure") {:watchers_count 2670, :stargazers_count 2670, :size 10499} user=>
Clojure Contrib ライブラリとは
今年も残すところ1ヶ月となり,恒例のアドベントカレンダーの季節がやってきました。このエントリは,Clojure Contrib Library Advent Calendar 2013 の第1日目の記事です。今回は,Contribライブラリの概要について説明します。
contribライブラリとは
そもそもContribライブラリとは何かというと,多くの場面で共通して使える便利な機能を提供する,Clojureの「準標準」的な位置づけのライブラリです。
Contribライブラリは,多くの点で標準ライブラリと共通する部分をもちます。たとえば,Clojure自身と同様,Contribライブラリは github.com/clojure 上でホスティングされています。また,Clojureと同じライセンスおよびCA(Contributor Agreement)で開発されていて,後々標準ライブラリへ移行することができるような仕組みになっています。
Contribライブラリと標準ライブラリの本質的な違いは開発体制にあります。Clojureコアや標準ライブラリは,スクリーニングやRich Hickeyのレビューなど比較的厳格な開発プロセスの下で開発されていますが,Contribライブラリにはそういった制限がありません。そのため,それぞれのライブラリで,わりと自由に開発が進められています。そういった事情を受けてか,Contribライブラリにはかなり野心的なものが多く*1,さながらライブラリとして提供する機能の実験場のような様相を呈しています。
どんなライブラリがあるか?
Contribライブラリは,もともとclojure-contribというひとつの大きなライブラリとして提供されていて,それぞれの名前空間でまったく別個の機能を扱っていました*2。しかし,この巨大なライブラリの扱いの悪さが問題となり,Clojure 1.3がリリースされる頃に各機能ごとに個別のライブラリとして提供される現在の形になりました*3。
2013年12月現在では,40個弱のライブラリがContribライブラリとして提供されています。それぞれのライブラリの概要を以下に示します。
ライブラリ名 | 概要 |
algo.generic | assocやconjなどの関数のマルチメソッド版 |
algo.monads | モナドライブラリ |
build.poms | contribライブラリ用のサンプルのPOMファイル |
core.async | チャネルベースの非同期プログラミング |
core.cache | 種々の戦略によるキャッシュの実装(主にcore.memoizeで使用) |
core.contracts | 契約プログラミングのための関数およびマクロ |
core.incubator | Clojureコアへの追加が検討されている関数・マクロ群 |
core.logic | Prologライクな論理プログラミング言語の実装 |
core.match | パターンマッチングライブラリ |
core.memoize | メモ化ライブラリ |
core.rrb-vector | RRB木による効率的でイミュータブルなベクタの実装 |
core.typed | Clojureに静的型をつける拡張 |
core.unify | 単一化アルゴリズムの実装 |
data.codec | 種々のコーデックのエンコード・デコード(現在はbase64のみ) |
data.csv | CSV形式の読み書き |
data.finger-tree | 2-3フィンガーツリーによる永続的なコレクション |
data.generators | ランダムなClojureデータ生成器(主にtest.generativeで使用) |
data.json | JSON形式の読み書き |
data.priority-map | 優先度つきマップの実装 |
data.xml | XML形式の読み書き |
data.zip | Zipper向けのフィルターの実装 |
java.classpath | JVMのクラスパスを扱うためのユーティリティ |
java.data | JavaBeansとClojureデータとの相互変換 |
java.jdbc | JDBCを介したSQLデータベースのインタフェース |
java.jmx | Clojure向けのJMXサポート |
math.combinatorics | 順列・組み合わせなどの効率的なアルゴリズムの実装 |
math.numeric-tower | Clojureの種々の数値型に対応した数学関数 |
test.benchmark | ベンチマークスイート |
test.generative | QuickCheckライクな生成的テスト |
tools.cli | コマンドライン引数のパーサ |
tools.logging | ロギングライブラリ |
tools.macro | ローカルマクロとシンボルマクロの実装 |
tools.namespace | 名前空間管理のためのツール |
tools.nrepl | nREPL通信用ライブラリ |
tools.reader | ClojureによるClojureリーダの実装 |
tools.trace | トレースをとるためのマクロ |
実にさまざまなライブラリがあります。なかには,開発がひと通りが完了し、枯れたライブラリになったもの(algo.genericやdata.csv)もあれば,Rich Hickeyが開発し,今年5月にContribライブラリ入りして一気に人気になったcore.asyncのような例もあります。最近では,クラウドファンディングにより,core.typedの開発に3万5千ドルの資金が集まったという話題もありました。そして,今もなお新しいライブラリがContribライブラリに追加され,活発に開発され続けています。
どんなライブラリが人気か?
どんなライブラリがあるかを紹介したついでに,どんなライブラリに人気があるかもお見せしましょう。以下の表は,GitHubのClojureで書かれた全プログラムに対して,Leiningenのproject.cljから依存ライブラリを解析して求めた2013年11月現在のContribライブラリのランキングです*4。順位は全ライブラリ中で何位であるかを表し,度数はどれだけのライブラリがそのライブラリに依存しているかを表しています。
順位 | ライブラリ名 | 度数 |
7 | data.json | 603 |
10 | tools.logging | 535 |
15 | tools.cli | 402 |
16 | java.jdbc | 388 |
18 | math.numeric-tower | 266 |
27 | core.logic | 165 |
28 | math.combinatorics | 164 |
33 | core.async | 140 |
34 | tools.nrepl | 139 |
44 | tools.trace | 118 |
47 | core.match | 114 |
48 | data.xml | 107 |
50 | data.csv | 103 |
55 | data.zip | 93 |
56 | tools.namespace | 84 |
69 | tools.macro | 69 |
79 | algo.monads | 61 |
79 | data.codec | 61 |
83 | core.memoize | 56 |
98 | tools.reader | 41 |
103 | algo.generic | 40 |
114 | core.typed | 36 |
142 | core.cache | 31 |
142 | data.priority-map | 31 |
166 | test.generative | 27 |
183 | java.classpath | 23 |
210 | java.jmx | 18 |
219 | data.generators | 16 |
269 | core.unify | 12 |
269 | data.finger-tree | 12 |
395 | core.contracts | 7 |
435 | java.data | 6 |
1625 | core.rrb-vector | 1 |
見ていただくと分かるように,ライブラリによって使用頻度はまちまちです。ライブラリがよく使われる理由,あまり使われない理由にもさまざまなものがあると思いますが,このアドベントカレンダーでは上位のライブラリを高い優先度で扱いながらも,万遍なくさまざまなライブラリについて紹介していくつもりです。
おわりに
今回はContribライブラリがどんなものかというざっくりとした説明をしました。
いよいよ明日からは具体的にそれぞれのライブラリをひとつずつ見ていきます。今まで知らなかったライブラリや,知っているライブラリの中でも知らなかった機能について,ひとつでも多く「こんなものもあるのか」という発見があることを期待します。
次回は@ponkoreさんです。よろしくお願いします。
CodeIQのRestricted Words問題をClojureで
CodeIQで次のような問題(通称「Restricted Words」問題)が出されていました。
標準出力に
Hello World
と出力するプログラムを作成して下さい。ただし、数値、文字及び文字列リテラルを解答に含めることはできません。
ログイン│CodeIQ
Perlのqqやqw、Rubyの%Q、%q、%wなども避けたほうが評価が高くなります。
言語仕様をフル活用して下さい!
9/19に解答期限が切れて,自分の解答を公開することができるようになったので,
Clojureで書いて提出した解答について適当に紹介してみようと思います。
Clojureで解答を考えるにあたって,以下の方針を立てました:
- シンボルやキーワード,正規表現などのリテラルも使用しない
- 文字列を使えるのとほとんど変わらず,チートっぽい
- マクロを使用しない
- シンボルが使いたい放題になるのでマクロも使わない
- 「文字コードを算出して一文字ずつ表示」する方法は使わない
- 面倒なうえにおもしろくない
ここまで制約を課すと,取れる方法はある程度限られてきます。
僕が考えたのは,「コード中に書いた"Hello"や"World"といった
識別子の情報をどうにかしてとってくる」方法です。その「どうにかして
とってくる」方法を2つほど考えました。
解答その1
(defn print-names [& vals] (apply println (for [val vals, [_ var] (ns-publics *ns*) :when (= val @var)] (.sym var)))) (declare Hello World) (print-names Hello World)
まず考えたのはあらかじめ定義しておいたVarから名前をとってくる方法。Varの名前は(.sym var)で取得できます。もしくは,Varのメタデータを使って (:name (meta var)) でも取得できます。
Var自体を取得する方法としては,ここではVarをあらかじめユニークな値に束縛しておいて,名前空間からそのユニークな値に束縛されたVarを見つけてくる方法を取っています。もちろん,素直に #'Hello でとってこれはするんですが,このフォームもリテラルっぽい感じで今回は使用を控えました。
と,ここまでが提出した解答その1なんですが,Varの名前を使う方法は突き詰めると下のコードまで短くできることに〆切が過ぎてから気づきました。
(println (.sym (def Hello)) (.sym (def World)))
解答その2
(defn get-error-message [thunk] (try (thunk) (catch Exception e (.getMessage e)))) (defn transpose [xs] (apply map list xs)) (defn drop-common-prefix [& strs] (->> (transpose strs) (drop-while #(apply = %)) (transpose) (map #(apply str %)))) (declare Hello World) (let [hello-msg (get-error-message #(Hello)) world-msg (get-error-message #(World))] (apply println (drop-common-prefix hello-msg world-msg)))
次の解答はエラーメッセージから文字列を抽出する方法をとりました。Clojureが発生させる例外の中には,メッセージに変数名を含むものがあるので,その例外をキャッチしてメッセージから変数名を抽出します。
発生させる例外はなんでもそれほど違いはありませんが,コンパイラが投げる類の例外はClojureの例外処理ではキャッチできないのでそういうものは避ける必要があります。たとえば,以下の例外はキャッチできません。
user=> hoge ; 未定義の変数hogeの参照はCompilerExceptionを発生させる CompilerException java.lang.RuntimeException: Unable to resolve symbol: hoge in this context, compiling:(NO_SOURCE_PATH:0:0) user=> user=> (try hoge (catch RuntimeException e (.getMessage e))) ; try-catchではキャッチできない CompilerException java.lang.RuntimeException: Unable to resolve symbol: hoge in this context, compiling:(NO_SOURCE_PATH:19:1) user=>
今回は,未束縛のVarを関数適用した際に出る例外を採用しました。
user=> (declare Hello) #'user/Hello user=> (Hello) IllegalStateException Attempting to call unbound fn: #'user/Hello clojure.lang.Var$Unbound.throwArity (Var.java:43) user=> (try (Hello) (catch IllegalStateException e (.getMessage e))) "Attempting to call unbound fn: #'user/Hello" user=>
残すはこのエラーメッセージの末尾のHelloを切り出してくるだけですが,問題は数値や文字,文字列,正規表現を使えない状況でどうやって所望の文字列を切り出してくるか。ムリクリ数値を作り出してsubstringで切り出すことはできなくはないですが,ダルいのでできればやりたくない。今回の解答では発想を転換して,Hello用のエラーメッセージとWorld用のエラーメッセージを用意して,共通部分を取り除く方法を使いました。
おわりに
今回のお題は「言語仕様をフル活用して下さい!」とのことだったので,Clojureのいろんな機能を使って解答を考えてみました。おかげで,細々とした部分の挙動(特にUnboundオブジェクトの扱いなど)で新しい発見もあって理解が深まりました。
まぁただし,ここに掲載したコードは,Clojureのバージョンが上がったら結果が変わる可能性があるような微妙な振る舞いに依存している部分もあるので,なにかの参考にする場合には注意が必要かもしれません。
おまけ
キーワードとマクロを使った解答も考えてみました。
(def alphabets (for [i (range) :let [c (char i)] :while (not= c (first (name :|))) :when (Character/isLetter c)] c)) (defmacro with-alphabets [& body] `(let [~(mapv #(symbol (str %)) alphabets) alphabets] ~@body)) (with-alphabets (println (str H e l l o) (str W o r l d)))
Clojureコンパイラの型推論器をとりだしてみる
clojure.orgには,Clojureについて次のような説明がある。
Clojure provides easy access to the Java frameworks, with optional type hints and type inference, to ensure that calls to Java can avoid reflection.
http://clojure.org/
この型推論(type inference)は,Clojureの説明でたまに名前だけは出てくるものの,その実態についての説明にはほとんどお目にかかったことがない。そこで今回は,Clojureの型推論の機能をClojureから触れるようにして遊んでみよう。
Clojureになぜ型推論が必要か
まずはじめに注意しておかないといけないのは,Clojureの型推論はMLやHaskellなどの静的型付言語がもつそれとは目的が異なるということだ。Clojureの型推論は型安全性のためには役立たない。型が推論できたからといって型の誤りによるエラーが実行時に起こらないという保証にはならないし,型が推論できないからといって必ずしも誤りがあるというわけでもない。
じゃあClojureの型推論が何のためにあるかというと,上の引用にもあるとおり「Javaにアクセスする際のリフレクションを極力避けるため」だ。
Clojureは実行時に型をチェックする言語なので,プログラムの断片を見ただけでは変数がどんな型の値に束縛されるか分からないことがある。
(defn upper-case [x] (.toUpperCase x))
たとえば,上のコードではxがどんな型をもつのかは実際にこの関数が呼び出されるまで分からない。そのため,ここで呼ばれているtoUpperCaseというメソッドもどのクラスに属するものなのかすら分からない。それにも関わらずこのコードがエラーも生じずに実行できるのは,xの実行時の型情報からJVMのリフレクションを使って適切なメソッドを選び出して呼び出しているためだ。メソッド呼び出しだけでなく,ClojureからJavaのフィールドにアクセスする場合にも同様の仕組みが内部では動いている。
しかし,リフレクションを介したメソッド呼び出しやフィールドへのアクセスは,リフレクションを介さないものと比較するとかなり効率が悪い(実行時間にして1〜2桁くらい遅い)。そこでClojureでは,「型ヒント」を入れることによって,リフレクションを発生させないようにすることができる。
(defn upper-case' [x] (.toUpperCase ^String x)) ; xがStringであることを型ヒントで指定
;; リフレクションが発生するバージョン user=> (dotimes [_ 5] (time (dotimes [_ 100000] (upper-case "hoge")))) "Elapsed time: 1188.655 msecs" "Elapsed time: 1246.814 msecs" "Elapsed time: 1165.256 msecs" "Elapsed time: 1346.774 msecs" "Elapsed time: 1296.931 msecs" nil ;; 型ヒントによってリフレクションを抑制したバージョン user=> (dotimes [_ 5] (time (dotimes [_ 100000] (upper-case' "hoge")))) "Elapsed time: 39.685 msecs" "Elapsed time: 35.238 msecs" "Elapsed time: 36.961 msecs" "Elapsed time: 44.772 msecs" "Elapsed time: 76.312 msecs" nil user=>
これでリフレクションの問題は解決できる。ただし,型ヒントだけでは不十分だ。より複雑なプログラムを書く場合,メソッドの呼び出しやフィールドへのアクセスのたびに型ヒントを書くのは面倒になる。
;; メソッド呼び出しのたびに型ヒントをつけるのは辛い… (defn f [^String x] (-> x ^String (.toUpperCase) ^String (.substring 1 4) ^String (.startsWith "HOGE")) ;; できればこんな感じにすっきり書きたい (defn f [^String x] (-> x (.toUpperCase) (.substring 1 4) (.startsWith "HOGE")))
必要最低限だけ型ヒントをつければ,あとは静的に分かる情報からうまく型を導き出してくれるような仕組みがほしい。それがClojureの型推論だ。
型推論と内部表現
前置きが長くなった。ここからが型推論についての具体的な内容になる。
Clojureの型推論は,以前にこのブロクでも説明したClojureコンパイラが使う内部表現Exprによって処理される。
Exprは以下のように定義されている。
interface Expr{ Object eval() throws Exception; void emit(C context, ObjExpr objx, GeneratorAdapter gen); boolean hasJavaClass() throws Exception; Class getJavaClass() throws Exception; }
このうちの hasJavaClass() および getJavaClass() が型推論に関連するメソッドだ。Clojureの型推論は,冒頭で触れたとおり,式によっては型が推論できず失敗することがある。hasJavaClass()は,その式から型が推論できる場合にtrueを返し,そうでなければfalseを返す。getJavaClass()は実際に推論された型を返す。getJavaClass()は,hasJavaClass()がtrueを返す場合以外に呼び出すとエラーになる可能性がある。
型推論ツール
Clojureの型推論の仕組みが分かれば,それを利用するツールを作るのは難しくない。
(ns type-infer) (defmacro $ [c] (symbol (str 'clojure.lang.Compiler$ c))) (defn call-private [class method obj] (let [args (into-array Class nil) m (.getDeclaredMethod class (str method) args)] (when-not (.isAccessible m) (.setAccessible m true)) (.invoke m obj clojure.lang.RT/EMPTY_ARRAY))) (defn extract [x] (let [i? instance?] (if (i? ($ InvokeExpr) x) (let [fexpr (.-fexpr x)] (if (and (i? ($ FnExpr) fexpr) (empty? (.-args x))) (.-body (first (.-methods fexpr))) x)) x))) (defn infer-fn [x] (let [expr (extract (Compiler/analyze clojure.lang.Compiler$C/EVAL x))] (if (boolean (call-private ($ Expr) 'hasJavaClass expr)) {:class (call-private ($ Expr) 'getJavaClass expr)}))) (defmacro infer [x] (infer-fn x))
ここでは使い方について特に説明しないが,以降の例で使い方と結果の見かたは分かるはずだ。
Clojureの型推論の実態
このツールを使って,実際にClojureの型推論がどうなっているのか調べてみよう。
リテラル
まず基本的なところで,いろんなデータ型のリテラルを試してみる。
user=> (infer 1) {:class long} user=> (infer 42) {:class long} user=> (infer 3.14) {:class double} user=> (infer 1N) {:class clojure.lang.BigInt} user=> (infer 1M) {:class java.math.BigDecimal} user=> user=> (infer \a) {:class java.lang.Character} user=> (infer "hoge") {:class java.lang.String} user=> (infer 'sym) {:class clojure.lang.Symbol} user=> (infer :keyword) {:class clojure.lang.Keyword} user=> (infer #'cons) {:class clojure.lang.Var} user=> (infer java.lang.StringBuilder) {:class java.lang.Class} user=> (infer nil) {:class nil} user=>
うまく推論されていることが分かる。
コレクションリテラル
コレクションの型が推論される。コレクションの要素の型は分からない。
user=> (infer [1 2 3]) {:class clojure.lang.PersistentVector} user=> (infer '(1 2 3)) {:class clojure.lang.PersistentList} user=> (infer {:a 0, :b 1}) {:class clojure.lang.PersistentHashMap} user=> (infer #{1 2 3}) {:class clojure.lang.PersistentHashSet} user=>
トップレベルに定義された変数の参照
トップレベルに定義された変数の参照は,変数定義に型ヒントがつけられている場合にはその型が推論され,そうでない場合には推論に失敗する。
user=> (def ^String x "hoge") #'user/x user=> (infer x) {:class java.lang.String} user=> (def y "fuga") #'user/y user=> (infer y) nil user=>
関数適用
関数適用は,適用される関数がトップレベルに定義されていて,かつ,関数の定義に型ヒントがつけられている場合にはその型が推論され,そうでない場合には推論に失敗する。
user=> (defn f ^String [x] (str x)) #'user/f user=> (infer (f 1)) {:class java.lang.String} user=> (defn g [x] (str x)) #'user/g user=> (infer (g 1)) nil user=>
if
第2引数と第3引数の式の型が推論でき,かつ,推論された型が等しい場合には,その型がif式の型として推論される。そうでない場合には推論に失敗する。
user=> (infer (if true 0 1)) {:class long} user=> (infer (if true 0 'a)) nil user=>
let
letの本体における最後の式の型が推論できる場合には,その型がlet式の型として推論される。そうでない場合には推論に失敗する。letで束縛される変数の参照は,変数の束縛に型ヒントがつけられている場合にはその型が推論される。型ヒントがつけれておらず,初期化の式から型が推論できる場合にはその型が推論される。loopも同様の規則に基づく。
user=> (infer (let [^String x nil] x)) {:class java.lang.String} user=> (infer (let [x 0] x)) {:class long} user=>
fn
Clojureの関数型を表す抽象クラスAFunctionが推論される。
user=> (infer (fn [x] (* x x))) {:class clojure.lang.AFunction} user=>
Java interop
Javaのクラスのコンストラクタ呼び出しは,そのクラスが推論される。メソッド呼び出しはメソッドの戻り値が推論される。フィールドの参照はフィールドの型が推論される。
user=> (infer (StringBuilder.)) {:class java.lang.StringBuilder} user=> (infer (Integer/valueOf "hoge")) {:class java.lang.Integer} user=> (infer System/out) {:class java.io.PrintStream} user=>
以上のことをふまえると,これくらいの複雑さの式なら型を推論してくれることが分かる。
user=> (infer #_=> (loop [x 10, a 0, b 1] #_=> (if (zero? x) #_=> a #_=> (recur (dec x) b (+ a b))))) {:class long} user=>
MLのlet多相とか値制限とかよく分からなかったので調べてみた
世間はもうすぐ予定されているTAPLの日本語版の発刊に色めき立ってますね。関数型都市と呼ばれていた(る?)なごやでは、いいかげん動的型の言語ばっかやってられない雰囲気をヒシヒシと感じてるので、ぼちぼちと静的型付言語の勉強を進めています。
で、このエントリでは、今までなんだか分かったような分からないような感じのままになっていた、ML系言語のlet多相とか値制限とかその辺りについて調べたときに、参考になったweb上の文献等をまとめるのをメインにしつつ、自分の中での理解なんかをチョロチョロっと書いていこうかなぁと思います。
全体を通した話としては、住井先生のこの辺りの記事が時系列で書かれてるし、分かりやすいと思いました。
このエントリは、基本的に上の記事の劣化コピーでしかないので、上の記事を見て理解できれば、以降は読む必要ないでしょう:P
let多相
let多相については、上の住井先生の記事に端的な説明があります。
MLの多相型推論は、let x = eのような宣言があったら、eの型を推論して、「決まらなかった」部分は「何でもよい」と解釈し、具体化されなかった型変数について∀を先頭を追加する。
ML多相 - sumiiの日記
「型の多相性がどこで与えられるか」に対するMLでの答えがlet多相なんだと理解してます。型推論的には、letは特別な扱いを受けています。たとえば、OCamlでは
# let f = fun x -> x in (f 1, f true);; - : int * bool = (1, true)
に型がつきます。fは多相的な関数で、let内でint->intとしてもbool->boolとしても使えていることに注意。一方で、上のコードをfunを使って書き直してみると、
# (fun f -> (f 1, f true)) (fun x -> x);; Error: This expression has type bool but an expression was expected of type int
このように型エラーになってしまいます*1。
let多相の概要はそんな感じですが、詳しくは実際に型推論アルゴリズムにあたるのが遠回りではあるけど確実なアプローチかなと思います。let多相を含む型推論については、以下の五十嵐先生の講義資料が分かりやすかったです。
型スキーム('a -> 'aみたいな多相な型を、∀で明示して∀α.α→αと表す表現)なんかは他のところでも散々出てくるので知っておいた方がいいと思います。
また、@pi8027さんが書かれた Algorithm W 入門 は、まさに型推論アルゴリズムについて書かれている薄い本で、let多相についても説明がされています。
- Algorithm W 入門 今は購入不可だけど、@pi8027さんに頼めば買える?(未確認)
- pi8027/typeinfer · GitHub 一応、GitHubからソースは見られるけど…?。
値制限
で、純粋な言語であればlet多相でOKなわけですが、破壊的操作が可能な言語では型安全でないようなケースが出てくるようです。このようなケースが生じないようにする回避策はいろいろ考えられたようですが、現在ではAndrew Wrightが考案した値制限という比較的単純な方法をベースとした方法が広く使われています。
値制限は、let x = e でlet多相によってeに多相性を持たせる場合の制限で、eとして数値や文字列といったリテラルやコンストラクタの呼び出し等、実行を伴わない「値」(syntactic value)しか許さないというものです。この辺りの制限がどうやって導かれたかについては、SML#のrank-1 多相性の理論の解説ページに詳しく書かれています。
値制限は単純である反面、必要以上に厳しい制限です。特に、関数適用がsyntactic valueとして扱われないことが非常に大きな制限になります。たとえば、以下のような場合、
# let f = List.map (fun x -> Some x);; val f : '_a list -> '_a option list = <fun>
fに束縛される List.map (fun x -> Some x) という式は関数適用であるため、値制限により多相になりません。OCamlでは、値制限によって多相にならなかった場合、'_aのような型変数が割り付けられますが、このような型変数は一度ある型で具体化されてしまうと他の型になることができなくなります。
# f [1; 2; 3];; - : int option list = [Some 1; Some 2; Some 3] # f;; - : int list -> int option list = <fun> # f [true; true; false];; Error: This expression has type bool but an expression was expected of type int
一応、この場合には、いわゆるη展開によってfに多相性を持たせることができます。
# let f xs = List.map (fun x -> Some x) xs;; val f : 'a list -> 'a option list = <fun> (* 上は以下と等価 *) # let f = fun xs -> List.map (fun x -> Some x) xs;; val f : 'a list -> 'a option list = <fun> (* 関数抽象はsyntactic valueとして扱われるため、値制限を回避できる *)
とはいえ、いちいちη展開をするのは、高階関数を使いまくるときなんかにはだるいですね。これまで見てきた例に限らず、値制限は不便な点が多いため、値制限をベースにしつつ、実際には各言語で制限を緩めるような拡張がなされています。
各言語での拡張
有名どころでは以下のような拡張があるみたいです。
- OCamlのRelaxed value restriction
- SML#のrank-1 多相
OCamlのRelaxed value restrictionはよく分かっておらず。共変な型変数ならsubtypingによって多相性が回復するといいますが。。。
それから、SML#のrank-1 多相について。もともと、MLの多相性はrank-1 多相というクラスに属していますが、その中でも∀が先頭にのみ現れる∀α.(α→α)や∀α.∀β.(α→β→α*β)といった型だけが許されています。SML#のrank-1 多相ではこの制限を緩めて、∀α.(α→∀β.(β→α*β))といったように、∀が→の右側に現れるのを許すようになっています(というか、そういう型に推論されるようになっている?)。これによって、上で挙げた部分適用された関数を束縛する例を含むいくつかのケースで、値制限を回避して多相性をもつことができるようです。
まとめ
- let多相は型に多相性を与えるための型推論の仕組み
- 値制限は純粋でない言語でlet多相の型安全性を保証するために広くとり入れられている方法
- 値制限は厳しいので、各言語で値制限をベースにしつつ、制限を緩めるような拡張がなされている
よく分からず書いている部分も多く、間違った記述があるかもしれません。間違いを見つけた場合は*お手柔らかに*ご指摘いただけると幸いです。
*1:rank-2 多相を使うと書けるという話もありますが、それはまた別の話。
gorubyライクな短縮形をClojureで
(このエントリはLisp Advent Calendar 2012 8日目の記事です。)
gorubyとは
gorubyはRubyに標準でついてくる、ゴルフ用のRuby処理系です。ゴルフ用というだけあって、普通のRubyに追加でゴルフに都合のいい機能をいくつかもっています。そのひとつに、「メソッドを短縮形の名前で呼び出せる」機能があります。たとえば、普通のRubyで以下のように書くコードは、
['foo','bar','baz'].each_with_index do |c, i| puts "#{i}: #{c}" end
gorubyでは以下のように書けます。
['foo','bar','baz'].ew do |c, i| ps "#{i}: #{c}" end
元のコードの"each_with_index"がgoruby版では"ew"に、"puts"が"ps"になっています。
gorubyでは、オブジェクトに定義されていないメソッドの呼び出しが見つかると、それを定義されたメソッドの短縮形として解決しようとします。実装としては、未定義のメソッドが呼ばれた時点でmethod_missingが呼び出され、その中でオブジェクトに定義された全メソッドを取得して名前の短い順にソートし、正規表現("ew"なら/^.*e.*w.*$/)にマッチする最初のメソッドを呼び出す、ということをやっています。
この「メソッドを短縮形で呼べる」というのはおもしろい機能だと思ったのでClojureでやってみました。ただし、短縮形の解決を実行時にするのは効率が悪そうなのでマクロで頑張ることにします。というわけで、作ったマクロが goclojure です。
goclojureマクロ
goclojureマクロは、
(goclojure <expr> ...)
という形で使うと、
(defn fibs [n] (letfn [(rec [a b] (lazy-seq (cons a (rec b (+ a b)))))] (take n (rec 0 1))))
goclojureを使うと以下のように書き直せます。
(goclojure (dn fibs [n] (lf [(rec [a b] (zq (cn a (rec b (+ a b)))))] (tk n (rec 0 1)))))
これを見ても分かるように、goclojureでは関数だけでなく、マクロ(や特殊形式)に対しても短縮形が使えます。ifがiに、fnがfに、letがlに短縮できて、ゴルフ的には非常に嬉しそうです :-)
ちなみに、Clojureの標準の名前空間であるclojure.coreには588の名前が提供されていますが、goclojureを使ってできる限り短い名前に短縮すると、4つの名前が4文字に短縮でき、残りの584の名前が3文字までに短縮できるようです。
上の図は、各文字数の名前がいくつあるかを表したグラフです。赤の系列が元のclojure.coreの分布、青の系列がgoclojureを使って短縮したときの分布です。名前の長さの平均は、元が約8.3文字に対し、goclojureを使うと約2.4文字になるようです。驚異的な圧縮率です(笑)
実装について
goclojureでは、マクロ展開時に短縮形の展開器を呼び出し、本体に含まれるフォームをトラバースして短縮形を展開します。短縮形の展開器は、その時点のスコープで見えている変数をすべて含む環境をとり、識別子に出会うたびにその識別子が何かの名前の短縮になっていないか環境の中を(gorubyと同様の方法により)探索します。マクロが存在すると、一般的にはどれが展開すべき識別子か判別することができないので、トラバースしていく過程でマクロ呼び出しのフォームに出会ったらmacroexpandを使って先に展開します。
ところで、goclojureはローカル変数の短縮に対応していません。これは、マクロの存在による制限です。
マクロはgensymなどによって暗黙にローカル変数を導入することがあります。短縮形の展開器にとっては、あるローカル変数がプログラマによって導入されたものなのか、マクロによって導入されたものかは分かりません。そのため、もしローカル変数の短縮を許してしまうと、短縮形の展開によって、マクロが暗黙に導入したローカル変数を意図せずに参照してしまう可能性があります。これを排するため、ローカル変数は短縮できないという制限を設けました。
この制限により、ローカル変数は短縮形の展開後の名前を探す環境には含めなくてよいものの、ローカル変数の参照を何かの名前の短縮形だと思って誤って展開されてしまっては困るので、何がローカル変数であるかは別に環境を用意して管理しておく必要があります。そのため、短縮形の展開器はトラバースの過程で束縛を含む特殊形式(fn*/let*/letfn*/loop*/catch)に出会ったら、このローカル変数を管理する環境に追加していきます。
goclojureのソースコードはこちら→athos/goclojure · GitHub。
おわりに
実は、goclojureでやっていることは、以前作ったsyntactic-closureとほとんど同じなんですが、見せ方だけでずいぶん違ったものになるのはおもしろいですね。
ところで、12/8にNGK2012BのLTで、事前にgoclojureについて発表したところ、
#NGK2012B goclojureという名前が長い
「(ゴルフで使うには)goclojureという名前が長い」と言われてしまったので、名前はそのうち変えるかもしれません :-P