Custom AST Transformation で メモ化を試してみました
Groovy AST変換によるコンパイル時メタプログラミングについて、調査を継続しています。
今日は、簡単なコードを書いてみました。コンパイル中に AST 変換を行い、任意のメソッドをメモ化できます。
とりあえず使用例を。
@Memoized def fib(n) { if (n <= 1) return n else return fib(n - 1) + fib(n - 2) }
上記のように、@Memoized とアノーテーションをつけると、そのメソッドがメモ化されるような Custom AST 変換を作ってみました。
AST変換動作の概要は、下記のような感じです。
- アノーテーションが付けられたメソッドを別名に変更する
- 元の名前でメモ化処理用のキャッシュ参照関数を生成する
現状では、1引数のメソッドにだけ対応しています。まだまだ Groovy での開発環境整備も出来ていない状況で、ろくにテスト/デバッグもできない有り様です。実際、ソースをご覧いただければ分かるとおり、メッセージボックスでデバッグメッセージを出しているという状態。というわけで、まずは環境整備を進めていこうと思います。
次回は、Custom AST コード開発におけるテスト環境などについて考えていきたいと思います。現状は、AST変換が楽しいので劣悪なテスト環境でも気にならないのですが、そのうちに嫌気が差してくるでしょうから。。。
比較はモノイド
比較モナドについて考察されている一連のエントリに感銘を受けて、私も比較について考えてみました。
まず、考察対象として「比較結果」と「比較操作」に分けて考えます。比較結果というのは、比較後に返ってくる値(例：Java の Comparator の compare における 負・零・正)を言います。比較操作というのは、比較する関数(あるいは関数オブジェクト)自体(例：Java の Compartor
比較結果モノイド
比較結果というのは、2つの比較対象に対して、その片方が他方よりも「小さいのか」「等しいのか」「大きいのか」を示す値です。例えば、Perl の 比較演算子 <=> や Java の Comparator において、左辺が小さいことを負の整数で、左辺と右辺が等しいことを 0 で、左辺のほうが大きいことを正の整数で示すときの「負の整数」「0」「正の整数」のことを指します。
比較結果をモノイドとして扱っている言語では、整列などの操作が驚くほどスマートに記述できます。
例題として、ブログのエントリを整列する問題を考えてみましょう。日付の降順で並べ、もし日付が同じ場合はエントリ毎のIDの昇順で並べるという問題です。なお、ブログのエントリを示すクラスのフィールドには、そのエントリが書かれた日付(pubDate)と、一意の整数型識別子(id)があるものとします。
これを Java で書くと、こんな感じでごつごつとしてしまいますね。
List<Entry> entries = ...// Entry が複数詰まっている Collections.sort(entries, new Comparator<Entry>() { public int compare(Entry e1, Entry e2) { if (!e1.pubDate.equals(e2.pubDate)) { return e2.pubDate.compareTo(e1.pubDate); } else { return new Integer(e1.id).compareTo(e2.id); } } });
下記に示すように groovy や Rubyだと事情は少し改善されますが、相変わらず条件分岐があってややこしかったり、あるいは、やや技巧的であったりという感じがしなくもないです。
（また、技巧的として示した側のコードは比較演算子が{-1, 0, +1}を返してくれず、単に{負, 零, 正}を返すような、そんなお行儀の悪い比較対象には使えません。とりわけ、Ruby の場合は、-1, 0, +1 を返すことが推奨されているだけで、-1, 0, +1 である保証はないです。つまり、-1 や +1 ではなくて、単なる負の数や単なる正の数が返ってきても、返す側は「正常動作」なので、技巧的なほうのコードが動く保証はないです。）
#-- 普通に書いてみたコード entries.sort { |e1, e2| if e1.pubDate != e2.pubDate e2.pubDate <=> e1.pubDate else e1.id <=> e2.id end } #-- やや技巧的なコード。（<=>が返す値の範囲は{負, 零, 正} ではなく 必ず{-1, 0, +1}を返してくれることを期待） entries.sort { |e1, e2| 2 * (e2.pubDate <=> e1.pubDate) + (e1.id <=> e2.id) }
逆に歴史的に古い perl のほうがむしろ、本質が見事に表現できます。pubDate で比較してそれでも決まらなければ id で比較するという本質が。
sort { my ($e1, $e2) = @_; ($e2->{pubDate} <=> $e1->{pubDate}) || ($e1->{id} <=> $e2->{id}) } @entries;
追記 2011-06-20
当初、上記の Rubyコード はGroovyコードであり、また、「GroovyやRubyでは」と記していましたが、この部分を修正しました。コメント欄で id:deve68 さんがご指摘の通り、?: 演算子を使えばスマートに解決できます。
entries.sort { e1, e2 -> (e2.pubDate <=> e1.pubDate) ?: (e1.id <=> e2.id) }
(追記ここまで、他の追記・削除箇所は>ins<による下線や>del<による打消線で示しました)
で、Perl やGroovyだと上手く書ける理由を突き詰めると、比較演算子 <=> の結果がモノイドだからだと思いました。整数を比較結果とみなしたとき、|| が半群の二項演算になっていて、0が単位元なのですよっ！
もう少し説明を試みると、モノイドというのは、単位元を持つ半群のことです。
半群というのは、2つの要素(つまり、ここでは比較結果)を2項演算でくっつけ1つの要素にできる2項演算(ここでは ||)が定義されている集合(ここでは比較結果である「負の整数」「0」「正の整数」)です。また、その半群における単位元とは、相手の要素と2項演算でくっつけても、相手の要素が変化しない要素のことです。ここでは、0のことです。
Perl の || という演算子の挙動って、現代的観点からみても驚くほどきちんと考えられていて、単にOR(論理和) というだけでなく、およそ「和」の動作を一般化したものになっています。例えば、scala における Option モナドの orElse 動作に相当する動作も、Perl の || には含まれています。 (null || value)と書けば、ちゃんと value が返ってきますね。ちなみに、この orElse って、仮に Maybe/Optionモナド の MonadPlus版なるものがあるとすれば、確実に plus === orElse と定義するのが理にかなっているくらい Plus なんですよ。
で、scala の話になりますが、scala標準って、驚くほどイケテイいない。scala.math.Ordering#compare によって返される比較結果の何がイケていないかと言えば、これが、もう驚くほど Java なんですね。いや、返る実体は Java も Perl も Groovy も、はたまた、C の strcmp でさえも同じで、整数の負・零・正なんですが、その返ってくる値をどう見做すのかがダメダメでして、scala 標準は、Perlに全然及ばない。少なくとも私の scala 実力においては、scala でのスマートなコードは思い浮かばないです。sorted の implicit な引数に Ordering を明示的に渡すのもスマートではない。sortWith は less か否かを Boolean で返すだけなので(minimalism の点では、私は好きだけれど)、Ordering や Comparator の相性が微妙ですよね。なんか、もう scala の整列の恥部という感じがしなくもないので、なんか、そういうコードを載せる気がしません。(普段は、そういうコードを書いていますけれどね。)
そこで、試しに、あえて、普段は絶対に書かないような書き方をしてみます。
// 正常動作するけれど、書き手の意図が分かりにくいウンコード entries.sortBy { e => e.pubDate -> (-1-e.id) }.reverse
もちろん、このコードもダメ。何がダメかというと、一見しただけでは何がしたいか不明だし、拡張性に乏しいからですね。また、譬え、このコード片を見て意図が一目瞭然で拡張の仕方も想定できる人ばかりの世界であったとしても、比較毎に Tuple2 を生成するしreverseするしでパフォーマンスが悪いです。
そこで、満を持して登場するのが ScalaZライブラリです。
ScalaZ の何がすごいかっていうと、「比較結果はモノイドだ」って明示的に言明しちゃってるのですね。正確には、まず、比較可能なものに対しては Order という型クラスを定義する約束になっているんですね。で、Order のインスタンスメソッド order による比較結果に専用の代数的データ型(scalaz.Ordering = LT | EQ | GT)を作っているんですね。うーん型安全ですね。さらに、こいつに対する型クラス Semigroup と Zero が備わっている（すなわち、scalaz.Ordering が単位的半群≡モノイドである）のですよ。
つまり、こんなことが、できるんです。
entries.sorted(OrderOrdering(order{ (e1: Entry, e2: Entry) =>
(e2.pubDate ?|? e1.pubDate) |+| (e1.id ?|? e2.id)
}))
要点はここです：
(e2.pubDate ?|? e1.pubDate) |+| (e1.id ?|? e2.id)
?|? は、比較演算子。Order型クラスが備わっている任意の型のインスタンス同士を比較する演算子メソッド。比較結果は、scalaz.Ordering (scala.math.Orderig[T] とは別物)。で、この scalaz.Ordering はモノイドであり、くっつける演算が |+| なんです。EQが単位元なのであることを念頭におけば、「片方が EQ であれば、他方の結果を返す；どちらもEQでないならば、左側（すなわち優先側）を返す」ということは、ほとんど自明かつ自然。
比較操作モノイド
で、ここまでは、比較結果(= LT, EQ, GT とか -1, 0, +1 とか)をモノイドと見做すとウレシイ（し、実際 scalaz では モノイド）ということについてでした。
次に、比較操作(= Comparator とか <=> とか)は、何なの（どのように見做せば世界がシンプルに見えるの、うまく回るの）っていう話です。
まずは、たたき台として、とりあえずモノイドにしてみました。
比較操作の半群のための2項演算は、将来的に apply されたとき(= 比較操作が行われたときに)、左辺が EQ を返すならば右辺に判断を委譲し、左辺がGT/LTを返すならばその結果を返す、そんな比較操作を返す。ここで、単位元は EQ。というような感じです。
// Order(scalaz の比較器)をモノイドにするための型クラス trait OrderAsMonoid { // 半群を与える implicit def OrderSemigroup[T]: Semigroup[Order[T]] = semigroup { (o1, o2) => order{ (x, y) => o1.order(x, y) |+| o2.order(x, y) } } // 単位元を与える implicit def OrderZero[T]: Zero[Order[T]] = zero(order{(x, y) => EQ}) }
上記のように Order に対するモノイド型クラスを定義すると、下記のような感じのことができます。
import scalaz._ import scalaz.Scalaz._ import java.util.Date object OrderMonoidTest extends App with OrderAsMonoid with OrderLow { // Entry を pubDate の降順で並べる Order val orderEntryByPubDateDesc: Order[Entry] = order {(e1, e2) => e2.pubDate ?|? e1.pubDate} // Entry を id の昇順で並べる Order val orderEntryByIdAsc: Order[Entry] = orderBy {_.id} // OrderAsMonoid により、今や Order 自体がモノイドなので、Order 自体を |+| により結合可能 val orderEntryByPubDateDescOrElseByIdDesc = orderEntryByPubDateDesc |+| orderEntryByIdAsc // scala の sorted を呼び出すために、scalaz.Order を scala.math.Ordering に変換 val theOrderAsScalaOrdering = Order.OrderOrdering(orderEntryByPubDateDescOrElseByIdDesc) val sortedEntries = EntryManager.entries.sorted(theOrderAsScalaOrdering) }
比較結果をモノイドとみる感じというのは、自分の中ではかなりいい感じじゃないかと思っています。（無論、モノイドという見方がよい見方というだけであって、他の見方が悪いわけではないです。もっといい見方もあるかもしれませんし、よい or よくない、というのは時と場合に依る部分もあると思いますし）
で、比較操作をモノイドとみる感じというのは、まだ自分の中でさえ納得できていない部分があります。というのは、素直に考えて、Comparator
ちょっと、最後のほうがグダグダになってしまいました＾＾；
実用的な同時並行ソートを実装する話
scala の parallel collection は、普通の collection を使うように使っているだけで、並列計算の恩恵を受けられる場合も多いのですが、そうではない場合も多いです。
その典型例が、ソートです。実は、並列のソートは、まだ実装されていません。
じゃあ、自分で実装すればいいのか、というと、これは半分正しくて半分間違いです。
どういう事かというと、シングルスレッドの java.util.Arrays.sort がとても高速なので、これより速いソートを自前で実装するのは難しいのです。Arrays.sort が速いのは、単にアルゴリズムだけの問題ではありません。自分で Array の整列処理を書くとすると、当然、配列の要素に添字でアクセスしますよね。すると、JVMは配列の範囲内かどうかをチェックしますよね。このオーバヘッドがあるために、java.util.Arrays.sort に勝つ処理を自前で書くのは困難なのです。
そこで、java.util.Arrays.sort を利用しつつ、並列でソートをする処理を考えてみました。
アイディアは簡単です。
- 配列を前半と後半の２つに分けます
- それぞれを同時並行して整列(Arrays.sort)します
- 最後にマージします。
これをコードに直しましょう。
import java.util.Arrays abstract class Sorter { def sorted(a: Array[Int]): Array[Int] } // 普通のソート object SimpleSorter extends Sorter { def sorted(a: Array[Int]) = { Arrays.sort(a) a } } // 並行ソート object DivideAndMergeParallelSorter extends Sorter { def sorted(a: Array[Int]) = { require(a.length >= 2) import scala.annotation.tailrec import scala.concurrent.ops._ val len = a.length val half = len / 2 // 注目部分！ par(Arrays.sort(a, 0, half), Arrays.sort(a, half, len)) val ret = new Array[Int](a.length) @tailrec def merge(i: Int, j: Int, k: Int) { if (a(j) <= a(k)) { ret(i) = a(j) if (j < half - 1) merge(i + 1, j + 1, k) else System.arraycopy(a, k, ret, i + 1, len - k) } else { ret(i) = a(k) if (k < len - 1) merge(i + 1, j, k + 1) else System.arraycopy(a, j, ret, i + 1, half - j) } } merge(0, 0, half) ret } }
上記のように工夫するだけで、処理時間が4割ほど削減できます。(当方の環境で 1000000要素の Array[Int] を整列するのに要する時間が 138[ms] から 83[ms] に短縮できました）
さて、上記のコードはそれなりに実用的なんですが、ちょっと気になる点がありますね。
CPUのコア数がいくらあっても2コアしか使っていないという点です。なんとなくもったいないですね。8コア環境なら8コアを使うように書きなおしてみましょう。
object DivideAndMergeParallelSorter2 extends Sorter { def sorted(a: Array[Int]) = { require(a.length >= scala.collection.parallel.availableProcessors) import scala.annotation.tailrec import scala.concurrent.ops._ val nDiv = collection.parallel.availableProcessors // 整列範囲をコア数に対応するように分割 val len = a.length val pslices = (0 until nDiv).par map {i => Arrays.copyOfRange(a, i * len / nDiv, (i + 1) * len / nDiv)} pslices foreach (Arrays.sort _) def merge(a: Array[Int], b: Array[Int]): Array[Int] = { val alen = a.length val blen = b.length val ret = new Array[Int](alen + blen); @tailrec def rec(i: Int, j: Int, k: Int) { if (a(j) <= b(k)) { ret(i) = a(j) if (j < alen - 1) rec(i + 1, j + 1, k) else System.arraycopy(b, k, ret, i + 1, blen - k) } else { ret(i) = b(k) if (k < blen - 1) rec(i + 1, j, k + 1) else System.arraycopy(a, j, ret, i + 1, alen - j) } } rec(0, 0, 0) ret } pslices reduce merge } }
4コア以上((Hyper Threading のコアじゃなくて、実コアじゃないとダメかもしれませんが)))環境なら、さらに高速に整列できるようになりました。HT8コア(実4コア)の環境での実測で、シングルスレッドの4割の実行時間にまで短縮できました。
手前味噌ですが、上記の手法は、それなりに実用的と言えるんではないでしょうか。（ただし、上記コード自体は、Int限定だったり整列される配列の要素数がコア数以上だと決め打ちしていたりしていますから、実際に使うには若干の修正が必要です。）
scala を左傾化させる話
Scala exercises for beginners を foldLeft で解いてみた。
// Exercise 2 def sum(x: List[Int]): Int = x.foldLeft(0){_ + _} // Exercise 3 def length[A](x: List[A]): Int = x.foldLeft(0){(sum, _) => sum + 1} // Exercise 4 def map[A, B](x: List[A], f: A => B): List[B] = x.foldLeft(identity: List[B] => List[B]){(kacc, h) => racc => kacc(f(h) :: racc)}(Nil) // Exercise 5 def filter[A](x: List[A], p: A => Boolean): List[A] = x.foldLeft(identity: List[A] => List[A]){(kxs, x) => (if (p(x)) xs => kxs(x :: xs) else kxs)}(Nil) // Exercise 6 def append[A](x: List[A], y: List[A]): List[A] = x.foldLeft(identity: List[A] => List[A]){(kxs, x) => xs => kxs(x :: xs)}(y) // Exercise 7 def concat[A](x: List[List[A]]): List[A] = x.foldLeft(identity: List[A] => List[A]){(kxs, x) => xs => kxs(append(x, xs))}(Nil) // Exercise 8 def concatMap[A, B](x: List[A], f: A => List[B]): List[B] = x.foldLeft(identity: List[B] => List[B]){(kxs, x) => xs => kxs(append(f(x), xs))}(Nil) // Exercise 9 /** raise error if the list is empty */ def maximum(x: List[Int]): Int = x.reduceLeft{_ max _} //x.foldLeft(Int.MinValue){_ max _} // Exercise 10 def reverse[A](x: List[A]): List[A] = x.foldLeft(List[A]()){(acc, e) => e :: acc} def foldRight[A, B](x: List[A], acc: B, f: (A, B) => B): B = x.foldLeft(identity: B => B){(kacc, h) => racc => kacc(f(h, racc))}(acc)
参考文献
蛇足ですが、上記文献の fold == 遅延評価版のfoldRight に相当します。「5.1 The foldl」が foldLeft の話です。
akka の例題を parallel collection で実装
akka の例題では、arctan(1) をテーラー級数展開して円周率を求めるという例題を取り上げている。具体的には、下記の数式を10000項ずつ Actor に割り振って、並列計算している。
このような級数を scala で並列計算する方法としては、akka を使う以外にも、scala 2.9.0 から加わった parallel collection を使うという方法もある。
object PiParallel extends App { import scala.collection.GenSeq // π = 4*atan(1) のテーラー展開 def calculatePi(rng: GenSeq[Int]): Double = rng.map{i => 4.0 * (1 - (i % 2) * 2) / (2 * i + 1)}.sum; val seqRng = Range(0, 10000 * 10000).view // 逐次計算する Range val parRng = Range(0, 10000 * 10000).par.view // 並列計算する ParRange // CPU コア数の表示 println("collection.parallel.availableProcessors == "+collection.parallel.availableProcessors) timeKeep(calculatePi(seqRng), "Sequential:") // 逐次直列計算 timeKeep(calculatePi(parRng), "Parallel:") // 平行同時計算 def timeKeep[A <: AnyRef](calcPi: => Double, msg: String) { println(msg) val t1 = System.nanoTime val pi = calcPi val t2 = System.nanoTime println( "\tPi estimate: \t\t%s\n\tCalculation time: \t%s millis" .format(pi, (t2 - t1) / 1000000)) } }
実行結果 @ Athlon II 250 (CPUコア数 == 2)
collection.parallel.availableProcessors == 2 Sequential: Pi estimate: 3.141592643589326 Calculation time: 8329 millis Parallel: Pi estimate: 3.1415926435898958 Calculation time: 4619 millis
πの計算結果が違うのは、計算順序の違いによる丸め誤差の違いによるもの。
ちなみに、この実行時間は「かなり遅い」ので要注意。その原因としては、scala collection 自体が遅いため。
下記のように手動でインライン展開してみると、実行時間は 2.4秒となり、直列 Range 版に比べて実行時間が7割も削減できる。
def calculatePiInline: Double = { var sum = 0.0 var i = 0; while (i < 10000 * 10000) { sum += 4.0 * (1 - (i % 2) * 2) / (2 * i + 1) i += 1 } sum }
高速化のために並列計算するのに、もともとの collection 自体のパフォーマンスが悪いというのは、なんとも皮肉な話である。
※ソース一式をgistに上げました。
Scala の内面を Haskell 化する話
Scala を使って Haskell 風の記述をしている例を時々見かけるけれど、徹頭徹尾 Haskell になっている例はあまり見掛けない。アプリケーションロジックだけ見れば同じなんだけれど、実際の内部動作は全然違っていたりする。そして、パフォーマンスが致命的に劣っていたりすると、悲しくてやりきれない気持ちになる。Scala は、本当は出来る子なんですと。
そこで、Haskell っぽい記述に耐えうる Scala Library を整備していこうと思う。
循環無限リストの整備
Haskell の無限リストのつもりで Scala の Stream を使うと、こんな落とし穴が待ち受けている。
例えば、無限リストの第1000000*1000番目が欲しいとき、Haskellならば、メモリ不足にはならないんだけれど、
Prelude> repeat 42 !! (1000000*1000) 42
Scala の Stream を普通に使うと、メモリ不足に陥る。
scala> Stream.continually(42)(1000000*100) java.lang.OutOfMemoryError: Java heap space
そこで、メモリを食わない continually を実装してみた。
def betterContinually[A](elem: => A): Stream[A] = { lazy val result: Stream[A] = Stream.cons(elem, result) result }
scala> betterContinually(42) res1: Stream[Int] = Stream(42, ?) scala> res1(1000000*100) res2: Int = 42
ふむ、うまくいった。あとはPimp my libraryパターンで、Stream object のメソッドとして追加しておこう。
implicit def equipRepeatWithStream(dummy: Stream.type) = new { def repeat[A](elem: => A): Stream[A] = { lazy val result: Stream[A] = Stream.cons(elem, result) result } } // 用例： // Stream.repeat(42)
2011-06-24 追記
上記の repeat コードは、当初は下記のように書いておりました。が、lazy val を用いたほうがスマートなので、本日修正しました。ご指摘くださいました okomok さんに感謝します。
def repeat[A](elem: => A): Stream[A] = { object CircularReferenceMaker { val result: Stream[A] = Stream.cons(elem, result) } CircularReferenceMaker.result }
遅延評価 fold としての foldRight の整備
Haskell の foldr のつもりで、Scala collection の foldRight を使うと、さらなる落とし穴も待ち受けている。
基本的に、Haskell の foldr は無限リストに適応可能である。リストに適用される関数が余再帰ならば何の問題も起こさない。
しかし、scala の foldRight はそうではなく、どんな場合でも無限リストには適用不可能である。必ず落ちてしまう。正格評価をする以上、foldRight の最初の動作としては最終要素への移動以外にはありえないからだ。（もちろん、その移動の実装としては、本当に tail をたどって移動する collection もあれば、全要素を反転した Array を作るという実装の collection もある）
まず、Haskell の foldr が無限リストに適用可能な例を示す。foldr を使って map を定義するという例。
myMap :: (a -> b) -> ([a] -> [b]) myMap f = foldr ((:) . f) []
当たり前だけれど、有限要素のリストで正常動作するし、
Prelude> map (2*) [1..10] [2,4,6,8,10,12,14,16,18,20]
無限要素のリストを渡しても正常動作する。
Prelude> take 10 (map (2*) [1..]) [2,4,6,8,10,12,14,16,18,20]
これをそのまま scala に書き直しても、
// ダメな例 def myMap[A, B](s: Stream[A], f: A => B): Stream[B] = s.foldRight[Stream[B]](Stream.Empty)((car, cdr) => Stream.cons(f(car), cdr))
有限要素の Stream には期待通りの動作をするが、
scala> myMap(Stream.range(1, 10), 2* : Int => Int) print 2, 4, 6, 8, 10, 12, 14, 16, 18, empty
無限要素になると、動作しない。
scala> myMap(Stream.from(1), 2* : Int => Int) take 10 print Exception in thread "main" java.lang.StackOverflowError
そこで、遅延評価をする本物の fold として foldr を下記のように定義してあげる。
def foldr[A, B](lseq: LinearSeq[A], f: (A, => B) => B, v: B): B = if (lseq.isEmpty) v else f(lseq.head, foldr(lseq.tail, f, v))
すると、有限要素はもとより無限要素の Stream に対しても、正常動作するようになる。
def myMap2[A, B](s: Stream[A], f: A => B): Stream[B] =
foldr[A, Stream[B]](s, (car, cdr) => Stream.cons(f(car), cdr), Stream.Empty)
scala> myMap2(Stream.range(1, 10), 2* : Int => Int) print 2, 4, 6, 8, 10, 12, 14, 16, 18, empty scala> myMap2(Stream.from(1), 2* : Int => Int) take 10 print 2, 4, 6, 8, 10, 12, 14, 16, 18, empty
